《编译原理》课程简介 (33).pdf

《《编译原理》课程简介 (33).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (33).pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编 译 原 理 C O M P I L A T I O N P RIN C IP LE 第五章 语法分析自下而上分析5.2.3 算符优先分析算法5.2.3 算符优先分析算法三、算符优先分析法的设计可归约串，句型，短语，直接短语，句柄，规范归约。可一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。3215.2.3 算符优先分析算法n例：考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|iEEF+*TiFTFTP+ETPp句型：T+F*P+ip短语：T

2、,F,P,i,F*P,T+F*P,T+F*P+ip直接短语：T,F,P,ip句柄:Tp素短语：F*P,ip最左素短语：F*P5.2.3 算符优先分析算法n算符优先文法句型(括在两个之间)的一般形式写成：#N1a1N2a2NnanNn+1#其中，每个ai都是终结符，Ni是可有可无的非终结符。n定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1，其中，aj-1 ai+1 5.2.3 算符优先分析算法n根据这个定理，下面我们讨论算符优先分析算法。n为了和定理叙述的相适应，我们使用一个符号栈S，用它寄存终结符和非终结符，下面的分析算法是直接根据这个定理构造

3、出来的，k代表符号栈S的使用深度。5.2.3 算符优先分析算法k:=1;Sk:=#;REPEAT 把下一个输入符号读进a中；IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sj a DOBEGIN REPEAT Q:=Sj;IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj.Q;把Sj+1Sk归约为某个N；k:=j+1;Sk:=N END OF WHILE;IF Sj.a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR/*调用出错诊察程序*/UNTIL a=#n自左至右，终结符对终结符，非终

4、结符对非终结符，而且对应的终结符相同。N X1 X2 Xk-j Sj+1 Sj+2 Sk5.2.3 算符优先分析算法n在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。n由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。5.2.3 算符优先分析算法n例：考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i 的句子i+i*i+i解：加界符“#”，分析串为#i+i*i#1.#+，最左素短语为i 归约为#P+i*i#2.#+,+*，最左素短语为i 归约为#P+P*i#3.#+,+*,*#，最左素短语为i 归约为#P+P*P#4.#+,+#，最左素短语为P*P 归约为#P+T#5.#，最左素短语为P+T 归约完毕，结论：输入串，i+i*i是文法的句子5.2.3 算符优先分析算法n算符优先分析法特点：1优点:简单，快速。11缺点:可能错误接受非法句子，能力有限。2n算符优先分析法是一种广为应用、行之有效的方法。1用于分析各类表达式11ALGOL 602n算符优先分析一般并不等价于规范归约。|编译原理谢 谢Thanks