LL Handles Direct Left Recursion - by Sir Whinesalot

Burning the Midnight Coffee

SubscribeSign in

LL Handles Direct Left Recursion<br>Theory vs Practice

Sir Whinesalot<br>Jul 16, 2026

Share

Consider the following question, which was the impetus for this post:<br>Is unability to handle left recursion a signifying trait of LL parsers? I.e., if a parser can handle left recursion, does it make that parser automatically not LL?

That question lead to me asking this followup question:<br>If my parser generator accepts as input a subset of left-recursive grammars, and the parsers it generates recognize them using classic table-driven LL(1), are they no longer LL(1)?

If you know any formal language theory, you probably know the following:<br>LL grammars cannot have rules containing left recursion.

Why? Because LL grammars are defined as “context-free grammars that can be parsed by an LL parser”, with an LL parser defined as a parser that “parses the input from L eft to right, performing L eftmost derivation of the sentence”1, and a parser that works like that cannot handle left recursion2.<br>Different issues occur depending on how the parser is implemented. Consider the following grammar:<br>expr : expr op term<br>| term;

op : "+" | "-"

A recursive descent parser (which fits the definition above) will enter an infinite loop:<br>def expression():<br>expression()<br>op()<br>term()

A table-driven parser will detect a conflict because it cannot decide how to make progress, usually with a cryptic message if it hasn’t been explicitly designed to detect and point out the left recursion.<br>So far, the sentence seems to be true. But it’s also not very useful, because in practice it is only really true for indirect left recursion.<br>Eliminating Left Recursion

It is well known that simple cases of left recursion can be eliminated pretty easily. Some tweaks to the grammar mostly avoid the problem. The grammar above (presented again for convenience):<br>expr : expr op term<br>| term;

Can be rewritten into the following:<br>expr : term expr_tail;<br>expr_tail: op term expr_tail | ε;

Or, if your LL parser generator allows it, to the following:<br>expr : term (op term)* | term;

If you studied formal language theory in university your professor probably taught you this trick. If you read the documentation of an LL parser generator like ANTLR33, this is how it suggests to handle expressions.<br>This results in a weakly equivalent grammar, meaning it recognizes the same language (and generates the same set of strings), but with a different parse tree. The parse tree tilts to the right rather than to the left.<br>Given an input like 1 - 2 - 3, the original grammar parses it as (1 - 2) - 3, whereas the transformed grammar parses it as 1 - (2 - 3).<br>So why does this matter? You probably didn’t even think of it, but I snuck in a little gotcha above:<br>Or, if your LL parser generator allows it , to the following:<br>expr : term (op term)* | term;

“Or if your LL parser generator allows it”. That little * operator there, is that LL? What about the group ()? Is that LL?<br>Reductions

If you’re implementing a table-driven LL parser, the EBNF grammar with those operators needs to be simplified (reduced) to a standard BNF form. That means the grammar that actually ends up being recognized is not the same grammar you fed the parser generator. It was rewritten 4.<br>Now, my question to you is, do you consider parser generators that support such operators (like ANTLR3, JavaCC, Yapps, etc.) to be LL parser generators? Most people seem to think so, and they refer to them as such. ANTLR3 is LL(*), others LL(k) or LL(1), but LL regardless.<br>They may not do the reduction to standard BNF internally because they’re not table-driven, instead directly generating recursive descent code, but does that change anything? Recursive descent code can handle full PEG. The part that makes it LL and not PEG is the lack of backtracking right? The important part is not that it is parsed by a table-driven solution, but that it could be.<br>ANTLR3, being LL(*), should actually be considered to be in the domain of TDPL (because it has syntactic and semantic predicates), making it closer to a restricted form of PEG, not your typical LL parser. But everyone is ok with calling it an LL(*) parser generator.<br>Which gets me to ANTLR4. ANTLR4 is an Adaptive LL(*) parser generator (whatever that means), and it supports direct left recursion. Does that disqualify it from being an LL parser? Maybe ALL(*) is a special case and doesn’t really count.<br>But I vibe coded an LL(1) parser generator in Python that handles direct left recursion just fine:<br>expr : a=expr "+" b=term { a + b }<br>| a=expr "-" b=term { a - b }<br>| t=term { t } ;<br>term : a=term "*" b=factor { a * b }<br>| a=term "/" b=factor { a / b }<br>| f=factor { f } ;<br>factor : "(" e=expr ")" { e }<br>| "-" f=factor { -f }<br>| token=NUMBER { float(token.text) }<br>| token=IDENT { ctx[token.text] } ;

This grammar is accepted and evaluates to the result you’d expect for a given expression with the correct...