语法分析自下而上分析.ppt

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

1、第五章语法分析—自下而上分析内容自下而上分析基本问题算符优先分析语法分析器的自动产生工具YACC5.1自下而上分析基本问题自下而上分析：从输入开始，逐步进行“归约”，直至归约到文法的开始符号。5.1.1归约自下而上分析法是一种“移进-归约”法。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。5.1.1归约例：设文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进-归约”分析。abbcdebabcdeAabcdebAacdeAacdecA

2、adedcAaeabbcdeeBcAaS5.1.1归约例：设文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进-归约”分析。5.1.1归约分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串bdbaceSABA5.1.2规范归约简述定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。5.1.2规范归约简述例：文法G[E]：E→E

3、+T

4、TT→T*F

5、FF→(E)

6、–F

7、id考虑文法G[E]上的句子id1+id2*id3。其最右推导和分析树如图5.1(a)、(b)所示。分析树中的叶子与短语、直接短语和句柄有下述关系。①短语：以非终结符为根的子树中所有从左到右排列的叶子；②直接短语：只有父子关系的树中所有从左到右排列的叶子(树高为2)；③句柄：最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)。图5.1id1+id2*id3的最右推导、分析树与短语(a)最右推导；(b)分析树；(c)短语根据定义，从文法开始符号经过0步推导得到E1，从E1经过若干步推导得到id1+id2*id3，所以id1+id2*id3是句型

8、id1+id2*id3相对于E1的短语(其中α和δ均为ε，β是句子的全体)。考虑推导E1=>E2+id2*id3=>T2+id2*id3=>F1+id2*id3=>id1+id2*id3，id1是相对于非终结符E2、T2和F1的短语(其中α为ε，δ为+id2*id3)，特别是相对于F1的直接短语，也是句柄。id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语，因为找不到任何一个非终结符，它的子树中的所有叶子构成id1+id2。EFFTTTi1+*EFi3i25.1.2规范归约简述例：考虑文法G[E]：ET

9、E+TTF

10、T*FF(E)

11、i和句型i1*i2+i3：在一

12、个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EE+TE+FE+i3T+i3T*F+i3T*i2+i3F*i2+i3i1*i2+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i15.1.2规范归约简述可用句柄来对句子进行归约例：设文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd句型归约规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS5.1.2规

13、范归约简述定义：假定是文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。5.1.2规范归约简述把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。规范归约的中心问题：确定句型的句柄。5.1.2规范归约简述最右推导，推导的每一步结果都是一个右句型。该推导即分析树“剪句柄”的全过程。图3.18剪句

14、柄的过程(a)句子；(b)剪去b之后；(c)剪去Abc之后；(d)剪去d之后；(e)开始符号5.1.3符号栈的使用与语法树的表示从分析树上直观地看，“剪句柄”的方法十分简单。但是若在语法分析器中实现剪句柄，则有两个问题必须解决：①确定右句型中将要归约的子串(确定句柄)；②确定如何选择正确的产生式进行归约。具体实现采用移进—归约方法，用一个栈“记住”将要归约句柄的前缀，并用一个分析表来确定何时栈顶已形成句柄，以及形成句柄后选择哪个产生