The Internet is full of claims that an $LL(1)$ grammar cannot be ambiguous, left-recursive, or not left-factored.
But is the statement "An $LL(1)$ grammar cannot be non-left-factored or left-recursive" strictly true?
I don't think so.
Here's a counterexample where the grammar is not left-factored but still $LL(1)$:
$$ S \to Aa \mid Ab \\ A \to \epsilon $$
This grammar is $LL(1)$ since the parsing table has no multiple entries.
Now, consider another grammar:
$$ A \to Aa $$
This grammar is left-recursive, yet it is still $LL(1)$. Its language is empty. So, $LL(1)$ parser will reject every string.
While these grammars don't generate particularly interesting languages, they do serve as counterexamples.
So, although the general claim holds in almost all cases, but it seems misleading to state it as an absolute rule.
Can someone shed more light on this? Am I missing anything?
-
$\begingroup$ My impression as a non-expert is that you're right, but it might also be a common kind of throwaway sentence not meant to be taken too literally (= "there may be exceptions but they don't matter in practice"). It's a general rule that one shouldn't blindly trust what they read on the internet, so "The internet is full of claims" is not a status quo that can be addressed without being intimately familiar with the topic. If you instead cite claims from authoritative sources, that would be easier to answer in a definitive way. $\endgroup$Li-yao Xia– Li-yao Xia2025年11月03日 21:11:17 +00:00Commented Nov 3 at 21:11