Left recursive grammars

When moving on to more complex expressions, such as addition, we need to write a recursive rule since the left and right parts of an addition are expressions themselves. It would be natural to express such a rule as follows:

Expression:
  ... as above
  {Plus} left=Expression '+' right=Expression;

However, this results in an error from the Xtext editor as shown in the following screenshot:

Xtext uses a parser algorithm that is suitable for interactive editing due to its better handling of error recovery. Unfortunately, this parser algorithm does not deal with left recursive rules. A rule is left recursive when the first symbol of the rule is non-terminal and refers to the rule itself. The preceding rule for addition is indeed left recursive and is rejected by Xtext. Note that a rule can also be left recursive via multiple rule calls without any token consumption.

Note

Xtext generates an ANTLR parser (see the book Parr 2007), which relies on an LL(*) algorithm...