[编译原理之自顶向下语法分析方法.ppt

第五章 自顶向下语法分析方法 本章要点 LL(1)分析 First 集合和Follow集合 使用递归下降分析算法进行自顶向下的分析 预测分析程序 非LL(1)文法的改造 自上而下分析算法 自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是给定的句子,则必能推出,反之必然出错。 自顶向下分析法又分为确定的和不确定的两种。 5.1 确定的自顶向下分析思想 确定的自顶向下分析方法，首先要解决从 文法的开始符号出发，如何根据当前的输 入符号（单词符号）唯一地确定选用哪个 产生式替换相应非终结符往下推导，或构 造一棵相应的语法树。 例5.1 若有文法G1[S]： S ? pA | qB A ? cAd | a B ? dB | b 若输入串W=pccadd。自顶向下推导过程为 S=pA=pcAd=pccAdd=pccadd 这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 例5.2 若有文法G2[S]为： S ? Ap S ? Bq A ? a A ? cA B ? b B ? db 例5.2文法的特点是： 产生式的右部不全是由终结符开始 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。 文法中无空产生式 定义5.1 设G=(VT,VN,P，S)是上下文无关文法 FIRST（?）={a|? a?,a∈VT, ?,?∈V*} 若? ε则规定ε∈FRIST（?） 不难求出在文法G2中 FIRST(Ap) = {a, c} FIRST(Bq) = {b, d} 例5.3 若有文法G[S]: S?aA S?d A?bAS A?? 若输入串W=abd，则试图推导出abd串的推 导过程为：S=aA=abAS=abS=abd 从例5.3可以得出下列结论 当某一非终结符的产生式中含有空产生式 时，它的非空产生式右部的首符号集两两 不相交，并与在推导过程中紧跟该非终结 符右边可能出现的终结符集也不相交，则 仍可构造确定的自顶向下分析。 定义5.2 设G=(VT,VN,P，S)是上下文无关文法, A∈VN, S是文法开始符号 FOLLOW(A)={a?S ?A? 且a∈VT a∈FRIST(?)，?∈V*，?∈V+ } 若S ?A? ,且? ε，则 #∈FOLLOW(A) 定义5.3 给定上下文无关文法的产生式A??, A?VN, ? ?V*, 若??*?，则 SELECT(A?? ) = FIRST(?) 如果? ?，则 SELECT(A?? ) = (FIRST(?) - {?})?FOLLOW(A) 定义5.4 一个上下文无关文法是LL（1）文法的充 分必要条件是，对每个非终结符A的两个 不同产生式，A??， A??，满足 SELECT(A??) ? SELECT(A? ?) = ? 其中?、?不能同时 ?。 LL(1)文法的含义： 第1个“L”指的是由左向右地处理输入。第2 个“L”指的是它为输入串描绘出一个最左推 导。括号中的数字1意味着它只需向右看一 个符号便可决定如何推导即选择哪个产生 式（规则）进行推导。 例5.3的文法 S?aA S?d A?bAS A?? 例5.4 设文法G[S]为： S?aAS S?b A?bA A?? 5.2 LL(1)文法的判别 1．求出推出?的非终结符 2．计算FIRST集 3．计算FOLLOW集 4．计算SELECT集 1．求出推出?的非终结符 扫描文法中的产生式 删除所有右部含有终结符的产生式, 若这使得以某个非终结符为左部的所有产生式都被删除，说明该非终结符不能推出?. 若某个非终结符的某个产生式的右部为?,说明该非终结符能推出?. 删除以该非终结符为左部的所有产生式. 扫描产生式右部的每一个符号 若扫描到的非终结符能推出?, 则删除该非终结符，如这样使产生式右部为空，说明该非终结符能推出?. 删除以该非终结符为左部的所有产生式. 若扫描到的非终结符不能推出?, 则删除该产生式，如这样使以该非终结符为左部的所有产生式都被删除，说明该非终结符不能推出?. 重复②，直到扫描完文法的产生式，数组中非终结符的特征在没有改变为止. 例5.5 若文法G[S]为： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 定义法：求文法符号FIRST(X) 若X?V?，则FIRST(X)={X}； 若X?VN，且有产生式X?a…，则把a加入到FIRST(X)中； 若X?VN，X?? 也是一条产生式，则把?也加到FIRST(X)中； 若X?VN， X