南京大学计算机系 赵建华语法分析 ----自底向上的分析技术引言
自底向上技术是从输入符号出发，每一步对相应举行中的某个简单短语（或其他短语）
进行规约。如果能够最终规约到识别符号，
那么就说明这个输入符号串是句子。
要解决的问题
– 如何找出简单短语（或其它某特定类型的短语）？
– 将短语规约成哪个非终结符号？
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术引言（续）
讨论的前提
– 对象是上下文无关文法以及相应的语言。
– 文法是压缩了的。
一般采用移入 -归约方法（例子 5.1），归约过程中有四种不同的动作：
– 移入：尚未发现可归约的短语，继续读入符号。
– 归约：发现了可归约的短语，将短语归约为特定非终结符号。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术引言（续）
– 接受：发现输入符号串是句子。
– 报错：发现归约过程没有办法继续，也就是输入符号串不是句子。
基本的实现是使用一个栈，如果输入的符号串是句子，那么将栈中的符号（自底向上）
序列和未扫描的符号并置后得到的必然是一个句型（ LR技术归约时例外）。在移入时，
将当前输入符号压入栈中。而归约的时候，
被归约的短语总是栈顶开始的一个符号串。
将此符号串替换为非终结符号完成归约。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术
试图通过考察句型中相邻两个符号的关系来确定句柄。
在从左到右扫描的时候，首先确定句柄尾部，
然后再回头（在栈中）确定句柄的头部。
确定句柄之后可以进行相应的归约。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术（续）
对于任何两个可能在句型中相邻出现符号 S1，
S2，其关系可以有如下三种：
– S1S2可以出现在同一个短语中。
– S1是一个简单短语的尾符号，而 S2紧跟在此短语的后面。
– S2是一个简单短语的头符号，而 S1在这个短语的紧前面。
对应于语法树，这三种情况分别表示了,S1,S2
具有同一个父亲,S2和 S1的父亲具有同一个父亲，
以及 S1和 S2的父亲具有同一个父亲 。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术（续）
将前面提到的关系分别记为,=,>和 <(因为不容易找到和书上相同的符号）。
如果对于任何一对符号，最多只可能出现前面的其中一种情况，那么我们可以得到分析这个文法的句子的方法。
显然，一个句型的简单短语就是最左的 >关系和它左边的最右的 <的关系所限定的子符号串。这就给出了确定句柄的方法。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术（续）
在选择句柄的时候使用如下的方法：
– 对于句型 S1…S j-1SjSj+1…S i-1SiSi+1…S n，如果子符号串 Sj-1SjSj+1…S i-1SiSi+1是满足 Sj-1<Sj,Sj=Sj+1,…,
Si-1=Si,Si>Si+1的最左的子符号串，那么它就是句柄。
这些关系，可以使用关系矩阵来表示。
具体的归约过程可以见例 5.3。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术（续）
优先关系的定义：
– Sj=Si iff 文法中有规则 U::=,..SjSi…
– Sj<Si iff 存在规则 U::=…S jV… 且 V HEAD+ Si
– Sj>Si iff 存在规则 U::=…VW… 且 V TAIL+ Sj 以及
W HEAD* Si。
定理 5.1-5.3证明了这个定义和前面的定义是等价的，但是具有更加好的操作性。可以由这个定义得到求解这些关系的算法。
南京大学计算机系 赵建华语法分析 ----自底向上的分析技术简单优先分析技术（续）
优先关系的形式化定义给出了相应的求解优先关系的方法。