0
$\begingroup$

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?

asked Oct 25 at 13:28
$\endgroup$
1
  • $\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$ Commented Nov 3 at 21:11

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.