In any recursive descent parser, left recursion is a pain in the neck. For the following production rule:
A ::= foo | A B C
You cannot intuitively write the parser like:
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):
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:
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":
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.