4.1句法分析器概述(Ɡàishù)确定的自顶向下分析思想例文法G1[S]:SpASqBAcAdAaBdBBbW=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dBW=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+TEE+TE+T+TE+T+T+T…(2)无回溯，对文法的任一非终结符号(fúhào)，当其产生式右部有多个候选式可供选择时，各候选式所推导出的终结符号(fúhào)串的首字符集合要两两不相交。例如，如果有文法G[S]：SxAyA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∣TTT*F∣FF(E)∣i消去直接左递归后得到文法G'[E]为：G'[E]:ETE'E'+TE'∣TFT'T'*FT'∣F(E)∣i2.间接左递归将间接左递归变为直接左递归，然后(ránhòu)消除直接左递归。如文法G[A]含有间接左递归：AaBAaBAaBABbABbABbBAcBaBcBaBcB'|dB'BdBBbcB'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|a1)对非终结符排序：S、Q、R2)把(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、S2）把(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→bB1.化为：A→adA→aAcA→bBcB→aAB→bBF(E)∣ivoidF(){if(lookahea