第四章自下而上语法分析.ppt

《第四章自下而上语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自下而上语法分析方法2）本章要求主要内容：自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。重点掌握：掌握自下而上分析的基本思想，基本概念，算符优先文法、算符优先关系的判定，最左素短语、句柄、活前缀的定义与判定，求FirstVT集,LastVT集,构造算符优先关系表,能用算符优先分析法进行表达式分析若ZS则SL(G[Z])否则SL(G[Z])+G[Z]存在主要问题:左递归问题回溯问题主要方法:递归子程序法LL分析法自顶向下分析算法的基本思想为：若ZS则SL(G[Z])否则SL(G[Z])+G[Z]自底向

2、上分析算法的基本思想为：存在主要问题:句柄的识别问题主要方法:算符优先分析法LR分析法G=({E},{i,+,*,(,)},P,E)P：EE+EEE*EE(E)Ei使用最左推导：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i例：判定输入串(i+i)*i是否是下述文法的句子？结论：自上而下语法分析采用最左推导，每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。自下而上语法分析是最左推导的逆过程，由输入符号串反向推导到文法的开始符号。自下而上的语法分析实现思想

3、：“移进-归约”方法设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。核心寻找句柄(这是关键)进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。最左推导(Left-mostDerive)每次推导都替换当前句型的最左边的非终结符。——与最右归约对应最右推导(Right-mostDerive)每次推导都替换当前句型的最右边的非终

4、结符。——与最左归约(规范归约)对应，得规范句型例：设有文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd使用最右推导：因为SaAcBeaAcdeaAbcdeabbcde，所以abbcde是文法G的句子。步骤动作(1)SaAcBe(2)Ab(3)AAb(4)Bd最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。abAcS1移进aAa移进b4a归约35cAa移进d7cAa归约48BcAa移进e910归

5、约1移进b2a归约23ab移进c6AadBeA这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。关键是如何判断可归约串？语法分析树的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd这一方法简单明了,不

6、断地进行移进归约,关键是确定当前句型的句柄.说明:例子的分析过程是一步步地归约当前句型的句柄该句子输入串为bbcde的语法树的构造过程为:Aba)AbAbb)AbAbcdBc)cdBeAbAbSd)例：G[S]:S→AcBeA→bA→AbB→d问题的提出：①在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。规范归约：使用句柄来定义可归约串。算符

7、优先：使用最左素短语来定义可归约串规范归约的概念有文法G，开始符号为S,如果有S=>xβy,则xβy是文法G的句型，x,y是任意的符号串如果有S=>xAy,且有A=>β,则β是句型xβy相对于非终结符A的短语如果有S=>xAy,且有A->β,则β是句型xβy相对于A->β的直接短语位于一个句型最左边的直接短语称为句柄.**+*注意:每次归约的部分必须是句柄(最右推导)。关键的问题是如何识别句柄例：考虑如下文法：求句型i1*i2+i3的短语、直接短语和句柄。ET

8、E+TTF

9、T*FFi

10、(E)因此：短语有：i1,i2,i3,

11、i1*i2,i1*i2+i3直接短语有：i1,i2,i3句柄是：i1E=>F*i2+i3E=>i1*F+i3E=>i1*i2+FE=>T+i3（T=>T*F=>i1*i2）E=>i1*i2+i3Fii2+i3不是短语，因为E=>i1*E（E=>i2+i3）*从