第二节 自顶向下语法分析
?语法分析, 自上而下 (自顶而下 )
自下而上 (自底而上 )
?自顶向下语法分析法,或从开始符号出发,
找最左推导 ;或从根开始,构造推导树 。
一, 回溯分析法
1.一个实例
S→xAy
A→ab│a
输入串为 xay,说明分析过程
S
x A y
S
x A y
a b
S
x A y
a
2.存在的问题
(1)回溯 —— 公共左因子的存在
A→ ??1| ??2
(2)左递归
A→Aα 或 A?Aα +
二, 无回溯的递归下降分析法
1,提取公共左因子
A→ ??1| ??2|,.,|??n| δ
改写为,A→αB|δ
B→ ?1| ?2|,.,|?n
2.左递归的消除
(1)直接左递归的消除
P→Pα│β
改写为,P→ ?P＇
P＇ → αP＇ │ε
一般地 A→A ?1|A?2|… |A?m|?1|?2|… |?n
（ ?i?ε,?j不以 A开头 ）
改写为,P→ ?1P’│ ?2P’│.,,│ ?nP’
P’ → ?1P’│?2P’│.,,│?mP’│ε
(2)间接左递归的消除
P?Pα
(a)将文法 G的所有非终结符按任一给定的顺序排列,设为
A1,A2,… An;
+
(b)消除可能的左递归 ;
for i:=1 to n do
begin
for j:=1 to i-1 do
把一个形如 Ai?Aj?的产生式改写为
Ai??1?|?2?|…| ?k?
其中 Aj??1|?2|…| ?k是 Aj的所有产生式 ;
消除 Ai产生式的直接左递归
end
(c)化简
以 S→Qc│c
Q→Rb│b
R→Sa│a
为例,按 S,Q,R排列,或 R,Q,S排列
?按 S,Q,R排列,代入后
S→Qc│c
Q→Rb│b
R→ Rbca│bca│ca│a
?消除 R中的直接左递归
R→ bcaR’│caR’│aR’
R’→ bcaR’│ ?
?文法产生的语言,(bca|ca|a)(bca)*bc|bc|c
?按 R,Q,S排列,代入后
R→Sa│a
Q→Sab│ab│b
S→Sabc│abc │bc│c
?消除 S中的直接左递归
S→abcS’│bcS’│cS’
S’→abcS’│ ?
?文法产生的语言,(abc|bc|c)(abc)*
3,递归下降分析器的构造
当改造文法为无公共左因子,无左递归时,
让每个非终结符对应一个过程 ;该过程对
相应的非终结符产生式的右部短语进行
语法分析
例, G(E) E→E+T│T
T→T*F│F
F→(E) │i
?消除左递归, E→T│E’
E’→+TE’│ε
T→FT’
T’→*FT’│ε
F→(E)│i
?过程 match:匹配单词符号,并读入下一符号
?变量 lookahead:即将处理但尚未处理的符号
procedure match(t:token);
begin
if lookahead=t then lookahead=nexttoken
else error
end;
procedure E;
begin
T;
E’
end;
procedure T;
begin
F;
T’
end;
procedure E’;
if lookahead=‘+’ then begin match(‘+’);
T;
E’
end;
procedure T’;
if lookahead=‘*’ then begin match(‘*’);
F;
T’
end;
procedure F;
if lookahead=‘i’ then match(‘i’)
else if lookahead=‘(’ then
begin
match(‘(’);
E;
if lookahead=‘)’ then match(‘)’)
else error
end;
4,文法的另一种表示及应用,
(1)表示形式,
?用花括号 {α}表示闭包运算 α* ;
?用 {α} 表示 α可任意重复 0次至 n次
{α} =α0=ε;
?用方括号表示 {α},即表示 α的出现可有可
无 (等价于 α│ε)
n
0
0
0 1
0
例, 实数可定义为
decimal→ [sign]integer.{digit}[exponent]
exponent→E[sign]integer
integer→digit{digit}
sign→+│ -
(2)左递归的消除
p→x│y│,..,.│z│pv
改写成, p→(x│y│,,.,│z){v}
(3)文法的转换图表示
因产生式右端是一个正则式,故可用
转换图表示 。
如, E→T{+T} 表示成
0 1 2 T ?
+
?
(4)递归下降分析器的改进
procedure E;
begin T;
while lookahead=’+’ do
begin match(‘+’);
T
end
end;
procedure T;
begin F;
while lookahead=’*’ do
begin match(‘*’);
F
end
end;
procedure F;
if lookahead=‘i’ then match(‘i’)
else if lookahead=‘(’ then
begin
match(‘(’);
E;
if lookahead=‘)’ then match(‘)’)
else error
end;
三, 预测分析程序
? 构成,下推栈,预测分析表,控制程序,输入串
1,预测分析表
?形式,M[A,a]矩阵,A?VN,a ?VT?{$}
?内容,A→α 或出错标志 (空白 )
预测分析表
E
E’
T
T’
F
i + * ( ) $
E→TE’ E→TE’
E’→+TE’
T→FT’ T→FT’
T’→*FT’
F→i F→(E)
E’→ε E’→ε
T’→ε T’→ε T’→ε
2,分析方法
初始时,$和开始符入栈,输入指针指
向第一个符号,然后根据下推栈栈顶
符 x和当前输入符 a进行工作,
① x=a=$,成功
② x=a?$,匹配
③ x?VN,查表
例,i+i*i的分析过程
下推栈 输入串 查分析表
i+i*i$ $E
$E’T
$E’T’F
$E’T’
$E’T’i
$E’
$E’T
$E’T+
i+i*i$
+i*i$
i+i*i$
i+i*i$
+i*i$
+i*i$
i*i$
E→TE’
T→FT’
T→FT’
F→i
T’→ε
E’→+TE’
$E’T’F
i*i$ $E’T’i
$E’T’
$E’T’F*
$E’T’i
$E’T’F
$E’T’
$
$E’
*i$
i$
*i$
i$
$
$
$
T’→*FT’
结束
F→i
T’→ε
i*i$ F→i
E’→ε
?语法分析, 自上而下 (自顶而下 )
自下而上 (自底而上 )
?自顶向下语法分析法,或从开始符号出发,
找最左推导 ;或从根开始,构造推导树 。
一, 回溯分析法
1.一个实例
S→xAy
A→ab│a
输入串为 xay,说明分析过程
S
x A y
S
x A y
a b
S
x A y
a
2.存在的问题
(1)回溯 —— 公共左因子的存在
A→ ??1| ??2
(2)左递归
A→Aα 或 A?Aα +
二, 无回溯的递归下降分析法
1,提取公共左因子
A→ ??1| ??2|,.,|??n| δ
改写为,A→αB|δ
B→ ?1| ?2|,.,|?n
2.左递归的消除
(1)直接左递归的消除
P→Pα│β
改写为,P→ ?P＇
P＇ → αP＇ │ε
一般地 A→A ?1|A?2|… |A?m|?1|?2|… |?n
（ ?i?ε,?j不以 A开头 ）
改写为,P→ ?1P’│ ?2P’│.,,│ ?nP’
P’ → ?1P’│?2P’│.,,│?mP’│ε
(2)间接左递归的消除
P?Pα
(a)将文法 G的所有非终结符按任一给定的顺序排列,设为
A1,A2,… An;
+
(b)消除可能的左递归 ;
for i:=1 to n do
begin
for j:=1 to i-1 do
把一个形如 Ai?Aj?的产生式改写为
Ai??1?|?2?|…| ?k?
其中 Aj??1|?2|…| ?k是 Aj的所有产生式 ;
消除 Ai产生式的直接左递归
end
(c)化简
以 S→Qc│c
Q→Rb│b
R→Sa│a
为例,按 S,Q,R排列,或 R,Q,S排列
?按 S,Q,R排列,代入后
S→Qc│c
Q→Rb│b
R→ Rbca│bca│ca│a
?消除 R中的直接左递归
R→ bcaR’│caR’│aR’
R’→ bcaR’│ ?
?文法产生的语言,(bca|ca|a)(bca)*bc|bc|c
?按 R,Q,S排列,代入后
R→Sa│a
Q→Sab│ab│b
S→Sabc│abc │bc│c
?消除 S中的直接左递归
S→abcS’│bcS’│cS’
S’→abcS’│ ?
?文法产生的语言,(abc|bc|c)(abc)*
3,递归下降分析器的构造
当改造文法为无公共左因子,无左递归时,
让每个非终结符对应一个过程 ;该过程对
相应的非终结符产生式的右部短语进行
语法分析
例, G(E) E→E+T│T
T→T*F│F
F→(E) │i
?消除左递归, E→T│E’
E’→+TE’│ε
T→FT’
T’→*FT’│ε
F→(E)│i
?过程 match:匹配单词符号,并读入下一符号
?变量 lookahead:即将处理但尚未处理的符号
procedure match(t:token);
begin
if lookahead=t then lookahead=nexttoken
else error
end;
procedure E;
begin
T;
E’
end;
procedure T;
begin
F;
T’
end;
procedure E’;
if lookahead=‘+’ then begin match(‘+’);
T;
E’
end;
procedure T’;
if lookahead=‘*’ then begin match(‘*’);
F;
T’
end;
procedure F;
if lookahead=‘i’ then match(‘i’)
else if lookahead=‘(’ then
begin
match(‘(’);
E;
if lookahead=‘)’ then match(‘)’)
else error
end;
4,文法的另一种表示及应用,
(1)表示形式,
?用花括号 {α}表示闭包运算 α* ;
?用 {α} 表示 α可任意重复 0次至 n次
{α} =α0=ε;
?用方括号表示 {α},即表示 α的出现可有可
无 (等价于 α│ε)
n
0
0
0 1
0
例, 实数可定义为
decimal→ [sign]integer.{digit}[exponent]
exponent→E[sign]integer
integer→digit{digit}
sign→+│ -
(2)左递归的消除
p→x│y│,..,.│z│pv
改写成, p→(x│y│,,.,│z){v}
(3)文法的转换图表示
因产生式右端是一个正则式,故可用
转换图表示 。
如, E→T{+T} 表示成
0 1 2 T ?
+
?
(4)递归下降分析器的改进
procedure E;
begin T;
while lookahead=’+’ do
begin match(‘+’);
T
end
end;
procedure T;
begin F;
while lookahead=’*’ do
begin match(‘*’);
F
end
end;
procedure F;
if lookahead=‘i’ then match(‘i’)
else if lookahead=‘(’ then
begin
match(‘(’);
E;
if lookahead=‘)’ then match(‘)’)
else error
end;
三, 预测分析程序
? 构成,下推栈,预测分析表,控制程序,输入串
1,预测分析表
?形式,M[A,a]矩阵,A?VN,a ?VT?{$}
?内容,A→α 或出错标志 (空白 )
预测分析表
E
E’
T
T’
F
i + * ( ) $
E→TE’ E→TE’
E’→+TE’
T→FT’ T→FT’
T’→*FT’
F→i F→(E)
E’→ε E’→ε
T’→ε T’→ε T’→ε
2,分析方法
初始时,$和开始符入栈,输入指针指
向第一个符号,然后根据下推栈栈顶
符 x和当前输入符 a进行工作,
① x=a=$,成功
② x=a?$,匹配
③ x?VN,查表
例,i+i*i的分析过程
下推栈 输入串 查分析表
i+i*i$ $E
$E’T
$E’T’F
$E’T’
$E’T’i
$E’
$E’T
$E’T+
i+i*i$
+i*i$
i+i*i$
i+i*i$
+i*i$
+i*i$
i*i$
E→TE’
T→FT’
T→FT’
F→i
T’→ε
E’→+TE’
$E’T’F
i*i$ $E’T’i
$E’T’
$E’T’F*
$E’T’i
$E’T’F
$E’T’
$
$E’
*i$
i$
*i$
i$
$
$
$
T’→*FT’
结束
F→i
T’→ε
i*i$ F→i
E’→ε
