Compilers: Principles and Practice

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 ...