Compilers: Principles and Practice by Pearson

86 Compilers – Principles and Practice

4.2.5 LL(1) Grammars with ε-rules

The definition of the FIRST(α) set is to be extended to include zero length strings:

Example

Consider the following grammar:

0. S’ -> A#

1. A -> iB = e

2. B -> SB

3. B -> <empty>

4. S -> [eC]

5. S -> .i

6. C -> eC

7. C -> <empty>

Here, we have the following FIRST() functions:

FIRST(A#) = {i} FIRST(<empty>) = {<empty>}

FIRST(iB = e) = {i} FIRST(eC) = {e} FIRST(.i) = {.}

FIRST(SB) = {[.} FIRST([eC]) = {[}

Note that in this grammar we have two nullable non-terminals – B and C. We use a name V

Nε

for

the set of Nullable-NT and say that B, C ∈ V

Nε

.

For the grammar without ε-rules, ...