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

编 译 原 理C O M P I L A T I O N P RIN C IP LE 第五章 语法分析自下而上分析5.3.8 二义文法的使用5.3.8 二义文法的使用二义文法的应用n任何二义文法决不是LR(k)的，但是二义文法却很有用。能否让二义文法也使用LR分析法？n方法是：当发生冲突时，规定其解决冲突的方法，也即规定算符之间的优先级。n例：文法 EE+E|E*E|(E)|i 该文法排版为：(1)EE+E(3)E(E)(2)EE*E(4)Ei5.3.8 二义文法的使用5.3.8 二义文法的使用n其LR分析表如下状态ACTIONGOTOi+*()#E0S3S211S4S5acc2S3S263r4r4r4r44S3S275S3S286S4S5S97S4/r1S5/r1r1r18S4/r2S5/r2r2r29r3r3r3r35.3.8 二义文法的使用分析发现，I7、I8两个集合存在移进/归约、冲突，而且由于FOLLOW(E)=+,*,),#。与“+”，“*”的冲突不能通过SLR(1)方法解决。但由于算符+，*有优先级关系，可利用此来分析取舍。考察I7：说明堆栈中已有E+E。若当前指针指向符号是“+”，而堆栈中已有“E+E”，同样是“+”运算，先进栈的先计算。用E+E归约为E，而不取把“+”移进。若当前指针指向符号是“*”，而堆栈中已有“E+E”，前面运算（在堆栈中）是+，而现在运算是*必须先运算“*”运符而不能让前面的“+”先运算。选取把“*”移进，而不取把“E+E”归约。5.3.8 二义文法的使用考察I8:说明堆栈中已有E*E若当前指针指向的符号是“+”，而堆栈中已有“E*E”，显然应优先做前面的“E*E”运算，选用E*E归约，而不取移进“+”；若当前指针指向的符号是“*”，而堆栈中已有“E*E”，由于同样是“*”运算符，堆栈里面的部分排在前面，应先计算，选用E*E归约，而不取移进“*”。5.3.8 二义文法的使用n例2文法 S iSeS|iS|a n构造DFA图如下：5.3.8 二义文法的使用状态ACTIONGOTOiea#S0S2S311acc2S2S343r3r34S5/r2r25S2S366r1r1nLR分析表如下：|编译原理谢 谢Thanks