Chapter 5:

Top-Down
Parsing
陳奇業 成功 學資訊 程系

1
大
工
Objectives of Top-Down Parsing
▪ an attempt to find a leftmost derivation for an input string.
▪ an attempt to construct a parse tree for the input string starting from the root and creating
the nodes of the parse tree in preorder.

2
Objectives of Top-Down Parsing
▪ In this chapter, we study the following two forms of top-down parsers:
▪ Recursive-descent parsers contain a set of mutually recursive procedures that cooperate to
parse a string. Code for these procedures can be written directly from a suitable grammar.
▪ Table-driven LL parsers use a generic LL(k) parsing engine and a parse table that directs the
activity of the engine. The entries for the parse table are determined by the particular LL(k)
grammar. The notation LL(k) is explained below.

3
The Basic Method of Recursive-Descent

4
 Using EBNF
▪ Consider now the case of an exp
in the grammar for simple
arithmetic expressions in BNF:
→ exp |
▪ The solution is to use the EBNF
rule
→ { }

5
𝑒
𝑥
𝑝
𝑡
𝑒
𝑟
𝑚
𝑎
𝑑
𝑑
𝑜
𝑝
𝑡
𝑒
𝑟
𝑚
𝑒
𝑥
𝑝
𝑎
𝑑
𝑑
𝑜
𝑝
𝑡
𝑒
𝑟
𝑚
𝑡
𝑒
𝑟
𝑚
Syntax Tree

6
Syntax Tree
▪ We consider the expression
3+4+5

7
Approaches of Top-Down Parsing
with backtracking (making repeated scans of the input, a general form of top-down
parsing)

Methods: To create a procedure for each nonterminal.

8
Problems for top-down parsing with
backtracking

9
e.g. S -> cAd A -> ab | a L = { cabd, cad }

S( ) { if input symbol == ‘c’ A( ) { isave= input-pointer;

{ Advance(); if input-symbol == ‘a’
if A() { Advance();
if input-symbol == ‘d’ if input-symbol == ‘b’
{ Advance(); { Advance();
return true; return true;
} }
} }
return false; input-pointer = isave;
} if input-symbol == ‘a’
{ Advance();
return true; }
else
c a d
return false;
} 10
 Problems for top-down parsing with
backtracking
▪ left-recursion (can cause a top-down parser to go into an infinite loop)
▪ Def. A grammar is said to be left-recursive if it has a nonterminal s.t. there is a
derivation ⟹ for some .

▪ backtracking - undo not only the movement but also the semantics entering in symbol
table.

▪ the order the alternatives are tried (For the grammar shown above, try = where
→ is applied first)

11
𝐴𝐴
𝛿𝑤
𝐴
𝑐
𝑎
𝑎
𝐴
𝑏
𝑑
𝛿
 The LL(1) Predict Function
▪ Given the productions
→ 1
→ 2
⋯
→
▪ During a (leftmost) derivation
⋯ ⋯ ⇒ … 1⋯ or
⋯ 2⋯ or
⋯ or
⋯ ⋯
▪ Deciding which production to match
▪ Using lookahead symbols

12
𝑛
𝑛
𝐴
𝐴
𝐴
𝛼
𝛼
𝛼
𝛼
𝛼
𝐴
𝛼
The LL(1) Predict Function
Single Symbol Lookahead

(First( 1⋯ ) − ) ∪ Follow( ), if ∈ First( 1⋯ )

