自顶向下分析 —— 递归下降法
递归下降法 (Recursive-Descent Parsing)
对每个非终极符按其产生式结构产生相应
语法分析子程序,
终极符产生匹配命令
非终极符则产生调用命令
文法递归相应子程序也递归，所以称这种
方法为 递归子程序方法或递归下降法。
例,Stm→ while Exp do Stm
则对应产生式右部的语法分析程序部
分如下：
begin
Match($while)；
Exp；
Match($do)；
Stm
end
while x>y do if x>z then x:= x+y else x:= y
Begin Match($while); Exp; Match($do); Stm End
? 当产生式中形如, A ? ?1| ?2| … | ?n
则按下面的方法编写子程序 A：
procedure A( )
begin if token?Predict(A??1) then ?(?1) else
if token?Predict(A??2) then ?(?2) else
……
if token?Predict(A??n) then ?(?n) else
err( )
end
其中对 ?i=X1X2…X n,?(?i) = ?’(X1);?’(X2);…; ?’(Xn);
如果 X?VN,?’ (X)= X
如果 X?VT,?’(X)= Match(X)
如果 X= ?,?(?) = skip(空语句 )
假设有文法
Z → a B a
B → b B | c
则相应的递归子程序可如下：
procedure Z( )
begin
if token=a then Match(a)；
B；
Match(a)
else err( )
end;
procedure B ( )
begin
if token = b then Match(b);
B;
else
if token = c
then Match(c);
else err( )
end;
主程序,Begin ReadToken; Z end
ReadToken
ReadToken
?递归子程序方法的条件：
(1)predict(A→ ?k)? predict(A→ ?j )=?,当 k ? j
(2)任一非终极符 A都不是左递归的 。
?产生式 A→ ?被选择的条件是：
当前的输入符属于 predict(A→ ?)。
?至多一个产生式被选择的条件是：
predict(A→ ?k) ? predict(A→ ?j )=?,当 k ? j
文法的等价变换
? 某个非终极符 A有如下的两个产生式：
A→ ??,A→ ?? (即有左公共前缀 )
? 某个非终极符 A有直接左递归产生式：
A→ A ? |,.....
? 消除左公共前缀
? 消除左递归
消除公共前缀
? 变换步骤：
1.产生式形如,A???1|??2|… |??n| ?
?表示不以 ?开头的字符串。
2.引进非终极符 A’,使产生式替换为：
A ? ? A? | ?
A? ? ?1|?2 |… | ?n
Stm → id,= Exp
Stm → id (ExpL)
ExpL → Exp
ExpL → Exp,ExpL
Stm → id Stm?
Stm? →,= Exp
Stm? → ( ExpL )
ExpL → Exp ExpL?
ExpL? →,Exp ExpL?
ExpL? → ?
?
消除公共前缀的例子
消除公共前缀的例子 2
?A ?ad
?A ?Bc
?B ?aA
?B ?bB
?A ?ad
?A ?aAc
?A ?bBc
?B ?aA
?B ?bB
?A?a(d|Ac)
?A ?bBc
?B ?aA
?B ?bB
?A ?aA?
?A? ?d
?A? ? Ac
A ?bBc
B ?aA
B ?bB
替换
?
提因子
?
引进 A’?
左递归
? 一个文法含有下列形式的产生式时
? （ 1） A?A? A?VN,? ?V*
? （ 2） A?B?
? B?A? A,B?VN,?,? ?V*
? 其中（ 1）为 直接左递归,（ 2）为 间接左递
归,因此文法中只要有 A?+A…,则称文法
为左递归的。
消除左递归
? 对直接左递归形如：
A ? A? | ?
消除左递归为：
A ? ? A?
A? ? ? A? | ?
消除左递归
? 间接左递归形如：
A ? B? | ?
B ? A? | b
消除左递归：
转为直接左递归形式：
A ? A ? ? | b? | ? 或者
B ? B ? ? | ? ? | b
按照直接左递归方式消除。去掉多余的
产生式
例,[1] A → B ?1 | a
[2] B → C ?2 | b
[3] C → A ?3 | c
A? B ?1 ? C ?2 ?1 ? A ?3 ?2 ?1
[3]? C →( B ?1| a ) ?3 | c
[3]? C → C ?2 ?1 ?3 |b ?1 ?3 |a ?3 |c
[4] C → (b ?1 ?3 | a ?3 | c ) C?
[5] C? → ?2 ?1 ?3 C? | ?
[1],[2],[4],[5]与原文法等价
? 作业
写出下面文法 G[p]的递归下降语法分析
程序,
P ? begin SL end
SL ? S | SL;S
S ? i | i:= E | i,S
| if E then S
| while E do S
E ? i | (E) | E + E
递归下降法 (Recursive-Descent Parsing)
对每个非终极符按其产生式结构产生相应
语法分析子程序,
终极符产生匹配命令
非终极符则产生调用命令
文法递归相应子程序也递归，所以称这种
方法为 递归子程序方法或递归下降法。
例,Stm→ while Exp do Stm
则对应产生式右部的语法分析程序部
分如下：
begin
Match($while)；
Exp；
Match($do)；
Stm
end
while x>y do if x>z then x:= x+y else x:= y
Begin Match($while); Exp; Match($do); Stm End
? 当产生式中形如, A ? ?1| ?2| … | ?n
则按下面的方法编写子程序 A：
procedure A( )
begin if token?Predict(A??1) then ?(?1) else
if token?Predict(A??2) then ?(?2) else
……
if token?Predict(A??n) then ?(?n) else
err( )
end
其中对 ?i=X1X2…X n,?(?i) = ?’(X1);?’(X2);…; ?’(Xn);
如果 X?VN,?’ (X)= X
如果 X?VT,?’(X)= Match(X)
如果 X= ?,?(?) = skip(空语句 )
假设有文法
Z → a B a
B → b B | c
则相应的递归子程序可如下：
procedure Z( )
begin
if token=a then Match(a)；
B；
Match(a)
else err( )
end;
procedure B ( )
begin
if token = b then Match(b);
B;
else
if token = c
then Match(c);
else err( )
end;
主程序,Begin ReadToken; Z end
ReadToken
ReadToken
?递归子程序方法的条件：
(1)predict(A→ ?k)? predict(A→ ?j )=?,当 k ? j
(2)任一非终极符 A都不是左递归的 。
?产生式 A→ ?被选择的条件是：
当前的输入符属于 predict(A→ ?)。
?至多一个产生式被选择的条件是：
predict(A→ ?k) ? predict(A→ ?j )=?,当 k ? j
文法的等价变换
? 某个非终极符 A有如下的两个产生式：
A→ ??,A→ ?? (即有左公共前缀 )
? 某个非终极符 A有直接左递归产生式：
A→ A ? |,.....
? 消除左公共前缀
? 消除左递归
消除公共前缀
? 变换步骤：
1.产生式形如,A???1|??2|… |??n| ?
?表示不以 ?开头的字符串。
2.引进非终极符 A’,使产生式替换为：
A ? ? A? | ?
A? ? ?1|?2 |… | ?n
Stm → id,= Exp
Stm → id (ExpL)
ExpL → Exp
ExpL → Exp,ExpL
Stm → id Stm?
Stm? →,= Exp
Stm? → ( ExpL )
ExpL → Exp ExpL?
ExpL? →,Exp ExpL?
ExpL? → ?
?
消除公共前缀的例子
消除公共前缀的例子 2
?A ?ad
?A ?Bc
?B ?aA
?B ?bB
?A ?ad
?A ?aAc
?A ?bBc
?B ?aA
?B ?bB
?A?a(d|Ac)
?A ?bBc
?B ?aA
?B ?bB
?A ?aA?
?A? ?d
?A? ? Ac
A ?bBc
B ?aA
B ?bB
替换
?
提因子
?
引进 A’?
左递归
? 一个文法含有下列形式的产生式时
? （ 1） A?A? A?VN,? ?V*
? （ 2） A?B?
? B?A? A,B?VN,?,? ?V*
? 其中（ 1）为 直接左递归,（ 2）为 间接左递
归,因此文法中只要有 A?+A…,则称文法
为左递归的。
消除左递归
? 对直接左递归形如：
A ? A? | ?
消除左递归为：
A ? ? A?
A? ? ? A? | ?
消除左递归
? 间接左递归形如：
A ? B? | ?
B ? A? | b
消除左递归：
转为直接左递归形式：
A ? A ? ? | b? | ? 或者
B ? B ? ? | ? ? | b
按照直接左递归方式消除。去掉多余的
产生式
例,[1] A → B ?1 | a
[2] B → C ?2 | b
[3] C → A ?3 | c
A? B ?1 ? C ?2 ?1 ? A ?3 ?2 ?1
[3]? C →( B ?1| a ) ?3 | c
[3]? C → C ?2 ?1 ?3 |b ?1 ?3 |a ?3 |c
[4] C → (b ?1 ?3 | a ?3 | c ) C?
[5] C? → ?2 ?1 ?3 C? | ?
[1],[2],[4],[5]与原文法等价
? 作业
写出下面文法 G[p]的递归下降语法分析
程序,
P ? begin SL end
SL ? S | SL;S
S ? i | i:= E | i,S
| if E then S
| while E do S
E ? i | (E) | E + E
