Project ForgeSign up free
Compiler Design
Lexical Analysis & Parsing
GATE 2007
Hard

Consider the grammar with non-terminals N={S,C,S1}, terminals T={a,b,i,t,e}, with S as the start symbol, and rules: S → iCtSS1 | a, S1 → eS | ε, C → b. The grammar is NOT LL(1) because:

  • Ait is left recursive
  • Bit is right recursive
  • it is ambiguous
  • Dit is not context-free

Explanation

This is the classic 'dangling else' grammar (i=if, t=then, e=else). When parsing sees a trailing 'e' after nested if-statements, it's genuinely ambiguous which 'if' the 'else' should attach to — the grammar admits more than one valid parse tree for the same string, i.e. it is ambiguous (not left/right recursive, and clearly context-free).

Source: GATE CS 2007 (2007)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free