left recursion

Picture asking a friend for directions and they begin with 'first, ask me for directions...'. You would loop forever before taking a single step. Left recursion is a grammar's version of this trap: a rule whose first thing to do is to expand the very same variable again, so a naive top-down parser keeps expanding without ever consuming any input.

A variable A is directly left-recursive if it has a rule A -> A alpha — the right-hand side begins with A itself. It is indirectly left-recursive if a chain of rules leads back to A on the left, such as A -> B beta and B -> A gamma. Left recursion is perfectly fine for DEFINING a language and is natural for left-associative operators (A -> A + b | b describes b, b+b, b+b+b growing leftward). The problem is purely procedural: a top-down, recursive-descent parser that tries to match A by first trying the rule A -> A alpha will call itself on A again with no input consumed, recursing infinitely.

Because of this, left recursion must be removed before a grammar can be parsed top-down (LL parsing, recursive descent) or converted to Greibach normal form, which forbids a leading variable outright. The fix rewrites left recursion into right recursion using a helper variable, preserving the language but, importantly, changing the parse trees (left-leaning becomes right-leaning). Bottom-up parsers (LR, shift-reduce) actually prefer left recursion and have no trouble with it — so whether left recursion is a bug depends entirely on the parsing method you intend to use.