编译原理_第4章_第3节_LR分析法.ppt

《编译原理_第4章_第3节_LR分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自底向上语法分析方法基本思想（不断进行规约的过程）从输入符号串开始，利用文法规则逐步规约，试图规约到文法的识别符号语法树的观点：以输入串作为末端节点符号串，向着根节点的方向向上构造语法树，使识别符号正好是该语法树的根节点。如果最终根节点是识别符号，则输入符号串是相应语言的句子，否则不是关键问题采用自底向下语法分析方法，在分析过程中的每一步，都会面对两个关键问题：（1）如何确定句柄（2）找出的句柄应规约到哪一个非终结符解决方法：（移进-规约法）（1）引入一个先进后出的符号栈来存放符号，按照顺序把当前输入符号入栈（移进），

2、然后查看栈顶符号串是否形成一个句柄。（2）形成一个句柄时，便对此句柄直接规约，把它代替为相应的非终结符号（规约），接着在检查是否出现新的句柄，如出现继续规约。（3）如不是句柄，继续把输入符号入栈（移进）。（4）重复（2）、（3），直到到达输入符号串的末端（5）最后，如果栈顶为文法识别符号，则合法，否则报错4.3.1LR分析器规范推倒的逆过程，分析过程是一种规范规约过程L表示从左到右扫描输入串，R表示构造最右推导的逆过程（即达到某规则右部的最右符号时，识别出句柄）。LR文法LR(0)分析法：无需查看句柄之外的任意输入符号

3、，局限性极大，但是建立其它分析表的基础；SLR(1)分析法：需要查看句柄以外的一个符号，虽有一些文法构造不出SLR分析表，但这是一种比较容易实现又极有使用价值的方法；LR(1)分析法：能力最强，但实现代价过高；LALR分析法：能力介于SLR和规范LR之间，可高效实现。4.3.1LR分析器记住已经移进和归约出的整个符号串，即“记住历史”；根据所用的产生式推测未来可能碰到的输入符号，即“展望未来”；当一串貌似句柄的符号串呈现于分析栈的顶端时，根据“历史”、“展望”和“现实”的输入符号三方面材料，来确定栈顶符号串是否构成相对

4、于某一个产生式的句柄。LR分析的基本思想：4.3.1LR分析器历史展望状态状态栈存入现实输入串归约出的符号串归约栈有助于明确归约手续S0S1…SmX0X1…Xm状态符号LR分析器的构成：已归约串4.3.1LR分析器S0S1…SmX0X1…Xm分析栈LR分析程序a1……ai……an#输入串ActionGoto分析表输出动作表状态转换表LR分析器工作原理：i+*()#ETFActionGoto状态01234567891011s5s4123s6accr2s7r2r2r4r4r4r4s5s4823s5s493r6r6r6r6s

5、5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi4.3.1LR分析器LR分析表4.3.1LR分析器(1)移进：把s’=Action[s,a]和输入符号a进栈；Sn(2)归约：用某一个产生式Aβ进行归约；rn,goto(3)接受：宣布分析成功，停止分析器的工作；(4)报错：发现源程序错误，调用出错处理程序。Action[s,a]的动作：i+*()#ETFActionGoto状态01234567891011s5s412

6、3s6accr2s7r2r2r4r4r4r4s5s4823s5s493r6r6r6r6s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi4.3.1LR分析器工作过程可看成(状态序列，已归约串，输入串)的变化初始化：(s0,#,a1a2…an#)每步结果：(s0s1…sm,#X1X2…Xm,aiai+1…an#)Action[sm,ai]为移进，且s=Action[sm,ai]，则三元式变为：(s0s1…sms,#X1

7、X2…Xmai,ai+1…an#)(2)Action[sm,ai]=rn:{Aβ}，且s=Goto[sm-

8、β

9、,A]，则三元式变为：(s0s1…sm-

10、β

11、s,#X1X2…Xm-

12、β

13、A,aiai+1…an#)(3)Action[sm,ai]=acc，宣布接受，三元式不再变化。(4)Action[sm,ai]=err，报错，三元式不再变化。LR总控程序：(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fii+*()#ETFActionGoto状态01234567891011s5s41

14、23s6accr2s7r2r2r4r4r4r4s5s4823s5s493r6r6r6r6s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5序号状态符号输入串例：i*i+i的分析过程10#i*i+i#205#i*i+i#303#F*i+i#402#T*i+i#5027#T*i+i#60275#T*i+i#7027