{First(
Predict( → 1⋯ )=
1⋯ ) , otherwise

▪ The limitation of LL(1)

▪ LL(1) contains exactly those grammars that have disjoint predict sets for productions that share
a common left-hand side
𝑚
𝑋
𝑋
𝑚
13
𝐴
𝑋
𝑋
𝑚
𝑚
𝑋
𝑋
𝜆
𝐴
𝜆
𝑋
𝑋
 A grammar G is LL(1) if and only if whenever → | are two distinct productions of G,
the following conditions hold:
▪ 1. For no terminal do both and derive strings beginning with .
▪ 2. At most one of and can derive the empty string.
▪ 3. If ⇒∗ then does not derive any string beginning with a terminal in FOLLOW( ).
Likewise, if ⇒∗ , then does not derive any string beginning with a terminal in
FOLLOW( )

14
𝐴
𝒂𝛼𝛽𝒂𝛼𝛽𝛽
𝛼𝐴𝛼
𝛽𝐴
𝛼
𝜖
𝜖
𝛽
The LL(1) Predict Function

15
 First set
▪ To compute First( ) for all grammar symbols , apply the following rules until no more
terminals or can be added to any First set.
1. If is a terminal, then First( ) = { }.
2. If in a nonterminal and → 1 2⋯ is a production for some ≥ 1, then place in
First( ) if for some , is in First( ), and is in all of First( 1), …, First( −1); that is
1⋯ −1 ⟹∗ . If is in First( ) for all = 1, 2, …, , then add to First( ).

3. If → is a production, then add to First( ).

16
𝑗
𝑌
𝑖
𝑖
𝑖
𝑘
𝑌
𝑌
𝑌
𝑋𝜆𝑋
𝑋𝑋
𝑎
𝑘
𝑖𝑎
𝜆
𝑌
𝜆
𝑗
𝜆
𝑋
𝜆
𝑌
𝑋
𝑋
𝑋
𝑋
𝑋
𝑌
𝜆
𝑌
𝑌
𝑋
𝑘
𝜆
 An Example
→ ′
′ → + ′|
→ ′
′ → ∗ ‘|
→ ( )|

( ) = ( ) = ( ) = {(, }
( ′) = { + , }
( ′) = { ∗ , }

17
𝐸
𝐸
𝑇
𝑇
𝐹
𝐹
𝐹
𝐹
𝑖
𝑖
𝑖


𝑟
𝑟
𝑟
𝑠
𝑠
𝑠
𝑡
𝑡
𝑡
𝐹
𝐸
𝐸
𝑇
𝑇
𝐸
𝐸
𝑇


𝐹
𝑇


𝑇
𝐸
𝑖
𝐹
𝑑

𝑖
𝜆
𝑟
𝜆
𝑠
𝑡
𝜆
𝜆
𝑇
𝐹
𝑖
𝑟
𝑠
𝑡
𝐹
𝑖
𝑑
18
 Follow set
▪ To compute Follow( ) for all nonterminals , apply the following rules until nothing can
be added to any Follow set.
1. Place in Follow( ), where is the start symbol.
2. If there is a production → , then everything in First( ) except is in Follow( ).
3. If there is a production → , or a production → , where First( ) contains ,
then everything in Follow( ) is in Follow( ).

19
𝛽
𝛽
𝐴𝜆
𝑆𝐴
𝜆
𝐴
𝐴
𝜆
𝛼
𝛼
𝛼
𝐵
𝐵
𝐵
𝐴
𝑆
𝐵
𝐵
𝐴
𝛽
𝛽
 Follow( ) = { , )} // rules 1 & 2
An Example Follow( ′) = { , )} // rule 3
Follow( ) = { + , , )} // rules 2 & 3
Follow( ′) = { + , , )} // rule 3
→ ’ Follow( ) = { ∗ , + , , )} // rules 2 & 3
′ → + ′|
→ ’
′→ ∗ ′|
→ ( )| First( ) = First( ) = First( ) = {(, }
First( ′) = { + , }
/* is the start symbol */
First( ′) = { ∗ , }

20
𝐸
𝐸
𝑇
𝑇
𝐹


𝐹
𝑇
𝐸
𝐸
𝑇
𝐹
𝑇
𝑇
𝐸
𝑖


𝑑
𝜆
𝜆
𝐸
𝐸
𝐸
𝑇


𝑇
𝜆
𝜆
𝐹
𝑖
𝑑
𝐸
𝐸
𝑇
𝑇
𝐹


𝜆
𝜆
𝜆
𝜆
𝜆
 The LL(1) Predict Function
▪ A grammar is LL(1) if and only if whenever → | are two distinct productions of ,
the following conditions hold: common prefixes
1. For no terminal do both and derive strings beginning with .
First( ) ∩ First( ) =
2. At most one of and can derive the empty string.
3. If ⟹∗ , then does not derive any string beginning with a terminal in Follow( ).
Likewise, if ⟹∗ , then does not derive any string beginning with a terminal in
Follow( ).
First( ) ∩ Follow( ) = (i.e. If First( ) contains then First( ) ∩ Follow( ) = )

21
𝛼
𝛽
𝛽
𝐴
𝜙
𝜙
𝐺𝐴
𝐺𝑎𝛼𝛽𝑎
𝛼𝛽𝛽
𝛼
𝛼
𝛽
𝜆
𝛼
𝛼
𝛼
𝜆
𝜆
𝐴
𝐴
𝛽
𝐴
𝜙
Not extended BNF form

$: end of file token

22
 The LL(1)
Parse Table
▪ An LL(1) parse table
: × → ∪ {Error}
▪ The definition of

[ ][ ] = → 1⋯ if
∈ Prediction( → 1⋯ );
[ ][ ] = Error, otherwise

23
𝑚
𝑚
𝑛
𝑡
𝑇
𝑡
𝑇
𝐴
𝐴
𝑡
𝑡
𝐴
𝐴
𝑋
𝑋
𝑋
𝑋
𝑇
𝑇
𝑉
𝑉
𝑃
24
25
Building Recursive
Descent Parsers
from LL(1) Tables
▪ The form of parsing procedure:

26
Building Recursive
Descent Parsers
from LL(1) Tables
▪ E.g. of an parsing procedure for
<statement> in Micro
▪ An algorithm that automatically
creates parsing procedures like
the one in Figure 5.6 from LL(1)
table

27
Building Recursive
Descent Parsers
from LL(1) Tables
▪ The data structure for describing
grammars

28
Building Recursive
Descent Parsers
from LL(1) Tables
▪ gen_actions()
▪ Takes the grammar symbols and
generates the actions necessary
to match them in a recursive
descent parse

29
30
 LL(1) Parsing
▪ →( )
▪ →
S
▪ Input String: ()

( S ) S
-----------------------------
▪ ⟹lm ( ) ⟹lm () ⟹lm ()

31
𝜆
𝜆
𝑆
𝑆
𝑆
𝜆
𝑆
𝑆
𝑆
𝑆
𝑆
 Elimination of Left Recursion
▪ It is possible for a recursive-descent parser to loop forever. A problem arises with "left-
recursive" productions like
expr → expr + term
▪ A left-recursive production can be eliminated by rewriting the offending production.
Consider a nonterminal A with two productions
A→A |
▪ For example, A= expr, = + term, = term

32
𝛼𝛽𝛼𝛽
 Elimination of
Left Recursion
▪ We can convert left recursion to
right recursion in the following
manner, using a new
nonterminal R:
A→ R
R → R|ϵ

33
𝛽𝛼
 Elimination of Immediate Left Recursion
▪ Immediate left recursion can be eliminated by the following technique, which works for
any number of -productions. First, group the productions as
→ 1| 2|⋯| | 1| 2|⋯|

where no begins with an . Then, replace the -productions by

→ 1 ′| 2 ′| ⋯ | ′
′→ 1 ′| 2 ′| ⋯ | ′|

34
𝑖
𝑛
𝑚
𝑚
𝑛
𝐴𝐴
𝛽
𝐴𝐴𝐴
𝐴

𝐴
𝛽
𝛼
𝛼
𝐴
𝐴


𝐴
𝛽
𝛼
𝛼
𝐴
𝐴


𝐴
𝛽
𝛼
𝛼
𝐴
𝐴

𝛽

𝜆
𝛽
𝛽
 e.g.
→ + |
→ ∗ | → ( )|
After transformation:

→ ′ ′→ + ′|
→ ′ ′→ ∗ ′|
→( )|

35
𝐸
𝑇
𝐹
𝐸
𝑇
𝐹
𝐸
𝐸
𝑇
𝐹
𝑇
𝐸
𝐸
𝑇
𝑇
𝐹
𝑖


𝑑
𝑖
𝑇
𝑑
𝑇
𝐹
𝐸


𝐹
𝑇
𝑇
𝐸


𝜆
𝜆
 How about left recursion occurred for
derivation with more than two steps?
e.g., → | → | |
where ⟹ ⟹

36
𝑆
𝑺
𝐴
𝐴
𝑎
𝑎
𝑏
𝐴
𝑺
𝑑
𝑎
𝐴
𝑐
𝑆
𝑑
𝑒
 Algorithm: Eliminating left recursion
Input: Context-free Grammar G with no cycles or -production
Methods:
1. Arrange the nonterminals in some order 1, 2, …,
2. for = 1 to do
{
for = 1 to − 1 do
{
replace each production of the form → by the production
→ 1 | 2 | ⋯ | , where → 1 | 2 | ⋯ | are all current -production;
}
eliminate the immediate left-recursion among the -production;
}
#We say a grammar G is cyclic if for some nonterminal A in G, we have A + A 37
𝑖
𝑖
𝑗
𝑗
𝑖
𝑗
𝑛
𝑘
𝑘
𝜆𝐴
𝐴
𝑖
𝑛𝑗
𝑖
𝐴
𝐴
𝐴
𝐴
𝐴
𝐴
𝛿
𝛿
𝛾
𝛾
𝛿
𝛿
𝐴
𝛾
𝛿
𝛿
𝛾
 An Example
e.g.
→ |
→ | |

Step 1: ==> → |
Step 2: ==> → | | |
Step 3: ==> → ′| ′ ′ → ′| ′|

38
𝐴
𝑏
𝑑
𝐴

𝑒
𝐴

𝐴

𝑐
𝐴

𝑎
𝑑
𝐴


𝑆
𝐴
𝑆
𝐴
𝐴
𝐴
𝐴
𝐴
𝑎
𝑎
𝑐
𝑐
𝑏
𝑆
𝐴
𝑏
𝑑
𝑎
𝑑
𝑒
𝑏
𝑑
𝑒
 Non-backtracking (recursive-descent)
parsing
recursive descent : use a collection of mutually recursive
routines to perform the syntax analysis.

Left Factoring : → 1 | 2 ==> → ′ ′ → 1| 2

Methods:
1. For each nonterminal find the longest prefix common to two or more of its alternatives. If
replace all the productions
→ 1| 2| …| | h by → ‘| h ′→ 1| 2| …| |
2. Repeat the transformation until no more found
e.g. → | | →
==> → ′| ′ → | →
39
𝑛
𝑛
𝛼

𝜆
𝐴
𝐴
𝐴𝜶
𝐴𝐴
𝐴
𝑆
𝑆
𝑖
𝐶
𝛼
𝑖
𝛼
𝛼
𝛼
𝐶
𝛽
𝑡
𝛽
𝐴
𝐴
𝑆
𝑡
𝑆

𝛼
𝑆
𝐴
𝛼
𝛽
𝑖
𝑜
𝐶

𝛽
𝑡

𝑡
𝑆
𝑎
𝑒
𝑟
𝑒
𝑠
𝑆
𝛽
𝑆
𝐴
𝛼

𝛽
𝛽
𝑎

𝐶
𝛽
𝑜
𝑒
𝑡
𝑆
𝑒
𝛽
𝑟
𝑏
𝑠
𝜆
𝐶
𝛽
𝑏
 Predicative Parsing
Features:
- maintains a stack rather than recursive calls
- table-driven
Components:
1. An input buffer with end marker ($)
2. A stack with endmarker ($) on the bottom
3. A parsing table, a two-dimensional array [ , ], where ‘ ’ is a nonterminal symbol and
‘ ’ is the current input symbol (terminal/token).

40
𝑀
𝐴𝑎
𝐴
𝑎
41
 Parsing Table

[ , ] ( ) $

→ ( ) → →

42
𝑀
𝑺
𝑺
𝑺
𝐴
𝑎
𝝀
𝑺
𝑺
𝑺
𝝀
 Algorithm:
Input: An input string and a parsing table for grammar .

Output: A leftmost derivation of or an error indication.

43
𝑤𝑀𝐺𝑤
 Initially $ is in input buffer and $ is in the stack.
Starting Symbol of the grammar
Method:
do { Let of be the next input symbol and be the top stack symbol;
if is a terminal
{ if == then pop from stack and remove from input;
else ERROR();}
else
{ if [ , ] = → 1 2⋯ then
1. pop from the stack;
2. push −1⋯ 1 onto the stack with 1 on top;
else
ERROR();
}
} while ( ≠ $)
if ( = = $) and (the next input symbol = = $) then accept else error();

44
𝑛
𝑛
𝑛
𝑆
𝑤
𝑎𝑤𝑋𝑋𝑋
𝑋𝒂𝑀
𝑋𝑌
𝑋
𝑋
𝑌
𝑌
𝑋
𝑎
𝑌
𝒂
𝑋
𝑌
𝑌
𝑌
45
 [ , ] ( ) $

→ ( ) → → 46
𝑀
𝑺
𝑺
𝑺
𝐴
𝑎
𝝀
𝑺
𝑺
𝑺
𝝀
Start →statement $
First(state) ={if, other}
First(if-stmt)={if}
First(else-part)={else, ε}
First(exp)={0.1}

Follow(state)={$, else}
Follow(if-stmt)={$ , else}
Follow(else-part)={$, else}
Follow(exp)={)}

