nonempty sequence of nonterminals and terminals, and each is a sequence of nonterminals and terminals that does not start with . Replace these with two sets of productions, one set for : and another set for the fresh nonterminal (often called the "tail" or the "rest"): Repeat this process until no direct left recursion remains. As an example, consider the rule set This could be rewritten to avoid left recursion as Removing all left recursion By establishing a topological ordering on nonterminals, the above process can be extended to also eliminate indirect left recursion : Inputs A grammar: a set of nonterminals and their productions Output A modified grammar generating the same language but without left recursion For each nonterminal : Repeat until an iteration leaves the grammar unchanged: For each rule , being a sequence of terminals and nonterminals: If begins with a nonterminal and : Let be without its leading . Remove the rule . For each rule : Add the rule . Remove direct left recursion for as described above. Note that this algorithm is highly sensitive to the nonterminal ordering; optimizations often focus on choosing this ordering well. Pitfalls Although the above transformations preserve the language generated by a grammar, they may change the parse trees that witness strings' recognition. With suitable bookkeeping, 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: the standard transformations to remove left recursion yield the following: 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: This parse tree groups the terms on the left, giving the correct semantics (1 - 2) - 3. Parsing with the second grammar gives 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). Accommodating left recursion in top-down parsing A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted