第五章自顶向下语法分析方法语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类:5.1确定的自顶向下分析思想1确定分析的条件例1设有文法G1[S]:S→pA|qBA→cAd|aB→dB|b若输入串W=pccadd。自顶向下的推导过程为:例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dB例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：2开始符号集FIRST(α)的定义例文法G2[S]:3后跟符号集FOLLOW(A)的定义例文法G3[S]:S→aA|dA→bAS|ε说明：对于非终结符A的两个产生式A→bAS和A→ε，当输入符号∈FIRST(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d}时，选A→ε推导。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。4选择集合SELECT(A→α)的定义解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式A→进行推导：First()中包含a；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A→也是可以的。直观上说某产生式A→α的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。例G3[S]:S→aAS→dA→bASA→ε5LL(1)文法的定义例有文法G[S]为：S→aASS→bA→bAA→ε5.2LL(1)文法的判别1.求出能推出ε的非终结符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c2.计算每个产生式右部α的FIRST(α)集其中SectionFirst(X1…Xj…Xn)=(First(X1)-{ε})(First(X2)-{ε})…(First(Xj)-{ε})First(Xj+1)Xj+1是产生式右部中第一个不能推出ε的符号若X1≠>*ε则SectionFirst(X1…Xj…Xn)=First(X1)若X1…Xn全可推出ε则SectionFirst(X1…Xn)=FIRST(X1)∪…∪FIRST(Xn)重复3直到每个符号的FIRST集合都不再增大为止。例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c利用求出每个文法符号的FIRST集求符号串的FIRST集例G[S]S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c3．计算每个非终结符A的FOLLOW(A)集例G[S]：[1]S→AB[2]S→bC[3]A→b[4]A→ε[5]B→aD[6]B→ε[7]C→AD[8]C→b[9]D→aS[10]D→c4．计算每个产生式A→α的SELECT(A→α)集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c5.按LL(1)文法的定义判别5.3某些非LL(1)文法到LL(1)文法的等价变换1提取左公共因子2.消除左递归消除间接左递归将间接左递归变成直接左递归，再消除算法步骤：把文法的所有非终结符按任一顺序排列，如：A1，A2，…，An从A1开始，按以下顺序处理Ai。首先，消除左部为Ai的产生式的直接左递归然后，若左部为Ai的产生式的右部为非终结符Aj(j<i)开头，即Ai→Aj…，则用左部为Aj的所有产生式的右部分别代替Ai→Aj…中的Aj最后，得到的左部为Ai的产生式若有直接左递归，则消除之去掉无用产生式。例文法G：(1)S→Qc|c(2)Q→Rb|b(3)R→Sa|a示例说明：当非终结符顺序为R，Q，S，消除左递归的最终结果为：S→abcS’|bcS’|cS’S’→abcS’|ε若非终结符顺序为S，Q，R，则消除左递归的最终结果为：S→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。5.4不确定的自顶向下分析思想例1设有文法S→xAyA→ab|a，对输入串w=xay，推导树为例2文法G：S→aASS→bA→bASA→ε输入串w=ab，推导树为:例3文法G：S→SaS→b输入串w=baa，推导树为:5.5确定的自顶向下分析方法5.5.1递归子程序法例算术表达式文法GE→E+T│TT→T*F│FF→(E)│i2构造文法G'的递归下降分析器定义：当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