Не леворекурсивная грамматика PEG для "выражения"

Question

Это либо простой идентификатор (например, cow) что-то, заключенное в скобки ((...)) что-то похожее на вызов метода (...(...)) или что-то похожее на членский доступ (thing.member):

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

Это дано в синтаксисе Scala Parser Combinator, но это должно быть довольно просто для понимания. Это похоже на то, как выражения выглядят во многих языках программирования (отсюда и название exprТем не менее, в его нынешнем виде он является леворекурсивным и вызывает взрыв моего хорошего PEG-парсера.

Мне не удалось вычленить левую рекурсию, сохраняя правильность для таких случаев, как (cow.head).moo(dog.run(fast)), Как я могу реорганизовать это, или мне нужно перейти на какой-нибудь генератор синтаксических анализаторов, который может переносить левые рекурсивные грамматики?

Answer 1

Хитрость заключается в том, чтобы иметь несколько правил, где первый элемент каждого правила является следующим правилом, а не рекурсивным вызовом одного и того же правила, а остальная часть правила является необязательной и повторяющейся. Например, следующее будет работать для вашего примера:

def expr              = method_call
def method_call       = member_access ~ ( "(" ~> expr <~ ")" ).*
def member_access     = atomic_expression ~ ( "." ~> identifier).*
def atomic_expression = identifier |
                        "(" ~> expr  <~ ")"