编译原理讲义
(第五章,语法分析 --
自底向上分析技术 )
南京大学计算机系赵建华概论
从输入符号出发，试图把它规约成识别符号。每一步都寻找特定得某个类型的短语（一般是简单短语）进行规约。
在分析过程中，每次规约的都是最左边的简单短语（或其它短语）。
从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。
基本问题
如何找出进行直接规约的简单短语？
将找到的简单短语规约到哪个非终结符号？
讨论前提
和自顶向下技术同样，不考虑符号的具体构成方式。
文法是压缩了的。
识别过程是从左到右，自底向上进行的。
一般都采用规范规约：每一步都是对句柄进行规约（特例除外）。
基本方法
基本都采用移入 -规约方法。
使用一个栈来存放规约得到的符号。
在分析的过程中，识别程序不断地 移入符号。移入的符号暂时存放在一个栈中。
一旦在已经移入的（和规约得到的）符号串中包含了一个句柄时，将这个句柄规约 成为相应的非终结符号。
基本方法（续）
规约中的动作有 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
文法 G5.1[E],E::=E+E|E*E|(E)
输入符号串,i*i+i
已处理符号 未处理符号 句型 句柄 规则例子的解释
当栈中的符号的栈顶部分还不能形成句柄时，
进行移入操作。
一旦 发现 栈顶部分形成了句柄的时候，对该句柄进行 规约 。将句柄出栈，然后将规约得到的非终结符号压栈。
如果输入是句子，则栈中的符号（从底到上）
和未处理的符号组成句型。
在例子中，发现句柄和规约是人为干预的结果。
所以移入 -规约不是实际可运行的技术，而是技术的模板。
简单优先分析技术
基本思想：
– 每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。
S0…S j-1SjSj+1Sj+2… …S i-1SiSi+1…S n
U
简单优先分析技术 (基本思想续）
我们要通过两个相邻符号 SiSi+1之间的关系来找到句柄：
– SiSi+1在句柄内：必然有规则 U::=…S iSi+1…
– Si在句柄内部，但是 Si+1在句柄之后：必然有规则 U::=…S i，且存在规范句型 …US i+1… 。
– 如果 Si+1在句柄内，而 Si在句柄外，那么必然存在规范句型 …S iU…,且 U::=Si+1… 。
优先关系
和树上的写法不一样，凑合用。
Si?Sj Si? Sj Si?Sj
注意,?,?,?之间不同于 =,>和 <。
由 Si? Sj不能导出 Sj?Si。
优先关系的例子
文法,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 | a L::=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
优先关系的定义
Sj?Si：当且仅当 G中有规则 U::=…SjSi…
Sj?Si：当且仅当 U::=…SjV…,且 V
HEAD+ Si；
Sj?Si：当且仅当 U::=…VW…,其中 V和
W分别满足 V TAIL+ Sj和 W
HEAD* Sj且 Sj为终结符号。
HEAD和 TAIL
U HEAD S 当且仅当 U::=S…
U TAIL S 当且仅当 U::=…S
HEAD+,HEAD*分别是 HEAD的传递闭包和自反传递闭包。
– U HEAD+ S当且仅当 U::=U1…,U1::=U2…,…,
Un::= S… 。
– U HEAD* S当且仅当 U=S或者 U HEAD+ S
TAIL+是 TAIL的传递闭包。
– U TAIL+ S当且仅当 U::=…U1,U1::=…U2,…,
Un::= …S
优先关系
定理 5.1 Sj? Si当且仅当 SjSi出现在某个规范句型的句柄中。
定理 5.2 Sj?Si当且仅当存在规范句型 …SjSi…,且 Sj是该句型的句柄的最后一个符号。
定理 5.3 Sj?Si当且仅当存在规范句型 …SjSi…,且 Si是该句型的句柄的第一个符号。
定理 5.1的证明
如果 SjSi出现在句柄中，当然有 U::=…SjSi…
如果有规则 U::=uSjSiv，
– 必然有某个符号串的推导使用了该规则。（假设文法是已压缩的）
– 根据该推导构造语法树。则必然存在一个结点标记为 U，其子结点为 uSjSiv。
– 根据语法树构造最左规约（每一步都对句柄进行规约）。那么上面的结点对应的一步就是将 uSjSi规约为 U。此时,uSjSiv为句柄。
定理 5.2的证明 (1)
如果 Sj?Si，
– 按照定义存在规则 U::=…VW…,V TAIL+ Sj，且 W
HEAD*S。
– 必然有句型 …VW…,由 TAIL+和 HEAD*的定义，必然存在句型 …vuSjSi…,且 V=>*vU=>vuSj,W=>Si… 。
– 构造相应的语法树，并且从语法树构造相应的规范推导。
uSj必然在某一步成为句柄。而此时由于 Si在 Sj的右面，
它必然还没有被规约。所以，当 uSj成为句柄的时候，其规范句型必然为 …uSjSi… 。
定理 5.2证明 (2)
如果存在规范句型 …SjSi… 且 Sj是某个句柄的最后符号,
– 考虑语法树中，同时包含有 Sj和 Si的最小子树。设其根结点为 U。而 U的子结点从左到右为 u。
– 短语 u的形状必然为 …VW…,且 V=>*…Sj 而
W=>*Si。这是因为如果有某个 u中的符号
X=>…SjSi…,那么以 X为根的子树才是最小的包含
Sj和 Si的子树。
– 显然，根据定义 Sj?Si。
优先关系的构造
根据优先关系的构造性的定义（定义 5.1），我们立刻可以得到构造算法。
的构造：直接对每个规则右部处理，没有右部 X1X2…X n，
都有 Xi? Xi+1。
的构造：由定义,Sj?Si可以得到
– 存在规则 U::=… SjV…,也就是 Sj? V。
– V HEAD+ Si。
– HEAD关系可以通过检查每个规则得到。
– 由此可以得到?就是 (?)(HEAD+)。因此?可以通过计算关系?和 HEAD的传递闭包。
优先关系的构造（续）
关系的构造：由定义,Sj?Si表示,
– 存在规则 U::=…VW… V?W
– V TAIL+ Sj Sj (TAIL+ )T V
– W HEAD* Si
– 将上面三个规则综合起来，可以得到?关系就是
(TAIL+)T? HEAD*
从上面的算法可以看到,?,TAIL,HEAD可以直接检查每个规则得到。因此，我们只需要有对关系的联接，闭包运算就可以得到上面的三个优先关系。
关系的 bool矩阵表示和运算
关系可以使用 bool矩阵来表示。对某个关系 R,SjRSi在矩阵中用 Bij=TURE来表示。
对于两个关系 R1,R2对应的矩阵 B1,B2，
B1和 B2的乘积矩阵对应的关系就是 R1和
R2联接运算结果。
关系闭包和 Warshall算法
Warshall算法是利用矩阵计算关系传递闭包的方法。计算 B的传递闭包的算法伪代码如下：
A = B;
for (i = 1; i<=n; i++)
for (j=1; j<=n; j++)
{
if (A[j,i]==1)
for(k=1; k<=n; k++)
A[j,k] = A[j,k]+A[i,k]
}
使用矩阵计算优先关系?
步骤 1：构造优先关系矩阵 B?
步骤 2：构造关系 HEAD的矩阵 BHEAD
步骤 3：使用 Warshall算法计算 BHEAD+
步骤 4：计算 B?BHEAD+
使用矩阵计算优先关系?
步骤 1：计算 TAIL的布尔矩阵 BTAIL
步骤 2：计算 BTAIL+，并将该矩阵转置得到
(BTAIL+)T。
步骤 3：构造优先关系矩阵 B?
步骤 4：构造 HEAD的矩阵 BHEAD。
步骤 5：计算 BHEAD+的矩阵，并由此得到
I+HEAD+的矩阵 BI+HEAD+。
步骤 6：计算 (BTAIL+ ) TB?BI+HEAD+。
需要在得到的矩阵中，把非终结符号对应列中的 1去掉。 (因为?的右边时终结符号）
计算优先关系的例子 P136
文法,S::=Wa W::=Wb W::=a
将文法中的符号按照 S,W,a,b排列。
BHEAD=
0100
0110
0000
0000
BHEAD+=
0110
0110
0000
0000
BTAIL=
0010
0011
0000
0000
(BTAIL+)T=
0100
0110
0000
0000
计算优先关系的例子 (续 )
B?=
0000
0011
0000
0000
B I+HEAD+=
1110
0110
0010
0001
B?=B?BHEAD+=
0000
0000
0000
0000
B?=(BTAIL+ ) TB?BI+HEAD+=
0000
0000
0011
0011
优先关系的冲突
当优先矩阵中出现值不唯一的元素时，
文法不适合使用优先识别技术来识别句型。
简单优先文法
定义 5.2 如果某个文法满足：
– 字汇表中的任意两个符号之间至多有一种优先关系成立。
– 任何两个重写规则的右部不相同。
那么称这个文法为简单优先文法。
第一点保证可以识别出句柄,
第二点保证可以确定规约到哪个非终结符号。
定理 5.4
一个简单优先文法是无二义性的，且其任何一个句型 Sm…Sn 的唯一句柄是满足条件：
Sj-1≤Sj≡Sj+1≡Sj+2≡… … ≡Si-1≡Si≥Si+1
的最左子符号串 SjSj+1Sj+2… …S i-1Si。
定理 5.4的证明
首先用反证法证明任何句型的句柄是唯一的。
– 句型必然有句柄，且这个句柄必然满足
Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡S i-1≡Si≥Si+1（句柄 1）
– 如果还有另外一个语法树，那么它对应的归约（称为归约过程 2）必然不是把上面的句柄作为一个整体规约的。
– 在归约过程 2中，当首次有句柄 1(包括 Sj-1和 Si+1)中间的某个符号 St作为句柄（句柄 2）的一部分被规约的时候，我们可以考虑以下的情况：（下一页）
定理 5.4的证明 (续 )
如果 t=j-1，那么由句柄 1,Sj-1≤Sj；由句柄 2,Sj-1≡Sj或
Sj-1≥Sj；矛盾！
如果 t=i+1，由句柄 1,Si≥ Si+1；由句柄 2,Si≤ Si+1或者 Si ≡ Si+1。
如果 i<= t <= j；那么
– Sj在句柄中：
– Si在句柄中：
– Sj和 Si都不在句柄中：
定理 5.4的证明 (续 )
简单优先文法的无二义性是显而易见的：
– 每个句型只有一个句柄。
– 句柄只能归约到确定的非终结符号。
该证明的实质就是：句柄 1和句柄 2相互重叠，重叠的边缘必然由优先关系的多重定义。
S0…S j-1SjSj+1Sj+2… …S i-1SiSi+1…S n
U
应用优先技术的困难与克服
简单优先技术只适应于简单优先文法。
实际上，一般的程序设计语言的文法都不是简单优先文法。比如四则运算表达式的文法。
可能的解决办法是：分离法（成层法）
简单优先分析技术的实现
识别过程,从左到右地扫描输入符号。已经扫描或归约得到的符号被存放在一个栈中。
每次扫描的时候，将当前符号 a和栈顶符号 S相比较。如果 S≥a表示已经碰到了一个句柄的尾。然后在栈里面向前（下）
找，直到找到句柄的头。此时找到右部为该句柄的规则进行归约。
简单优先分析技术流程图开始初始化
R=下一个输入符号栈顶 Si≥R? 把 R入栈找出栈中第一个满足 Sj-1≤Sj的值
AB
否是简单优先分析技术流程图 (续 )
A
寻找其右部和句柄匹配的规则存在这样的规则是句子？ 出错处理停止将句柄中的符号退去，
将规则的左部入栈。
B
是是否否例子
1 #b ≤ ( aa)b# 移入
2 #b( ≤ a a)b# 移入
3 #b(a ≥ a )b# 归约
4 #b(M ≡ a )b# 移入
5 #b(Ma ≡ ) b# 移入
7 #b(L ≥ b # 归约
8 #bM ≡ b # 移入
9 #bMb ≥ # # 归约
10 #Z # # 接受
0 # ≤ b (aa)b# 移入步骤 栈 关系 Next 余下部分 动作
6 #b(Ma) ≥ b # 归约优先函数
对于一个实际的程序设计语言的文法，
优先矩阵将会非常大。对于有 n个字汇的文法，矩阵的大小是 n?n
解决的方法是引入优先函数，将矩阵线性化。这里介绍的方法称为双线性优先函数法。
定义 5.3 优先函数
对于某个优先矩阵 M，如果存在两个函数 f和 g，它满足下列条件：
– 如果 Sj≡Si，那么 f(Sj)=g(Si)；
– 如果 Sj≤Si，那么 f(Sj)<g(Si)；
– 如果 Sj≥Si，那么 f(Sj)=g(Si)；
那么 f和 g称为 M的线性优先函数。
注意：
– 不是所有的矩阵都有优先函数的。
– 两个没有关系的符号之间的优先函数值也有大小。
优先函数的例子
Z M L a b ( )
Z
M = =
L > >
a > >
( < = < <
b = < <
) > >
=
Z M L a b ( )
1 7 8 9 4 2 8
1 4 2 7 7 5 9
f
g
优先函数的例子
下面的矩阵没有优先函数
≡
≡ ≥
≡
优先函数的构造（逐次加一法）
步骤 1：对所有符号 S∈ V，让 f(S)=g(S)=1
步骤 2：对于 Sj≤Si，如果 f(Sj)≥g(Si)，让 g(Sj)=f(Si)+1;
步骤 3：对于 Sj≥Si，如果 f(Sj) ≤ g(Si)，让 f(Sj)=g(Si)+1;
步骤 4：对于 Sj≡Si，如果 f(Sj) ≡ g(Si)，让
f(Sj)=g(Si)=max(f(Sj),g(Si));
步骤 5：重复步骤 2-4，直到过程收敛（所有的值都不再增长）。如果所有的值都大于 2n，那么不存在优先函数。
逐次加一法例子
Z M L a b ( )
1 1 1 1 1 1 1
1 1 1 1 1 1 1
f
g
Z M L a b ( )
1 1 1 1 1 1 1
1 2 1 2 1 2 1
f
g
考虑关系 ≤
逐次加一法例子（例子）
Z M L a b ( )
1 1 3 3 1 1 3
1 2 1 2 1 2 1
f
g
考虑关系 ≥
… … … …
最后结果
Z M L a b ( )
1 3 4 4 2 1 4
1 2 1 3 3 3 4
f
g
Bell有向图法
利用有向图构造优先函数。
基本思想：
– 利用优先关系建立 f和 g的各个值之间的关系。
– 利用有向图的弧表示各个值之间应该具有的大小关系。
– 优先函数通过计算 fi和 gi所能够到达的结点确定（如果 fi能够到达结点 gj，表示 fi的值必须不小于 gj的值）。
Bell有向图算法
步骤 1：作具有 2n个结点的有向图。标记分别为 f1,f2,… …,fn 和 g1,g2,… …,gn 。如果 Sj>Si或者 Sj=Si，那么从 fj到 gi画一条弧；如果 Sj<Si或者 Sj=Si，那么从 gi到 fj
画一条弧。
步骤 2：给每个结点一个数值，等于从该点出发沿弧所能到达的结点的个数。
步骤 3：检验这样的函数是否优先函数。
若否，则该优先关系不存在优先函数。
Bell有向图的例子
M )Z L a b (
M )Z L a b (
L≥a,L≥b,a ≥a,a≥b,)≥a,) ≥b
b≤a,b≤(,(≤M,(≤a,(≤(
M≡a,M≡b,a ≡),b ≡M,(≡L
定理 5.5
如果优先矩阵存在优先函数,那么使用 Bell有向图方法构造得到的函数就是优先函数。
首先证明：如果 Sj ≡Si，那么 fj=gi；如果 Sj≥ Si，那么
fj>=gi；如果 Sj≤Si，那么 fj<=gi。
– 该结论显然成立。这是因为如果 Sj ≡Si，那么有从 fj
到 gi和从 gi到 fj的弧。因此,fj可以到达的结点,gi
也可以到达，并且 gi的可以到达的结点,fj也可以到达。如果 Sj ≤Si，那么有 gi到 fj的弧，所以 fj可以到达的结点,gi也可以到达。因此 gi的值至少不比 fj小。
同样可以证明如果 Sj≥ Si，那么 fj>=gi。
定理 5.5的证明
然后证明：如果存在符号 Sj≥ Si且 fj=gi，那么不存在优先函数。
– 由有向图的构造可以知道,gi可以达到的结点,fj必然也可以达到。又由于 fj=gi，所以，由 gi必然也可以到达 fj（否则 fj要大于 gi)。因此，在 fj到 gi，再到 fj
的有一个圈。假设这个圈的结点为 n1=fj,n2=
gi,n3,…nk=fj 。考虑给 ni任意赋值：由弧的定义 ni的值必然不小于 ni+1的值，而且至少 n1的值大于 n2的值。因此，不可能有优先函数。
同样可以证明：如果 Sj ≤ Si且 fj=gi，也不存在优先函数。
Bell有向图的优点
非迭代过程；
再确定多步内可以完成；
改变对文法符号的排序时，优先函数不变。
Bell有向图法的矩阵方法
关系 R：如果 fj到 gi（ gi到 fj）或有一条弧，
那么 fj R gi(或 gi R fj)。
显然该关系 R的矩阵如下：
0 B ≥≡
0
0(B≥≡)T
B≥≡f
g
f g
Bell有向图法的矩阵方法 (续 )
那么关系 R传递闭包就表示了一个结点可以到达另外一个结点的关系。
使用 Warshall算法求解上述矩阵的传递闭包 B+，计算 B*=I+B+。
令每个结点对应的值为：该结点对应的行上的 1的个数。
检查该赋值是否是优先函数。若是，则得到函数，否则，该优先关系不存在优先函数。
结点排序函数
后继结点：如果 x,y∈ X，且存在一个弧的序列从 x到 y，那么 y是 x后继结点,x是
y的后继结点。如果弧序列长度为 1，那么 y是 x的直接后继。
用 σ(x)表示 x的后即结点的结合，用 σ1(x)
表示其直接后继结点的集合。
ND:X→{0,1,…|X|} 定义为 ND(x)=| σ(x) |
结点排序函数
任意一个函数 N:X→{0,1,…|X|},如果满足对于所有的 x,y,y∈ σ(x)都有 N(x)>N(y)，
那么称 N为结点排序函数。
定理 5.7 ND是结点排序函数，当且仅当 D
中没有回路。
Martin算法
步骤 1：作有向图，结点为 f1,f2,…fn,g1,g2,…gn 。并且，如果 Sj>Si，那么从 fj到 gi画一条弧；如果 Sj<Si，
那么从 gi到 fj画一条弧。
步骤 2：如果 Sj ≡Si，那么从 fj向 gi的后继作弧，也从 gi
向 fj的后继作弧。 重复这一个过程,直到这个过程没有新弧加入。
对于最后的有向图，令 f(Si)=ND(fi)，令 g(Si)=ND(Si)。
如果最后的有向图没有回路，那么所得到的函数就是优先函数，否则就没有优先函数。
Martin算法的例子
M )Z L a b (
M )Z L a b (
Martin算法例子
M )Z L a b (
M )Z L a b (
Martin算法的矩阵方法
步骤 1：构造布尔矩阵 B≤≥。此时的矩阵相当于画图时的第一步得到的图。
步骤 2：计算 B=C+B≤≥。其中 C为
I B ≡
(B ≡)T I
步骤 3：计算 B+。
步骤 4：计算各个行中的 1的个数。如果对于某个 i，
B[ii]=1表示图存在回路，优先函数不存在。
优先函数的缺点
信息的丢失，原来两个符号之间有 4中关系（大于，小于，等于，无关），引入优先函数之后，只有 3种关系。
信息的丢失错误的延迟发现。
见 P153页例子。
简单优先技术的局限性
文法的适用范围小。
虽然使用成层法可以使一些文法变成简单优先文法，但是
– 成层法的技术非常复杂。
– 当两个关系既有 ≤又有 ≥时，成层法无能为力。
如果使用高阶矩阵，将使得算法的内存需求更加大。
算符优先分析技术
简单优先技术对字汇表中的所有符号之间建立优先关系。但是，有些情况下，
不需要对所有两个符号之间建立优先关系。
算符优先分析技术只在部分符号（终结符号）之间建立优先关系。
算符优先分析技术基本思想
对于算术表达式，只需要按照操作符之间的优先关系，就可以确定运算的顺序。
不需要考虑操作数就可以对表达式进行分析。
例如,E+T*F。只需要知道 *的优先级高于 +，就可以知道 T*F时句柄。
在一般的文法中，终结符号的地位相当于操作符号。
算符文法
定义：如果文法中没有形状如
U::= …VW…
的规则，该文法称为算符文法。
算符文法的性质
定理 5.9 对于算符文法，不存在包含有相邻两个非终结符号的句型。
定理 5.10 如果 TU出现在句型中，其中 T
为终结符号,U为非终结符号，那么包含
T的短语也必然包含 U.
定理 5.11 如果 UT出现在句型中，其中 T
为终结符号,U为非终结符号，那么包含
T的短语也必然包含 U.
定理 5.9的证明
只需要证明：如果 x不包含两个相邻的非终结符号，且
x=>y，那么 y也不包含相邻的非终结符号。
假设 x=wUv，而 y=wuv。
– 那么由于 x不包含两个相邻的非终结符号，那么 w和
v中没有不相邻的非终结符号。
– 根据算符文法的定义,u中也不包含相邻的非终结符号。
– 根据假设,w的结尾不是非终结符号（否则,x中包含有相邻的非终结符号）。
– 同样,v的开始符号也不是非终结符号。
综上所述,y中不存在相邻的非终结符号。
定理 5.10,5.11的证明
假设 w=xvy是文法的句型，而 v是详相对于 V的短语。
那么 xVy也是句型。
如果 w中有两个相邻的符号 TU，且 T在 v中，而
U不在 v中。显然 U是 y的头符号。
因此 xVy中存在两个相邻的非终结符号 VU。
和定理 5.9矛盾。
定理 5.11的证明和定理 5.10类似。
算符优先关系
定义 5.8 设文法 G是一个算符文法,Tj和 Ti是两个任意的终结符号，而 U,V,W∈ VT，定义算符优先关系如下：
– ≈：当且仅当文法 G中存在形如,U::=…TjTi…
或 U::=…TjVTi… 的规则。
– ≮,当且仅当文法 G中存在规则：
U::=…TjV… 的规则，且 V=>+ Ti… 或
V=>+WTi… 。
– ≯,当且仅当文法 G中存在规则：
U::=…VTi… 的规则，且 V=>+ …Tj 或
V=>+ …TjW 。
算符优先关系的直观意义
算符优先分析技术的基本思想是通过终结符号之间的优先关系，确定句型的句柄。
对于句型
[N1]T1…[N i-1]Ti-1[Ni]Ti…[N j]Tj[Nj+1]Tj+1…[N k]Tk[Nk+1]
满足关系 Ti-1≮ Ti ≈Ti+1≈… ≈Tj≯ Tj+1的最左子符号串就是要被归约的短语。
优先关系例子
文法,Z::=E E::=T|E+T
T::=F|T*F F::=(E)|i
等于关系：（ ≈）
由推导
– Z→E→E+T→E+F→E+i
– Z→E→E+T→E+T*F→E+T*(E)→E+T*(E+T)
– Z→E→E+T→E+T+T→E+T+F→E+T+(E)
得到以下关系：
+≮ i,+≮ *,*≮ (,(≮ +,+≯ ),+≯ +,+≮ (等,
优先关系的构造
优先关系 ≈的构造，只需要按照定义，枚举各个规则的右部就可以得到。
对于关系 ≮ 和 ≯ 的构造，我们需要引入两个辅助的关系,FIRSTTERM和 LASTTERM。
– U FIRSTTERM T当且仅当存在规则 U::=T… 或者
U::=VT… 。
– U LASTTERM T当且仅当存在规则 U::=…T 或者
U::=…TV 。
FIRSTTERM+关系的构造
FIRSTTERM+并不是 FIRSTTERM的传递闭包。
U FIRSTTERM+ T表示 T是 U经过若干步推导得到的字的首终结符号。构造算法如下：
– 步骤 1：如果 U FIRSTTERM T，那么 U
FIRSTTERM+ T.
– 步骤 2：如果 U::=V…,且 V FIRSTTERM+ T，
那么 U FIRSTTERM+ T。
– 步骤 3：重复步骤 2，知道过程收敛。
LASTTERM+的构造算法
LASTTERM+不是 LASTTERM的传递闭包。 U
LASTTERM+ S表示 U经过若干步推导得到的字的尾终结符号为 S。构造算法为：
– 步骤 1：如果 U LASTTERM T，那么 U
LASTTERM+ T。
– 步骤 2：如果 U::=…V,且 V LASTTERM+ T，
那么 U LASTTERM+ T。
– 步骤 3：重复步骤 2直到收敛。
关系 ≮ 和 ≯ 的构造
关系 ≮ 的构造：
≮ = (≡)(HEAD*)(FIRSTTERM)
= (≡)(FIRSTTERM+)
≯ = ((TAIL*)(LASTTERM))T(≡)
= (LASTTERM+)T(≡)
算符优先文法
定义 5.11：设有算符文法 G，如果其任意两个终结符号之间，算符优先关系最多只有一种关系成立，那么该文法 G称为算符优先文法。
算符优先文法句型的识别
由于算符优先分析技术在分析的过程中，
非终结符号是‘不可见’的。因此，对于单规则，算符优先技术无法处理。
定义 5.12 质短语是满足下面条件的短语：
– 至少包含一个终结符号。
– 该短语不再包含满足第一个条件的更小的短语。
质短语的例子
短语有 T+T*F+i,T+T*F，
T*F，最左边的 T,i。
其中，质短语为 T*F,i。
T+T*F+i,T+T*F不是质短语，因为其中包含了 T*F。
T不是质短语，因为其中没有终结符号。
E
E
+ T
E
Z
T+ F
i
T * F
T
定理 5.14
定理 5.14：句型
[N1]T1…[N i-1]Ti-1[Ni]Ti…[N j]Tj[Nj+1]Tj+1…[N k]Tk[Nk+1]
中满足关系 Ti-1≮ Ti ≈Ti+1≈… ≈Tj≯ Tj+1的最左子符号串 [Ni]Ti…[N j]Tj[Nj+1]就是句型的质短语。
句型识别过程关系 质短语 符号句型
1 # ≮ i ≯ + i Fi+(i+i)*i
2 # ≮ +≮ (≮ i≯ + i FF+(i+i)*i
3 #≮ +≮ (≮ +≮ i≯ ) i FF+(F+i)*i
4 #≮ +≮ (≮ + ≯ ) F+F EF+(F+F)*i
5 #≮ +≮ (≈) ≯ * (E) FF+(E)*i
6 #≮ +≮ *≮ i≯ # i FF+F*i
7 #≮ +≮ *≯ # F*F TF+F*F
8 #≮ +≯ # F+T ZF+T
识别得到的语法树
F
Z
+ T
*
E
Fi F
)(
+F F
i i
i
E
E
+ T
*
E
TT F
)(
+E
FF
i
i
F
i
F
T
T
Z
i
算符优先技术的说明
在算符优先技术的应用中，分析过程并不考虑非终结符号。可以认为：编译程序不考虑具体符号的名字，只考虑它的意义。
需要有处理质短语的语义处理子程序。
在使用算符优先技术的过程中，我们可以使用同一个符号 N来表示归约得到的非终结符号，分析过程照样可以进行。
识别算法流程图开始
i=1; S[i]=#
R=Next Symbol
S[i]?VT
或 S[i]=#j=i-1 j=i
S[j]>R
否 i=i+1;S[i]=R
A
N Y
Y
识别算法流程图 (续 )
A
Q=S[j];j=j-1
S[j]?VTj=i-1
S[j]<Q
调用语义处理子程序,判断是否质短语?
出错处理归约已经归约完成?
N
N
Y
Y
N
语义处理子程序
语义处理子程序需要根据栈里面的符号
（和其它信息）分析是否是一个质短语。
建议归约的时候，遵照以下法则：
– 对于质短语 w=[Ni-1]Ti[Ni]Ti+1…Tj[Nj+1],
归约到如下的非终结符号 V：
– V →u →+w,且在 u到 w的推倒过程中，只用到了如
U::=W的单规则。 U,W为非终结符号。
实际应用的算符优先分析技术
可以使用优先函数来替代优先矩阵。优先函数的求解方法等同于简单优先矩阵的算法。（前面的算法不考虑优先关系的种类）
可以使用两个栈：运算符栈，运算分量栈。运算分量（非终结符号）和运算符
（终结符号）将分别存放在两个栈中。
算符优先文法的范围
可以被用来处理各种表达式。
如果把各个关键字看作算符，这个技术也可以被使用来处理程序设计语言。
对于实际使用的程序设计语言，只需要对文法稍微修改就可以应用算符优先分析技术。
对于有些情况，比如表达式，我们可以使用单优先函数来解决。（实际上即
f(S)=g(S);
两种优先技术的比较使用范围 简单优先文法 算符优先文法关系定义集 字汇表 终结符号集项目 简单优先技术 算符优先技术归约方式 规范归约 ‘规范’归约被归约者 句柄 质短语语义子程序 要求少 要处理的多功能 低 较高存储需求 比较大 比较小归约条件控制方式 优先矩阵或优先函数 优先矩阵或优先函数实现工具 栈 栈优先关系 简单优先关系 算符优先关系
LR(K)分析技术
LR(K)是指,可以以 k为界,从左到右地翻译。
也就是说，在扫描的过程中，最多向前看 K
个符号，就可以确定句柄。
LR(K)技术可以应用于几乎所有的用 CFG描述的程序设计语言。并且有识别程序自动生成器。
LR(K)文法定义
定义 5.14 一个文法是 LR(K)的，当且仅当句子的识别过程中，任何一个句柄都可以由它左边的符号和右边的 K个符号确定。
定义 5.15(句柄 )设 α=X1X2…Xn…Xt 是文法的句型。假定 Xr+1…Xn 是和第 p个规则相匹配的，那么称二元组 (n,p)为 α的句型。
LR(K)文法的定义
定义 5.16 后面跟了 K个 #的句型称为 K句型。
定义 5.17 （ LR(K)的形式化定义）设有文法 G，
并且 α=X1X2…XnXn+1…Xn+kY1…Yu 和
β=X1X2…XnXn+1…Xn+kZ1…Zv 是 G的两个句型,Xn+1…Xn+k,Yi,Zi 都不是非终结符号。
设 α β的句柄分别为 (n,p)和 (m,q)。如果 G满足：
对于任何两个这样的句型,n=m且 p=q，那么
G就是 LR(K)的。
LR(K)是文法的概念。
LR(K)文法的若干性质
性质 1：对于任何可用一个 LR(K)文法定义的上下文无关语言都能用一个确定的下推自动机以自底向上方式识别。
性质 2,LR(K)文法无二义性。
性质 3：当 K确定的时候，一个文法是否
LR(K)文法是可判定的。
性质 4：一个语言能够由 LR(K)文法生成，
当且仅当它能够由 LR(1)生成。
LR(K)技术的算法框架
由驱动程序和分析表组成。
根据分析表，对栈中信息和当前输入符号做出动作决定：移入 /归约 /接受 /报错。
栈中的一个元素分成两个部分：
– 状态：综合了‘历史’和‘展望’信息。状态的形状为,[Xp1…Xpj·Xpj+1…Xpn; α],
意义为：试图按照规则 p归约，已经扫描和归约得到了 Xpj前的符号，希望扫描以后的符号。如果右部都扫描得到了，只有下 K个符号为 α时，才按照这个规则归约。
– 文法符号：被移入或者归约得到的符号。
LR分析表
LR分析表有两个部分：动作部分 ACTION
和状态转换 GO部分。都对应于二维数组。
ACTION[S,y]表明当状态为 S，向前看符号串 y时，应该采取的动作
– 移入：将 S,y的下一个状态 S以及当前符号入栈。
– 归约：对栈顶的符号串按照某个规则进行归约。
– 接受：宣布输入符号串为一个句子。
– 报错：宣布输入符号串不是句子。
GO[S,U]表示当前状态 S和非终结符号匹配的时候所转换到的下一个状态。
LR驱动程序算法流程开始初始化
R:=下一个输入符号
y:=向前看 k个符号执行 ACTION[TOP(S),y]
移入接受报错归约
LR分析表例子状态 i E+ #)* ( FT
0 S5 1S4 32
1 S6 acc
2 r2 r2r2S7
3 r4 r4r4r4
4 S5 8S4 32
5 r6 r6r6r6
6 S5 S4 9
7 S5 S4 10
8 S6 S11
9 r1 r1r1S7
3
11 r5 r5r5r5
10 r3 r3r3r3
LR分析例子
3 0F3 +i*i r4 归约 F
9 0E1+6T9 *i S7 移入 *
10 0E1+6T9*7 i S5 规约 i
11 0E1+6T9*7i5 # r6 规约 i
12 0E1+6T9*7F10 # r3 规约 T*F
13 0E1+6T9 # r1 规约 E+T
4 0T2 +i*i r2 归约 T
5 0E1 +i*i S6 移入 +
6 0E1+6 i*i S5 移入 i
7 0E1+6i5 *i r6 规约 i
8 0E1+6F3 *i r4 规约 F
步骤 栈 输入 动作 说明
1 0 i+i*i S5 移入 i
2 0i5 +i*i r6 归约 i
14 0E1 # acc 接受例子的说明
分析过程的动作是由栈顶元素（状态）和当前输入符号决定的，栈中的文法符号可以忽略。
原因是状态中实际包含了关于文法规则的信息。
只有当执行归约的时候，才需要考虑文法规则。
在分析开始的时候，构型为 S0|i+i*i#。结束的时候，构型为 S0ES1|#
识别过程适用于全部的 LR(1)文法。
LR(K)分析技术的思想
首先猜测下一步归约要使用的规则。猜测的顺序从左边开始猜测，过程是逐步进行的。
逐步读入符号，根据当前符号和向前看符号串来剔除那些没有希望的猜测。同时，相应地进行归约。
下面，我们用文法 E::=E+T,E::=T T::=T*F
T::=F F::=(E) F::=i进行演示。输入为 i+i。
LR(K)分析技术的思想 (例子）
要归约到 E，必须经过规则 E →E+T,或者 E →T 。
而要使用上面的两个规则，首先要归约到 T。而要归约到 T，必须要使用规则 T →F 或者 T →T*F 。
因此，要归约到 T，首先要归约得到 F。而得到 F
可以使用的规则为 F →i,或者 F →(E) 。
现在，第一个符号为 i。只有 F →i 可能归约这个符号。所以，第一次归约的规则为 F →i 。
LR(K)分析技术的思想 (例子 )
经过归约，第一个符号为 F。此时，有可能进行归约的规则为 T →F 。第一个符号为 T。
随后，再次进行归约，第一个符号为 E。
由于还有输入符号，我们发现，要将 E(和后面的某些符号 )归约，可能使用的规则为 E →E+T 。
我们读入 +，现在要归约的符号为 E+… 。显然，
我们要试图‘读入’一个 T，然后才能按照 E
→E+T 归约。这样，我们需要把余下输入的前面部分首先归约为 T，然后才可以得到结果。
因此，我们的下面首先尝试归约得到 T。
LR(K)分析技术的思想 (例子 )
要将余下的开始部分归约得到 T，我们可能的方法是，根据规则 T →F,或者 T →T*F 进行归约。
要试图按照规则 T →T*F 归约,必须首先归约得到 T。最初必须归约得到 F。而要得到 F，我们必须按照规则 F →i 或者 F →(E) 归约。
下一个符号是 i。所以，我们可以得到 F。
同样，我们由 F可以得到 T。
由于，前面我们已经得到了 E+，加上现在的 T，
我们得到了 E →E+T 。归约完成。
基本思想的实现
首先，如果我们试图按照某个规则来归约的话，
我们需要记住已经归约或移入得到的规则右部的前半部分。对于第 P规则 U →X1X2…Xn,我们用 U →X1X2…Xj.Xj+1…Xn 表示已经读入
（或归约得到）了前 j个符号，现在需要试图得到后面的符号。上面的称为一个‘ 项 ’,可以用
(P,j)表示。
但是，我们前面看到，在一个时刻会有多个可能猜测。所以，当前状态使用 项集 来表示。项集中的每个项都表示了一个可能的猜测。
基本思想的实现（续）
从前面的例子里面可以看到，我们尝试某个规则时，有必要先归约得到一个非终结符号。比如，我们尝试 E →E+T,并扫描到了 E+的时候，
需要首先归约得到一个 T。因此，当圆点在某个非终结符号的时候，我们需要首先尝试该非终结符号的规则。
定义：（项集闭包）
CLOSURE(S)=S?{[q,0;β]|[p,j,α]∈ CLOSUER(S),
j<np,Xpj+1=Uq，且 β∈ Hk(Xpj+2…Xpnp α)}
基本思想的实现（续）
Hk函数的说明,Hk函数的值是参数对应的字的前 K个符号。
定义,Hk(α)={β| α→* β…,| β|=K,β ∈ VT*}.
当 k=1的时候,Hk的求法就类似于 LL(1)技术中的第一个终结符号的求法。
项集闭包的例子
文法,0 Z::=E# 1 E::=E+T,2 E::=T
3 T::=T*F 4 T::=F 5 F::=(E)
6 F::=i
S={[Z→.E#,#]}
CLOSURE(S)还包含以下项：
[E→.E+T,#],[E→.T,#]
[E→.E+T,+],[E→.T,+],[T→.T*F,#],[T→.F,#]
[T→.T*F,+],[T→.F,+],[T→.T*F,*],[T →.F,*],[F →.i,#],
[F →.(E),#]
[F →.i,*],[T→.(E),*]
向前看符号串
向前看符号的说明：项中的向前看符号串是用来解决冲突问题的。在前面的例子中，我们已经归约得到了第一个 T，为什么没有尝试 T→T*F 呢？
原因就在于我们发现下一个符号是 +。这个 +号表明了我们可以将 T归约。
那么，当尝试一个规则，并移入 /归约得到了它右部的所有规则之后，什么时候可以归约呢?显然，
我们要考虑当初为什么要尝试这个规则。
如果尝试规则 U →u 的原因是：在尝试规则
V→…Ur 时，已经扫描到了 U的前面，试图归约得到 U。所以，此时如果要进行归约，向前看符号串必须时可以由 r推导得到（或者加上 V对应的向前看符号）。
向前看符号串
再次考虑项集闭包中，对于新增加项的向前看符号串的定义：
CLOSURE(S)=S?{[q,0;β]|[p,j,α]∈ CLOSUER(S),
j<np,Xpj+1=Uq，且 β∈ Hk(Xpj+2…Xpnp α )}
初始项集
我们将一个项集作为一个状态。
初始状态：在开始的时候，我们考虑的是最后归约到识别符号时候使用的规则。所以猜测的可能性 (项集 )为,CLOSURE(S)。其中 S为,
{[q,0;#k] | 第 q个规则为关于识别符号的规则 }。
显然，如果某个关于识别符号的规则的第一个符号是非终结符号的时候，我们还需要进行关于给识别符号的猜测。
初始项集的例子见前面项集之间的转换关系 (Action归约 )
我们需要构造两个分析表,Action和 Go。
状态对应于项集。在 Action中,A[S,α]表示的是栈顶状态为
S的时候，向前看符号串为 α的时候应该采取的动作。
当其中某个项的形状如,[U →x.,α] 的时候，表示针对该规则的扫描已经完成，并且，如果当前的符号为 α的话，就可以进行归约。因此这个项主张,A[S,α]的动作应该是按照这个规则进行归约。
如果有多个这样的规则，那么显然当栈顶符号为 S而向前看符号为 α的时候，我们有多个可能的归约方式。由于我们只有一个栈，不可能同时对这个栈中的符号进行多种操作。
所以这样就引起了冲突。
例子：当前状态（项集）为 {[2,1;#],[4,0,+],[6,0,#],…} 而向前看符号为 #，表示应该进行归约。
项集之间的转换关系 (Action移入 )
如果项集中有项 [U→x.ay,T],表示对应于这个项集的猜测需要输入一个 a，并且，如果 ay可能推导出 α的时候，这个项主张 A[S,α]的动作应该为移入。
如果有多个这样的项，那么表示它们都主张下一个操作是移入。由于移入的动作是将当前符号压入栈中，所以相互之间的主张并不冲突。
但是，如果同时还有项主张归约，那么就可能形成冲突。
当没有冲突的时候，可以将主张移入的项的圆点向右移动一位，表示该猜想离开成功已经又近了一步。而其它项被删除，
表示这些项对应的猜想已经失败。
例如：当前项集为 {[F→.(E),+],[F→.(E),#],…},当前符号为 (。那么它的下一个状态是 CLOSURE{[F→(.E),+],
[F→(.E),#],…}
项集之间的转换关系 (GO表 )
Go表确定了如果发生归约动作，将归约得到的非终结符号入栈之后，在栈顶的状态。
如果在非终结符号 U入栈之前，栈顶的状态中有项 [V→x.Uy,
a]。这个项表示，它对应的猜想希望输入一个 U。因此在下一个状态中，必然有项 [V →xU.y] 。
如果原状态中有多个这样的项，并不引起冲突。所有这样的项都应该将圆点后移，添加到后继状态中。其余的项对应的猜想已经失败。
后继状态为所有添加到表中的项的项集闭包。
Go表中的动作不会有冲突的情况。
LR(K)分析表的构造
构造初始项集闭包，这个项集在状态集合中。
对于每个项集 S，和每个终结符号串 α,S对应于 α首符号的移入 _后继的闭包也在状态集合中。相应的分析表项 A[S,α]中为移入，并且后继状态为该后继项集。
对于每个项集 S，如果项集中有项 [U→x.,α],那么分析表中有 A[S,α]=ri。其中 i为 U→x 对应的规则编号。
对于每个项集 S，和每个非终结符号 U，它们的移入 _
后继的闭包也在项集中。并且，分析表 Go中有对应项为 G[S,U]=后即对应的集合。
LR(K)文法的判定
如果按照上述算法得到的 LR(K)分析表中每一项最多只有一个值，那么这个文法就是 LR(K)的。
LR(K)技术的评价
适用面广：几乎可以适用于所有用上下文无关文法描述的程序设计语言，且一般只需要 K=1.
效率高：适用确定的下推自动机来实现。
错误发现及时：一旦语法有错误，立刻可以发现。便于进行其它出错处理。
便于识别程序的自动构造。
LR(0)方法和 SLR(K)技术
在 LR(K)技术中，每次都需要通过向前看 K个符号来确定下一步的动作。导致的结果是，状态非常多。
有的时候，不需要向前看就可以确定下一步的动作（归约，还是移入）。因此一个可能的解决办法是：当不能确定下一步动作的时候才向前看 K个符号。这个方法称为 SLR(K)方法。
首先，我们构造不向前看的 LR(0)分析表。
LR(0)分析
首先,LR(0)技术不需要向前看符号就可以确定是归约（到哪个符号）还是移入。
所以,LR(0)的分析表没有 ACTION部分。
在 LR(0)状态中，只有状态根据当前输入符号的转换关系。这些转换关系由特征自动机 (CFSM)表示。
CFSM的状态是 LR(0)项集闭包。
特征自动机 (CFSM)
完备项,U →u,称为完备项。包括接受项和归约项。如,Z →E#.,E →E+T.
不完备项,E →E.+T 。
接受项,Z →u,称为接受项。 Z →E#.
移入项,U →u.Tv,其中 T为终结符号。 E
→E.+T 。
待约项,U →u.Vv,其中 v为非终结符号。 E
→E+.T 。
特征自动机 (CFSM)
初始项,Z→.E# 。
后继项,U →u.Av 的后继项为 U →uA.v 。
项集和项集闭包：
LR(0)项集规范族的构造：
– 初始项的闭包在规范族里面。
– 如果 Si在规范族里面，那么其后继也在。
项集规范族的例子
0：初始项,Z →.E#,闭包集合,E →.E+T; E →.T; T→.T*F;
T→.F; F→.(E); F→.i 。
0 ---E---> 1：基本项,Z →E.# ； E →E.+T ；
0 ---T---> 2：基本项,E →T,； E → T.*F ；
0 ---F---> 3：基本项,T →F.
0 ---(---> 4：基本项,T →(.E) ；闭包集合,E →.E+T; E
→.T;,..
0 ---i---> 5：基本项,F→i,；
特征自动机
项集规范族和它们之间的转换关系可以用特征自动机描述。方法如下：
– 将 LR(0)项集规范族中的集合作为自动机的状态。
– 将状态之间的转换关系对应于后继关系。
– 和初始项集对应的状态为初始状态。和 #归约 _后继项集对应的状态作为该 FSM的终止状态。
特征自动机的例子
0 1
12
6 9
7 102
3
5
4 8 11
13
LR(0)项集的分类
归约状态：项集中只有一个完备项。这个状态只有一条到归约后继的出弧。
读状态：项集中包含的全部是不完备状态。没有到归约后继的出弧。
不适定状态：即有完备项，又有不完备项的状态称为不适定状态。这个状态既有到归约后继的出弧，还有到其它状态的弧。
利用 CFSM判断 LR(0)文法
一个文法是 LR(0)的，当且仅当该文法的
CFSM中间没有不设定状态。
利用 CFSM识别 LR(0)句子
将状态 0入栈。
读入下一个符号，入栈。由 CFSM确定栈顶状态，如果不能确定，出错。
如果当前的栈顶状态为读状态,goto步骤 2；如果是归约状态，根据相应的规则进行归约（此时可以进行相应的语义工作）。归约时，将相应的右部弹出。如果是归约到识别符号，那么句子接受，否则将非终结符号作为输入符号，
转步骤 2。
利用 CFSM识别 LR(0)文法的句子
文法,Z::=E# E::=aA | bB A::=Ca|d B::=cB|d
相应的 CFSM
0
3
2
1 12
5
4
6
7
8
9
11
13
10
识别过程步骤 栈 其余输入部分
0 0 其余输入部分
1 0a2 其余输入部分
2 0a2c5 其余输入部分
3 0a2c5c5 其余输入部分
4 0a2c5c5d6 其余输入部分
5 0a2c5c5A10 其余输入部分
6 0a2c5A10 其余输入部分
7 0a2A4 其余输入部分
8 0E1 其余输入部分
SLR(K)文法
LR(K)分析技术
活前缀：规范句型的一个头符号串，并且不包含句柄右部的任何符号。
比如：句型 E+T*i+i的活前缀有 E,E+T,
E+T*,E+T*i。
E+T*i+不是活前缀，因为句柄为 i，并且
+在 i的右面。
(第五章,语法分析 --
自底向上分析技术 )
南京大学计算机系赵建华概论
从输入符号出发，试图把它规约成识别符号。每一步都寻找特定得某个类型的短语（一般是简单短语）进行规约。
在分析过程中，每次规约的都是最左边的简单短语（或其它短语）。
从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。
基本问题
如何找出进行直接规约的简单短语？
将找到的简单短语规约到哪个非终结符号？
讨论前提
和自顶向下技术同样，不考虑符号的具体构成方式。
文法是压缩了的。
识别过程是从左到右，自底向上进行的。
一般都采用规范规约：每一步都是对句柄进行规约（特例除外）。
基本方法
基本都采用移入 -规约方法。
使用一个栈来存放规约得到的符号。
在分析的过程中，识别程序不断地 移入符号。移入的符号暂时存放在一个栈中。
一旦在已经移入的（和规约得到的）符号串中包含了一个句柄时，将这个句柄规约 成为相应的非终结符号。
基本方法（续）
规约中的动作有 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
文法 G5.1[E],E::=E+E|E*E|(E)
输入符号串,i*i+i
已处理符号 未处理符号 句型 句柄 规则例子的解释
当栈中的符号的栈顶部分还不能形成句柄时，
进行移入操作。
一旦 发现 栈顶部分形成了句柄的时候，对该句柄进行 规约 。将句柄出栈，然后将规约得到的非终结符号压栈。
如果输入是句子，则栈中的符号（从底到上）
和未处理的符号组成句型。
在例子中，发现句柄和规约是人为干预的结果。
所以移入 -规约不是实际可运行的技术，而是技术的模板。
简单优先分析技术
基本思想：
– 每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。
S0…S j-1SjSj+1Sj+2… …S i-1SiSi+1…S n
U
简单优先分析技术 (基本思想续）
我们要通过两个相邻符号 SiSi+1之间的关系来找到句柄：
– SiSi+1在句柄内：必然有规则 U::=…S iSi+1…
– Si在句柄内部，但是 Si+1在句柄之后：必然有规则 U::=…S i，且存在规范句型 …US i+1… 。
– 如果 Si+1在句柄内，而 Si在句柄外，那么必然存在规范句型 …S iU…,且 U::=Si+1… 。
优先关系
和树上的写法不一样，凑合用。
Si?Sj Si? Sj Si?Sj
注意,?,?,?之间不同于 =,>和 <。
由 Si? Sj不能导出 Sj?Si。
优先关系的例子
文法,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 | a L::=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
优先关系的定义
Sj?Si：当且仅当 G中有规则 U::=…SjSi…
Sj?Si：当且仅当 U::=…SjV…,且 V
HEAD+ Si；
Sj?Si：当且仅当 U::=…VW…,其中 V和
W分别满足 V TAIL+ Sj和 W
HEAD* Sj且 Sj为终结符号。
HEAD和 TAIL
U HEAD S 当且仅当 U::=S…
U TAIL S 当且仅当 U::=…S
HEAD+,HEAD*分别是 HEAD的传递闭包和自反传递闭包。
– U HEAD+ S当且仅当 U::=U1…,U1::=U2…,…,
Un::= S… 。
– U HEAD* S当且仅当 U=S或者 U HEAD+ S
TAIL+是 TAIL的传递闭包。
– U TAIL+ S当且仅当 U::=…U1,U1::=…U2,…,
Un::= …S
优先关系
定理 5.1 Sj? Si当且仅当 SjSi出现在某个规范句型的句柄中。
定理 5.2 Sj?Si当且仅当存在规范句型 …SjSi…,且 Sj是该句型的句柄的最后一个符号。
定理 5.3 Sj?Si当且仅当存在规范句型 …SjSi…,且 Si是该句型的句柄的第一个符号。
定理 5.1的证明
如果 SjSi出现在句柄中，当然有 U::=…SjSi…
如果有规则 U::=uSjSiv，
– 必然有某个符号串的推导使用了该规则。（假设文法是已压缩的）
– 根据该推导构造语法树。则必然存在一个结点标记为 U，其子结点为 uSjSiv。
– 根据语法树构造最左规约（每一步都对句柄进行规约）。那么上面的结点对应的一步就是将 uSjSi规约为 U。此时,uSjSiv为句柄。
定理 5.2的证明 (1)
如果 Sj?Si，
– 按照定义存在规则 U::=…VW…,V TAIL+ Sj，且 W
HEAD*S。
– 必然有句型 …VW…,由 TAIL+和 HEAD*的定义，必然存在句型 …vuSjSi…,且 V=>*vU=>vuSj,W=>Si… 。
– 构造相应的语法树，并且从语法树构造相应的规范推导。
uSj必然在某一步成为句柄。而此时由于 Si在 Sj的右面，
它必然还没有被规约。所以，当 uSj成为句柄的时候，其规范句型必然为 …uSjSi… 。
定理 5.2证明 (2)
如果存在规范句型 …SjSi… 且 Sj是某个句柄的最后符号,
– 考虑语法树中，同时包含有 Sj和 Si的最小子树。设其根结点为 U。而 U的子结点从左到右为 u。
– 短语 u的形状必然为 …VW…,且 V=>*…Sj 而
W=>*Si。这是因为如果有某个 u中的符号
X=>…SjSi…,那么以 X为根的子树才是最小的包含
Sj和 Si的子树。
– 显然，根据定义 Sj?Si。
优先关系的构造
根据优先关系的构造性的定义（定义 5.1），我们立刻可以得到构造算法。
的构造：直接对每个规则右部处理，没有右部 X1X2…X n，
都有 Xi? Xi+1。
的构造：由定义,Sj?Si可以得到
– 存在规则 U::=… SjV…,也就是 Sj? V。
– V HEAD+ Si。
– HEAD关系可以通过检查每个规则得到。
– 由此可以得到?就是 (?)(HEAD+)。因此?可以通过计算关系?和 HEAD的传递闭包。
优先关系的构造（续）
关系的构造：由定义,Sj?Si表示,
– 存在规则 U::=…VW… V?W
– V TAIL+ Sj Sj (TAIL+ )T V
– W HEAD* Si
– 将上面三个规则综合起来，可以得到?关系就是
(TAIL+)T? HEAD*
从上面的算法可以看到,?,TAIL,HEAD可以直接检查每个规则得到。因此，我们只需要有对关系的联接，闭包运算就可以得到上面的三个优先关系。
关系的 bool矩阵表示和运算
关系可以使用 bool矩阵来表示。对某个关系 R,SjRSi在矩阵中用 Bij=TURE来表示。
对于两个关系 R1,R2对应的矩阵 B1,B2，
B1和 B2的乘积矩阵对应的关系就是 R1和
R2联接运算结果。
关系闭包和 Warshall算法
Warshall算法是利用矩阵计算关系传递闭包的方法。计算 B的传递闭包的算法伪代码如下：
A = B;
for (i = 1; i<=n; i++)
for (j=1; j<=n; j++)
{
if (A[j,i]==1)
for(k=1; k<=n; k++)
A[j,k] = A[j,k]+A[i,k]
}
使用矩阵计算优先关系?
步骤 1：构造优先关系矩阵 B?
步骤 2：构造关系 HEAD的矩阵 BHEAD
步骤 3：使用 Warshall算法计算 BHEAD+
步骤 4：计算 B?BHEAD+
使用矩阵计算优先关系?
步骤 1：计算 TAIL的布尔矩阵 BTAIL
步骤 2：计算 BTAIL+，并将该矩阵转置得到
(BTAIL+)T。
步骤 3：构造优先关系矩阵 B?
步骤 4：构造 HEAD的矩阵 BHEAD。
步骤 5：计算 BHEAD+的矩阵，并由此得到
I+HEAD+的矩阵 BI+HEAD+。
步骤 6：计算 (BTAIL+ ) TB?BI+HEAD+。
需要在得到的矩阵中，把非终结符号对应列中的 1去掉。 (因为?的右边时终结符号）
计算优先关系的例子 P136
文法,S::=Wa W::=Wb W::=a
将文法中的符号按照 S,W,a,b排列。
BHEAD=
0100
0110
0000
0000
BHEAD+=
0110
0110
0000
0000
BTAIL=
0010
0011
0000
0000
(BTAIL+)T=
0100
0110
0000
0000
计算优先关系的例子 (续 )
B?=
0000
0011
0000
0000
B I+HEAD+=
1110
0110
0010
0001
B?=B?BHEAD+=
0000
0000
0000
0000
B?=(BTAIL+ ) TB?BI+HEAD+=
0000
0000
0011
0011
优先关系的冲突
当优先矩阵中出现值不唯一的元素时，
文法不适合使用优先识别技术来识别句型。
简单优先文法
定义 5.2 如果某个文法满足：
– 字汇表中的任意两个符号之间至多有一种优先关系成立。
– 任何两个重写规则的右部不相同。
那么称这个文法为简单优先文法。
第一点保证可以识别出句柄,
第二点保证可以确定规约到哪个非终结符号。
定理 5.4
一个简单优先文法是无二义性的，且其任何一个句型 Sm…Sn 的唯一句柄是满足条件：
Sj-1≤Sj≡Sj+1≡Sj+2≡… … ≡Si-1≡Si≥Si+1
的最左子符号串 SjSj+1Sj+2… …S i-1Si。
定理 5.4的证明
首先用反证法证明任何句型的句柄是唯一的。
– 句型必然有句柄，且这个句柄必然满足
Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡S i-1≡Si≥Si+1（句柄 1）
– 如果还有另外一个语法树，那么它对应的归约（称为归约过程 2）必然不是把上面的句柄作为一个整体规约的。
– 在归约过程 2中，当首次有句柄 1(包括 Sj-1和 Si+1)中间的某个符号 St作为句柄（句柄 2）的一部分被规约的时候，我们可以考虑以下的情况：（下一页）
定理 5.4的证明 (续 )
如果 t=j-1，那么由句柄 1,Sj-1≤Sj；由句柄 2,Sj-1≡Sj或
Sj-1≥Sj；矛盾！
如果 t=i+1，由句柄 1,Si≥ Si+1；由句柄 2,Si≤ Si+1或者 Si ≡ Si+1。
如果 i<= t <= j；那么
– Sj在句柄中：
– Si在句柄中：
– Sj和 Si都不在句柄中：
定理 5.4的证明 (续 )
简单优先文法的无二义性是显而易见的：
– 每个句型只有一个句柄。
– 句柄只能归约到确定的非终结符号。
该证明的实质就是：句柄 1和句柄 2相互重叠，重叠的边缘必然由优先关系的多重定义。
S0…S j-1SjSj+1Sj+2… …S i-1SiSi+1…S n
U
应用优先技术的困难与克服
简单优先技术只适应于简单优先文法。
实际上，一般的程序设计语言的文法都不是简单优先文法。比如四则运算表达式的文法。
可能的解决办法是：分离法（成层法）
简单优先分析技术的实现
识别过程,从左到右地扫描输入符号。已经扫描或归约得到的符号被存放在一个栈中。
每次扫描的时候，将当前符号 a和栈顶符号 S相比较。如果 S≥a表示已经碰到了一个句柄的尾。然后在栈里面向前（下）
找，直到找到句柄的头。此时找到右部为该句柄的规则进行归约。
简单优先分析技术流程图开始初始化
R=下一个输入符号栈顶 Si≥R? 把 R入栈找出栈中第一个满足 Sj-1≤Sj的值
AB
否是简单优先分析技术流程图 (续 )
A
寻找其右部和句柄匹配的规则存在这样的规则是句子？ 出错处理停止将句柄中的符号退去，
将规则的左部入栈。
B
是是否否例子
1 #b ≤ ( aa)b# 移入
2 #b( ≤ a a)b# 移入
3 #b(a ≥ a )b# 归约
4 #b(M ≡ a )b# 移入
5 #b(Ma ≡ ) b# 移入
7 #b(L ≥ b # 归约
8 #bM ≡ b # 移入
9 #bMb ≥ # # 归约
10 #Z # # 接受
0 # ≤ b (aa)b# 移入步骤 栈 关系 Next 余下部分 动作
6 #b(Ma) ≥ b # 归约优先函数
对于一个实际的程序设计语言的文法，
优先矩阵将会非常大。对于有 n个字汇的文法，矩阵的大小是 n?n
解决的方法是引入优先函数，将矩阵线性化。这里介绍的方法称为双线性优先函数法。
定义 5.3 优先函数
对于某个优先矩阵 M，如果存在两个函数 f和 g，它满足下列条件：
– 如果 Sj≡Si，那么 f(Sj)=g(Si)；
– 如果 Sj≤Si，那么 f(Sj)<g(Si)；
– 如果 Sj≥Si，那么 f(Sj)=g(Si)；
那么 f和 g称为 M的线性优先函数。
注意：
– 不是所有的矩阵都有优先函数的。
– 两个没有关系的符号之间的优先函数值也有大小。
优先函数的例子
Z M L a b ( )
Z
M = =
L > >
a > >
( < = < <
b = < <
) > >
=
Z M L a b ( )
1 7 8 9 4 2 8
1 4 2 7 7 5 9
f
g
优先函数的例子
下面的矩阵没有优先函数
≡
≡ ≥
≡
优先函数的构造（逐次加一法）
步骤 1：对所有符号 S∈ V，让 f(S)=g(S)=1
步骤 2：对于 Sj≤Si，如果 f(Sj)≥g(Si)，让 g(Sj)=f(Si)+1;
步骤 3：对于 Sj≥Si，如果 f(Sj) ≤ g(Si)，让 f(Sj)=g(Si)+1;
步骤 4：对于 Sj≡Si，如果 f(Sj) ≡ g(Si)，让
f(Sj)=g(Si)=max(f(Sj),g(Si));
步骤 5：重复步骤 2-4，直到过程收敛（所有的值都不再增长）。如果所有的值都大于 2n，那么不存在优先函数。
逐次加一法例子
Z M L a b ( )
1 1 1 1 1 1 1
1 1 1 1 1 1 1
f
g
Z M L a b ( )
1 1 1 1 1 1 1
1 2 1 2 1 2 1
f
g
考虑关系 ≤
逐次加一法例子（例子）
Z M L a b ( )
1 1 3 3 1 1 3
1 2 1 2 1 2 1
f
g
考虑关系 ≥
… … … …
最后结果
Z M L a b ( )
1 3 4 4 2 1 4
1 2 1 3 3 3 4
f
g
Bell有向图法
利用有向图构造优先函数。
基本思想：
– 利用优先关系建立 f和 g的各个值之间的关系。
– 利用有向图的弧表示各个值之间应该具有的大小关系。
– 优先函数通过计算 fi和 gi所能够到达的结点确定（如果 fi能够到达结点 gj，表示 fi的值必须不小于 gj的值）。
Bell有向图算法
步骤 1：作具有 2n个结点的有向图。标记分别为 f1,f2,… …,fn 和 g1,g2,… …,gn 。如果 Sj>Si或者 Sj=Si，那么从 fj到 gi画一条弧；如果 Sj<Si或者 Sj=Si，那么从 gi到 fj
画一条弧。
步骤 2：给每个结点一个数值，等于从该点出发沿弧所能到达的结点的个数。
步骤 3：检验这样的函数是否优先函数。
若否，则该优先关系不存在优先函数。
Bell有向图的例子
M )Z L a b (
M )Z L a b (
L≥a,L≥b,a ≥a,a≥b,)≥a,) ≥b
b≤a,b≤(,(≤M,(≤a,(≤(
M≡a,M≡b,a ≡),b ≡M,(≡L
定理 5.5
如果优先矩阵存在优先函数,那么使用 Bell有向图方法构造得到的函数就是优先函数。
首先证明：如果 Sj ≡Si，那么 fj=gi；如果 Sj≥ Si，那么
fj>=gi；如果 Sj≤Si，那么 fj<=gi。
– 该结论显然成立。这是因为如果 Sj ≡Si，那么有从 fj
到 gi和从 gi到 fj的弧。因此,fj可以到达的结点,gi
也可以到达，并且 gi的可以到达的结点,fj也可以到达。如果 Sj ≤Si，那么有 gi到 fj的弧，所以 fj可以到达的结点,gi也可以到达。因此 gi的值至少不比 fj小。
同样可以证明如果 Sj≥ Si，那么 fj>=gi。
定理 5.5的证明
然后证明：如果存在符号 Sj≥ Si且 fj=gi，那么不存在优先函数。
– 由有向图的构造可以知道,gi可以达到的结点,fj必然也可以达到。又由于 fj=gi，所以，由 gi必然也可以到达 fj（否则 fj要大于 gi)。因此，在 fj到 gi，再到 fj
的有一个圈。假设这个圈的结点为 n1=fj,n2=
gi,n3,…nk=fj 。考虑给 ni任意赋值：由弧的定义 ni的值必然不小于 ni+1的值，而且至少 n1的值大于 n2的值。因此，不可能有优先函数。
同样可以证明：如果 Sj ≤ Si且 fj=gi，也不存在优先函数。
Bell有向图的优点
非迭代过程；
再确定多步内可以完成；
改变对文法符号的排序时，优先函数不变。
Bell有向图法的矩阵方法
关系 R：如果 fj到 gi（ gi到 fj）或有一条弧，
那么 fj R gi(或 gi R fj)。
显然该关系 R的矩阵如下：
0 B ≥≡
0
0(B≥≡)T
B≥≡f
g
f g
Bell有向图法的矩阵方法 (续 )
那么关系 R传递闭包就表示了一个结点可以到达另外一个结点的关系。
使用 Warshall算法求解上述矩阵的传递闭包 B+，计算 B*=I+B+。
令每个结点对应的值为：该结点对应的行上的 1的个数。
检查该赋值是否是优先函数。若是，则得到函数，否则，该优先关系不存在优先函数。
结点排序函数
后继结点：如果 x,y∈ X，且存在一个弧的序列从 x到 y，那么 y是 x后继结点,x是
y的后继结点。如果弧序列长度为 1，那么 y是 x的直接后继。
用 σ(x)表示 x的后即结点的结合，用 σ1(x)
表示其直接后继结点的集合。
ND:X→{0,1,…|X|} 定义为 ND(x)=| σ(x) |
结点排序函数
任意一个函数 N:X→{0,1,…|X|},如果满足对于所有的 x,y,y∈ σ(x)都有 N(x)>N(y)，
那么称 N为结点排序函数。
定理 5.7 ND是结点排序函数，当且仅当 D
中没有回路。
Martin算法
步骤 1：作有向图，结点为 f1,f2,…fn,g1,g2,…gn 。并且，如果 Sj>Si，那么从 fj到 gi画一条弧；如果 Sj<Si，
那么从 gi到 fj画一条弧。
步骤 2：如果 Sj ≡Si，那么从 fj向 gi的后继作弧，也从 gi
向 fj的后继作弧。 重复这一个过程,直到这个过程没有新弧加入。
对于最后的有向图，令 f(Si)=ND(fi)，令 g(Si)=ND(Si)。
如果最后的有向图没有回路，那么所得到的函数就是优先函数，否则就没有优先函数。
Martin算法的例子
M )Z L a b (
M )Z L a b (
Martin算法例子
M )Z L a b (
M )Z L a b (
Martin算法的矩阵方法
步骤 1：构造布尔矩阵 B≤≥。此时的矩阵相当于画图时的第一步得到的图。
步骤 2：计算 B=C+B≤≥。其中 C为
I B ≡
(B ≡)T I
步骤 3：计算 B+。
步骤 4：计算各个行中的 1的个数。如果对于某个 i，
B[ii]=1表示图存在回路，优先函数不存在。
优先函数的缺点
信息的丢失，原来两个符号之间有 4中关系（大于，小于，等于，无关），引入优先函数之后，只有 3种关系。
信息的丢失错误的延迟发现。
见 P153页例子。
简单优先技术的局限性
文法的适用范围小。
虽然使用成层法可以使一些文法变成简单优先文法，但是
– 成层法的技术非常复杂。
– 当两个关系既有 ≤又有 ≥时，成层法无能为力。
如果使用高阶矩阵，将使得算法的内存需求更加大。
算符优先分析技术
简单优先技术对字汇表中的所有符号之间建立优先关系。但是，有些情况下，
不需要对所有两个符号之间建立优先关系。
算符优先分析技术只在部分符号（终结符号）之间建立优先关系。
算符优先分析技术基本思想
对于算术表达式，只需要按照操作符之间的优先关系，就可以确定运算的顺序。
不需要考虑操作数就可以对表达式进行分析。
例如,E+T*F。只需要知道 *的优先级高于 +，就可以知道 T*F时句柄。
在一般的文法中，终结符号的地位相当于操作符号。
算符文法
定义：如果文法中没有形状如
U::= …VW…
的规则，该文法称为算符文法。
算符文法的性质
定理 5.9 对于算符文法，不存在包含有相邻两个非终结符号的句型。
定理 5.10 如果 TU出现在句型中，其中 T
为终结符号,U为非终结符号，那么包含
T的短语也必然包含 U.
定理 5.11 如果 UT出现在句型中，其中 T
为终结符号,U为非终结符号，那么包含
T的短语也必然包含 U.
定理 5.9的证明
只需要证明：如果 x不包含两个相邻的非终结符号，且
x=>y，那么 y也不包含相邻的非终结符号。
假设 x=wUv，而 y=wuv。
– 那么由于 x不包含两个相邻的非终结符号，那么 w和
v中没有不相邻的非终结符号。
– 根据算符文法的定义,u中也不包含相邻的非终结符号。
– 根据假设,w的结尾不是非终结符号（否则,x中包含有相邻的非终结符号）。
– 同样,v的开始符号也不是非终结符号。
综上所述,y中不存在相邻的非终结符号。
定理 5.10,5.11的证明
假设 w=xvy是文法的句型，而 v是详相对于 V的短语。
那么 xVy也是句型。
如果 w中有两个相邻的符号 TU，且 T在 v中，而
U不在 v中。显然 U是 y的头符号。
因此 xVy中存在两个相邻的非终结符号 VU。
和定理 5.9矛盾。
定理 5.11的证明和定理 5.10类似。
算符优先关系
定义 5.8 设文法 G是一个算符文法,Tj和 Ti是两个任意的终结符号，而 U,V,W∈ VT，定义算符优先关系如下：
– ≈：当且仅当文法 G中存在形如,U::=…TjTi…
或 U::=…TjVTi… 的规则。
– ≮,当且仅当文法 G中存在规则：
U::=…TjV… 的规则，且 V=>+ Ti… 或
V=>+WTi… 。
– ≯,当且仅当文法 G中存在规则：
U::=…VTi… 的规则，且 V=>+ …Tj 或
V=>+ …TjW 。
算符优先关系的直观意义
算符优先分析技术的基本思想是通过终结符号之间的优先关系，确定句型的句柄。
对于句型
[N1]T1…[N i-1]Ti-1[Ni]Ti…[N j]Tj[Nj+1]Tj+1…[N k]Tk[Nk+1]
满足关系 Ti-1≮ Ti ≈Ti+1≈… ≈Tj≯ Tj+1的最左子符号串就是要被归约的短语。
优先关系例子
文法,Z::=E E::=T|E+T
T::=F|T*F F::=(E)|i
等于关系：（ ≈）
由推导
– Z→E→E+T→E+F→E+i
– Z→E→E+T→E+T*F→E+T*(E)→E+T*(E+T)
– Z→E→E+T→E+T+T→E+T+F→E+T+(E)
得到以下关系：
+≮ i,+≮ *,*≮ (,(≮ +,+≯ ),+≯ +,+≮ (等,
优先关系的构造
优先关系 ≈的构造，只需要按照定义，枚举各个规则的右部就可以得到。
对于关系 ≮ 和 ≯ 的构造，我们需要引入两个辅助的关系,FIRSTTERM和 LASTTERM。
– U FIRSTTERM T当且仅当存在规则 U::=T… 或者
U::=VT… 。
– U LASTTERM T当且仅当存在规则 U::=…T 或者
U::=…TV 。
FIRSTTERM+关系的构造
FIRSTTERM+并不是 FIRSTTERM的传递闭包。
U FIRSTTERM+ T表示 T是 U经过若干步推导得到的字的首终结符号。构造算法如下：
– 步骤 1：如果 U FIRSTTERM T，那么 U
FIRSTTERM+ T.
– 步骤 2：如果 U::=V…,且 V FIRSTTERM+ T，
那么 U FIRSTTERM+ T。
– 步骤 3：重复步骤 2，知道过程收敛。
LASTTERM+的构造算法
LASTTERM+不是 LASTTERM的传递闭包。 U
LASTTERM+ S表示 U经过若干步推导得到的字的尾终结符号为 S。构造算法为：
– 步骤 1：如果 U LASTTERM T，那么 U
LASTTERM+ T。
– 步骤 2：如果 U::=…V,且 V LASTTERM+ T，
那么 U LASTTERM+ T。
– 步骤 3：重复步骤 2直到收敛。
关系 ≮ 和 ≯ 的构造
关系 ≮ 的构造：
≮ = (≡)(HEAD*)(FIRSTTERM)
= (≡)(FIRSTTERM+)
≯ = ((TAIL*)(LASTTERM))T(≡)
= (LASTTERM+)T(≡)
算符优先文法
定义 5.11：设有算符文法 G，如果其任意两个终结符号之间，算符优先关系最多只有一种关系成立，那么该文法 G称为算符优先文法。
算符优先文法句型的识别
由于算符优先分析技术在分析的过程中，
非终结符号是‘不可见’的。因此，对于单规则，算符优先技术无法处理。
定义 5.12 质短语是满足下面条件的短语：
– 至少包含一个终结符号。
– 该短语不再包含满足第一个条件的更小的短语。
质短语的例子
短语有 T+T*F+i,T+T*F，
T*F，最左边的 T,i。
其中，质短语为 T*F,i。
T+T*F+i,T+T*F不是质短语，因为其中包含了 T*F。
T不是质短语，因为其中没有终结符号。
E
E
+ T
E
Z
T+ F
i
T * F
T
定理 5.14
定理 5.14：句型
[N1]T1…[N i-1]Ti-1[Ni]Ti…[N j]Tj[Nj+1]Tj+1…[N k]Tk[Nk+1]
中满足关系 Ti-1≮ Ti ≈Ti+1≈… ≈Tj≯ Tj+1的最左子符号串 [Ni]Ti…[N j]Tj[Nj+1]就是句型的质短语。
句型识别过程关系 质短语 符号句型
1 # ≮ i ≯ + i Fi+(i+i)*i
2 # ≮ +≮ (≮ i≯ + i FF+(i+i)*i
3 #≮ +≮ (≮ +≮ i≯ ) i FF+(F+i)*i
4 #≮ +≮ (≮ + ≯ ) F+F EF+(F+F)*i
5 #≮ +≮ (≈) ≯ * (E) FF+(E)*i
6 #≮ +≮ *≮ i≯ # i FF+F*i
7 #≮ +≮ *≯ # F*F TF+F*F
8 #≮ +≯ # F+T ZF+T
识别得到的语法树
F
Z
+ T
*
E
Fi F
)(
+F F
i i
i
E
E
+ T
*
E
TT F
)(
+E
FF
i
i
F
i
F
T
T
Z
i
算符优先技术的说明
在算符优先技术的应用中，分析过程并不考虑非终结符号。可以认为：编译程序不考虑具体符号的名字，只考虑它的意义。
需要有处理质短语的语义处理子程序。
在使用算符优先技术的过程中，我们可以使用同一个符号 N来表示归约得到的非终结符号，分析过程照样可以进行。
识别算法流程图开始
i=1; S[i]=#
R=Next Symbol
S[i]?VT
或 S[i]=#j=i-1 j=i
S[j]>R
否 i=i+1;S[i]=R
A
N Y
Y
识别算法流程图 (续 )
A
Q=S[j];j=j-1
S[j]?VTj=i-1
S[j]<Q
调用语义处理子程序,判断是否质短语?
出错处理归约已经归约完成?
N
N
Y
Y
N
语义处理子程序
语义处理子程序需要根据栈里面的符号
（和其它信息）分析是否是一个质短语。
建议归约的时候，遵照以下法则：
– 对于质短语 w=[Ni-1]Ti[Ni]Ti+1…Tj[Nj+1],
归约到如下的非终结符号 V：
– V →u →+w,且在 u到 w的推倒过程中，只用到了如
U::=W的单规则。 U,W为非终结符号。
实际应用的算符优先分析技术
可以使用优先函数来替代优先矩阵。优先函数的求解方法等同于简单优先矩阵的算法。（前面的算法不考虑优先关系的种类）
可以使用两个栈：运算符栈，运算分量栈。运算分量（非终结符号）和运算符
（终结符号）将分别存放在两个栈中。
算符优先文法的范围
可以被用来处理各种表达式。
如果把各个关键字看作算符，这个技术也可以被使用来处理程序设计语言。
对于实际使用的程序设计语言，只需要对文法稍微修改就可以应用算符优先分析技术。
对于有些情况，比如表达式，我们可以使用单优先函数来解决。（实际上即
f(S)=g(S);
两种优先技术的比较使用范围 简单优先文法 算符优先文法关系定义集 字汇表 终结符号集项目 简单优先技术 算符优先技术归约方式 规范归约 ‘规范’归约被归约者 句柄 质短语语义子程序 要求少 要处理的多功能 低 较高存储需求 比较大 比较小归约条件控制方式 优先矩阵或优先函数 优先矩阵或优先函数实现工具 栈 栈优先关系 简单优先关系 算符优先关系
LR(K)分析技术
LR(K)是指,可以以 k为界,从左到右地翻译。
也就是说，在扫描的过程中，最多向前看 K
个符号，就可以确定句柄。
LR(K)技术可以应用于几乎所有的用 CFG描述的程序设计语言。并且有识别程序自动生成器。
LR(K)文法定义
定义 5.14 一个文法是 LR(K)的，当且仅当句子的识别过程中，任何一个句柄都可以由它左边的符号和右边的 K个符号确定。
定义 5.15(句柄 )设 α=X1X2…Xn…Xt 是文法的句型。假定 Xr+1…Xn 是和第 p个规则相匹配的，那么称二元组 (n,p)为 α的句型。
LR(K)文法的定义
定义 5.16 后面跟了 K个 #的句型称为 K句型。
定义 5.17 （ LR(K)的形式化定义）设有文法 G，
并且 α=X1X2…XnXn+1…Xn+kY1…Yu 和
β=X1X2…XnXn+1…Xn+kZ1…Zv 是 G的两个句型,Xn+1…Xn+k,Yi,Zi 都不是非终结符号。
设 α β的句柄分别为 (n,p)和 (m,q)。如果 G满足：
对于任何两个这样的句型,n=m且 p=q，那么
G就是 LR(K)的。
LR(K)是文法的概念。
LR(K)文法的若干性质
性质 1：对于任何可用一个 LR(K)文法定义的上下文无关语言都能用一个确定的下推自动机以自底向上方式识别。
性质 2,LR(K)文法无二义性。
性质 3：当 K确定的时候，一个文法是否
LR(K)文法是可判定的。
性质 4：一个语言能够由 LR(K)文法生成，
当且仅当它能够由 LR(1)生成。
LR(K)技术的算法框架
由驱动程序和分析表组成。
根据分析表，对栈中信息和当前输入符号做出动作决定：移入 /归约 /接受 /报错。
栈中的一个元素分成两个部分：
– 状态：综合了‘历史’和‘展望’信息。状态的形状为,[Xp1…Xpj·Xpj+1…Xpn; α],
意义为：试图按照规则 p归约，已经扫描和归约得到了 Xpj前的符号，希望扫描以后的符号。如果右部都扫描得到了，只有下 K个符号为 α时，才按照这个规则归约。
– 文法符号：被移入或者归约得到的符号。
LR分析表
LR分析表有两个部分：动作部分 ACTION
和状态转换 GO部分。都对应于二维数组。
ACTION[S,y]表明当状态为 S，向前看符号串 y时，应该采取的动作
– 移入：将 S,y的下一个状态 S以及当前符号入栈。
– 归约：对栈顶的符号串按照某个规则进行归约。
– 接受：宣布输入符号串为一个句子。
– 报错：宣布输入符号串不是句子。
GO[S,U]表示当前状态 S和非终结符号匹配的时候所转换到的下一个状态。
LR驱动程序算法流程开始初始化
R:=下一个输入符号
y:=向前看 k个符号执行 ACTION[TOP(S),y]
移入接受报错归约
LR分析表例子状态 i E+ #)* ( FT
0 S5 1S4 32
1 S6 acc
2 r2 r2r2S7
3 r4 r4r4r4
4 S5 8S4 32
5 r6 r6r6r6
6 S5 S4 9
7 S5 S4 10
8 S6 S11
9 r1 r1r1S7
3
11 r5 r5r5r5
10 r3 r3r3r3
LR分析例子
3 0F3 +i*i r4 归约 F
9 0E1+6T9 *i S7 移入 *
10 0E1+6T9*7 i S5 规约 i
11 0E1+6T9*7i5 # r6 规约 i
12 0E1+6T9*7F10 # r3 规约 T*F
13 0E1+6T9 # r1 规约 E+T
4 0T2 +i*i r2 归约 T
5 0E1 +i*i S6 移入 +
6 0E1+6 i*i S5 移入 i
7 0E1+6i5 *i r6 规约 i
8 0E1+6F3 *i r4 规约 F
步骤 栈 输入 动作 说明
1 0 i+i*i S5 移入 i
2 0i5 +i*i r6 归约 i
14 0E1 # acc 接受例子的说明
分析过程的动作是由栈顶元素（状态）和当前输入符号决定的，栈中的文法符号可以忽略。
原因是状态中实际包含了关于文法规则的信息。
只有当执行归约的时候，才需要考虑文法规则。
在分析开始的时候，构型为 S0|i+i*i#。结束的时候，构型为 S0ES1|#
识别过程适用于全部的 LR(1)文法。
LR(K)分析技术的思想
首先猜测下一步归约要使用的规则。猜测的顺序从左边开始猜测，过程是逐步进行的。
逐步读入符号，根据当前符号和向前看符号串来剔除那些没有希望的猜测。同时，相应地进行归约。
下面，我们用文法 E::=E+T,E::=T T::=T*F
T::=F F::=(E) F::=i进行演示。输入为 i+i。
LR(K)分析技术的思想 (例子）
要归约到 E，必须经过规则 E →E+T,或者 E →T 。
而要使用上面的两个规则，首先要归约到 T。而要归约到 T，必须要使用规则 T →F 或者 T →T*F 。
因此，要归约到 T，首先要归约得到 F。而得到 F
可以使用的规则为 F →i,或者 F →(E) 。
现在，第一个符号为 i。只有 F →i 可能归约这个符号。所以，第一次归约的规则为 F →i 。
LR(K)分析技术的思想 (例子 )
经过归约，第一个符号为 F。此时，有可能进行归约的规则为 T →F 。第一个符号为 T。
随后，再次进行归约，第一个符号为 E。
由于还有输入符号，我们发现，要将 E(和后面的某些符号 )归约，可能使用的规则为 E →E+T 。
我们读入 +，现在要归约的符号为 E+… 。显然，
我们要试图‘读入’一个 T，然后才能按照 E
→E+T 归约。这样，我们需要把余下输入的前面部分首先归约为 T，然后才可以得到结果。
因此，我们的下面首先尝试归约得到 T。
LR(K)分析技术的思想 (例子 )
要将余下的开始部分归约得到 T，我们可能的方法是，根据规则 T →F,或者 T →T*F 进行归约。
要试图按照规则 T →T*F 归约,必须首先归约得到 T。最初必须归约得到 F。而要得到 F，我们必须按照规则 F →i 或者 F →(E) 归约。
下一个符号是 i。所以，我们可以得到 F。
同样，我们由 F可以得到 T。
由于，前面我们已经得到了 E+，加上现在的 T，
我们得到了 E →E+T 。归约完成。
基本思想的实现
首先，如果我们试图按照某个规则来归约的话，
我们需要记住已经归约或移入得到的规则右部的前半部分。对于第 P规则 U →X1X2…Xn,我们用 U →X1X2…Xj.Xj+1…Xn 表示已经读入
（或归约得到）了前 j个符号，现在需要试图得到后面的符号。上面的称为一个‘ 项 ’,可以用
(P,j)表示。
但是，我们前面看到，在一个时刻会有多个可能猜测。所以，当前状态使用 项集 来表示。项集中的每个项都表示了一个可能的猜测。
基本思想的实现（续）
从前面的例子里面可以看到，我们尝试某个规则时，有必要先归约得到一个非终结符号。比如，我们尝试 E →E+T,并扫描到了 E+的时候，
需要首先归约得到一个 T。因此，当圆点在某个非终结符号的时候，我们需要首先尝试该非终结符号的规则。
定义：（项集闭包）
CLOSURE(S)=S?{[q,0;β]|[p,j,α]∈ CLOSUER(S),
j<np,Xpj+1=Uq，且 β∈ Hk(Xpj+2…Xpnp α)}
基本思想的实现（续）
Hk函数的说明,Hk函数的值是参数对应的字的前 K个符号。
定义,Hk(α)={β| α→* β…,| β|=K,β ∈ VT*}.
当 k=1的时候,Hk的求法就类似于 LL(1)技术中的第一个终结符号的求法。
项集闭包的例子
文法,0 Z::=E# 1 E::=E+T,2 E::=T
3 T::=T*F 4 T::=F 5 F::=(E)
6 F::=i
S={[Z→.E#,#]}
CLOSURE(S)还包含以下项：
[E→.E+T,#],[E→.T,#]
[E→.E+T,+],[E→.T,+],[T→.T*F,#],[T→.F,#]
[T→.T*F,+],[T→.F,+],[T→.T*F,*],[T →.F,*],[F →.i,#],
[F →.(E),#]
[F →.i,*],[T→.(E),*]
向前看符号串
向前看符号的说明：项中的向前看符号串是用来解决冲突问题的。在前面的例子中，我们已经归约得到了第一个 T，为什么没有尝试 T→T*F 呢？
原因就在于我们发现下一个符号是 +。这个 +号表明了我们可以将 T归约。
那么，当尝试一个规则，并移入 /归约得到了它右部的所有规则之后，什么时候可以归约呢?显然，
我们要考虑当初为什么要尝试这个规则。
如果尝试规则 U →u 的原因是：在尝试规则
V→…Ur 时，已经扫描到了 U的前面，试图归约得到 U。所以，此时如果要进行归约，向前看符号串必须时可以由 r推导得到（或者加上 V对应的向前看符号）。
向前看符号串
再次考虑项集闭包中，对于新增加项的向前看符号串的定义：
CLOSURE(S)=S?{[q,0;β]|[p,j,α]∈ CLOSUER(S),
j<np,Xpj+1=Uq，且 β∈ Hk(Xpj+2…Xpnp α )}
初始项集
我们将一个项集作为一个状态。
初始状态：在开始的时候，我们考虑的是最后归约到识别符号时候使用的规则。所以猜测的可能性 (项集 )为,CLOSURE(S)。其中 S为,
{[q,0;#k] | 第 q个规则为关于识别符号的规则 }。
显然，如果某个关于识别符号的规则的第一个符号是非终结符号的时候，我们还需要进行关于给识别符号的猜测。
初始项集的例子见前面项集之间的转换关系 (Action归约 )
我们需要构造两个分析表,Action和 Go。
状态对应于项集。在 Action中,A[S,α]表示的是栈顶状态为
S的时候，向前看符号串为 α的时候应该采取的动作。
当其中某个项的形状如,[U →x.,α] 的时候，表示针对该规则的扫描已经完成，并且，如果当前的符号为 α的话，就可以进行归约。因此这个项主张,A[S,α]的动作应该是按照这个规则进行归约。
如果有多个这样的规则，那么显然当栈顶符号为 S而向前看符号为 α的时候，我们有多个可能的归约方式。由于我们只有一个栈，不可能同时对这个栈中的符号进行多种操作。
所以这样就引起了冲突。
例子：当前状态（项集）为 {[2,1;#],[4,0,+],[6,0,#],…} 而向前看符号为 #，表示应该进行归约。
项集之间的转换关系 (Action移入 )
如果项集中有项 [U→x.ay,T],表示对应于这个项集的猜测需要输入一个 a，并且，如果 ay可能推导出 α的时候，这个项主张 A[S,α]的动作应该为移入。
如果有多个这样的项，那么表示它们都主张下一个操作是移入。由于移入的动作是将当前符号压入栈中，所以相互之间的主张并不冲突。
但是，如果同时还有项主张归约，那么就可能形成冲突。
当没有冲突的时候，可以将主张移入的项的圆点向右移动一位，表示该猜想离开成功已经又近了一步。而其它项被删除，
表示这些项对应的猜想已经失败。
例如：当前项集为 {[F→.(E),+],[F→.(E),#],…},当前符号为 (。那么它的下一个状态是 CLOSURE{[F→(.E),+],
[F→(.E),#],…}
项集之间的转换关系 (GO表 )
Go表确定了如果发生归约动作，将归约得到的非终结符号入栈之后，在栈顶的状态。
如果在非终结符号 U入栈之前，栈顶的状态中有项 [V→x.Uy,
a]。这个项表示，它对应的猜想希望输入一个 U。因此在下一个状态中，必然有项 [V →xU.y] 。
如果原状态中有多个这样的项，并不引起冲突。所有这样的项都应该将圆点后移，添加到后继状态中。其余的项对应的猜想已经失败。
后继状态为所有添加到表中的项的项集闭包。
Go表中的动作不会有冲突的情况。
LR(K)分析表的构造
构造初始项集闭包，这个项集在状态集合中。
对于每个项集 S，和每个终结符号串 α,S对应于 α首符号的移入 _后继的闭包也在状态集合中。相应的分析表项 A[S,α]中为移入，并且后继状态为该后继项集。
对于每个项集 S，如果项集中有项 [U→x.,α],那么分析表中有 A[S,α]=ri。其中 i为 U→x 对应的规则编号。
对于每个项集 S，和每个非终结符号 U，它们的移入 _
后继的闭包也在项集中。并且，分析表 Go中有对应项为 G[S,U]=后即对应的集合。
LR(K)文法的判定
如果按照上述算法得到的 LR(K)分析表中每一项最多只有一个值，那么这个文法就是 LR(K)的。
LR(K)技术的评价
适用面广：几乎可以适用于所有用上下文无关文法描述的程序设计语言，且一般只需要 K=1.
效率高：适用确定的下推自动机来实现。
错误发现及时：一旦语法有错误，立刻可以发现。便于进行其它出错处理。
便于识别程序的自动构造。
LR(0)方法和 SLR(K)技术
在 LR(K)技术中，每次都需要通过向前看 K个符号来确定下一步的动作。导致的结果是，状态非常多。
有的时候，不需要向前看就可以确定下一步的动作（归约，还是移入）。因此一个可能的解决办法是：当不能确定下一步动作的时候才向前看 K个符号。这个方法称为 SLR(K)方法。
首先，我们构造不向前看的 LR(0)分析表。
LR(0)分析
首先,LR(0)技术不需要向前看符号就可以确定是归约（到哪个符号）还是移入。
所以,LR(0)的分析表没有 ACTION部分。
在 LR(0)状态中，只有状态根据当前输入符号的转换关系。这些转换关系由特征自动机 (CFSM)表示。
CFSM的状态是 LR(0)项集闭包。
特征自动机 (CFSM)
完备项,U →u,称为完备项。包括接受项和归约项。如,Z →E#.,E →E+T.
不完备项,E →E.+T 。
接受项,Z →u,称为接受项。 Z →E#.
移入项,U →u.Tv,其中 T为终结符号。 E
→E.+T 。
待约项,U →u.Vv,其中 v为非终结符号。 E
→E+.T 。
特征自动机 (CFSM)
初始项,Z→.E# 。
后继项,U →u.Av 的后继项为 U →uA.v 。
项集和项集闭包：
LR(0)项集规范族的构造：
– 初始项的闭包在规范族里面。
– 如果 Si在规范族里面，那么其后继也在。
项集规范族的例子
0：初始项,Z →.E#,闭包集合,E →.E+T; E →.T; T→.T*F;
T→.F; F→.(E); F→.i 。
0 ---E---> 1：基本项,Z →E.# ； E →E.+T ；
0 ---T---> 2：基本项,E →T,； E → T.*F ；
0 ---F---> 3：基本项,T →F.
0 ---(---> 4：基本项,T →(.E) ；闭包集合,E →.E+T; E
→.T;,..
0 ---i---> 5：基本项,F→i,；
特征自动机
项集规范族和它们之间的转换关系可以用特征自动机描述。方法如下：
– 将 LR(0)项集规范族中的集合作为自动机的状态。
– 将状态之间的转换关系对应于后继关系。
– 和初始项集对应的状态为初始状态。和 #归约 _后继项集对应的状态作为该 FSM的终止状态。
特征自动机的例子
0 1
12
6 9
7 102
3
5
4 8 11
13
LR(0)项集的分类
归约状态：项集中只有一个完备项。这个状态只有一条到归约后继的出弧。
读状态：项集中包含的全部是不完备状态。没有到归约后继的出弧。
不适定状态：即有完备项，又有不完备项的状态称为不适定状态。这个状态既有到归约后继的出弧，还有到其它状态的弧。
利用 CFSM判断 LR(0)文法
一个文法是 LR(0)的，当且仅当该文法的
CFSM中间没有不设定状态。
利用 CFSM识别 LR(0)句子
将状态 0入栈。
读入下一个符号，入栈。由 CFSM确定栈顶状态，如果不能确定，出错。
如果当前的栈顶状态为读状态,goto步骤 2；如果是归约状态，根据相应的规则进行归约（此时可以进行相应的语义工作）。归约时，将相应的右部弹出。如果是归约到识别符号，那么句子接受，否则将非终结符号作为输入符号，
转步骤 2。
利用 CFSM识别 LR(0)文法的句子
文法,Z::=E# E::=aA | bB A::=Ca|d B::=cB|d
相应的 CFSM
0
3
2
1 12
5
4
6
7
8
9
11
13
10
识别过程步骤 栈 其余输入部分
0 0 其余输入部分
1 0a2 其余输入部分
2 0a2c5 其余输入部分
3 0a2c5c5 其余输入部分
4 0a2c5c5d6 其余输入部分
5 0a2c5c5A10 其余输入部分
6 0a2c5A10 其余输入部分
7 0a2A4 其余输入部分
8 0E1 其余输入部分
SLR(K)文法
LR(K)分析技术
活前缀：规范句型的一个头符号串，并且不包含句柄右部的任何符号。
比如：句型 E+T*i+i的活前缀有 E,E+T,
E+T*,E+T*i。
E+T*i+不是活前缀，因为句柄为 i，并且
+在 i的右面。
