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

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

1、第五章语法分析—自下而上分析主要内容：5.1自下而上分析基本问题5.2算符优先分析5.3LR分析概述5.4LR(0)分析5.5SLR(1)分析5.6LR(1)分析5.7LALR(1)分析5.8二义文法的应用8/7/20212中南大学软件学院陈志刚5.1自下而上分析基本问题自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合

2、分析表达式。LR分析法：规范归约8/7/20213中南大学软件学院陈志刚例：G(E)：Ei

3、E+E

4、E-E

5、E*E

6、E/E

7、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE8/7/20214中南大学软件学院陈志刚一、归约采用“移进－归约”思想进行自下而上分析。基本思想：设计一个堆栈，把符号串从左至右压入栈中，判别栈顶符号是否为某一个产生式的右部，若是则把栈顶的这一部分替换成(归约为)该产生式的左部符号。可归约串在算符优先分析法中即为最左素短语，在规范归约中是句柄。最左归约是最右推导的逆过程，最左归

8、约称为规范。8/7/20215中南大学软件学院陈志刚例：设文法G(S)：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae8/7/20216中南大学软件学院陈志刚8/7/20217中南大学软件学院陈志刚二、分析树语法分析过程可用一棵语法分析树表示出来。自下而上分析过程：边输入单词符号，边归约。即，在自下而上分析的每一步，都可画出一棵子树，随着归约的完成，便最终形成

9、一棵分析树。如果文法无二义，分析树恰好等同于语法树。核心问题：识别可归约串bdbaceSABA8/7/20218中南大学软件学院陈志刚三、规范归约定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别地，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。8/7/20219中南大学软件学院陈志刚例：考虑文法G(E)：ET

10、E+TTF

11、T*FF(E)

12、i和句型i1*i2+i3：EE+TE+FE

13、+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句柄：i18/7/202110中南大学软件学院陈志刚在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i28/7/202111中南大学软件学院陈志刚可用句柄来对句子进行归约句型归约规则abbcde(2)AbaAbcde(3)AAb

14、aAcde(4)BdaAcBe(1)SaAcBeS8/7/202112中南大学软件学院陈志刚定义：假定是文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1、n=2、0为文法的开始符号，即0=S3、对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。8/7/202113中南大学软件学院陈志刚把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。最右推导常被称为规范推导。容易看到，规范归约是关于

15、的一个最右推导的逆过程。因些，规范归约也称最左归约。由规范推导推出的句型称为规范句型。8/7/202114中南大学软件学院陈志刚bdbaceSABAdbaceSABAdaceSABaceSABS8/7/202115中南大学软件学院陈志刚四、符号栈的使用栈是语法分析的一种基本数据结构。’#’作为栈底符号。初始状态：栈＃输入串ω#自左至右把输入符号一一进栈，一旦栈顶形成句柄，就把其归约，直至栈顶不再形成句柄为止。然后继续移进，重复上述过程，直至形成栈＃S,输入串＃。若达到上述状态，则表示分析成功，否则输入串不是句子。8/7/

16、202116中南大学软件学院陈志刚步骤符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*i2+i3#进例：考虑文法G(E)：ET

17、E+TTF

18、T*FF(E)

19、i输入串为i1*i2+i3，分析步骤为：8/7/202117中南大