47
 Construct a Predicative Parsing Table
1. For each production → of the grammar, do steps 2 and 3.
2. For each terminal in First( ), add → to [ , ].
3. If is in First( ), add → to [ , ] for each terminal in Follow( ).
4. Make each undefined entry of be error.

48
𝐴
𝐴
𝐴





𝒂
𝑀
𝜆
𝑀
𝑏
𝑀
𝐴
𝐴
𝑎
𝑏
𝐴
LL(1) grammar
A grammar whose parsing table has no multiply-defined entries is said to be LL(1).

First 'L' : scan the input from left to right.

Second ‘L’ : produce a leftmost derivation.
'1' : use one input symbol to determine parsing
action.

* No ambiguous or left-recursive grammar can be LL(1).

49
 Def. for Multiply-defined entry
If G is left-recursive or ambiguous, then will have at least one multiply-defined entry.
e.g.
→ ′| ′ → | →
generates:
[ ′, ] = { → , ′ → } with multiply- defined entry.

Start → S $
First(S)={i, a}, First(S’)={e, }, First(C)={b}
Follow(S)={$, e}, Follow(S’)={$, e}, Follow(C)={t}

50
𝑀𝑺
𝑀
𝝀
𝑆

𝒊
𝑒
𝑪
𝒕
𝑺
𝑺

𝑆
𝒂
𝑺
𝜆

𝑆

𝒆
𝑺
𝑒
𝑆
𝝀
𝑪
𝒃
 Parsing table with multiply-defined entry

→ ′| ′ → | →
Start → S $
First(S)={i, a}, First(S’)={e, }, First(C)={b}
Follow(S)={$, e}, Follow(S’)={$, e}, Follow(C)={t} 51
𝑺
𝒊
𝑪
𝒕
𝑺
𝑺

𝒂
𝑺

𝒆
𝑺
𝝀
𝑪
𝒃
𝝀