O'Reilly logo

Compilers: Principles and Practice by Himanshu B. Dave, Parag H. Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

D.1 Problems for Chapter 4: Parsers

D.1.1 Top-down Parsing

Problem 1.1.1  Is this a LL(1) grammar?

0. S‘–> S#            3. A –> abS
1. S –> aAa           4. A –>  c
2. S –> empty

First of all, we note that it is a CFG (single NT's on the LHS of all rules), it has ∊-rule, there is no left recursion. So it is a candidate for being an LL(1) grammar. In FIRST(A), the RHS are disjoint, so we need test only productions from S.As one of the S productions is an ∊-rule, we find the FOLLOW(S)= {#,a}. Now, FIRST(aAaFOLLOW(S)) ∩ FIRST(∊FOLLOW(S)) = {a}∩{#, a}≠ Ø. Therefore, this is not an LL(1) grammar.

For example, consider a string “aaba…#”. The productions for this strings can be: S#aAa#aabSa#.

Now at this stage, we do not know whether to use rule 1 or rule 2 for the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required