Ngữ pháp PEG không phải là đệ quy trái cho một "biểu thức"

Question

Đó là một số nhận dạng đơn giản (như cow) một cái gì đó được bao quanh bởi các dấu ngoặc đơn ((...)) giống như một cuộc gọi phương thức (...(...)) hoặc cái gì đó giống như quyền truy cập thành viên (thing.member):

def expr = identifier | 
      "(" ~> expr <~ ")" | 
      expr ~ ("(" ~> expr <~ ")") | 
      expr ~ "." ~ identifier 

Được đưa ra trong cú pháp Kết hợp trình phân tích cú pháp Scala, nhưng sẽ rất đơn giản để hiểu. Nó tương tự như cách biểu thức kết thúc tìm kiếm trong nhiều ngôn ngữ lập trình (do đó tên expr) Tuy nhiên, khi nó đứng, nó là trái đệ quy và nguyên nhân phân tích cú pháp PEG đẹp của tôi phát nổ.

Tôi đã không thành công trong việc tính toán đệ quy trái trong khi vẫn duy trì tính chính xác cho các trường hợp như (cow.head).moo(dog.run(fast)). Làm thế nào tôi có thể refactor này, hoặc tôi sẽ cần phải chuyển sang một số máy phát điện phân tích cú pháp có thể chịu đựng được ngữ pháp đệ quy trái?

Answer 1

Bí quyết là có nhiều quy tắc trong đó nguyên tố đầu tiên của mỗi quy tắc là quy tắc tiếp theo thay vì gọi đệ quy đến cùng một quy tắc và phần còn lại của quy tắc là tùy chọn và lặp lại. Ví dụ như sau sẽ làm việc cho ví dụ của bạn (không sử dụng ký hiệu máy phát Scala vì tôi không biết nó):

expr ::= method_call 
method_call ::= member_access ("(" expr ")")* 
member_access ::= atomic_expression ("." identifier)* 
atomic_expression ::= identifier | "(" expr ")"