最新【考研计算机专业课】天津大学 编译原理讲义 二义性文法的应用(共6张PPT课件).pptx

《最新【考研计算机专业课】天津大学 编译原理讲义 二义性文法的应用(共6张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理讲义 二义性文法的应用(共6张PPT课件).pptx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.3.6 二义性文法二义性文法(wnf)的应用的应用任何二义文法都不是一个任何二义文法都不是一个LR文法，因此也不是文法，因此也不是SLR或或LALR文法。但是文法。但是(dnsh)，某些二义文法是非常重要的。，某些二义文法是非常重要的。例例，文法，文法(wnf)(wnf) EE+E| |E*E|(|(E)|i )|i 是一个二义文法是一个二义文法 但只要对算符但只要对算符 + +、* 赋予优先级和结合关系，就可以用于描赋予优先级和结合关系，就可以用于描述算术表达式。述算术表达式。 与文法与文法 ET| |E+TTF| |T*FF(E)| |i相比，也有明显的好处。相比，也有明显的好处。第一

2、页，共六页。1. 1. 二义性文法二义性文法(wnf)(wnf)的优缺点的优缺点 优优a. 如需要如需要(xyo)改变算符的优先级或结合关系无需去改变改变算符的优先级或结合关系无需去改变文法自身。文法自身。b. 文法的无单一文法的无单一(dny)(dny)产生式，按产生式，按LR分析法构造的分析法构造的LR分分析表体积小。析表体积小。缺缺二义性文法决不是二义性文法决不是LR文法，所以，构造的项目集规范族一文法，所以，构造的项目集规范族一定会出现动作冲突。定会出现动作冲突。 这种冲突，可以人为的规定终极符的优先级，使得冲突得以解决。这种冲突，可以人为的规定终极符的优先级，使得冲突得以解决。 第二

3、页，共六页。2. . 构造二义性文法构造二义性文法(wnf)(wnf)LRLR分析表分析表 文法文法(wnf)(wnf) EE+E|E*E|(E)|i 的的LR(0)LR(0)项目集项目集E E E E+E E E*E E (E) E iI0:EE EE +E EE *EI1:EE+ E E E+E E E*E E (E) E iI4:EE* E E E+E E E*E E (E) E iI5:E (E) E E+E E E*E E (E) E iI2:Ei I3:iEi(E (E ) EE +E EE *EI6:E+i(i(*E(E) I9:)EE+E EE +E EE *EI7:EE*E

4、EE +E EE *EI8:EE*+*+第三页，共六页。状态状态I1中，存在中，存在“接受接受”和和“移进移进”冲突，可用冲突，可用SLR的方法解决，因为的方法解决，因为FOLLOW(E)仅含有仅含有#，所以，所以(suy)，当面临，当面临#时，执行时，执行“接受接受”；面临；面临+、*时时执行执行“移进移进”。状态状态I7中，存在中，存在“规约规约”和和“移进移进”冲突，但不能用冲突，但不能用SLR的方法解决，因为的方法解决，因为+和和*都都属于属于(shy)FOLLOW(E)。不过借助于算符的优先级和结合关系这些条。不过借助于算符的优先级和结合关系这些条件就可以解决冲突了。件就可以解决冲突

5、了。考虑输入串考虑输入串i+i*i，在处理了，在处理了i+i后，分析器进入状态后，分析器进入状态I7，此时当前输入字符为，此时当前输入字符为*，规定规定*的优先级高于的优先级高于+，则应该，则应该(ynggi)把把*移进栈，即执行移进栈，即执行“移进移进”动作。动作。考虑输入串考虑输入串i+i+i，在处理了，在处理了i+i后，分析器进入状态后，分析器进入状态I7，此时当前输入字符，此时当前输入字符为为+，规定，规定+服从左结合，则应该用服从左结合，则应该用EE+E进行规约，即执行进行规约，即执行“规约规约”动作。动作。第四页，共六页。例例，描述两种条件语句的文法，描述两种条件语句的文法G:(0) SS (1) SiSeS(2) SiS (3) Saa 第五页，共六页。内容(nirng)总结4.3.6 二义性文法的应用。4.3.6 二义性文法的应用。任何二义文法都不是一个LR文法，因此也不是SLR或LALR文法。但只要对算符 +、* 赋予优先级和结合关系(gun x)，就可以用于描述算术表达式。TF|T*F。a. 如需要改变算符的优先级或结合关系(gun x)无需去改变文法自身。b. 文法的无单一产生式，按LR分析法构造的LR分析表体积小。二义性文法决不是LR文法，所以，构造的项目集规范族一定会出现动作冲突第六页，共六页。