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

国防科技大学计算机系602教研室
语法分析的方法:
自下而上分析法(Bottom-up)
基本思想:从输入串开始,逐步进行“归约”,直到文法的开始符号。即从树末端开始,构造语法树。所谓归约,是指根据文法的产生式规则,把产生式的右部替换成左部符号。
算符优先分析法:按照算符的优先关系和结合性质进行语法分析。适合分析表达式。
LR分析法:规范归约
国防科技大学计算机系602教研室
归约
采用“移进-归约”思想进行自下而上分析。
基本思想:用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
国防科技大学计算机系602教研室
国防科技大学计算机系602教研室
b
d
b
a
c
e
S
A
B
A
分析树和语法树不一定一致。
自下而上分析过程:边输入单词符号,边归约。
核心问题:识别可归约串
国防科技大学计算机系602教研室
规范归约
定义:令G是一个文法,S是文法的开始符号,假定是文法G的一个句型,如果有
且
则称是句型相对于非终结符A的短语。
特别是,如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。
国防科技大学计算机系602教研室
在一个句型对应的语法树中,以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语,如果子树只有两代,则该短语就是直接短语。
E
F
F
T
T
T
i1
+
*
E
F
i3
i2
国防科技大学计算机系602教研室
定义:假定是文法G的一个句子,我们称序列
n, n-1,,0
是的一个规范归约,如果此序列满足:
1 n= 
2 0为文法的开始符号,即0=S
3 对任何i,0  i  n, i-1是从i经把句柄替换成为相应产生式左部符号而得到的。
国防科技大学计算机系602教研室
把上例倒过来写,则得到:
S  aAcBe aAcde  aAbcde  abbcde
显然这是一个最右推导。
规范归约是关于是一个最右推导的逆过程
最左归约规范推导
由规范推导推出的句型称为规范句型。
国防科技大学计算机系602教研室
算符优先分析
四则运算的优先规则:
先乘除后加减,同级从左到右
考虑二义文法文法G(E):
G(E): E  i| E+E|E-E|E*E|E/E|(E)
它的句子有几种不同的规范规约。
归约即计算表达式的值。归约顺序不同,则计算的顺序也不同,结果也不一样。
如果规定算符的优先次序,并按这种规定进行归约,则归约过程是唯一的。
国防科技大学计算机系602教研室
起决定作用的是相邻的两个算符之间的优先关系。
所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”和进行归约。