第五章语法分析自下而上分析ppt课件.ppt

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

1、第五章语法分析——自下而上分析自上而下分析法(Top-down)自下而上分析法(Bottom-up)语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约5.1.1归约采用“移进－归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为

2、)该产生式的左部符号。bdbaceSABA分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串5.1.2规范归约定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i2定义：假定是文法G的

3、一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。5.2算符优先分析四则运算的优先规则：先乘除后加减，同级从左到右考虑二义文法文法G(E)：G(E)：Ei

4、E+E

5、E-E

6、E*E

7、E/E

8、(E)它的句子有几种不同的规范规约。归约即计算表达式的值。

9、归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。首先必须定义任何两个可能相继出现的终结符a与b的优先关系三种关系aba的优先级低于baba的优先级等于baba的优先级高于b注意：与数学上的<>=不同，ab并不意味着ba5.2.1算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：…QR…则我们称该文法为算符文

10、法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表由终结符和非终结符组成的任意序列，包括空字。假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab，ab则称G是一个算符优先文法。2.ab当且仅当G中含有形如P→…aR…的产生式，而Rb…或RQb…；3.ab当且仅当G中含有形如P→…Rb…的产生式，而R…a或R…aQ。优先关系表从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式

11、的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为…aP…那么，对任何bFIRSTVT(P)，有ab。假定有个产生式的一个候选形为…Pb…那么，对任何aLASTVT(P)，有ab。首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式P→a…或P→Qa…，则aFIRSTVT(P)；2.若a

12、FIRSTVT(Q)，且有产生式P→Q…，则aFIRSTVT(P)。数据结构：布尔数组F[P，a]，使得F[P，a]为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素F[P，a]赋初值。栈STACK，把所有初值为真的数组元素F[P，a]的符号对(P，a)全都放在STACK之中。运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如P→Q…的产生式，若F[P，a]为假，则变其值为真且将(P，a)推进