《自低而上的优先分析法》由会员分享，可在线阅读，更多相关《自低而上的优先分析法（67页珍藏版）》请在金锄头文库上搜索。
1、*1第六章 自底向上的优先分析法自底向上语法分析概述 简单优先分析 算符优先分析课前思考 什么是自下而上语法分析的策略？ 什么是移进-归约分析？ 移进-归约过程和自顶向下最右推导有何关系？ 自下而上语法分析成功的标志是什么？ 什么是可归约串？ 移进-归约过程的关键问题是什么？ 如何确定可归约串？ 如何决定什么时候移进，什么时候归约？ 什么是算符文法？什么是算符优先文法？ 算符优先分析是如何识别可归约串的？ 算符优先分析法的优缺点和局限性有哪些？ 语法分析 推导导 自上而下的语语法分析过过程 预测预测 分析程序（最左推导导） 注：要求文法是LL(1)文法 归约归约 自下而上的语语法分析过过程 简
2、单优简单优 先分析法，算符优优先分析法，LR 分析法学习目标算符优先分析法是自下而上（自底向上）语法分析的一种， 尤其适应于表达式的语法分析，由于它的算法简单直观易于 理解，因此，也是学习其他自下而上语法分析的基础。通过 本章学习应掌握： 对给定的文法能够判断该文法是否是算符文法 对给定的算符文法能够判断该文法是否是算符优先文法 对给定的算符文法能构造算符优先关系表，并能利用算符 优先关系表判断该文法是否是算符优先文法。 能应用算符优先分析算法对给定的输入串进行移进-归约分 析，在分析的每一步能确定当前应移进还是归约，并能判断 所给的输入串是否是该文法的句子。 了解算符优先分析法的优缺点和实际
3、应用中的局限性。学习指南 算符优先分析法是自下而上语法分析的一种， 它的算法简单、直观、易于理解，所以通常作 为学习其它自下而上语法分析的基础。为学好 本章内容，应复习有关语法分析的知识，如： 什么是语言、文法、句子、句型、短语、简单 短语、句柄、最右推导、规范归约基本概念。短语、直接短语、句柄对于文法GS， 如果S A且A 则称是句型相对 于非终结符A的短语。 若有A 则称是句型相对于A或规则 A的直接短语。一个句型的最左直接短语称为该句型的句 柄。 自下而上的语法分析过程 自下而上的语法分析过程思想 自下而上的语法分析过程是一个最左归约的过程， 从输入串开始，朝着文法的开始符号进行归约，直
4、 到到达文法的开始符号为止的过程 注意：输入串在这里是指从词法分析器送来的单词 符号组成的二元式的有限序列自底而上语法分析比自顶向下语法分析更有效率， 对语法的限制更少*8 工作方式：“移进-归约”方式 即：自左到右把输入串的符号一个一个移 进栈，在移动过程中不断查看栈顶符号串 ，一旦形成某个句型的句柄时，就将此句 柄用相应的产生式左部替换（归约），若 再形成句柄，就继续替换，直到栈顶不再 形成句柄为止。然后继续移进符号，重复 上面的过程直到栈顶只剩下文法的开始符 号，输入串读完为止，这样就认为识别了 一个句子。*9“移进-归约”法的栈实现自顶顶向下：初始：分析栈栈：#S 输输入串:a1a2a
5、n#分析过过程：用产产生式的右部按反序进栈进栈 替换换左部 。 结结束： # #（成功）自底向上：初始：分析栈栈：# 输输入串:a1a2an#分析过过程：自左至右把输输入符号串W的符号一一 移进栈进栈 里，一旦发现栈顶发现栈顶 的一部分符号形成一个 可归约归约 串，就把栈栈中这这个子串用相应应的归约归约 符号 替换换。 结结束： #S #（成功）四类操作：移进、归约、接受、出错处理。 移进 读入一个单词并压入栈内，读头后移 归约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编 号 接受 移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符
6、 出错处理*11文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B da b b c de步骤符号栈输入符号串动作1） # abbcde# 移进2） #a bbcde# 移进A3） #ab bcde# 归约(Ab)4） #aA bcde# 移进A5） #aAb cde# 归约(AAb)6） #aA cde# 移进7） #aAc de# 移进B8） #aAcd e# 归约(Bd)9） #aAcB e# 移进11） #S # 接受S10） #aAcBe # 归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-归约分析过程*12 归约过
7、程恰好是最右推导的逆过程 最右推导称为规范推导，规范推导得到的句型称为 规范句型。规范归约也称最左归约。 规范归约定义： 假定是文法G的一个句子，我们称序列n, n-1, 0是的一个规范归约。如果此序列满足：1、 n= 2、 0为开始符号。3、对任何i，0a,归约Aa5） #b(A a)b# A=a,移进6） #b(Aa )b# a=),移进7） #b(Aa) b# )b,归约BAa)8） #b(B b# Bb,归约A(B9） #bA b# A=b,移进 10） #bAb # b#,归约SbAb11） #S # 接受对输入串b(aa)b#的简单优先分析过程简单优先关系矩阵*236.2.3简单优
8、先分析法的算法步骤 将输入符号串a1a2an#依次逐个存入符号栈S 中，直到遇到栈顶符号ai的优先性 下一个待输 入符号aj为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找 句柄的头符号ak，即找到ak-1 ak为止。 由句柄akai在文法的产生式中查找右部为 akai的产生式，若找到则用相应左部代替句 柄，若找不到则为出错。 重复1，2，3步，直到栈中只剩开始符。 简单优先分析法的优缺点 优点：技术简单 缺点：适用范围小，分析表尺寸太大*256.3 算符优先分析 算符优先分析法 所谓算符优先分析法就是仿效四则运算的计算过程 而构造的一种语法分析方法 算符优先分析法的特点： 简单直观，特别方
9、便于表达式分析，易于手工实现 ，是自下而上的归约过程，但未必按照句柄归约 算符优先分析法的关键 规定算符（终结符）的优先级及结合性质 例如：8+7*6的运算*26 算符优先分析的基本思想 只考虑算符（广义为终结符）之间的优先关 系对输入串i1+i2*i3的归约过程可表示为 例,若有文GS： (1) E E+E (2) E E*E (3) E i*286.3.1 直观算符优先分析 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先 级别和同一级别的结合性 算符间的优先关系表示规定如下：a b 表示a的优先性低于b。a b 表示a的优先性等于b，即与b
10、相同。a b 表示a的优先性高于b。注意：当有关系a b时，却不一定有关系b a，当有关系a b时，却不一定有b a*30如何确定算符优先关系？（1）i的优先级最高（2）优先级次于i，右结合（3）*和/优先级次之，左结合（4）+和-优先级最低，左结合（5）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括 号的优先性大于外括号（6）#的优先性低于与其相邻的算符文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i算符优先关系表*31文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i步骤符号栈输入符号串动作1） # i+i*i# #+,归约3） #E +i*i# #*
11、,归约6） #E+E *i# +#,归约9） #E+E*E # +#,归约 10） #E+E # #,归约11） #E # 接受对输入串i+i*i的算符优先分析过程算符优先关系表归约成功标志：栈中只剩#E，输入符号串剩#*326.3.2 算符优先文法的定义 定义6.1 如果不含空产生式的上下文无关文法 G 中没有形如 ABC的产生式，其中B, CVN，则称G 为算符文法（OG）。 例如：表达式文法EE+E|E*E|(E)|i 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。（数学归纳法） 性质2：如 Ab 或 bA 出现在算符文法的句型 中，其中AVN, bVT, 则中任何含b的短语
12、必含有A。（反证法） 注意：含b的短语必含A，含A的短语不一定含b。 *34算符优先关系的定义6.2在OG中 定义 （算符优先关系） a b G中有形如Aab或A aBb. 的产生式。 a b G中有形如A aB的产生式，而 B b.或B Cb a b G中有形如A Bb的产生式，而B a或B aC规定 若 S a 或 S Ba 则 # aS a 或 S aB 则 a # 由语法树结构决定优先性 *36算符优先文法的定义6.3 在一不含产生式的OG文法G中，若任意两个终结符间至多有一种算符优先关系 存在，则称G 为算符优先文法(OPG)。 EE+E|E*E|(E)|i 不是算符优先文法。 结论
13、 算符优先文法是无二义的。*376.3.3 算符优先关系表的构造 由定义直接构造 由关系图法构造算符优先关系表（自学 ）*38 首先引入两个概念 FIRSTVT(B)=b|B b或B Cb. 对于非终结符B，其往下推导所可能出现的首个 算符 LASTVT(B)=a|B a或B . aC 对于非终结符B，其往下推导所可能出现的最后 一个算符*39如何计算算符优先关系1) 关系 直接看产生式的右部，若出现了 A ab或A aBb,则a b 2) 关系 求出每个非终结符B的FIRSTVT(B) 若AaB,则bFIRSTVT(B),a b 3) 关系 求出每个非终结符B的LASTVT(B) 若ABb,则aLASTVT(B),a b例：设文法G的产生式为：(1)SaAcBe (2)AAb
