文档介绍：第五章语法分析——自下而上分析
所谓自下而上分析法就是从输入串开始,逐步进行“归约”,直至归约到文法的开始符号;或者说从语法树的末端开始,步步向上“归约”,直到根结。
自下而上分析基本问题
我们先讨论自下而上分析的一些基本思想和基本概念:
自下而上分析的关键问题是寻找可归约串。对“可归约串”概念的不同定义,就形成了不同的自下而上的分析方法。在算符优先分析法中我们用“最左素短语”来刻画“可归约串”,在“规范归约”中,则用“句柄”来刻画“可归约串”
规范归约简述
在这一部分应掌握短语和直接短语和句柄三个重要概念
第五章语法分析--自下而上分析
令G是一个文法,S是文法的开始符,假定是文法G的一个句型,如果有:
S*A且 A + 则称是句型相对于非终结符A的短语。特别是,如果有
A 则称是句型相对于规则A的直接短语,一个句型的最左直接短语成为该句型的句柄。注意:短语的两个条件是:
S*A且 A +
[]考虑文法:
E T|E+T
T F|T*F
F i | (E) () 对于句型i*i+i 推导
解: E→E+T→T+T→T*F+T→F*F+T→i*F+T→i*i+F
→ i*i+i
第五章语法分析--自下而上分析
尽管有E +i+i 但是, i+i 并不是该句型的一个短语,因为不存在从E(文法开始符)到i*E的推导。但是,i, i*i,和i*i+ i 自身都是句型i*i+i 的短语。而且为为直接短语。
[例5。2] 上题文法(5。2)的另一个句型E+T*F+i 的短语有 E+T*F+i ,E+T*F, T*F,和i. 其中T*F和i为直接短语, T*F为句柄。
解:E→E+T→E+T+T→E+T*F+T→E+T*F+F→
E+T*F+i
第五章语法分析--自下而上分析
关于规范归约精确的说,假定是文法G的一个句子,我们称序列
n n-1 n-2, 。。。, 0
是的一个规范规约,如果此序列满足:
(1) n = ;
(2) 0 为文法的开始符,即0 =S;
(3)对于任何的i, 0<i <=n, i-1 是从 i 经把句柄替换为相应产生式的左部符号而得到的。
容易看到,规范归约是关于α的一个最右推导的逆过程。因此规范归约也成最左归约。
在形式语言中,最右推导常被称为规范推导。由规范推导所得的句型称为规范举行。如果文法G是无二义的,那么规范推导的逆过程必是规范归约。
符号栈的使用与语法树的表示
本节重点掌握符号栈的使用请阅读P87相应段落。
现在举个例子以加深对这一节的理解。
第五章语法分析--自下而上分析
[]:对于文法()输入串i1*i2+i3 的分析(规范归约)步骤可表示如下:
步骤符号栈输入串动作
0 # i1*i2+i3# 预备
#i1 *i2+i3# 读入i1
#F *i2+i3# 归约,Fi
#T *i2+i3 # 归约,T F
#T* i2+i3# 读入
#T*i2 +i3# 读入
#T*F +i3# 归约,F i
#T +i3# 归约,T T*F
#E +i3# 归约,E T
# E+ i3# 读入
#E+i3 # 读入
#E+F # 归约, F i
#E+T # 归约, T F
#E # 归约,E E+T
#E # 接受
第五章语法分析--自下而上分析
算符优先分析
算符优先文法及优先表的构造
一个文法,如果它的任何产生式的右部都不含量个相继(并列)的非终结符,即不含如下形式的产生式右部:
…QR…则我们称该文法为算符文法。
在后面的定义中,a、b代表任意终结符;P、Q、R代表任意非终结符;‘…’代表有终结符和非终结符组成的任意序列,包括空字。
假定G是一个不含--产生式的算符文法。对于任何一对终结符a、b,我们说:
(1) ab 当且仅当文法G中含有形如P …ab…或P …aQb…的产生式;
(2) a<b当且仅当G中含有形如P …aR…的产生式,R而R+b…或R +Qb…;
(3) a>b当且仅当G中含有形如P …Rb…的产生式, R而R+…a或R +…aQ;
第五章语法分析--自下而上分析
如果一个文法G中的任何终结符对(a, b )至多只满足下述三关系之一:
a=·b, a<·b, a·>b 则称G是一个算符优先文法。
应掌握算符优先表的构造方法。
通过检查G的每个产生式的每个候选式,可以找出满足a=·b的终结符对。为了找出所有满足关系<·和·>的终结符对,我们需要对