Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migrated to Confluence 5.3

In any recursive descent parser, left recursion is a pain in the neck. For the following production rule:

Code Block
A ::= foo | A B C

You cannot intuitively write the parser like:

Code Block
Parser.Referenece<A> ref = Parser.newReference();
Parser<A> a = foo.or(Parsers.sequence(ref.lazy(), b, c));
ref.set(a);

Postfix

An easy solution is to model "B C" as a postfix operator that applies to A (assuming "A B C" is modeled by class Abc, which implements A):

Code Block
Parser<A> foo = ...;
Parser<A> a = foo.postfix(Mapper.<A>curry(Abc.class).postfix(b, c));

Infix

In case the production has both left recursion and right recursion, such as:

Code Block
A ::= foo | A B C A

We can model "B C" as an infix operator that applies to A operands. Similar to above example, let's assume that Abca class is used to model "A B C A":

Code Block
Parser<A> foo = ...;
Parser<A> a = foo.infixl(Mapper.<A>curry(Abca.class).infix(b, c));

A real example is to parse the Java ternary conditional operator as in expressions like "conditionalExpr ? consequenceExpr : alternativeExpr", where the "? consequenceExpr :" part is the right associative infix operator applied to the conditionExpr and alternativeExpr. See Parsing Ternary Operator for details.