编译原理5.3.1-LR分析器.ppt

《编译原理5.3.1-LR分析器.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章语法分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC5.3LR分析5.3.1LR分析器5.3.2LR(0)项目集族＆LR(0)分析表的构造5.3.3SLR分析表的构造5.3.4规范LR分析表的构造5.3.5LALR分析表的构造5.3.6二义文法的应用课前思考自下而上分析是一种___________过程自下而上分析法的关键问题是在分析过程中___________________。算符优先分析法如何确定可归约串？什么是规范推导和规范归约？它们之间有什么关系？规范归约过程是当分析的栈顶符号串形成___

2、____时就采取归约动作移进-归约句柄如何确定可归约串LR(K)L:自左向右扫描R:逆向完成最右推导(规范归约)K:向右查看输入串符号的个数(K省略时,表示K等于1)LR分析过程是规范归约过程四种LR分析器LR(0)SLR(1)LR(1)LALR(1)LR方法的基本思想LR方法的关键:确定句柄历史:已移进和归约出的整个符号串展望:根据所用的产生式推测未来可能碰到的输入符号现实:当前的输入符号LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。一个LR分析器实质上是一个DFA状态5.3.1LR分析器P100a1a2…a

3、i…an#LR分析表总控程序输入串：栈顶输出s0s1…sm状态栈#x1…xm符号栈分析栈GotoAction图5.4LR分析器模型分析表例：p101G:(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi3...3.3102...2.91...8.accr2.r4r6...r1r3r5..r2r4.r6..S11r1r3r5S4...S4.S4S4..S7r4.r6...S7r3r5.S6r2r4.r6...S6r1r3r5S5...S5.S5S50123

4、4567891011FTE#)(*+i状态GOTO[s,A]ACTION[s,a]表达式文法的LR分析表p101将LR分析器的工作过程看成三元式的变化过程状态栈符号栈输入串分析开始时的初始三元式为:(s0,＃，ala2...an＃）分析过程每步的结果可表示为(s0s1...sm，＃X1X2...Xm，aiai+1…an＃）分析器的下一步动作由sm和ai所唯一决定栈顶栈顶现行输入符号Action[sm,ai]:4种可能动作(1)移进–sj(2)归约–rm(3)接受–acc(4)报错–空白/‘出错’/‘error’(1

5、)移进–sjpushs;pushai;状态栈符号栈输入串s0s1...sm＃X1X2...Xmaiai+1…an＃s0s1...sm＃X1X2...Xmai+1…an＃s=GOTO[sm，ai]=jsaij(2)归约-rmpop文法符号栈r次pop状态栈r次pushA查表s=GOTO[sm-r,A]pushs用第m条产生式A→β归约.

6、β

7、=r状态栈符号栈输入串s0s1...sm-r…sm＃X1X2...Xm-r…Xmaiai+1…an＃s0s1...sm-r＃X1X2...Xm-raiai+1…an＃As步骤状态栈符号栈剩余输

8、入串动作10#i*i+i#2345…例5.7对i*i+i#进行移进-归约分析P102移进S50#*i+i#归约r6FiG:(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi0#*i+i#F3归约r4TF0#*i+i#T25i移进S7027#T*i+i#移进S5步骤状态栈符号栈剩余输入串动作10#i*i+i#移进S5205#i*i+i#归约r6Fi303#F*i+i#归约r4TF402#T*i+i#移进S75027#T*i+i#移进S560275#T*i+i#归约r6Fi702710#T

9、*F+i#归约r3TT*F802#T+i#归约r2ET901#E+i#移进S610016#E+i#移进S5110165#E+i#归约r6Fi120163#E+F#归约r4TF130169#E+T#归约r1EE+T1401#E#接受accp102补充：LR分析算法*状态栈中放入状态0;文法符号栈中放入＃ip指向输入串w的第一个符号Sm为栈顶状态;a是ip指向的符号Repeat…//见下页end.RepeatifACTION[Sm,a]=SjbeginPUSHj,aip前进endelseifACTION[Sm,a]=rj/

10、/A→βbeginpop

11、β

12、项//当前栈顶状态为SkpushGOTO[Sk,A],AendelseifACTION[Sm,a]=accreturn(成功）elseerrorend.LR分析器小结总控程序-对所有的LR分析器都是相同的。根据当前栈顶的状态号和输入