自顶向下句法分析学习教案.ppt

4.1句法分析器概述(Ɡàishù)确定的自顶向下分析思想
例文法G1[S]:SpASqBAcAdAaBdBBb
W=pccadd自顶向下的推导(tuīdǎo)过程：
SpApcAdpccAddpccadd文法G1[S]:SpA|qBAcAd|aBdB|b
文法的特点：
每个产生式的右部都由终结符号开始。
如果两个产生式有相同的左部，那么(nàme)它们的右部由不同的终结符开始。文法G2[S]:SApSBqAaAcABbBdB
W=ccap自顶向下的推导(tuīdǎo)过程：
SApcApccApccap文法G2[S]:SAp|BqAa|cABb|dB
文法的特点：
每个产生式的右部不全是由终结符号开始。
如果两个产生式有相同的左部，那么(nàme)它们的右部由不同的终结符或非终结符开始。
文法中无空产生式。 为了实现确定的(即无回溯的)自顶向下分析，则要求(yāoqiú)文法满足下述两个条件：
(1)文法不含左递归
直接左递归：AA…
间接左递归：AB…，B+A
左递归文法使自上而下分析工作陷入死循环。
例如，如果有产生式
EE+T
EE+TE+T+TE+T+T+T…(2)无回溯，对文法的任一非终结符号(fúhào)，当其产生式右部有多个候选式可供选择时，各候选式所推导出的终结符号(fúhào)串的首字符集合要两两不相交。
例如，如果有文法G[S]：
SxAy
Aab∣a
输入串xay的分析就需要回溯。
带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低。消除左递归
1.直接左递归
方法是引入一个新的非终结符，把含有左递归的产生(chǎnshēng)式改为右递归。设关于A的产生(chǎnshēng)式为
AA1∣A2∣…∣Am∣1∣2∣…∣n
其中，每个i都不为且每个j都不以A开头，则消除A的直接左递归就是将其改写为：例如(lìrú)，含有直接左递归的表达式文法G[E]为：
G[E]: EE+T∣T
TT*F∣F
F(E)∣i
消去直接左递归后得到文法G'[E]为：
G'[E]: ETE'
E'+TE'∣
TFT'
T'*FT'∣
F(E)∣i2.间接左递归
将间接左递归变为直接左递归，然后(ránhòu)消除直接左递归。
如文法G[A]含有间接左递归：AaB AaB AaBABb ABb ABbBAc BaBc BaBcB'|dB'Bd BBbc B'bcB'|ε
Bd (1) 将所有非终结符排序(páixù)：A1、A2、…、An；
(2) for(i=1;i<=n;i++){
for(j=1;j<=i−1;j++){
若Aj的所有产生式为：Aj1|2|…|k
则把形如AiAjr的产生式变换为：
Ai1r|2r|…|kr
}
消除Ai规则中的一切直接左递归;
}
(3) 删除无用的产生式 这里第二步所做的工作是：
a)若产生式出现直接左递归则用消除直接左递归的方法消除掉。
b)若产生式右部最左符号是非终结符且其序号大于左部的非终结符，则不处理。
c)若序号小于左部的非终结符，则将这序号小的非终结符用其右部串来取代，然后消除新的直接左递归。
注意：1）若非终结符排列顺序不同(bùtónɡ)，改写后的文法也不同(bùtónɡ)，但它们是等价的。2）开始符号不能改变。例：对下面(xiàmian)文法消除左递归：
(1)SQc|c(2)QRb|b(3)RSa|a
1)对非终结符排序：S、Q、R
2)把(1)代入(3)得：(4)RQca|ca|a
再把(2)代入(4)得：(5)RRbca|bca|ca|a
对(5)消除直接左递归得：
(6)RbcaR'|caR'|aR'
(7)R'bcaR'|
得到不含左递归的文法：(1)、(2)、(6)、(7) 对非终结符也可以有不同的排序。
1）对非终结符重新排序：R、Q、S
2）把(3)代入(2)得：(4')QSab|ab|b
再把(4')代入(1)得：(5')SSabc|abc|bc|c
对(5')消除直接左递归得：
(6')SabcS'|bcS'|cS'
(7')S'abcS'|
得到(dédào)不含左递归的文法：(6')、(7')例：文法(wénfǎ)G2为:A→adA→BcB→aAB→bB
1.化为：A→ad
A→aAc
A→bBc
B→aA
B→bBF(E)∣i
voidF()
{ if(lookahea