第5章 自底向上的句法分析.ppt

文档介绍：5 自底向上的分析方法
思想：从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。
核心：寻找句型中的“可归约串”进行归约，用不同的方法寻找可归约串，就可获得不同的分析方法。
移进-归约分析器
思想：对输入符号串自左向右进行扫描，并将输入符号逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的可归约串时，（对应某产生式的右部），就用该产生式的左部非终结符代替该栈顶符号串，完成一次归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。
动作
移进：把下一个输入符号压栈成为栈顶。
归约：语法分析器知道句柄的右端已在栈顶。它必须在栈中确定句柄的左端，并选择正确的非终结符替代句柄。
接受：语法分析器宣告分析成功。
出错：语法分析器发现了一个错误，并调用错误恢复程序进行错误处理。
例如，文法G[S]为：
SaAbB
Ac∣Ac
Bd
试对输入串accbd进行分析，检查该符号串是否是G[S]的一个句子。
对输入串accbd自底向上的分析过程
步骤
分析栈
句 柄
输入串
动 作
1
#
accbd#
移进
2
#a
ccbd#
移进
3
#ac
c
cbd#
归约(A→c)
4
#aA
cbd#
移进
5
#aAc
Ac
bd#
归约(A→Ac)
6
#aA
bd#
移进
7
#aAb
d#
移进
8
#aAbd
d
#
归约(B→d)
9
#aAbB
aAbB
#
归约(S→aAbB)
10
#S
#
接受
SaAbB
Ac∣Ac
Bd
自底向上构造分析树的过程
在这里每一步的“可归约串”是句柄。句柄的“最左”特征，这一点对于“移进－归约”来说很重要，因为句柄的“最左”性和分析栈的栈顶两者是相关的。对于规范句型来说，句柄的后面不会出现非终结符。基于这一点，我们可用句柄来刻画“移进－归约”过程的“可归约串”。因此，规范归约的实质是，在移进过程中，当发现栈顶呈现句柄时就用相应产生式的左部符号进行替换(即归约)。
句柄
一个字符串的“句柄”是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。
匹配某个产生式A右部的最左输入子串不一定是句柄，因为用这个产生式归约产生的串不能归约成开始符号。
如果文法是二义性的，则句柄不一定唯一，因为可能有不止一个最右推导。
句柄裁剪
句柄代表了由一个内节点和其所有子节点组成的最左简单子树。
在句型中，把归约到一个非终结符A可以想象成“裁剪句柄”，即把语法树中内节点A的所有子孙节点删除。之后，A成为新的叶节点。
通过“裁剪句柄”可以得到最右推导的逆过程。
如果w是文法的一个句子，有：
S=012n-1n=w
为了构造推导的逆过程，关键是在i中寻找句柄i，并用产生式Aii的右部代替得到i-1  i。
修剪语法树实现归约