t1u0v6-LR0.pptVIP免费

第六章ＬＲ分析自下而上的语法分析特定的一种shift-reduce实现技术能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器第六章ＬＲ分析6.1概述自下而上的语法分析LR分析器6.2LR(0)分析6.3SLR(1)分析技术，二义文法的应用6.4LR(1)和LALR(1)分析6.1概述自下而上的语法分析例：文法G：S→cAdA→abA→a识别输入串w=cabd是否该文法的句子SAAcabdcabdcd归约过程构造的推导：cAdcabdScAd(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”cabdcAbda刻画“可归约串”文法G[S]句型的短语S=>*αAδ且A=>+β，则称β是句型αβδ相对于非终结符A的短语句型的直接短语若有Aβ，则称β是句型αβδ相对于非终结符A的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄例：i*i+i的短语、直接短语和句柄EE+TTFT*Fi3短语：i1*i2+i3，i1*i2，Fi2i1，i2，i3。i1直接短语：i1，i2，i3。句柄：i1G[E]：E→E+T|TT→T*F|FF→(E)|i句型：i*i+i自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”•选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）•选择“可归约串”是句型的句柄－规范归约G[E]：E→E+T|TT→T*F|FF→(E)|i•句型i*i+i的自下而上分析，总是归约当前句型的句柄形成的规范推导序列：EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i•句型i*i+i的自下而上分析总是归约当前句型的最左素短语形成的推导：ET+FT+iF*F+iF*i+ii*i+i自下而上的分析模式移进－归约模式Shift:移进，输入符进栈reduce:归约，用第i个产生式归约总控程序output…产生式表Input$(#)…移进归约依据表文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤栈余留输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8...