编译原理_05自底向上的语法分析方法.ppt

xzh 第6章 自底向上优先分析法 主要内容 6.1 自底向上优先分析概述 6.3 算符优先分析法 课题：自底向上分析方法、算符优先文法 目的要求： 1.理解自底向上的语法分析方法的基本思想； 2.掌握算符文法、算符优先文法的定义和性质 教学重点： 1.优先分析法的基本思想和术语； 2.算符文法、算符优先文法的定义和性质 教学难点 ： 算符优先关系的定义 教学课时：2 教学方法：多媒体教学 教学内容和步骤 ：（如下） 第 十二 讲 自底向上分析方法，也称移进归约分析法 实现思想（是推导的逆过程）： 对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。 自底向上分析方法的基本思想 例1：文法: S?aAcBe A ?b A ?Ab B ?d 输入串abbcde#分析 最右推导： S?aAcBe ?aAcde ?aAbcde ?abbcde 规约分析过程如下： 接受 # #S 11 规约 S→aAcBe # #aAcBe 10 移进 e# #aAcB 9 归约 B→b e# #aAcd 8 移进 de# #aAc 7 移进 cde# #aA 6 归约 A→Ab cde# #aAb 5 移进 bcde# #aA 4 归约 A→b bcde# #ab 3 移进 bbcde# #a 2 移进 abbcde# # 1 动作 输入符号串 符号栈 步骤 上述的每一步规约可以构造一颗语法树： A b B d A A b b S A b b a c e B d A 问题的提出： ①在构造语法树的过程中，何时规约？ 当句柄出现在栈顶符号串中就可以规约。 ②如何知道在栈顶符号串中已经形成句柄？ 通过自底向上的分析算法来解释（优先关系） 优先分析法又可分简单优先分析法和算符优先分析法。 ①简单优先分析法（规范归约）－对文法按一定原则求出所有文法符号间的优先关系； ②算法优先分析法（不规范归约）－规定算符之间的优先关系） 6.1 自底向上优先分析法概述 6.3 算符优先分析法 算符优先优先分析法 只规定算符（终结符）之间的优先关系。在归约过程中只要找到句柄就归约，不必考虑归约到哪个非终结符，因此不是规范归约。 特点：速度快，特别适合于表达式的分析 通过算符之间的优先关系来确定句柄 先看一个例题： 例. 已知文法G[E]： E→E+E E→ E*E E→ i 输入串i+i*i ，归约过程如下 步骤 符号栈 输入符号串 优先关系 1） # i+i*i# #i 移进 2） #i +i*i# #i+ 规约 3） #E +i*i# #+ 移进 4） #E+ i*i# +i 移进 5） #E+i *i# +i* 规约 6） #E+E *i# +* 移进 7） #E+E* i# *i 移进 8） #E+E*i # *i# 规约 9） #E+E*E # +*# 规约 10） #E+E # #+# 规约 11） #E # 接受 动作 分析可知：若只从移进—归约的角度来考虑， 在第6步