《编译原理语法分析》PPT课件

《《编译原理语法分析》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.4自下而上分析方法3.4.1自下而上分析原理自下而上分析自左至右扫描输入串,通过反复查找当前句型的句柄,并将找到的句柄归约为相应的非终结符,这样逐步归约,直至文法开始符。即从语法树末端开始步步向上归约,直至根结点。自下而上分析法是一种移进-归约法。分析过程中采用了一个FIFO分析栈。分析开始后，把输入符号自左至右逐个移进分析栈，边移入边分析，一旦栈顶符号串形成句柄就进行一次归约，再继续查看栈顶是否形成新的句柄，若仍为句柄，则再归约，如此重复直至栈顶不是句柄。此时再继续向栈中移进后续输入符号。重复该过程，直到将整个输入串处理完毕。若此时分析栈只有文法开始符，则输入串是一个句子，否

2、则输入串有错。下面通过例子说明这种分析过程。文法G[S]：S→aAbBA→c∣AcB→d试对输入串accbd进行分析，检查该符号串是否是G[S]的一个句子。假设“#”为输入串界符，将输入串前的“#”放入分析栈，接着将输入串的符号依次进栈，具体分析过程如下:步骤分析栈句柄输入串动作1#accbd#移进2#accbd#移进3#accbd#移进4#aAccbd#归约(用A→c)5#aAcbd#移进6#aAAcbd#归约(用A→Ac)7#aAbd#移进8#aAbd#移进9#aAbBd#归约(B→d)10#SaAbB#归约(S→aAbB)SaccbdABA(d)accbdABA(c)accA

3、A(b)acA(a)在自下而上分析过程中，每一步归约都可画出一棵子树，随着归约的完成，这些子树连成一棵完整的分析树。上述分析过程可用分析树表示如下:由上述建树过程知，自下而上分析过程的每一步归约都是对当前句型的句柄进行归约，即句柄一旦形成总是出现在分析栈栈顶。由于每一步归约都把栈顶符号串用某产生式左部符号替换，故把栈顶的这样一串符号称为可归约串。上述第6步若不选A→Ac而选A→c进行归约，则无法归约到S。如何确知栈顶的Ac是可归约串而c不是呢？这需精确定义“可归约串”的概念。若文法G[S]是无二义文法，则规范推导的逆过程必是规范归约(最左归约)。对于移进-归约过程，句柄的最左性和分

4、析栈栈顶相关。对于规范推导所得句型(规范句型)，句柄后面不会出现非终结符，故可用句柄刻画“可归约串”，规范归约的实质是在移进过程中当栈顶呈现句柄时进行归约。为加深对句柄和归约等概念的理解，用修剪语法树方法进一步阐明自下而上分析过程。语法树的一个子树由该树的某结点及其所有子孙组成，子树的所有叶结点的自左至右排列形成一个相对于子树根的短语。一个句型的句柄是该句型对应的语法树中最左简单子树的所有树叶的自左至右排列。可采用修剪语法树方法实现归约，即寻找当前语法树的句柄，将句柄中的树叶剪去(归约)，不断修剪直到只剩根结点，完成整个归约过程：SaAbBAcdcSaAbBAcdSaAbBdSaA

5、bBS至此讨论了句柄和规范归约这两个基本概念，但并没有解决规范归约的问题，因为没有给出寻找句柄的算法。事实上，规范归约的中心问题就是如何寻找句柄。寻找句柄的不同算法对应不同的规范归约方法，这一点将在LR分析器中讨论。算符优先分析法是一种简单直观、广为使用的自下而上分析法，特别适合于表达式分析且宜于手工实现。它实际上是依照表达式四则运算过程来进行语法分析。所谓算符优先分析，就是预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，借助于这种优先关系来比较相邻运算符的优先级，以确定句型的可归约串并进行归约。注意：算符优先分析不是规范归约。3.4.2算符优先分析法1.算符优先文法算

6、符文法:若一个文法的任一产生式的右部都不含两个相继的非终结符，即不含…QR…这样的右部，则称该文法为算符文法。算符优先文法:算符优先文法首先应是算符文法,其次还要定义任意两个可能相继出现的终结符的优先关系。具体定义如下:假定G是一个不含ε产生式的算符文法,对任一对终结符a,b,定义(1)a=b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式;(2)ab当且仅当G中含有形如P→…Rb…的产生式，而R…a或RaQ。++++若一个算符文法G中任一终结符对(a,b)至多满足下述三种关系之一:a=

7、b，ab则称文法G是一个算符优先文法。例3.10试说明下述文法G是算符文法，但不是算符优先文法。E→E+E∣E*E∣(E)∣i解:由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是算符文法。(1)由于存在E→E+E，而E+E中第二个E可推出E*E，故有+<*(2)由于存在E→E*E，而E*E中第一个E可推出E+E，即有+>*可见,运算符+和*之间同时存在两种不同的优先关系，故文法G不是算符优先文法。2.算符优先关系表的构造通过检查文法的每个产生式