Take the 2-minute tour ×

It's either a simple identifier (like cow) something surrounded by brackets ((...)) something that looks like a method call (...(...)) or something that looks like a member access (thing.member):

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

It's given in Scala Parser Combinator syntax, but it should be pretty straightforward to understand. It's similar to how expressions end up looking in many programming languages (hence the name expr) However, as it stands, it is left-recursive and causes my nice PEG parser to explode.

I have not succeeded in factoring out the left-recursion while still maintaining correctness for cases like (cow.head).moo(dog.run(fast)). How can I refactor this, or would I need to shift to some parser-generator that can tolerate left recursive grammars?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

The trick is to have multiple rules where the first element of each rule is the next rule instead of being a recursive call to the same rule, and the rest of the rule is optional and repeating. For example the following would work for your example (not using Scala generator notation because I don't know it):

expr ::= method_call
method_call ::= member_access ( "(" expr ")" )*
member_access ::= atomic_expression ( "." identifier)*
atomic_expression ::= identifier | "(" expr ")"
share|improve this answer
add comment

Your Answer


