《编译原理课程教案》第4章：自下而上语法分析

《《编译原理课程教案》第4章：自下而上语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自下而上语法分析方法第四章（2）本章要求主要内容：自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。重点掌握：掌握自下而上分析的基本思想，基本概念，算符优先文法、算符优先关系的判定，最左素短语、句柄、活前缀的定义与判定，求FirstVT集,LastVT集,构造算符优先关系表,能用算符优先分析法进行表达式分析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例：判定输入

2、串(i+i)*i是否是下述文法的句子？结论：自上而下语法分析采用最左推导，每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。自下而上语法分析是最左推导的逆过程，由输入符号串反向推导到文法的开始符号。自下而上的语法分析实现思想：“移进-归约”方法设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。核

3、心寻找句柄(这是关键)进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。最左推导(Left-mostDerive)每次推导都替换当前句型的最左边的非终结符。——与最右归约对应最右推导(Right-mostDerive)每次推导都替换当前句型的最右边的非终结符。——与最左归约(规范归约)对应，得规范句型例：设有文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd使用最右推导：因为SaAcBeaAcdeaAbcdeabbcde，所以abbcde是文法G的句子。步骤动作(1)SaAcBe

4、(2)Ab(3)AAb(4)Bd最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。abAcS1移进aAa移进b4a归约35cAa移进d7cAa归约48BcAa移进e910归约1移进b2a归约23ab移进c6AadBeA这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归

5、约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。关键是如何判断可归约串？语法分析树的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd问题的提出：①在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。规范归

6、约：使用句柄来定义可归约串。算符优先：使用最左素短语来定义可归约串规范归约的概念有文法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

7、E+TTF

8、T*FF

9、i

10、(E)因此：短语有：i1,i2,i3,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）*从语法分析树来识别：一棵子树是由树的某个结点连同它的所有子孙组成的。子树的所有端末结点自左至右排列成一个相对子树根的短语。直接短语：只有父子两代结点形成的短语。句柄：最左子树的直接短语。EE+TTFi3i2i1T*FF

11、从语法树可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短语直接短语有：i1,i2,i3句柄是：i1ET

12、E+TTF

13、T*FFi

14、(E)句型i1*i2+i3的语法树如图：对下述文法，求句型E+T*F+i的短语、直接短语、句柄ET

15、E+TTF

16、T*FFi

17、(E)EE+TFiE+TT*F短语有：i,T*F