编译原理 - 自下而上的语法分析

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

1、第五章语法分析—自下而上分析内容自下而上分析基本问题算符优先分析5.1自下而上分析基本问题自下而上分析基本问题归约规范归约符号栈的使用语法树的表示算符优先分析5.1.1自下而上分析自下而上分析bdbaceSABAabbcdeaAbcde(Ab)aAcde(AAb)aAcBe(Bd)S(SaAcBe)从输入字符的角度而言从输入开始逐步进行“归约”直至归约到文法的开始符号从语法树的角度而言从语法树的末端开始步步向上“归约”直到根结5.1.2自下而上分析法的基本思想自下而上分析法是一种“移进-归约”法基本思想用一个寄

2、存符号的先进后出栈把输入符号一个一个地移进到栈里当栈顶形成某个产生式的候选式时，把栈顶的这一部分替换成(归约为)该产生式的左部符号5.1.3先进后出栈例：设文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进-归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaS5.1.4移进-归约分析例：设文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进-归约”分析。5.1.5归

3、约的语法树分析法分析树和语法树不一定一致自下而上分析过程边输入单词符号，边归约核心问题识别可归约串bdbaceSABA5.1.6规范归约简述定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语一个句型的最左直接短语称为该句型的句柄5.1.7规范归约例一例：文法G[E]：E→E+T

4、TT→T*F

5、FF→(E)

6、–F

7、id考虑文法G[E]上的句子id1+id2*id3其最右推导和分析树如图

8、5.1(a)、(b)所示图5.1id1+id2*id3的最右推导、分析树与短语(a)最右推导；(b)分析树；(c)短语5.1.7.1归约的分析树分析树的叶子与短语、直接短语和句柄有下述关系短语以非终结符为根的子树中所有从左到右排列的叶子直接短语只有父子关系的树中所有从左到右排列的叶子树高为2句柄最左边父子关系树中所有从左到右排列的叶子句柄是唯一的5.1.7.2短语以非终结符为根的子树中所有从左到右排列的叶子从文法开始符号经过0步推导得到E1，从E1经过若干步推导得到id1+id2*id3，所以id1+id2*id3是句

9、型id1+id2*id3相对于E1的短语id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语，因为找不到任何一个非终结符，它的子树中的所有叶子构成id1+id25.1.7.3直接短语与句柄只有父子关系的树中所有从左到右排列的叶子从考虑推导E1E2+id2*id3T2+id2*id3F1+id2*id3id1+id2*id3id1是相对于非终结符E2、T2和F1的短语特别地，相对于F1的直接短语，也是句柄EFFTTTi1+*EFi3i25.1.8规范归约例二例：考虑文法G[E]ET

10、E+TT

11、F

12、T*FF(E)

13、I和句型i1*i2+i3在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。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句型归约

14、规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeSbdbaceSABA5.1.2规范归约简述定义：假定是文法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显然这是一个最右推导。规范归约是关于是一个最右推

15、导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。规范归约的中心问题：确定句型的句柄。5.1.2规范归约简述最右推导，推导的每一步结果都是一个右句型。该推导即分析树“剪句柄”的全过程。图3.18剪句柄的过程(a)句子；(b)剪去b之后；(c)剪去Abc之后；(d)剪去d之后；(e)开始符号5.1.3符号栈的使用与语法树的