Do I Have A Bug In My Grammar, Or The Parser-generation Tool?

The following is an EBNF-format (mostly - the actual syntax is documented here) grammar that I am attempting to generate a parser for: expr = lambda_expr_list $; lambda_expr_list

Solution 1:

It may be a bug in the grammar, but the error message is not telling you where it actually happens. What I always do after finishing a grammar is to embed cut (~) elements throughout it (after keywords like if, operators, opening parenthesis, everywhere it seems reasonable).

The cut element makes the Grako-generated parser commit to the option taken in the closest choice in the parse tree. That way, instead of having the parser fail at the start on an if, it will report failure at the expression it actually couldn't parse.

Some bugs in grammars are difficult to spot, and for that I just go through the parse trace to find out how far in the input the parser went, and why it decided it couldn't go further.

I will not use left-recursion on a PEG parser for professional work, though it may be fine for simpler, academic work.

boolean_or_expr = boolean_xor_expr {"or" boolean_xor_expr};

The associativity can then be handled in a semantic action.

Also see the discussion under issue 49 against Grako. It says that the algorithm used to support left recursion will not always produce the expected associativity in the resulting AST.