Question

Which of the following statements is TRUE regarding LL(1) grammars?

• A. A grammar with left recursion can be LL(1).
• B. Every LL(1) grammar is also LR(1).
• C. LL(1) parsers are bottom-up parsers.
• D. Ambiguous grammars can be LL(1).

Hint:

To convert a grammar into an LL(1) format, you must perform "Left Recursion Elimination" and "Left Factoring" to ensure the parser can always make a unique choice based on the next input symbol.

Answer 1

The Correct Option is B

Concept: Parsers are categorized by how they process a grammar. LL(1) is a Top-Down parser, while LR(1) is a Bottom-Up parser.
• LL(1): Left-to-right, Leftmost derivation, 1 lookahead symbol.
• LR(1): Left-to-right, Rightmost derivation in reverse, 1 lookahead symbol.

Step 1: Eliminating incorrect statements about LL(1).
Left Recursion (A) prevents LL(1) because the parser would loop infinitely. LL(1) is a Top-Down parser, so (C) is false. No ambiguous grammar (D) can be parsed by a deterministic LL(1) parser.

Step 2: Understanding the hierarchy of grammars.
LR(1) parsers are more powerful than LL(1) parsers. Any language that can be parsed Top-Down can also be parsed Bottom-Up.

Step 3: Conclusion on the relationship.
LL(1) $\subset$ LR(1). Therefore, every grammar that satisfies the strict requirements of LL(1) will also satisfy the more flexible requirements of LR(1).