CpS 450 Lecture Notes

Grammar Analysis


In order for a recursive descent parse to proceed when there are multiple alternatives for a given LHS, the parser must be able to use the current input token to predict which production to use to expand a nonterminal. This requires the parser to know First and Follow sets.

Example from this grammar:

First(Vn) - the set of terminals which can begin a string derivable from a nonterminal Vn

Two cases to consider.

  1. The grammar contains no nullable productions

  2. The grammar contains nullable productions

Note that, in general, it's impossible to compute the First set for an isolated nonterminal; we usually must compute the First set for all nonterminals.

Here's a description of the more complicated case, to compute First(A), where A is a nonterminal:

Example Exercise: Compute First(this grammar)

Solution

 

First

start

read, write, id

stmt_list

read, write, id

stmt_tail

read, write, id, ε

stmt

read, write, id

expr

intlit, id

Example Exercise: Compute First of the following grammar:

1.

A

::= B C D

2.
3.

B

::= c E b
::=

3.
4.

C

::= a E D
::= B

5.
6.

D

::= a D
::=

7.

E

::= B b D

Answer

 

First

A

c a ε

B

c ε

C

a c ε

D

a ε

E

c, b

 

First(XYZ...)

When constructing an LLPT, we must compute the set of symbols that can begin a string derivable from the right-hand side of each production. For arbitrary LL(1) grammars, this can be done only after the First( ) sets are computed for all of the nonterminals.

See p. 113 (Step 5) for the technique.

Follow(Vn) - the set of terminal symbols which can follow a nonterminal Vn in a sentential form

Example Exercise: Compute Follow(this grammar)

Solution

 

Follow

start

$

stmt_list

$

stmt_tail

$

stmt

;

expr

) ;

Example Exercise: Compute Follow(this grammar)

 

Follow

A

$

B

a b c $

C

a $

D

a b $

E

a b $

 

 

Disappearing Nonterminals