第6章自底向上优先分析法
概述
•自底向上分析法，也称移进-归约分析法，或自下而上分析。
•自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规
范推导，自左向右的归约过程也称规范
归约。
例6.1G[S]：(1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
容易看出对输入串abbcde的最右推导是：S=>aAcBe
=>aAcde => aAbcde => abbcde 。
它的逆过程即归约过程。
基本问题
•如何找出进行直接归约的简单短语？
•将找到的简单短语归约到哪个非终结符号？
基本方法
•基本都采用移入-归约方法。
•使用一个栈来存放归约得到的符号。
•在分析的过程中，识别程序不断地移入符号。
移入的符号暂时存放在一个栈中。
一旦在已经移入的（和归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。
基本方法（续）
•归约中的动作有4类
–移入：读入一个符号并把它归约入栈。
–归约：当栈中的部分形成一个句柄（栈
顶的符号序列）时，对句柄进行归约。
–接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执
行接受动作。
–当识别程序觉察出错误的时候，表明输
入符号串不是句子。
进行错误处理。
例子
i
*i+i i*i+i i E::=i E
*i+i E*i+i E*
i+i E*i+i E*i
+i E*i+i i E::=i E*E
+i E*E+i E*E E::=E*E E
+i E+i E+i
E+i i E::=i E+E
E+E E+E E::=E+E
E 文法G E [E]:E::=E+E|E*E|(E)
输入符号串：i*i+i
已处理未处理句型句柄规则
例子的解释
•当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。
•一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。
将句柄出栈，然后将归约得到的非终结符号压栈。
•如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。
•在例子中，发现句柄和归约是人为干预的结果。
所以移入-归约不是实际可运行的技术，而是技术的模板。
简单优先分析技术
•基本思想：
–每次察看句型中相邻的两个符号。
通过两个符号的优先关系判定出前一个符号是句柄的尾。
然后，反向找出句柄的头。
这样我们就找到了一个句柄。
U
S0…S j-1S j S j+1S j+2… …S i-1S i S i+1…S n
优先关系的定义
•Sj≡Si：当且仅当G中有规则U::=…SjSi…•Sj≤Si：当且仅当U::=…SjV…，且
V =>+ Si…；
•Sj≥Si：当且仅当U::=…VW…，其中V和W分别满足
V =>+…Sj和
W =>+ Sj…且Sj为终结符号。
优先关系的例子
•文法：Z::=bMb M::=(L|a L::=Ma)•语言：{bab, b(aa)b, b((aa)a)b, …}•可以从语法树里面到处部分优先关系。
b M b
a
Z
b ≤a a ≥b b M b
Z
(L
b ≤(
(≡L
L ≥b
优先矩阵
•可以将优先关系填写到一个矩阵，得到优先矩阵。
(将矩阵作为关系的表示形式）
Z M L a b() Z
M==
L>>
a>>
(<=<<
b=<< )>>
=
识别过程(例子)
•文法: G5.2
Z::=bMb M::=(L | aL::=Ma)•输入: b((aa)a)b
•过程:
# b ( ( a a ) a ) b #
< < < < >句柄: a 归纳为M
# b ( ( M a ) a ) b #
< < < < = = >句柄: M a) 归纳为L # b ( ( L a ) b #
< < < = > 句柄: (L 归纳为M
识别过程(例子续)
# b ( L b #< < = >句柄: (L 归约为M # b ( M a ) b #< < < = = >句柄: Ma) 归约为L # b ( M a ) b #< < < = = >句柄: Ma) 归约为L
# b M b #< = = >
句柄: bMb 归约为Z
# b ( L b #< < = >句柄: (L 归约为M
例子
步骤栈关系Next余下部分动作0#≤b(aa)b#移入1#b≤(aa)b#移入2#b(≤a a)b#移入3#b(a≥a)b#归约4#b(M≡a)b#移入5#b(Ma≡)b#移入6#b(Ma)≥b#归约7#b(L≥b#归约8#bM≡b#移入9#bMb≥##归约10#Z##接受
简单优先文法
•定义如果某个文法满足：
–字母表中的任意两个符号之间至多有一种
优先关系成立。
–任何两个规则的右部不相同。
那么称这个文法为简单优先文法。
•第一点保证可以识别出句柄.
•第二点保证可以确定归约到哪个非终结符号。