LL Handles Direct Left Recursion

Theory vs Practice

Consider the following question, which was the impetus for this post:

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:

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:

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 Left to right, performing Leftmost derivation of the sentence”¹, and a parser that works like that cannot handle left recursion².

Different issues occur depending on how the parser is implemented. Consider the following grammar:

expr : expr op term
     | term;

op : "+" | "-"

A recursive descent parser (which fits the definition above) will enter an infinite loop:

def expression():
  expression()
  op()
  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.

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.

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):

expr : expr op term
     | term;

Can be rewritten into the following:

expr : term expr_tail;
expr_tail: op term expr_tail | ε;

Or, if your LL parser generator allows it, to the following:

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 ANTLR3³, this is how it suggests to handle expressions.

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.

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).

So why does this matter? You probably didn’t even think of it, but I snuck in a little gotcha above:

Or, if your LL parser generator allows it, to the following:

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?

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⁴.

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.

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.

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.

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.

But I vibe coded an LL(1) parser generator in Python that handles direct left recursion just fine:

expr : a=expr "+" b=term { a + b } 
     | a=expr "-" b=term { a - b }
     | t=term { t } ;
term : a=term "*" b=factor { a * b } 
     | a=term "/" b=factor { a / b } 
     | f=factor { f } ;
factor : "(" e=expr ")" { e }
       | "-" f=factor { -f }
       | token=NUMBER { float(token.text) }
       | token=IDENT { ctx[token.text] } ;

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

It can work in a table-driven manner, and the left-recursion rewrite sits alongside the same code that rewrites groups () and repetitions *.

It can also directly generate recursive descent code, in which case it translates the direct left-recursion into a fold, similar to a Pratt parser. Or it can translate the rewritten BNF grammar into a recursive descent parser too; it still works, albeit less efficiently. The rewrite is completely trivial, I showed you the trick previously, but here is the internal BNF, generated automatically:

expr : t=term _v=$expr_star[t]  { _v } ;
term : f=factor _v=$term_star[f]  { _v } ;
factor : "(" e=expr ")"  { e }
       | "-" f=factor  { -f }
       | token=NUMBER  { float(token.text) }
       | token=IDENT  { ctx[token.text] } ;
$expr_step[a] : "+" b=term  { a + b }
              | "-" b=term  { a - b } ;
$expr_star[a] : _i=$expr_step[a] _v=$expr_star[_i]  { _v }
              | { a } ;
$term_step[a] : "*" b=factor  { a * b }
              | "/" b=factor  { a / b } ;
$term_star[a] : _i=$term_step[a] _v=$term_star[_i]  { _v }
              | { a } ;

Where do you draw the line? Some PEG parsers, which also cannot handle left-recursion, also handle direct left-recursion, like OhmJS.

If the definition of what makes an LL(k) parser is “parses the input from Left to right, performing Leftmost derivation of the sentence, with k tokens of lookahead”, then my little parser generator above fits the bill.

Reductions are the Norm

In other computer science areas of study, we’re not usually too worried about the exact input that goes into something, but what can be reduced to that input.

A classic example is the Boolean Satisfiability Problem (SAT), which asks whether there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the formula's variables can be consistently replaced by the values TRUE or FALSE to make the formula evaluate to TRUE.

SAT is the prototypical NP-complete problem. If you want to know if a problem is in NP, one way to figure that out is by coming up with a reduction to SAT.

What makes SAT useful are precisely these reductions. Not just theoretically, but in practice too. Checking if a propositional logic formula is satisfiable isn’t particularly interesting, but finding a solution to Sudoku is, and Sudoku can be reduced into SAT.

Most SAT solvers don’t even accept arbitrary boolean formulas, they require them to be rewritten into Conjunctive Normal Form. You can even reduce the problem to 3-SAT, which only allows a maximum of 3 variables per disjunction. Still just as expressive.

It’s that expressive power that matters. The fact that you can solve Sudoku, not that the solver is actually working with conjunctions of boolean variables internally. Not the input format, but what can reasonably (i.e., in polynomial time) be reduced to it.

Theory and practice are at odds here as well. NP problems have exponential complexity, O(2ⁿ), but SAT solvers can tackle absolutely massive industrial problems with millions of variables and constraints. The algorithms they use can exploit hidden structures in the problem and converge to a solution incredibly fast.

The CPU in your computer probably has a SAT solver to thank for its existence, either for how its internals are laid out, or for its correctness (or both!). This wouldn’t be possible if SAT solving was always O(2ⁿ). O(2ⁿ) is the worst case scenario, most problems can be solved much more efficiently. The worst case is important to know, but what can actually be done in practice is perhaps even more so.

Back to LL

So given the above, I hope I’ve shown you why the sentence:

LL grammars cannot have rules containing left recursion.

Should instead be:

LL grammars can only have rules containing direct left recursion⁵.

Because an LL grammar is defined by what an LL parser can recognize, and an LL parser can easily deal with direct left recursion. And direct left recursion happens to include the most relevant category of left recursion: mathematical expressions.

If you search around the web or ask your favorite LLM (including Google’s if you need a free one) why one should favor LR over LL, they’ll tell you something like:

Support for Left Recursion: LL parsers will fall into infinite loops if the grammar contains left-recursive rules (e.g., A → A α). LR parsers natively handle left recursion, making it easier to define structures like mathematical expressions.

This statement is mostly false. This is not a reason to use LR over LL. Definitely not for the specific rule example Gemini used (which is directly left recursive). Even the “infinite loop” part of the answer is wrong, you’ll get a conflict unless you’re translating to a recursive descent parser by hand.

This type of answer is what you get when you only focus on worst-case theoretical limitations rather than what can be done in practice.

But the thing that makes the sentence not entirely false is one word: natively. It is true most LL parsers do not natively handle any left recursion. They could handle some, but they don’t. This is an engineering problem, not a theoretical one.

Conclusion

When a silly discord question leads a person to vibe coding an LL parser generator. Programmers sure are a weird bunch, or at least I am.

I’ve made my point as to what I think the answer to the original question is and why: parsers that can handle direct left recursion can 100% still be considered LL, because what matters is how they work, and preprocessing is normal anyway.

But I’m curious to know what you think.

1. Thanks Wikipedia. Read this if you want something more formal.

2. Wait for it 😉.

3. There’s a reason I said 3 and not ANTLR4. More on ANTLR4 later.

4. Strongly equivalent, sure, but weakly equivalent only matters if you want the same exact parse tree with no transformations applied to it what so ever, and I can’t think of any case where I’d want that. At the very least you usually want to filter many tokens out or hide certain auxiliary productions.

5. Technically it is possible to eliminate all left-recursion, not just direct, but the process is far more convoluted and dependent on the order in which grammar rules are specified, so I don’t consider it a reasonable reduction.