Skip to end of metadata
Go to start of metadata

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

You cannot intuitively write the parser like:

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):

Infix

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

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":

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.

  • No labels