Compilers: Principles and Practice by Pearson

Worked-out Problems

APPENDIX D

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