自上而下语法分析方法.ppt

第四章 自上而下的语法分析方法 本章重点： 1. LL(1)文法判别 2. 某些非LL(1)文法到LL(1)文法的等价转换 3. 预测分析法实现过程 4. 递归子程序法实现思想 语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子。 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 直观、简单和宜于手工实现。 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 4.1 确定自顶向下分析思想和LL(1)文法 G1[S]: S →pA | qB A →cAd | a B →dB | b G2[S]: S →Ap S → Bq A →a A → cA B → b B → dB FIRST集定义 令G是一个上下无关文法，对G的所有非终结符的每个候选?定义它的终结首符号集FIRST(?)为： 根据定义计算FIRST集 1.若X?V?,则FIRST(X)={X}. 2.若X?VN,且有产生式X?a…，a?V? 则把a加入到FIRST(X)中;若X??是一条产生式,则把?也加到FIRST(X)中。 3.若X?Y…是一个产生式且Y?VN,则把FIRST(Y)中的所有非?元素都加到FIRST(X)中; 4.若 X? Y1Y2…Yk 是一个产生式, Y1,Y2,…,Y(i-1) (i ≤k)都是非终结符,而且,对于任何j,(1≤j ≤i-1)FIRST(Yj)都含有? (即Y1，Y2，…，Y(i-1)都 ? ),则把FIRST(Yj)中的所有非?元素和FIRST(Yi)都加到FIRST(X)中; 特别是,若所有的FIRST(Yj ) , ( j=1,2,…,k)均含有?,则把?也加到FRIST(X)中。 例子文法： S ?AB S ?bC A ? ? A ? b B ? ? B ? aD C ? AD C ? b D ? aS D ? c FOLLOW集定义 令G是一个上下无关文法，对G的所有非终结符A定义它的后跟符号集FOLLOW(A)为： 根据定义计算FOLLOW集 1.对于文法的开始符号S,置#?FOLLOW(S); 2.若Ａ→αBβ是一个产生式,则把 ?? FIRST(β)- {?}加至FOLLOW(B)中; 3.若Ａ→αB 是一个产生式,或Ａ→αBβ是一个产生式，而β ?(即??FIRST(β)），则把FOLLOW（A）加到FOLLOW（B）中。 SELECT集定义 一个上下文无关文法的产生式A →α 若α ε ，则SELECT(A →α)=FIRST(α) 若α ε ，则 SELECT(A →α)=（FIRST(α)-{ε}）∩FOLLOW(A) LL(1)文法的充要条件 一个上下文无关文法是LL(1)文法的充要条件是： 对每个非终结符A的两个不同的产生式 A →α，A →β，满足 SELECT(A →α)∩ SELECT(A → β)=? 其中α 和β不能同时n次推出ε。 LL(1)文法判别的步骤 (1)求出能推出ε的非终结符 (2)计算每个VN的FIRST集 (3)计算每个VN的FOLLOW集 (4)计算每个产生式的SELECT集合 根据充要条件判别文法是否为LL(1) 4.2 某些非LL(1)到LL(1)文法的等价变换 分析自顶向下分析过程中产生不确定性的原因： 1. 由于相同左部的产生式的右部FIRST集相交不为空而引起回溯 2. 由于相同左部非终结符的右部肯能推导出ε的产生式，且该非终结符的FOLLOW集合中含有其他产生式右部FIRST集合的元素 3.由于文法含有左递归而引起回溯 G1[S]: S →xAy A →ab | a 输入串： xay 4.2.1 消除左递归 1 消除直接左递归 消除直接左递归（改写为等价的右递归） 形如：A → A α|β α非?，