【精品】【考研计算机专业课】天津大学 编译原理讲义 二义性文法的应用精品ppt课件.ppt

【考研计算机专业课】天津大学 编译原理讲义 二义性文法的应用1.1.二义性文法的优缺点二义性文法的优缺点 优优a.如需要改变算符的优先级或结合关系无需去改变文如需要改变算符的优先级或结合关系无需去改变文法自身。法自身。b.文法的无单一产生式，按文法的无单一产生式，按LR分析法构造的分析法构造的LR分析分析表体积小。表体积小。缺缺二义性文法决不是二义性文法决不是LR文法，所以，构造的项目集规范文法，所以，构造的项目集规范族一定会出现动作冲突。族一定会出现动作冲突。这种冲突，可以人为的规定终极符的优先级，使得冲突这种冲突，可以人为的规定终极符的优先级，使得冲突得以解决。得以解决。2.构造二义性文法构造二义性文法LRLR分析表分析表 文法文法 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 EE+E EE*EI8:EE*+*+状态状态I1中，存在中，存在“接受接受”和和“移进移进”冲突，可用冲突，可用SLR的方法解决，因为的方法解决，因为FOLLOW(E)仅含有仅含有#，所以，当面临，所以，当面临#时，执行时，执行“接受接受”；面临；面临+、*时执行时执行“移进移进”。状态状态I7中，存在中，存在“规约规约”和和“移进移进”冲突，但不能用冲突，但不能用SLR的方法解决，的方法解决，因为因为+和和*都属于都属于FOLLOW(E)。不过借助于算符的优先级和结合关。不过借助于算符的优先级和结合关系这些条件就可以解决冲突了。系这些条件就可以解决冲突了。考虑输入串考虑输入串i+i*i，在处理了，在处理了i+i后，分析器进入状态后，分析器进入状态I7，此时当前，此时当前输入字符为输入字符为*，规定，规定*的优先级高于的优先级高于+，则应该把，则应该把*移进栈，即执行移进栈，即执行“移进移进”动作。动作。考虑输入串考虑输入串i+i+i，在处理了，在处理了i+i后，分析器进入状态后，分析器进入状态I7，此时当前，此时当前输入字符为输入字符为+，规定，规定+服从左结合，则应该用服从左结合，则应该用EE+E进行规约，进行规约，即执行即执行“规约规约”动作。动作。例例，描述两种条件语句的文法，描述两种条件语句的文法G:(0)SS (1)SiSeS(2)SiS (3)Saa