Non-left-recursive PEG grammar for an "expression"

Question

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?

sepp2k sepp2k · Accepted Answer · 2012-11-14T06:48:39

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:

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

Non-left-recursive PEG grammar for an "expression"

1 Answers