FIRST, FOLLOW and LL(1) Parsing

Text

Grammar:
E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

FIRST Sets

FIRST(α) is the set of terminals that can begin a string derived from α (plus ε if α ⇒* ε).

FOLLOW Sets

FOLLOW(A) is the set of terminals that can appear immediately to the right of A. $ ∈ FOLLOW(start symbol).

Non-terminal	FIRST	FOLLOW
E	{ (, id }	{ ), $ }
E'	{ +, ε }	{ ), $ }
T	{ (, id }	{ +, ), $ }
T'	{ *, ε }	{ +, ), $ }
F	{ (, id }	{ *, +, ), $ }

LL(1) Parsing Table

For each A → α: add it under every terminal in FIRST(α); if ε ∈ FIRST(α), add it under every terminal in FOLLOW(A).

	id	+	*	(	)	$
E	E→TE'			E→TE'
E'		E'→+TE'			E'→ε	E'→ε
T	T→FT'			T→FT'
T'		T'→ε	T'→*FT'		T'→ε	T'→ε
F	F→id			F→(E)

There's no cell with two entries, so the grammar is LL(1).

Parsing id + id

Text

Stack          Input      Action
$E             id+id$     E → TE'
$E'T           id+id$     T → FT'
$E'T'F         id+id$     F → id
$E'T'id        id+id$     match id
$E'T'          +id$       T' → ε
$E'            +id$       E' → +TE'
$E'T+          +id$       match +
$E'T           id$        T → FT'
$E'T'F         id$        F → id
$E'T'id        id$        match id
$E'T'          $          T' → ε
$E'            $          E' → ε
$              $          ACCEPT

Track your progress through the Compiler Design course

← Prev Next →