ch6自底向上优先分析方法.ppt

第六章自下而上优先分析法
所有的自下而上分析移进-归约法的原理.
基本思想是用一个寄存文法符号的先进后出栈，将输入符号按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时（对应于某条规则右部）就进行一次归约，“#”和文法的开始符号，,就不是正确的句子，报告错误.
1
设 G =(VT,VN,S,P), α,β∈(VT∪VN)*, A→β∈P,αAw αβw
归约的过程是，已知αβw 和产生式 A→β，用产生式A→β左部 A 替换αβw 中的β，得到符号串αAw.
从输入符号串出发，每次从被归约的句型中找到一个产生式的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号。
归约
2
【例】文法G[S]对输入串 abbcde# 进行语法分析，检查该符号串是否是该文法的正确句子。
S→aAcBe
A→bA→Ab
B→d
3
S→aAcBe A→b A→Ab B→d
a
b
b
c
d
e
abbcde
aAbcde
aAcde
aAcBe
S
A
A
B
S
4
从例子中可以看出，一个句型中当含有多个子串可以匹配不同产生式的右部时，将有不同的归约过程，究竟应该对谁先归约呢？
5
一个句型的最左直接短语称为该句型的句柄，句柄是规范归约的可归约串。
假定α是文法 G 的一个句子，称序列αn,αn-1,αn-2,…,α0是α的一个规范归约，如果此序列满足：1)αn=α；α0为文法的开始符，即α0=S；2)对任何i，0＜i＜n, αi-1是从αi经把句柄替换为相应产生式的左部符号而得到的。
如果文法G是无二义的，规范归约是最右推导的逆过程，规范归约也称最左归约,最右推导也称规范推导。
结论：对规范句型来说，句柄的后面不会出现非终结符。因此，规范归约的实质是在移进过程中，发现栈顶呈现句柄时就用相应的产生式的左部符号进行替换。
规范归约简述
6
对输入串 abbcde 的最右推导过程是： SaAcBeaAcdeaAbcdeabbcde。
用语法树表示如下图所示：
7
用语法树表示规范归约过程如下图所示：它与最右推导的逆过程相对应。
8
非形式地，一个符号串的“句柄”是和一个规则右部匹配的子串，而且把它归约到该规则左部的非终结符,代表了最右推导逆过程的一步。
句柄
找句柄是非常重要的
在很多情况下，匹配某个规则 A 右部的最左输入子串  不是句柄，因为用这个规则归约产生的串不能归约到开始符号。
【例】对于串 aAbcde
b 是产生式 Ab 的右部,但 b 不是句柄。如果进行归约，得到 aAAcde，而 aAAcde 不能归约到 S.
因此我们必须更精确地定义句柄。
9
形式的说，右句型(最右推导可得的句型)γ的句柄是一个与规则 A→β和γ中的一个位置有关的，从这个位置开始往右可找到β，用 A 代替β得到γ最右推导的前一个右句型，即
如果 S  Aw  βw,
那么，在  后β是 βw 的句柄。
句柄右侧的 w 是未读入的终结符号。
句柄(续)
*
rm
rm
10