Editing Left recursion (section)

== Pitfalls ==
Although the above transformations preserve the language generated by a grammar, they may change the [[parse tree]]s that [[Witness (mathematics)|witness]] strings' recognition.  With suitable bookkeeping, [[Rewriting#Term rewriting systems|tree rewriting]] can recover the originals, but if this step is omitted, the differences may change the semantics of a parse.

Associativity is particularly vulnerable; left-associative operators typically appear in right-associative-like arrangements under the new grammar.  For example, starting with this grammar:
:<math>\mathit{Expression} \rightarrow \mathit{Expression}\,-\,\mathit{Term} \mid \mathit{Term}</math>
:<math>\mathit{Term} \rightarrow \mathit{Term}\,*\,\mathit{Factor} \mid \mathit{Factor}</math>
:<math>\mathit{Factor} \rightarrow (\mathit{Expression}) \mid \mathit{Integer}</math>
the standard transformations to remove left recursion yield the following:
:<math>\mathit{Expression} \rightarrow \mathit{Term}\ \mathit{Expression}'</math>
:<math>\mathit{Expression}' \rightarrow {} - \mathit{Term}\ \mathit{Expression}' \mid \epsilon</math>
:<math>\mathit{Term} \rightarrow \mathit{Factor}\ \mathit{Term}'</math>
:<math>\mathit{Term}' \rightarrow {} * \mathit{Factor}\ \mathit{Term}' \mid \epsilon</math>
:<math>\mathit{Factor} \rightarrow (\mathit{Expression}) \mid \mathit{Integer}</math>

Parsing the string "1 - 2 - 3" with the first grammar in an LALR parser (which can handle left-recursive grammars) would have resulted in the parse tree:
[[File:Left-recursive-parse-of-a-double-subtraction.png|center|Left-recursive parsing of a double subtraction]]
This parse tree groups the terms on the left, giving the correct semantics ''(1 - 2) - 3''.

Parsing with the second grammar gives
[[File:Right-recursive-parse-of-a-double-subtraction.png|center|Right-recursive parsing of a double subtraction]]
which, properly interpreted, signifies ''1 + (-2 + (-3))'', also correct, but less faithful to the input and much harder to implement for some operators.  Notice how terms to the right appear deeper in the tree, much as a right-recursive grammar would arrange them for ''1 - (2 - 3)''.