2.4 语法分析 — 自上而下分析本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。
采用正规式和有限自动机可以描述和识别语言的单词符号；
用上下文无关文法来描述语法规则。
2.4.1 语法分析器的功能语法分析的任务是分析一个文法的句子结构。
语法分析器的功能：按照文法的产生式
(语言的语法规则 )，识别输入符号串是否为一个句子 (合式程序 )。
源程序单词符号取下一单词
...
语法分析树词法分析器语法分析器符号表编译程序后续部分
*S?
},|{)( *TV SGL
定义：假定 G是一个文法,S 是它的开始符号。
如果,则?称是一个 句型 。仅含终结符号的句型是一个 句子 。文法 G所产生的句子的全体是一个 语言,将它记为 L(G)。
语法分析的方法：
自下而上分析法 (Bottom-up)
基本思想：从输入串开始，逐步进行,归约,,
直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，
把产生式的右部替换成左部符号。
算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。
LR分析法：一种更一般的自下而上分析法
G(E),E? i| E+E | E-E | E*E | E/E | (E)
i*i+i
E*i+i
E*E+i
E+i
E+E
E
i
+
*
E
i
i
E
E E
E
自上而下分析法 (Top-down)
基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找 "匹配 "的推导。
递归下降分析法：对每一语法变量 (非终结符 )
构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。
预测分析程序
优点：直观、简单和宜于手工实现。
2.4.2 自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。
带,回溯,的
不带回溯的递归子程序 (递归下降 )分析方法。
自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号 (根结点 )出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。
例 3.4.1 假定有文法 G(S):
(1) S→xAy
(2) A→**|*
分析 输入串 x*y(记为?)。
Sx*y
IP Ax y
Sx*y
IP x
**
IP
*
当某个非终结符有多个产生式候选时，可能带来如下问题,
1,回溯 问题分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的 。 出错 时,不得不,回溯,。
2,文法左递归问题 。
一个文法是含有左递归的，如果存在非终结符 P
P P
含有左递归的文法将使自上而下的分析陷入无限循环。
2.4.3 LL(1)分析法构造不带回溯的自上而下分析算法
要消除文法的左递归性
克服回溯
2.4.3.1 左递归的消除消除直接左递归
假定关于非终结符 P的规则为
P→P? |?
其中?不以 P开头。
则可以把规则等价地改写为如下的非直接左递归形式：
P→?P?
P?→?P?|?
一般而言，假定 P关于的全部产生式是
P→P?1 | P?2 | … | P?m |?1 |?2|… |?n
其中，每个?都不等于?，而每个?都不以 P
开头那么，消除 P的直接左递归性就是把这些规则改写成：
P→?1P?|?2P?| … |?nP?
P?→?1P?|?2P? |… |?mP? |?
例 文法 G(E):
E→E ＋ T | T
T→T*F | F
F→(E) | i
经消去直接左递归后变成：
E→TE?
E?→+TE?|?
T→FT?
T?→*FT?|?
F→(E) | i (4.2)
例如文法 G(S):
S→Qc|c
Q→Rb|b
R→Sa|a (4.3)
虽没有直接左递归，但 S,Q,R都是左递归的
S?Qc?Rbc?Sabc
一个文法消除左递归的条件：
不含回路。
PP
消除左递归的算法,
1,把文法 G的所有非终结符按任一种顺序排列成 P1,P2,…,Pn；按此顺序执行；
2,FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如 Pi→P j?的规则改写成
Pi→?1?|?2?|… |?k? ;
(其中 Pj→?1|?2|… |?k是关于 Pj的所有规则 )
消除关于 Pi规则的直接左递归性
END
3,化简由 2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。
例 考虑文法 G(S)
S→Qc|c
Q→Rb|b
R→Sa|a
令它的非终结符的排序为 R,Q,S。
对于 R，不存在直接左递归。
把 R代入到 Q的有关候选后，把 Q的规则变为
Q→Sab | ab | b
现在的 Q不含直接左递归，把它代入到 S
的有关候选后,S变成
S→Sabc | abc | bc | c
消除 S的直接左递归后：
S→abcS?| bcS? | cS?
S?→abcS?|?
Q→Sab |ab | b
R→Sa|a
关于 Q和 R的规则已是多余的，化简为：
S→abcS?| bcS? | cS?
S?→abcS?|? (4.4)
注：对非终结符排序不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。
例如，若对文法 (4.3)的非终结符排序选为 S、
Q,R，那么，最后所得的无左递归文法是
（课堂练习 5分钟）：
S→Qc | c
Q→Rb | b
R→bcaR? | caR? |a R? (4.5)
R?→ bca R? |?
文法 (4.4)和 (4.5)的等价性是显然的。
2.4.3.2 消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。
A→?1 |?2 | … |? n
Sa….
IP A...,..
令 G是一个不含左递归的文法，对 G的所有非终结符的每个候选?定义它的终结首符集 FIRST(?)为：
}...,|{=)( * TVaaaFI R S T
特别是，若,则规定FIRST(?)。? *?
如果非终结符 A的所有候选首符集两两不相交，即 A的任何两个不同候选?i和?j
FIRST(?i)∩ FIRST(?j)＝?
当要求 A匹配输入串时,A就能根据它所面临的第一个输入符号 a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含 a的?。
提取公共左因子,
假定关于 A的规则是
A→1 | 2 | … |n |? 1 |?2 | …? m
(其中，每个?不以?开头 )
那么，可以把这些规则改写成
A→?A? |?1 |? 2 | … |?m
A?→?1 |?2 | … |?n
经过反复提取左因子，就能够把每个非终结符 (包括新引进者 )的所有候选首符集变成为两两不相交。
例：语句序列的文法，
stmt-sequence→stmt;stmt -sequence | stmt
stmt → s
它可按如下提取左因子：
stmt-sequence→stmt stmt -seq’
stmt-seq‘ →;stmt -sequecne|?
提取左公因子举例当一个文法不含左递归,并且满足每个非终结的所有候选首符集两两不相交的条件,是不是就一定能进行有效的自上而下分析了呢？
如果空字?属于某个非终结符的候选首符集,
那么,问题就比较复杂 。
2.4.3.3 LL(1)分析条件
i + i ＃
IP
E
i + i＃
IP
E
T E’
i + i #
IP
E
T E’
F T’
i + i#
IP
E
T E’
F T’
i
i + i #
IP
E
T E’
F T’
i
i + i#
IP
E
T E’
F T’
i?
i + i#
IP
E
T E’
F T’
i?
+ T E’
i + i#
IP
E
T E’
F T’
i?
+ T E’
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i?
i + i#
IP
E
T E’
F T’
i?
+ T E’
F T’
i?
上面用到了,自动匹配,
这是不是意味着,当非终结符 A面临输入符号 a,且 a不属于 A的任意候选首符集但
A的某个候选首符集包含?时,就一定可以使 A自动匹配？ 如果我们仔细来考虑一下的话,就不难发现,只有当 a是允许在文法的某个句型中跟在 A后面的终结符时,
才可能允许 A自动匹配,否则,a在这里的出现就是一种语法错误 。
假定 S是文法 G的开始符号，对于 G的任何非终结符 A，我们定义
}...,...|{)( * TVaAaSaAFO L L O W
AS?*?特别是，若,则规定
＃?FOLLOW(A)
我们可以找出满足构造不带回溯的自上而下分析的文法条件：
1,文法不含左递归，
2,对于文法中每一个非终结符 A的各个产生式的候选首符集两两不相交。即，若
A→?1|?2|…|?n
则 FIRST(?i)∩ FIRST(?j)＝? (i?j)
3,对文法中的每个非终结符 A，若它存在某个候选首符集包含?，则
FIRST(?i)∩ FOLLOW(A)=?
i=1,2,...,n
如果一个文法 G满足以上条件，则称该文法
G为 LL(1)文法 。
对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符 A进行匹配，面临的输入符号为 a,A的所有产生式为
A→?1 |? 2 | … |? n
1,若 a?FIRST(? i)，则指派?i执行匹配任务；
2,若 a不属于任何一个候选首符集，则：
(1) 若?属于某个 FIRST(?i )且 a?FOLLOW(A)，
则让 A与?自动匹配。
(2) 否则,a的出现是一种语法错误。
构造 FIRST(?)
}...,|{=)( * TVaaaFI R S T
对每一文法符号 X?VT∪ VN构造 FIRST(X)
连续使用下面的规则，直至每个集合
FIRST不再增大为止：
1,若 X?VT，则 FIRST(X)＝ {X}。
2,若 X?VN，且有产生式 X→a …,则把 a加入到
FIRST(X)中；若 X→?也是一条产生式，则把?
也加到 FIRST(X)中。
3,
若 X→Y … 是一个产生式且 Y?VN，则把 FIRST(Y)中的所有非?-元素都加到 FIRST(X)中；
若 X→Y 1Y2… Yk是一个产生式,Y1,…,Yi-1都是非终结符，而且，对于任何 j,1?j?i-1,FIRST(Yj)都含有?(即 Y1… Yi-1?),则把 FIRST(Yi)中的所有非?-
元素都加到 FIRST(X)中；特别是，若所有的
FIRST(Yj)均含有?,j＝ 1,2,…,k，则把?加到
FIRST(X)中。
对文法 G的任何符号串?=X1X2… Xn构造集合 FIRST(?)。
1,置 FIRST(?)＝ FIRST(X1)\{?}；
2,若对任何 1?j?i-1,FIRST(Xj)，则把
FIRST(Xi)\{?}加至 FIRST(?)中；特别是，若所有的 FIRST(Xj)均含有?,1?j?n，则把?也加至 FIRST(?)中。显然，若?＝?则 FIRST(?)
＝ {?}。
构造 FOLLOW(A)
}...,...|{)( * TVaAaSaAFO L L O W
对于文法 G的每个非终结符 A构造
FOLLOW(A)的办法是，连续使用下面的规则，直至每个 FOLLOW不再增大为止：
1,对于文法的开始符号 S，置＃于 FOLLOW(S)
中；
2,若 A→?B?是一个产生式，则把 FIRST(?)\{?}
加至 FOLLOW(B)中；
3,若 A→?B是一个产生式，或 AB?是一个产生式而
(即FIRST(?))，
则把 FOLLOW(A)加至 FOLLOW(B)中。
例,对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT?|?
F→(E) | i
构造每个非终结符的 FIRST和 FOLLOW
集合 （板书过程）：
FIRST(E) ={(,i} FOLLOW(E) ={),#}
FIRST(E?)={+,?} FOLLOW(E?)={),#}
FIRST(T) ={(,i} FOLLOW(T) ={+,),#}
FIRST(T?)={*,?} FOLLOW(T?)={+,),#}
FIRST(F) ={(,i} FOLLOW(F) ={*,+,),#}
2.4.4 递归下降分析 程序构造构造不带回溯的自上而下分析程序
要消除文法的左递归性
克服回溯
递归下降分析的基本方法将一个非终结符 A的文法规则看作将识别 A的一个过程的定义。
A的文法规则的右边指出这个过程的代码结构：
终结符对应于一个与当前输入记号相匹配的过程，
非终结符对应过程调用，选择对应于分支语句 (if或
case语句 )，连接对应于语句序列，等等构造不带回溯的自上而下分析器
几个全局过程和变量：
ADVANCE，把输入串指示器 IP指向下一个输入符号，即读入一个单字符号
SYM,IP当前所指的输入符号
ERROR，出错处理子程序每个非终结符有对应的子程序的定义，
在分析过程中，当需要从某个非终结符出发进行展开 (推导 )时，就调用这个非终结符对应的子程序。
例,文法 G(E):
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | i
一般而言
E→T E?| BC|ε
对应的递归下降子程序为,
PROCEDURE E；
BEGIN
IF SYM?FIRST(T E? ) THEN
T； E?
ELSE IF SYM?FIRST(BC) THEN
B; C
ELSE IF not (SYS? FOLLOW(E) )THEN
ERROR
END；
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | I
对应的递归下降子程序为,
PROCEDURE E；
BEGIN
T； E?
END；
PROCEDURE T；
BEGIN
F； T?
END
对应的递归下降子程序为,
PROCEDURE E?；
IF SYM=‘+’ THEN
BEGIN
ADVANCE；
T； E?
END
ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN
ERROR
对应的递归下降子程序为,
PROCEDURE T?；
IF SYM=‘*’ THEN
BEGIN
ADVANCE；
F； T?
END
ELSE IF SYM<>‘#’ AND
SYM<>’)’ AND SYM<>’+’ THEN
ERROR
PROCEDURE F；
IF SYM=‘i’ THEN ADVANCE
ELSE
IF SYM=‘(’ THEN
BEGIN
ADVANCE;
E；
IF SYM=‘)’ THEN ADVANCE
ELSE ERROR
END
ELSE ERROR;
主程序,
PROGRAM PARSER;
BEGIN
ADVANCE;
E
END;
EBNF也可以用于消除左递归、提取左公共因子。
例 4.5 文法
E→T | E+T
T→F | T*F
F→i | (E)
可表示成
E→T{+T}
T→F{*F}
F→i | (E) (4.6)
可构造一组递归下降分析程序：
PROCEDURE E；
BEGIN
T；
WHILE SYM=‘+’ DO
BEGIN
ADVANCE；
T
END
END；
PROCEDURE T；
BEGIN
F；
WHILE SYM=‘*’ DO
BEGIN
ADVANCE；
F
END
END；
PROCEDURE F；
同前，见图 4.2。
2.4.5 预测分析程序一、预测分析程序工作原理预测分析程序或 LL(1)分析法：
总控程序
分析表 M[A,a]矩阵,A? VN,a? VT 是终结符或 ‘ ＃ ’,
分析栈 STACK 用于存放文法符号总控程序分析表 X?
#
输入串分析栈
STACK
a1a2...ai…#
预测分析程序的工作图
# S a1a2...ai…#
分析开始时：
总控程序根据现行栈顶符号 X和当前输入符号 a，执行下列三种动作之一,
1,若 X＝ a＝‘＃’，则宣布分析成功，
停止分析。
2,若 X＝ a?‘＃’，则把 X从 STACK栈顶逐出，让 a指向下一个输入符号。
3,若 X是一个非终结符，则查看分析表 M。
若 M[X,a]中存放着关于 X的一个产生式，
把 X逐出 STACK栈顶，把产生式的右部符号串按反序一一推进 STACK栈 (若右部符号为?
，则意味不推什么东西进栈 )。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。
若 M[X,a]中存放着“出错标志”，则调用出错诊察程序 ERROR。
预测分析程序的总控程序：
BEGIN
首先把 ‘ ＃ ’ 然后把文法开始符号推进 STACK
栈；
把第一个输入符号读进 a；
FLAG:=TRUE;
WHILE FLAG DO
BEGIN
把 STACK栈顶符号上托出去并放在 X中；
IF X?VT THEN
IF X= a THEN 把下一输入符号读进 a
ELSE ERROR
ELSE IF X=‘#’ THEN
IF X=a THEN FLAG:=FALSE
ELSE ERROR
ELSE IF M[A,a]={X→X 1X2… Xk}THEN
把 Xk,Xk-1,…,X1一一推进 STACK栈
/* 若 X1X2… Xk=?，不推什么进栈 */
ELSE ERROR
END OF WHILE;
STOP /*分析成功，过程完毕 */
END
例 4.6 对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | i
输入串为 i1*i2+i3，利用分析表进行预测分析：
i + * ( ) #
E E → TE? E → TE?
E? E? → +TE? E? →? E? →?
T T → FT? T → FT?
T? T? →? T? → *F T? T? →? T? →?
F F → i F → ( E)
步骤 符号栈 输入串 所用产生式
0 #E i1*i2+i3#
1 #E?T i1*i2+i3# E→TE?
2 #E?T?F i1*i2+i3# T→FT?
3 #E?T?i i1*i2+i3# F→i
4 #E?T? *i2+i3#
5 #E?T?F* *i2+i3# T?→*FT?
6 #E?T?F i2+i3#
7 #E?T?i i2+i3# F→i
步骤 符号栈 输入串 所用产生
8 #E?T? +i3#
9 #E? +i3# T?→?
10 #E?T+ +i3# E?→+TE?
11 #E?T i3#
12 #E?T?F i3# T→FT?
13 #E?T?i i3# F→i
14 #E?T? #
15 #E? # T?→?
16 # # E?→?
二、分析表 M[A,a]的构造
构造 FIRST(?)和 FOLLOW(A)
构造分析表 M[A,a]
例 4.6 对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT?|?
F→(E) | i
构造每个非终结符的 FIRST和 FOLLOW集合：
FIRST(E) ={(,i} FOLLOW(E) ={),#}
FIRST(E?)={+,?} FOLLOW(E?)={),#}
FIRST(T) ={(,i} FOLLOW(T) ={+,),#}
FIRST(T?)={*,?} FOLLOW(T?)={+,),#}
FIRST(F) ={(,i} FOLLOW(F) ={*,+,),#}
在对文法 G的每个非终结符 A及其任意候选
都构造出 FIRST(?)和 FOLLOW(A)之后，
现在可以用它们来构造 G的分析表 M[A,a]。
1,对文法 G的每个产生式 A→?执行第 2步和第 3步；
2,对每个终结符 a?FIRST(?)，把 A→?加至 M[A，
a]中；
3,若FIRST(?)，则对任何 b?FOLLOW(A)把
A→?加至 M[A,b]中。
4,把所有无定义的 M[A,a]标上,出错标志,。
i + * ( ) #
E E → TE? E → TE?
E? E? → +TE? E? →? E? →?
T T → FT? T → FT?
T? T? →? T? → *F T? T? →? T? →?
F F → i F → ( E)
如果 G是左递归或二义的，那么,M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表 M。
可以证明，一个文法 G的预测分析表 M不含多重定义入口，当且仅当该文法为
LL(1)的。
一个文法 G为 LL(1)的，当且仅当对于文法 G中每一个非终结符 A的任何两个产生式 A→?|?，
下面的条件成立：
1,FIRST(?)∩ FIRST(?)＝?
2,若 (即FIRST(?))，
则 FIRST(?)∩ FOLLOW(A)=? 。
If语句文法 G(S):
S? iCtS | iCtSeS | a
C? b
提取左因子之后，改写成：
G(S):
S?iCtSS’ | a
S’?eS |?
C? b
a b e i t #
S S → a S → iCt SS?
S? S?→?
S?→ eS
S?→?
C C → b
采用正规式和有限自动机可以描述和识别语言的单词符号；
用上下文无关文法来描述语法规则。
2.4.1 语法分析器的功能语法分析的任务是分析一个文法的句子结构。
语法分析器的功能：按照文法的产生式
(语言的语法规则 )，识别输入符号串是否为一个句子 (合式程序 )。
源程序单词符号取下一单词
...
语法分析树词法分析器语法分析器符号表编译程序后续部分
*S?
},|{)( *TV SGL
定义：假定 G是一个文法,S 是它的开始符号。
如果,则?称是一个 句型 。仅含终结符号的句型是一个 句子 。文法 G所产生的句子的全体是一个 语言,将它记为 L(G)。
语法分析的方法：
自下而上分析法 (Bottom-up)
基本思想：从输入串开始，逐步进行,归约,,
直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，
把产生式的右部替换成左部符号。
算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。
LR分析法：一种更一般的自下而上分析法
G(E),E? i| E+E | E-E | E*E | E/E | (E)
i*i+i
E*i+i
E*E+i
E+i
E+E
E
i
+
*
E
i
i
E
E E
E
自上而下分析法 (Top-down)
基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找 "匹配 "的推导。
递归下降分析法：对每一语法变量 (非终结符 )
构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。
预测分析程序
优点：直观、简单和宜于手工实现。
2.4.2 自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。
带,回溯,的
不带回溯的递归子程序 (递归下降 )分析方法。
自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号 (根结点 )出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。
例 3.4.1 假定有文法 G(S):
(1) S→xAy
(2) A→**|*
分析 输入串 x*y(记为?)。
Sx*y
IP Ax y
Sx*y
IP x
**
IP
*
当某个非终结符有多个产生式候选时，可能带来如下问题,
1,回溯 问题分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的 。 出错 时,不得不,回溯,。
2,文法左递归问题 。
一个文法是含有左递归的，如果存在非终结符 P
P P
含有左递归的文法将使自上而下的分析陷入无限循环。
2.4.3 LL(1)分析法构造不带回溯的自上而下分析算法
要消除文法的左递归性
克服回溯
2.4.3.1 左递归的消除消除直接左递归
假定关于非终结符 P的规则为
P→P? |?
其中?不以 P开头。
则可以把规则等价地改写为如下的非直接左递归形式：
P→?P?
P?→?P?|?
一般而言，假定 P关于的全部产生式是
P→P?1 | P?2 | … | P?m |?1 |?2|… |?n
其中，每个?都不等于?，而每个?都不以 P
开头那么，消除 P的直接左递归性就是把这些规则改写成：
P→?1P?|?2P?| … |?nP?
P?→?1P?|?2P? |… |?mP? |?
例 文法 G(E):
E→E ＋ T | T
T→T*F | F
F→(E) | i
经消去直接左递归后变成：
E→TE?
E?→+TE?|?
T→FT?
T?→*FT?|?
F→(E) | i (4.2)
例如文法 G(S):
S→Qc|c
Q→Rb|b
R→Sa|a (4.3)
虽没有直接左递归，但 S,Q,R都是左递归的
S?Qc?Rbc?Sabc
一个文法消除左递归的条件：
不含回路。
PP
消除左递归的算法,
1,把文法 G的所有非终结符按任一种顺序排列成 P1,P2,…,Pn；按此顺序执行；
2,FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如 Pi→P j?的规则改写成
Pi→?1?|?2?|… |?k? ;
(其中 Pj→?1|?2|… |?k是关于 Pj的所有规则 )
消除关于 Pi规则的直接左递归性
END
3,化简由 2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。
例 考虑文法 G(S)
S→Qc|c
Q→Rb|b
R→Sa|a
令它的非终结符的排序为 R,Q,S。
对于 R，不存在直接左递归。
把 R代入到 Q的有关候选后，把 Q的规则变为
Q→Sab | ab | b
现在的 Q不含直接左递归，把它代入到 S
的有关候选后,S变成
S→Sabc | abc | bc | c
消除 S的直接左递归后：
S→abcS?| bcS? | cS?
S?→abcS?|?
Q→Sab |ab | b
R→Sa|a
关于 Q和 R的规则已是多余的，化简为：
S→abcS?| bcS? | cS?
S?→abcS?|? (4.4)
注：对非终结符排序不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。
例如，若对文法 (4.3)的非终结符排序选为 S、
Q,R，那么，最后所得的无左递归文法是
（课堂练习 5分钟）：
S→Qc | c
Q→Rb | b
R→bcaR? | caR? |a R? (4.5)
R?→ bca R? |?
文法 (4.4)和 (4.5)的等价性是显然的。
2.4.3.2 消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。
A→?1 |?2 | … |? n
Sa….
IP A...,..
令 G是一个不含左递归的文法，对 G的所有非终结符的每个候选?定义它的终结首符集 FIRST(?)为：
}...,|{=)( * TVaaaFI R S T
特别是，若,则规定FIRST(?)。? *?
如果非终结符 A的所有候选首符集两两不相交，即 A的任何两个不同候选?i和?j
FIRST(?i)∩ FIRST(?j)＝?
当要求 A匹配输入串时,A就能根据它所面临的第一个输入符号 a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含 a的?。
提取公共左因子,
假定关于 A的规则是
A→1 | 2 | … |n |? 1 |?2 | …? m
(其中，每个?不以?开头 )
那么，可以把这些规则改写成
A→?A? |?1 |? 2 | … |?m
A?→?1 |?2 | … |?n
经过反复提取左因子，就能够把每个非终结符 (包括新引进者 )的所有候选首符集变成为两两不相交。
例：语句序列的文法，
stmt-sequence→stmt;stmt -sequence | stmt
stmt → s
它可按如下提取左因子：
stmt-sequence→stmt stmt -seq’
stmt-seq‘ →;stmt -sequecne|?
提取左公因子举例当一个文法不含左递归,并且满足每个非终结的所有候选首符集两两不相交的条件,是不是就一定能进行有效的自上而下分析了呢？
如果空字?属于某个非终结符的候选首符集,
那么,问题就比较复杂 。
2.4.3.3 LL(1)分析条件
i + i ＃
IP
E
i + i＃
IP
E
T E’
i + i #
IP
E
T E’
F T’
i + i#
IP
E
T E’
F T’
i
i + i #
IP
E
T E’
F T’
i
i + i#
IP
E
T E’
F T’
i?
i + i#
IP
E
T E’
F T’
i?
+ T E’
i + i#
IP
E
T E’
F T’
i?
+ T E’
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i
i + i #
IP
E
T E’
F T’
i?
+ T E’
F T’
i?
i + i#
IP
E
T E’
F T’
i?
+ T E’
F T’
i?
上面用到了,自动匹配,
这是不是意味着,当非终结符 A面临输入符号 a,且 a不属于 A的任意候选首符集但
A的某个候选首符集包含?时,就一定可以使 A自动匹配？ 如果我们仔细来考虑一下的话,就不难发现,只有当 a是允许在文法的某个句型中跟在 A后面的终结符时,
才可能允许 A自动匹配,否则,a在这里的出现就是一种语法错误 。
假定 S是文法 G的开始符号，对于 G的任何非终结符 A，我们定义
}...,...|{)( * TVaAaSaAFO L L O W
AS?*?特别是，若,则规定
＃?FOLLOW(A)
我们可以找出满足构造不带回溯的自上而下分析的文法条件：
1,文法不含左递归，
2,对于文法中每一个非终结符 A的各个产生式的候选首符集两两不相交。即，若
A→?1|?2|…|?n
则 FIRST(?i)∩ FIRST(?j)＝? (i?j)
3,对文法中的每个非终结符 A，若它存在某个候选首符集包含?，则
FIRST(?i)∩ FOLLOW(A)=?
i=1,2,...,n
如果一个文法 G满足以上条件，则称该文法
G为 LL(1)文法 。
对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符 A进行匹配，面临的输入符号为 a,A的所有产生式为
A→?1 |? 2 | … |? n
1,若 a?FIRST(? i)，则指派?i执行匹配任务；
2,若 a不属于任何一个候选首符集，则：
(1) 若?属于某个 FIRST(?i )且 a?FOLLOW(A)，
则让 A与?自动匹配。
(2) 否则,a的出现是一种语法错误。
构造 FIRST(?)
}...,|{=)( * TVaaaFI R S T
对每一文法符号 X?VT∪ VN构造 FIRST(X)
连续使用下面的规则，直至每个集合
FIRST不再增大为止：
1,若 X?VT，则 FIRST(X)＝ {X}。
2,若 X?VN，且有产生式 X→a …,则把 a加入到
FIRST(X)中；若 X→?也是一条产生式，则把?
也加到 FIRST(X)中。
3,
若 X→Y … 是一个产生式且 Y?VN，则把 FIRST(Y)中的所有非?-元素都加到 FIRST(X)中；
若 X→Y 1Y2… Yk是一个产生式,Y1,…,Yi-1都是非终结符，而且，对于任何 j,1?j?i-1,FIRST(Yj)都含有?(即 Y1… Yi-1?),则把 FIRST(Yi)中的所有非?-
元素都加到 FIRST(X)中；特别是，若所有的
FIRST(Yj)均含有?,j＝ 1,2,…,k，则把?加到
FIRST(X)中。
对文法 G的任何符号串?=X1X2… Xn构造集合 FIRST(?)。
1,置 FIRST(?)＝ FIRST(X1)\{?}；
2,若对任何 1?j?i-1,FIRST(Xj)，则把
FIRST(Xi)\{?}加至 FIRST(?)中；特别是，若所有的 FIRST(Xj)均含有?,1?j?n，则把?也加至 FIRST(?)中。显然，若?＝?则 FIRST(?)
＝ {?}。
构造 FOLLOW(A)
}...,...|{)( * TVaAaSaAFO L L O W
对于文法 G的每个非终结符 A构造
FOLLOW(A)的办法是，连续使用下面的规则，直至每个 FOLLOW不再增大为止：
1,对于文法的开始符号 S，置＃于 FOLLOW(S)
中；
2,若 A→?B?是一个产生式，则把 FIRST(?)\{?}
加至 FOLLOW(B)中；
3,若 A→?B是一个产生式，或 AB?是一个产生式而
(即FIRST(?))，
则把 FOLLOW(A)加至 FOLLOW(B)中。
例,对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT?|?
F→(E) | i
构造每个非终结符的 FIRST和 FOLLOW
集合 （板书过程）：
FIRST(E) ={(,i} FOLLOW(E) ={),#}
FIRST(E?)={+,?} FOLLOW(E?)={),#}
FIRST(T) ={(,i} FOLLOW(T) ={+,),#}
FIRST(T?)={*,?} FOLLOW(T?)={+,),#}
FIRST(F) ={(,i} FOLLOW(F) ={*,+,),#}
2.4.4 递归下降分析 程序构造构造不带回溯的自上而下分析程序
要消除文法的左递归性
克服回溯
递归下降分析的基本方法将一个非终结符 A的文法规则看作将识别 A的一个过程的定义。
A的文法规则的右边指出这个过程的代码结构：
终结符对应于一个与当前输入记号相匹配的过程，
非终结符对应过程调用，选择对应于分支语句 (if或
case语句 )，连接对应于语句序列，等等构造不带回溯的自上而下分析器
几个全局过程和变量：
ADVANCE，把输入串指示器 IP指向下一个输入符号，即读入一个单字符号
SYM,IP当前所指的输入符号
ERROR，出错处理子程序每个非终结符有对应的子程序的定义，
在分析过程中，当需要从某个非终结符出发进行展开 (推导 )时，就调用这个非终结符对应的子程序。
例,文法 G(E):
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | i
一般而言
E→T E?| BC|ε
对应的递归下降子程序为,
PROCEDURE E；
BEGIN
IF SYM?FIRST(T E? ) THEN
T； E?
ELSE IF SYM?FIRST(BC) THEN
B; C
ELSE IF not (SYS? FOLLOW(E) )THEN
ERROR
END；
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | I
对应的递归下降子程序为,
PROCEDURE E；
BEGIN
T； E?
END；
PROCEDURE T；
BEGIN
F； T?
END
对应的递归下降子程序为,
PROCEDURE E?；
IF SYM=‘+’ THEN
BEGIN
ADVANCE；
T； E?
END
ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN
ERROR
对应的递归下降子程序为,
PROCEDURE T?；
IF SYM=‘*’ THEN
BEGIN
ADVANCE；
F； T?
END
ELSE IF SYM<>‘#’ AND
SYM<>’)’ AND SYM<>’+’ THEN
ERROR
PROCEDURE F；
IF SYM=‘i’ THEN ADVANCE
ELSE
IF SYM=‘(’ THEN
BEGIN
ADVANCE;
E；
IF SYM=‘)’ THEN ADVANCE
ELSE ERROR
END
ELSE ERROR;
主程序,
PROGRAM PARSER;
BEGIN
ADVANCE;
E
END;
EBNF也可以用于消除左递归、提取左公共因子。
例 4.5 文法
E→T | E+T
T→F | T*F
F→i | (E)
可表示成
E→T{+T}
T→F{*F}
F→i | (E) (4.6)
可构造一组递归下降分析程序：
PROCEDURE E；
BEGIN
T；
WHILE SYM=‘+’ DO
BEGIN
ADVANCE；
T
END
END；
PROCEDURE T；
BEGIN
F；
WHILE SYM=‘*’ DO
BEGIN
ADVANCE；
F
END
END；
PROCEDURE F；
同前，见图 4.2。
2.4.5 预测分析程序一、预测分析程序工作原理预测分析程序或 LL(1)分析法：
总控程序
分析表 M[A,a]矩阵,A? VN,a? VT 是终结符或 ‘ ＃ ’,
分析栈 STACK 用于存放文法符号总控程序分析表 X?
#
输入串分析栈
STACK
a1a2...ai…#
预测分析程序的工作图
# S a1a2...ai…#
分析开始时：
总控程序根据现行栈顶符号 X和当前输入符号 a，执行下列三种动作之一,
1,若 X＝ a＝‘＃’，则宣布分析成功，
停止分析。
2,若 X＝ a?‘＃’，则把 X从 STACK栈顶逐出，让 a指向下一个输入符号。
3,若 X是一个非终结符，则查看分析表 M。
若 M[X,a]中存放着关于 X的一个产生式，
把 X逐出 STACK栈顶，把产生式的右部符号串按反序一一推进 STACK栈 (若右部符号为?
，则意味不推什么东西进栈 )。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。
若 M[X,a]中存放着“出错标志”，则调用出错诊察程序 ERROR。
预测分析程序的总控程序：
BEGIN
首先把 ‘ ＃ ’ 然后把文法开始符号推进 STACK
栈；
把第一个输入符号读进 a；
FLAG:=TRUE;
WHILE FLAG DO
BEGIN
把 STACK栈顶符号上托出去并放在 X中；
IF X?VT THEN
IF X= a THEN 把下一输入符号读进 a
ELSE ERROR
ELSE IF X=‘#’ THEN
IF X=a THEN FLAG:=FALSE
ELSE ERROR
ELSE IF M[A,a]={X→X 1X2… Xk}THEN
把 Xk,Xk-1,…,X1一一推进 STACK栈
/* 若 X1X2… Xk=?，不推什么进栈 */
ELSE ERROR
END OF WHILE;
STOP /*分析成功，过程完毕 */
END
例 4.6 对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT? |?
F→(E) | i
输入串为 i1*i2+i3，利用分析表进行预测分析：
i + * ( ) #
E E → TE? E → TE?
E? E? → +TE? E? →? E? →?
T T → FT? T → FT?
T? T? →? T? → *F T? T? →? T? →?
F F → i F → ( E)
步骤 符号栈 输入串 所用产生式
0 #E i1*i2+i3#
1 #E?T i1*i2+i3# E→TE?
2 #E?T?F i1*i2+i3# T→FT?
3 #E?T?i i1*i2+i3# F→i
4 #E?T? *i2+i3#
5 #E?T?F* *i2+i3# T?→*FT?
6 #E?T?F i2+i3#
7 #E?T?i i2+i3# F→i
步骤 符号栈 输入串 所用产生
8 #E?T? +i3#
9 #E? +i3# T?→?
10 #E?T+ +i3# E?→+TE?
11 #E?T i3#
12 #E?T?F i3# T→FT?
13 #E?T?i i3# F→i
14 #E?T? #
15 #E? # T?→?
16 # # E?→?
二、分析表 M[A,a]的构造
构造 FIRST(?)和 FOLLOW(A)
构造分析表 M[A,a]
例 4.6 对于文法 G(E)
E→TE?
E?→+TE? |?
T→FT?
T?→*FT?|?
F→(E) | i
构造每个非终结符的 FIRST和 FOLLOW集合：
FIRST(E) ={(,i} FOLLOW(E) ={),#}
FIRST(E?)={+,?} FOLLOW(E?)={),#}
FIRST(T) ={(,i} FOLLOW(T) ={+,),#}
FIRST(T?)={*,?} FOLLOW(T?)={+,),#}
FIRST(F) ={(,i} FOLLOW(F) ={*,+,),#}
在对文法 G的每个非终结符 A及其任意候选
都构造出 FIRST(?)和 FOLLOW(A)之后，
现在可以用它们来构造 G的分析表 M[A,a]。
1,对文法 G的每个产生式 A→?执行第 2步和第 3步；
2,对每个终结符 a?FIRST(?)，把 A→?加至 M[A，
a]中；
3,若FIRST(?)，则对任何 b?FOLLOW(A)把
A→?加至 M[A,b]中。
4,把所有无定义的 M[A,a]标上,出错标志,。
i + * ( ) #
E E → TE? E → TE?
E? E? → +TE? E? →? E? →?
T T → FT? T → FT?
T? T? →? T? → *F T? T? →? T? →?
F F → i F → ( E)
如果 G是左递归或二义的，那么,M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表 M。
可以证明，一个文法 G的预测分析表 M不含多重定义入口，当且仅当该文法为
LL(1)的。
一个文法 G为 LL(1)的，当且仅当对于文法 G中每一个非终结符 A的任何两个产生式 A→?|?，
下面的条件成立：
1,FIRST(?)∩ FIRST(?)＝?
2,若 (即FIRST(?))，
则 FIRST(?)∩ FOLLOW(A)=? 。
If语句文法 G(S):
S? iCtS | iCtSeS | a
C? b
提取左因子之后，改写成：
G(S):
S?iCtSS’ | a
S’?eS |?
C? b
a b e i t #
S S → a S → iCt SS?
S? S?→?
S?→ eS
S?→?
C C → b
