ch6自底向上算符优先语法分析_(张素琴).ppt

《ch6自底向上算符优先语法分析_(张素琴).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自底向上算符优先语法分析第6章1主要内容：规范归约，自上而下的算符优先分析方法及其相关概念。重点掌握：掌握自下而上分析的基本思想，规范规约的概念及过程；算符优先文法、算符优先关系的判定，最左素短语、句柄的定义与判定;构造算符优先关系表;能用算符优先分析法进行表达式分析。6.1自底向上优先分析概述2自下而上的语法分析实现思想：“移进-归约”方法输入：待分析的句子(终结符号串)。输出：语法树。从树叶开始，逐步向上归约构造分析树，直到形成根结点。核心寻找句柄进行规约。设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时(句柄)

2、，就用左部去代替，称为归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。3最左推导(Left-mostDerive)每一步推导都替换当前句型的最左边的非终结符。——其逆过程称为最右归约最右推导(Right-mostDerive)每一步推导都替换当前句型的最右边的非终结符。——其逆过程称为最左归约(规范归约)，得规范句型例：设有文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd最右推导：SaAcBeaAcdeaAbcdeabbcdeabbcde是文法G的句子

3、。4步骤动作(1)SaAcBe(2)Ab(3)AAb(4)Bd最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。abAcS1移进aAa移进b4a归约35cAa移进d7cAa归约48BcAa移进e910归约1移进b2a归约23ab移进c6AadBeA5语法分析树的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd6规范归约分析过程具有如下特点：从输入串的

4、开始依次读入单词(移进栈中)。一旦发现可归约串（某个产生式的右端）就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。关键是如何判断可归约串？7问题的提出：①在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串？如何进行归约？不同的自下而上的分析方法对可归约串的定义是不同的，但分析过程的一个共同特点是：边移进边归约。规范归约：使用句柄来定义

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

6、E+TTF

7、T*F

8、Fi

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

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

11、E+TTF

12、T*FFi

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

14、E+TTF

15、T*FFi

16、(E)EE+TFiE+TT*F短语有：i,T*F,E+T*F,E+T*F+i直接短语有：i,T*F句柄是：T*F练习12给定右边的文法，用句柄对符号串abbcde进行归约用句柄对句子进行归约的过程与用移进-归约过程是一致的，使

17、用归约的产生式及其顺序是一致的。符号串(句型)归约规则abbcde(1)SaAcBe(2)Ab(3)AAb(4)Bd(2)Ab(3)AAbaAbcdeaAcde(4)Bd(1)SaAcBeaAcBeSbAABSacdeb13规范归约分析中栈