第四章 语法分析语法分析是编译程序的核心部分、语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子
（程序），
自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法 (又称回溯法 )，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。
4.1 自顶向下的语法分析
4.1.1自顶向下的分析思想不确定的自顶向下分析思想主要是带回溯的自上而下的分析方法，所谓带回溯的自顶而下的分析方法是对任何输入串试图用一切可能的办法，从文法符号开始符号（根结点）出发，
自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻找一个最左推导。这种。这种过程本质上是一种试探过程，是反复使用不同的产生式谋求匹配输入串的过程。
例：设有文法 G[S]:
S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t
假定输入串为 abdet
显然上述分析法中不能有形如 P→Pα的规则，也不能有对某一非终结符 P存在 P=+=>Pα,即不能有规则左递归和文法左递归。
确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树，现举例说明：
例：若有文法 G1［ S］：
S→pA S→qB A→cAd A→a
若输入串 W=pccadd,自顶向下的推导过程为
S =>pA=>pcAd=>pccAdd=>pccadd
例：若有文法 G2[S]为：
S→Ap S→Bq A→a A→cA B→b B→dB
当输入串 W=ccap,那么试图推出输入串的推导过程为：
S=>Ap=>cAp=>ccAp=>ccap
例：若有文法 G3[S]：
S→aA S→d A→bAS A→ε
若输入串为 W=abd,则试图推导出 abd串的推导过程为：
S=>aA=>abAS=>abS=>abd
4.1.2 左递归和回溯性
1.左递归左递归在自顶向下的分析技术中是有害的，为此使用自顶向下的分析方法的文法中不能出现左递归,因此需要消去左递归。如果对于某非终结符 A存在着推导 A=+=>Aα，则称文法左递归或间接左递归；如果存在规则 A→Aα，则称规则左递归或直接左递归。对于规则左递归是可以消除的，
而对文法左递归只能对满足一定条的文法进行消去。
(1)规则左递归的消除
a.改写规则成右递归把 E→E+T|T 改写成 E→T+E|T
虽然在这里消去了左递归并不改变语言，但改变了结合性。
b.引进新的文法符号把 E→E+T|T T→T*F|F F→(E)|i 改写成
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
一般地：
A→Aα1|Aα2|Aα3|···|Aαm|β1|β2|β3|···|βn
改写成：
A→β1 A?|β2 A?|β3 A?|···|βnA?
A?→ α1 A?|α2 A?|α3 A?|···|αm A?|ε
例：消去 S→SS*|SS+|a中的左递归。
解,S→aS?
S?→ S*S?| S+S?|ε
(2)间接左递归的消除如果一个文法是无环的 (即 P=+=>P)和没有 ε产生式，那么可用下列算法消除。
a.以任意次序排列非终结符 A1,A2,A3,···,An
b.for(i=1;i<=n;i++)
{
for(j=1;j<=i-1;j++)
用产生式 Ai→δ1γ|δ2γ|δ3γ|···|δkγ代替每个形式为
Ai→Ajγ的产生式其中 Aj→δ1|δ2|δ3|···|δk是所有当前
Aj 产生式；
消去 Ai产生式中的直接左递归
}
c.除去那些从开始符号出发永远无法到达的非终结符的产生规则。
例：消去下列文法的左递归：
S→Aa|b A→Ac|Sd|ε
解：设 A1=S A2=A 则
S→Aa|b A→Ac|（ Aa|b） d|ε
S→Aa|b A→A（ c|ad） |bd|ε
S→Aa|b A→bdA?|A? A?→cA?|adA?|ε
2.回溯性在自顶向下的语法分析中，当前面临非终结符 P如存在规则
P→α1|α2|α3|···|αn，当前输入符号为 a时,究竟选用哪一个候选式，
如采用回溯则效率太低，现如能改变文法使每个候选式没有相同的“头符号”，则就能根据当前输入符号 a决定选用那一个产生式。
例,S→if E then S|if E then S else S|b
改写成：
S→if E then S S?|b
S?→else S|ε
一般地
A→δβ1|δβ2|δβ3|···|δβn|γ
改写成：
A→δA?|γ
A?→β1|β2|β3|···|βn
例：消去文法 G[S]:
S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t
的回溯性解,S→aBC B→ib|b C→dC?|c C?→eE? E?→h|G G→t
例：若有文法 G[S]：
S→aSd S→Ac A→aS A→b
解,S→aSd S→aSc S→bc
S→aSS? S→bc S?→d|c
但要注意不是所有的文法都能通过提左公因子消去回溯性的。
例：若有文法 G[S]：
S→Ap|Bq A→aAp|d B→aBq|e
解：上述文法的语言：
L[G]={andpn+1或 ameqm+1|m,n≥0}
由于不知道具体句子中 m和 n那一个大，也就无法知道应提多少个 a作为左因子递归下降分析法递归下降分析法又称递归子程序法简称递归下降法，它是一种无回溯的自顶向下分析技术，它的实现思想是让一个识别程序由一组过程（或函数）组成，其中每个过程对应于文法的一个非终结符号，由于文法的递归定义，故这些过程 往往是递归的，相应的程序称为递归下识别程序。
例：对于文法 G[E]：
E→E+T|T T→T*F F→（ E） |i
消去左递归和提左共因子后：
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
其递归子程序的流程图为：
其递归子程序为：
void E()
{T()； E?();
}
void E?()
{if(下一个符号 ==?+?)
{取下一个符号 ()；
T()； E?();
}
}
void T()；
{ F()； T?();
}
void T?()
{if(下一个符号 ==?*?)
{取下一个符号 ()；
F()； T?();
}
}
void F()
{
if(下一个符号 ==?i?)
取下一个符号 ();
else
if(下一个符号 ==?(?)
{取下一个符号 ()； E()；
if(下一个符号 ==?)?)
取下一个符号 ();
else 出错 ();
}
else 出错 ()；
}
在具体实现中,可以将写成拓广的 BNF,如下,
E→T{+T} T→F{*F) F→(E)|i
其递归子程序如下,
void E()
{T()；
while(下一个符号 ==?+?)
{取下一个符号 ()；
T();
}
}
void T()
{F()；
while(下一个符号 ==?*?)
{取下一个符号 ()；
F();
}
}
void F()
{
if(下一个符号 ==?i?)
取下一个符号 ();
else
if(下一个符号 ==?(?)
{取下一个符号 ()； E()；
if(下一个符号 ==?)?)
取下一个符号 ();
else 出错 ();
}
else 出错 ()；
}
递归下降分析法的优点：
(1)方法简单
(2)能灵活地在各过程中添加语义动作
(3)当能用某种程序设计语言写出所有这些过程或函数（包括递归过程或函数）时，可以由该语言的编译系统来生成整个识别程序。
4.1.4 预测分析法递归子程序是由一组递归过程组成的，它的实现极大程度地取决于递归过程的实现，如递归过程的允许嵌套调用层数，
但某些程序设计语言不允许递归,也有些程序设计语言递归的嵌套层数受限制,为此引进了一种新的自顶向下的分析方法 ——预测分析法。
预测分析法也是一种无回溯的自顶向下的分析技术，当然一般情况下，其文法也满足 LL（ 1）文法的条件。
所谓 LL（ K）分析法，这里的第一个 L表示从左到右扫描输入符号串，第二个 L表示分析过程中采用的是最左推导。括号中的 1表向前（向右）看 K个符号。
1.LL(1)分析器的逻辑结构和工作过程一个 LL（ 1）分析器是由一个总控程序，一个输入带、一张分析表和一个栈组成的，如图所示：
（ 1）分析表在 LL(1)分析器中使用了一张分析表。用 M[A,a]形式的矩阵（或二维数组）表示，其中 A 是文法的非终结符号,a是文法的终结符号或,#”（,#”是为分析方便而引入的一个特殊符号，把它作为输入符号串的结束符）。分析表矩阵元素
M[A,a]表示当前非终结符 A，面临输入符号 a时按存放关于符
A的产生式展开，如表中元素为空白时表示出错。
（ 2）分析栈用于存放分析过程中的文法符号。分析栈初始化时，在栈底压入一个,#”，然后再压入文法的开始符号，表示试图将开始符号推导出输入符号串。
（ 3）总控程序总控程序的功能是依据分析表、分析栈和输入符号串的状态进行分析和识别。它在任何时候都是根据当前分析栈的栈顶文法符号 X和当前的输入符号 a来决定采取相应的动作，从而达到语法分析的目的。
总控程序的具体算法如下：
分析开始时进行有关的初始化工作：把,#”及文法的开始符号
S依次压入分析栈，并把各指示器的指针调整至起始位置。
设分析到的某一步，分析栈当前的栈顶符号为 X，输入串分析指针当前指向的符号为 a，则：
a.若 X∈ Vt ∪ {#}
① X=a=“#”，表示分析成功，停止分析过程。
② X=a≠“#”，则从栈顶弹出 X，输入串指向下一个字符
③ X≠a，则表示发现错误，调相应的出错处理程序进行处理。
b.若 X∈ Vn：则根据 X与 a查分析表 M，根据 M[X,a]中的内容决定：
①若 M[X,a]中为一个规则，则将 X从分析栈中弹出，并将此规则右部的符号序列按倒序压入分析栈（若规则为 X→ε，则仅将 X从栈中弹出）。
②若 M[X,a]中为空白，则表示出错，调用相应的出错处理程序处理。
例,E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
的分析表如下：
i + * ( ) #
E E→TE ’ E→TE ’
E’ E→+TE ’ E’→ ε E’→ ε
T T→FT ’ T→FT ’
T’ T’→ ε T→*FT ’ T’→ ε T’→ ε
F F→i F→(E)
步骤 栈 剩余输入串 输出
0 #E i*(i+i)+i# E→TE?
1 #E?T i*(i+i)+i# T→FT?
2 #E?T?F i*(i+i)+i# F→i
3 #E?T?i i*(i+i)+i# i匹配
4 #E?T? *(i+i)+i# T? →*F T?
5 #E?T?F* *(i+i)+i# *匹配
6 #E?T?F (i+i)+i# F→(E)
7 #E?T?)E( (i+i)+i# (匹配
8 #E?T?)E i+i)+i# E→TE?
9 #E?T?)E?T i+i)+i# T→FT?
10 #E?T?)E?T?F i+i)+i# F→i
11 #E?T?)E?T?i i+i)+i# i匹配
12 #E?T?)E?T? +i)+i# T? →ε
13 #E?T?)E? +i)+i# E? →+TE?
14 #E?T?)E?T+ +i)+i# +匹配
15 #E?T?)E?T i)+i# T→FT?
16 #E?T?)E?T?F i)+i# F→i
17 #E?T?)E?T?i i)+i# i 匹配
18 #E?T?)E?T? )+i# T? →ε
19 #E?T?)E? )+i# E? →ε
20 #E?T?) )+i# )匹配
21 #E?T? +i# T? →ε
22 #E? +i# E? → +TE?
23 #E?T+ +i# +匹配
24 #E?T i# T→FT?
25 # E?T? F i# F→i
26 # E?T? i i# i 匹配
27 # E?T? # T? →ε
28 # E? # E?→ε
29 # # 接受
2.预测分析表的构造由于所有的 LL(1)分析器的输入带、栈和总控程序都是一样的，唯一区别的是分析表。下面介绍分析表的构造算法。
定义 4-1：
FIRST(α)={a|α=+=>a...,a∈ Vt}
特别地，若 α=*=>ε，则规定 ε∈ FIRST(α)
如果非终结符 A的所有选择的首符集两两不相交，即 A的任何两个不同的选择 αi和 αj有 FIRST(αi)∩ FIRST(αj)=Φ时，要求 A
匹配输入串时,A就能根据它所面临的第一个输入符号 a,准确地指派某一个选择前支执行任务，这个选择就是那个终结首符属于的 α。如果 ε∈ FIRST(α)，会使问题稍为复杂。由于某个非终结符 A如要推导成 ε，那么当输入符号 a不是 A中的符号而是 A
后面的符号，为此定义 FOLLOW集合。
定义 4-2
FOLLOW（ A） ={a|S=*=>...Aa...,a∈ Vt}
若 S=*=>...A，则规定 #∈ FOLLOW（ A）
如果,A的任何两个不同的选择 αi和 αj不同时能推导出 ε，
不失一般性设 αi=*=>ε。也能根据其 FIRST(αi)和
FIRST(α)∪ FOLLOW（ A）决定选择那一个产生式。
定义 4-3
对于产生式 A→α，若 α=*=>ε,
则 SELECT(A→α)=（ FIRST(α)-{ ε}） ∪ FOLLOW（ A）,否则
SELECT(A→α)= FIRST(α)
定理 一个上下文无关文法是 LL（ 1）文法的充分必要条件是，
对每个非终结符 A的任何两个不同产生式,A→αi和 A→αj，满足
SELECT（ A→αi ） ∩SELECT（ A→αj） =Φ
显然 αi和 αj不同时为 ε
LL（ 1）文法的性质：
（ 1）任何二义性文法都不是 LL（ 1）文法，任何 LL（ 1）文法都不是二义性的
（ 2）若一个文法中含有左公因子或左递归，则该文法必然不是 LL（ 1）文法，但不含左公因子和左递归的文法不一定是
LL（ 1）文法。
另外，存在算法能判定一个文法是否是 LL（ 1）文法；也存在能判定二个 LL（ 1）文法是否能产生相同的语言；但不存在能判定一个上下文无关的文法是否能变换成等价的 LL（ 1）
文法。
FIRST集合构造算法：
对于每一个文法符号 X∈ Vt∪ Vn,构造 FIRST（ X），可重复应用下列步骤直到再无终结符号或 ε能被添入到任何 FIRST集合中为止。
（ 1）若 X∈ Vt，则 FIRST（ X） ={X}
（ 2）若 X∈ Vn，且有产生式 X→a...则把 a加入到 FIRST（ X）
中；若 X→ε也是一条产生式，则把 ε也加到 FIRST（ X）中若 X→Y...是一个产生式且 Y∈ Vn，则把 FIRST（ Y）中的所有非
ε元素都加到 FIRST（ X）中，若 X→Y1Y2Y3...Yk是一个产生式，
Y1Y2Y3...Yi-1都 是非终结符，而且，对于任何 j,1≤j≤i-1,FIRST
（ Yi）都含有 ε（即 Y1Y2Y3...Yi-1=*=>ε）,则把 FIRST（ Yi）中的所有 FIRST（ Yi）中的所有非 ε元素加到 FIRST（ X）中去；特别是，若所有的 FIRST（ Yi）均有 ε,j=1,2,3...,k,则把 ε加到
FIRST(X)。
符号串 X1X2X3...Xn的 FIRST集合的算法：
把 FIRST（ X1）的非 ε元素加到 FIRST（ X1X2X3...Xn）中，如果 ε在 FIRST（ X1）中，那么加入 FIRST（ X2）中全部非 ε元素；
如果 FIRST（ X1）和 FIRST（ X2）中都有 ε则把 FIRST（ X3）中全部非 ε元素加到 FIRST（ X1X2X3...Xn）中，以此类推，最后对所有的 i，有 ε属于 FIRST（ Xi），那么把 ε加入 FIRST
（ X1X2X3...Xn）中。
对非终结的 FOLLOW算法：
对于文法 G的每个非终结符 A构造 FOLLOW（ A）的办法是重复应用下列步骤直到再无终结符号或 #能被添入到任何
FOLLOW（ A）中：
（ 1）对于文法的开始符号（识别符号） S，置 #于
FOLLOW（ A）中；
（ 2）若 A→αBβ是一个产生式，则把 FIRST（ β）中的非 ε的一切符号加至 FOLLOW(B)中；
（ 3）若 A→αB是一个产生式，或 A→αBβ是一个产生式，而
β=*=>ε(即 ε∈ FIRST（ β） )，则把 FOLLOW（ A）加入
FOLLOW（ B）中
SELECT构造算法：
对于每个产生式 A→α构造 SELECT（ A→α），当
ε∈ FIRST（ α），则 SELECT（ A→α） =（ FIRST(α)-{ε}）
∪ FOLLOW（ A）,否则 SELECT(A→α)= FIRST(α)
例：求文法 G[S],S→AB S→bC A→ε A→b B→ε B→aD
C→AD C→b D→aS D→c的 FIRST,FOLLOW和 SELECT
集。
(S)={a,b,ε}
FIRST(A)={b,ε}
FIRST(B)={a,ε}
FIRST(C)={a,b,c}
FIRST(D)={a,c}
FIRST(AB)={a,b,ε}
FIRST(bC)={b}
FIRST(ε)={ε}
FIRST(b)={b}
FIRST(aD)={a}
FIRST(b)={b}
FIRST(aS)={a}
FIRST(c)={c}
FOLLOW(S)={#}
FOLLOW(A)={a,#,c}
FOLLOW(B)={#}
FOLLOW(C)={#}
FOLLOW(D)={#}
SELECT(S→AB)={a,b,#}
SELECT(S→bC)={b}
SELECT(A→ε)={a,c,#}
SELECT(A→b)={b}
SELECT(B→ε)={#}
SELECT(B→aD)={a}
SELECT(C→AD)={a,b,c}
SELECT(C→b)={b}
SELECT(D→aS)={a}
SELECT(D→c)={c}
例：构造文法 G[E]：
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
的 FIRST,FOLLOW,SELECT集解,FIRST(E)={(,i}
FIRST(E?)={+,ε}
FIRST(T)={(,i}
FIRST(T?)={*,ε}
FIRST(F)= {(,i}
FOLLOW(E)={#,)}
FOLLOW(E?)={#,)}
FOLLOW(T)={#,),+}
FOLLOW(T?)={#,),+}
FOLLOW(F)={#,),+,*}
SELECT(E→TE?)={(,i}
SELECT(E?→+TE?)={+}
SELECT(E?→ε)= {#,)}
SELECT(T→FT?)={(,i}
SELECT(T?→*FT?)={*}
SELECT(T?→ε)= {#,),+}
SELECT(F→(E))= {(}
SELECT(F→i)={i}
构造预测分析表构造算法：
（ 1）先求出每个产生式的 SELECT集
（ 2）对于每个终结符或 #用 a表示。
若 a∈ SELECT(A→α),则把 A→α放入 M[A,a]中。
（ 3）把所有无定义的 M[A,a]标记为出错，用空白表示。
例：试构造上述文法的预测分析表。
解：先求 FIRST,FOLLOW和 SELECT集（略）
i + * ( ) #
E E→TE ’ E→TE ’
E’ E→+TE ’ E’→ ε E’→ ε
T T→FT ’ T→FT ’
T’ T’→ ε T→*FT ’ T’→ ε T’→ ε
F F→i F→(E)
二义性文法的应用虽然任何二义性文法都不是 LL（ 1）文法，但具体应用中，
可根据实际情况删减，也是能达到分析目的的。
例,G[S],S→if E then S S?|a
S?→else S|
E→b
解,FIRST(S)={if} FIRST(S?)={else,ε}
FIRST(E)={b}
FOLLOW(S)={else,#}
FOLLOW(S?)={else,#} FOLLOW(E)={then}
SELECT(S→if E then S S?)={if}
SELECT(S→a)={a}
SELECT(S?→else S)={else}
SELECT(S?→ε)={else,#}
SELECT(E→b)={b}
则分析表为
a b else if then #
S S→a S→if E then S S ’
S’ S’→else S
S’→ ε
S’→ ε
E E→b
可以根据实际情况在 M[s?,else]中删除 S?→ε即可。
4.2 自底向上的语法分析所谓自底向上的分析方法就是从输入符号出发逐步归约成识别符号,
4.2.1自底向上的分析法概述自底向上的分析法的思想方法主要是从左到右扫描输入符号串，从语法树的角度出发也就是从末端结点出发向根结点方向往上构造语法树，也就是说自底向上的分析方法是一个不断归约的过程。要实现自底向上的分析方法需要解决两个问题：
(1) 确定句型中将要归约的符号串
(2) 如果该子串能归约多个非终结符号，需决定归约成那一个符号由于栈在计算机中实现比较方便，在语法分析中往往使用栈，为更好地识别出输入串的结束，也引进了特殊符号 #，把它压入栈底以及放在输入符号后面，如：
栈 输入
# a1a2a3a4...an#
这样可以采用“移入 —归约”法，这种方法每移入一个字符判断是否可以归约，若能归约则归约到不能归约为止，否则再移入下一个字符。由于在“移入 —归约”中每次归约的是最左边的非终结符，应该就是最左归约即最右推导的逆过程，那么在没有二义性的前提下其最左归约是唯一的，也就是句柄是唯一的。如果在分析过程式中发现错误（找不到貌似句柄的符号串）或者呈下列情形结束栈 输入
#S #
其中 S是识别符号。
例：设 G[S],S→aAcBe A→b A→Ab B→d
识别符号串 abbcde
步骤 符号栈 输入符号串 动作
1 # abbcde# 移入
2 #a bbcde# 移入
3 #ab bcde# 归约（ A→b ）
4 #aA bcde# 移入
5 #aAb cde# 归约（ A→Ab ）
6 #aA cde# 移入
7 #aAc de# 移入
8 #aAcd e# 归约（ B→d ）
9 #aAcB e# 移入
10 #aAcBe # 归约（ S→aAcBe ）
11 #S # 接受
1,简单优先分析法概述简单优先分析法是按照每个文法符号之间的优先关系确定句柄的，这样如何找到这种优先关系也就是这种识别方法的关键。
优先关系定义 4-4
定义优先关系的定义：
X〧 Y 表示 X和 Y的优先 x级相等
X·>Y 表示 X优先级大于 Y的优先级
X<·Y 表示 X优先级小于 Y的优先级注意：〧 ·> <·与数学中的 =,>,< 不同定理：
X〧 Y 当且仅当 G中存在产生式规则Ａ →···XY···
X<·Y 当且仅当 G中存在产生式规则Ａ →···XB···,且 B=+=>Y···
X·>Y 当且仅当 G中存在产生式规则Ａ →···BD···,且 B=+=>···X
D=+=>Y···
例：若有文法 G[S]:
S→bAb A→(B|a B→Aa)
则,
根据上述文法符号之间的的关系，可以逐步列出其矩阵，
如下所示。
S b A ( B a ) #
S ·>
b 〧 <· <· ·>
A 〧 〧
( <· <· 〧 <·
B ·> ·>
a ·> ·> 〧
) ·> ·>
# <· <· 〧
显然用上述方法构造优先矩阵当文法较复杂时，就很难构造出全部元素，应采用 LAST,FIRST集合的算法。
定义 4-5
若一个文法是简单优先文法必须满足以下条件：
(1) 在文法符号集 V中，任意两个符号之间最多只有一种优先关系成立。
(2) 在文法中任意两个产生式没有相同的右部。
则称该文法是简单优先文法对于第一条件规定在任何时候都可以确切地找到形如 Sj-1<·Sj〧
Sj+1〧 … 〧 Si·> Si+1的“句柄”，第二条件就是找到上述符号串后能知道归约成那一个非终结符号。
简单优先分析法简优先分析法的思想方法是首先找出“句柄”的尾，然后再找句柄的头，找到貌似“句柄”的符号串寻求相应归约成的非终结符。算法如下：
2,算符优先分析法概述人们在计算表达式时习惯用先乘除后加减，因而在处理表达式 3+5*2时需先做 5*2，而处理 3+5-2时需先做 3+5，这时由于在运算符之间规定了优先级，计算表达式的过程和表达式的归约过程致相同，前者将子表达式的值代替子表达式，后者以非终结符代替。是否能将这种技术推广到具体的语言识别过程中呢？这就需要考虑运算符是什么？运算对象是什么？显然可以将终结符代表运算符，非终结符代表运算对象，这种公在终结符之间引进的优先关系的优先分析技术称为算符优先分析技术，在算符优先分析技术的讨论中，将术语“终结符号”视为
“运算符”，而把术语“非终结符”号视为“运算对象”。算符优分析过程式是自底向上的归约进程，但这种归约未必是严格的最左归约，也就是说，算符优先分析法不是一种规范归约法。
例：设 G[E]:E→E+E|E*E|(E)|i
其终结符号的优先关系表如下：
+ * （ ） i
+ ·> <· <· ·> <·
* ·> ·> <· ·> <·
( <· <· <· 〧 <·
) ·> ·> ·>
i ·> ·> ·>
下面利用其优先关系识别输入符号串 i+i+i*(i+i)
步骤 栈 输入符号串 动作
1 # i+i+i*(i+i)# 移入
2 #i +i+i*(i+i)# 归约 E→i
3 #E +i+i*(i+i)# 移入
4 #E+ i+i*(i+i)# 移入
5 # E+i +i*(i+i)# 归约 E→i
6 # E+E +i*(i+i)# 归约 E→E+E
7 # E +i*(i+i)# 移入
8 #E+ i*(i+i)# 移入
9 # E+i *(i+i)# 归约 E→i
10 # E+E *(i+i)# 移入
11 # E+E* (i+i)# 移入
12 # E+E*( i+i)# 移入
13 # E+E*(i +i)# 归约 E→i
14 # E+E*(E +i)# 移入
15 # E+E*(E+ i)# 移入
16 # E+E*(E+i )# 归约 E→i
17 # E+E*(E+E )# 归约 E→E+E
18 # E+E*(E )# 移入
19 # E+E*(E) # 归约 E→(E)
20 # E+E*E # 归约 E→E*E
21 # E+E # 归约 E→E+E
22 # E # 接受直观算符优先分析法从前面的例子可以看出其运算次序是先乘除后加减，而且加乘运算符都是左结合的。同样两个终结符之间的关系成这这种算法的关键。下面定义它的优先关系：
定义 4-6
a<·b 表示 a的优先级小于 b
a〧 b 表示 a的优先级等于 b
a·>b 表示 a的优先级大于 b
同样，〧 ·> <·与数学中的 =,>,< 不同这样可以根据运算符的优先级各结合性来构造出上述文法的算符优先分析表。
作为一种通用的分析技术，算符优先分析有它的缺点，它很难处理象减 /负这样的记号，因为它有不同的优先级。适用于算符优先分析技术的文法相对较小。
算符优先文法的定义算符优先技术能适用算符优先文法，那么是什么是算符优先文法，什么是算符文法呢？前面已经知道一般表达式中不能连续出二个运算对象。类似地，算符优先技术只能应用于规右部中任何两 个非终结符号之间必定出现终结符号的文法，这种文法就称为算符文法，为实现方便起间规定它不含有形如 P→ε
的产生式。
定义 4-7
如果某文法 G中没有形如 A→……BC…… 的产生式，其中
A,B,C∈ Vn,则文法称为算符文法，也称 OG文法。
算符文法的一些性质：
（ 1）对于算符文法，不存在包有两个相邻非终结符号的句型
（ 2）如果 aP出现在句型 α中，其 a∈ Vt,P∈ Vn，则 α中包含其 a
的短语必包含 P
（ 3）如果 Pa出现在句型 α中，其 a∈ Vt,P，则 α中包含其 a的短语必包含 P
（ 4）在算符文法的任何句型中，不存在其紧前或紧后是非终结符的短语例：对一些文法的讨论：
(1) 规则：
<如果子句 >→if <布尔表达式 > then
<如果语句 >→<如果子句 ><无条件语句 >
<条件语句 >→<如果语句 >|<如果语句 > else <语句 >
……
显然上述文法不是算符文法，为此可以不改变语言地改变文法使其成为算符文法，重新定义为：
<如果子句 >→if <布尔表达式 >
<如果语句 >→<如果子句 > then <无条件语句 >
<条件语句 >→<如果语句 >|<如果语句 > else <语句 >
(2)规则：
<左部 >→<变量 >:=|<函数标识符 >:=
<左部表 >→<左部 >|<左部表 ><左部 >
<赋值语句 >→<左部表 ><表达式 >
重新定义为：
<左部 >→<变量 >|<函数标识符 >
<左部表 >→<左部 >|<左部表 >:=<左部 >
<赋值语句 >→<左部表 >:=<表达式 >
定义 4-8
设文法 G是不含 ε产生式的算符文法,a,b是任意一对运算符
（终结符），而 A,B,C∈ Vn，其优先关系定义如下：
1.a〧 b 当且仅当 G中存在产生式Ａ →···ab···或Ａ →···aBb···
2.a<·b 当且仅当 G中存在产生式规则Ａ →···aB···,且
B=+=>b···或 B=+=>Cb···
3.a·>b 当且仅当 G中存在产生式规则Ａ →···Bb···,而 B=+=>···a
或 B=+=>···aC
定义 如果一个算符文法 G中的任何终结符对（ a.b）至多只满足下述三关系之一
a〧 b a<·b a·>b
则称 G是一个算符优先文法。
例：考虑文法 G[E]：
E→E+T|T T→T*F|F F→P↑F|P P→(E)|i
其中 Vt={+,*,↑，（，）,i}
根据规则 E→E+T和 T=+=>T*F可得 +<·*
根据规则 T→T*F和 F=+=>P↑F可得 *<·↑
根据规则 E→E+T和 E=+=>E+T可得 +·>+
根据规则 F→P↑F和 F=+=>P↑F可得 ↑<·↑
根据规则 P→(E)和
E=>E+T=>T+T=>T*F+T=>F*F+T=>P↑F*F+T=>i↑F*F+T
=>i↑F*F+T=>i↑F*F+T*F=>i↑F*F+F=>i↑F*F+T*i
可得：（ <·+ （ <·* （ <·↑ （ <·i +·>) *·>) i·>)
这种构造优先关系不仅复杂，而且很难全部构造出这运算符的优先关系，为此我们需研究构造 算符优先文法的优先关系表的算法。
算符优先关系的构造定义 4-9
FIRSTVT(B)={a|B=+=>a… 或 B=+=>Ca…}
LASTVT(B)={a|B=+=>…a 或 B=+=>…aC}
构造优先关系算法：
对于每个规则 A→…ab… 或 A→…aBb… 中的 a和 b置 a〧 b
对于每个规则 A→…aB… 的 FIRSTVT(B)中的每个终结符 b置
a<·b
对于每个规则 A→…Bb… 的 LASTVT(B)中的每个终结符 a置
a·>b
例：设有文法 G[E]:E→E+T|T T→T*F|F F→(E)|i
试构造其算符优先矩阵解：先求 FIRSTVT和 LASTVT集合：
FIRSTVT(E)={+,*,(,i}
FIRSTVT(T)={*,(,i}
FIRSTVT(F)={(,i}
LASTVT(E)={+,*,),i}
LASTVT(T)={*,),i}
LASTVT(F)={),i}
则：
+ * （ ） i
+ ·> <· <· ·> <·
* ·> ·> <· ·> <·
( <· <· <· 〧 <·
) ·> ·> ·>
i ·> ·> ·>
算符优先分析算法考虑算符优先文法，把句型括在二个 #之间的一般形式写成：
#N1a1N2a2……N n+1anNn+1#
其中，每个 ai都是终结符,Nj是可有可无的非终结符。
找出和归约的是满足如下条件的最左子串 Njaj……N iaiNi+1,
aj-1<·aj
aj〧 aj+1〧 ……a i-1〧 ai
ai·>ai+1
最左素短语在算符优先文法中，仅对终结符号引进优先关系，未对非终结符号定义算符优先关系，所以不能使用这些关系去查找由单个非终结符号组成的句柄。如文法 G[E],E→E+T|T
T→T*F|F F→(E)|i的句型 T+F，显然有 #<·+和 +·>#，但句柄却是 T而不是 T+F为此不能识别出句柄 T。下面将设计一种类似于规范分析的分析法，这种分析法仍然是自底向上的，但不是严格从左到右的，在每一步分析中，它将识别和最约那些所谓的
“最左素短语”（质短语）
定义 4-10
所谓最左素短语是这样的一个短语，它至少含有一个终结符，且除它本身外不包含其它素短语。
例：文法 G[E],E→E+T|T
T→T*F|F F→(E)|i的句型
T+T*F+i相应的语法树如图所示，显然有短语 T+T*F+i、
T+T*F,T,T*F,i。素短语为 T*F,i最左素短语为 T*F
例：句型 i+(i+i)*i的识别步骤 句型 关系 最左素短语 归约符号
1 #i+(i+i)*i# #<·i·>+ i F
2 #F+(i+i)*i# #<·+<·(<·i·>+ i F
3 #F+(F+i)*i# #<·+<·(<·+<·i·>) i F
4 #F+(F+F)*i# #<·+<·(<·+·>) F+F E
5 #F+(E)*i# #<·+<·(〧 )·>* (E) F
6 #F+F*i# #<·+<·*<·i·># i F
7 #F+F*F# #<·+<·*·># F*F T
8 #F+T# #<·+·># F+T E
9 #E# 接受从上述分析过程中可以看出了每个素短语所应归约成的非终结符号，但是请注意在查找所应归约的最左素短语的过程中，
全然没有用到非终结符。无论是 E+T,T+T,E+F,T+F、或
F+F都有归约成 E，这样的分析算法跳过了形如 P→Q的单规则的直接归约步骤，因此算符优先分析法速度稍快。但由于非终结符在识别过程中不起作用，甚至可以考虑非终结符用 N代表或者非终结符不进栈。这种忽略非终结符的归约有时会影响出错的位置，并且存在这样的危险性，可能导致把原来不是句子的输入串误认为句子，但这种缺陷容易从其它技术上加以弥补。
4.2.2 LR分析法的概念前面已经介绍了一些自顶向下的语法分析如：预测分析法、
递归子程序法以及自底向上的分析法，如：简单优先分析法、
算符优先文法。这些方法有一个共同的特点就是很能难适用自动构造,而且文法的适用范围比较小,这些方法往往需要人工构造，这种人工构造识别程序的方法不仅烦琐，而且很容易出错不利于编译程序的开发，为此希望有能够适应于自动构造类的识别程序。这类识别程序也是自底向上的分析的识别程序，其文法仍为上下文无关的文法，而且也是以“移入 —归约法”法为基础的，这种技术称为 LR（ K）分析技术。
LR（ K）分析方法是 1956年 Knuth提出的，其中 L指的是从左向右扫描输入,R指的是构造最右推导的逆,K指的是在决定分析动作时间前看的符号个数。括号和 K省略时，表示 K是 1。
这种方法比自顶向下的 LL（ K）分析方法和自底向上的优先分方法对文法的限制要少得多，也就是说对于绝大多数上下文无关的文法描述的语言都有可以用 LR分析方法进行识别。规范归约的的关键问题是寻找句柄，在一般的“移入 —归约法”过程中，当一串貌似句柄的符号呈现在栈顶时，如何知道它是不是句柄,LR方法就是根据已扫过的符号（用若干状态表示）及以后可能的输入符号判断是归约还是移入，并在归约时决定归约成哪一个非终结符号。 LR自左到右扫描输入串时就能发现其中的错误，并能指出其位置，这种分析法的缺点是若用手工构造成分析程序则工作量很大，需求助于自动产生这些分析程序的产生器。
一个 LR分析器是由三个部分组成的：
(1) 总控程序，也称驱动程序。对所有的 LR分析器总控程序都是一样的
(2) 分析表，不同的文法其分析表是不同的，因此分析表是整个 LR识别方法的核心。它是由两部分组成的，一是“动作” atction,另一是“状态转换” goto。
(3) 分析栈，包括文法符号栈和状态栈它们均是前进后出地处理已获得的信息。
分析器的动作就是由栈顶状态和当前输入符号所决定（ LR（ 0）
可以不由当前输入符号就可决定移入还是归约 )。
LR分析器如图如示。
ACTION[Si,a］规定了栈顶状态为 Si时遇到输入符号 a应执行的动作。动作有 4种可能：
（ l）移进,
把 Sj=GOTO[Si,a］移入到状态栈，把 a移入到文法符号栈。
其中 i,j表示状态号。
（ 2）归约,
当在栈顶形成句柄为 β时，则用 β归约为相应的非终结符 A，
即文法中有 A→β的产生式，若 β的长度为 r（即 |β|=r），则从状态栈和文法符号栈中自栈顶向下去掉 r个符号,即栈指针 SP减去 r。
并把 A移入文法符号栈内,Sj=GOTO[Si,A]移进状态栈，其中
Sj 为修改指针后的栈顶状态。
（ 3）接受 acc:
当归约到文法符号伐中只剩文法的开始符号 S?时，并且输入符号串已结束即当前输入符是‘＃’，则为分析成功。
（ 4）报错当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，
则报错，说明输入串不是该文法能接受的句子。
从上面可以看出 LR分析器的关键部分是分析表的构造，后边将针对每种不同的 LR分析器详细介绍其构造思想及方法。
例：设有文法 G[S]为：
(1) S→A
(2) S→B
(3) A→aAb
(4) A→c
(5) B→aBb
(6) B→d
有分析表：
状态
ACTION GOTO
a b c d # S A B
0 S4 S5 S6 1 2 3
1 acc
2 r1 r1 r1 r1 r1
3 r2 r2 r2 r2 r2
4 S4 S5 S6 7 8
5 r4 r4 r4 r4 r4
6 r6 r6 r6 r6 r6
7 S9
8 S10
9 r3 r3 r3 r3 r3
10 r5 r5 r5 r5 r5
现用移入归约法对输入串 aaaadbbbb＃进行分析：
步骤 状态栈 符号栈 输入串 ACTION GOTO
1 0 # aaaadbbbb＃ S4
2 04 #a aaadbbbb＃ S4
3 044 #aa aadbbbb＃ S4
4 0444 #aaa adbbbb＃ S4
5 04444 #aaaa dbbbb＃ S6
6 044446 #aaaad bbbb＃ r6 8
7 044448 #aaaaB bbbb＃ S10
8 04444810 #aaaaBb bbb＃ r5 8
9 04448 #aaaB bbb＃ S10
10 0444810 #aaaBb bb＃ r5 8
11 0448 #aaB bb＃ S10
12 044810 #aaBb b＃ r5 8
13 048 #aB b＃ S10
14 04810 #aBb # r5 1
15 03 #B # r2 1
16 01 #S # acc
从上例中可以看出在符号栈中的符号串为一个规范句型的前缀，
由于采用的是所谓“移入 —归约法”,即一旦发现句柄就将句柄归约，因此在栈中是不会含句柄后任何符号，为此指导把这些在栈中可以出现的符号串给一个定义。
定义 4-11：活前缀是指范句型的一个前缀,它不含句柄之后的任何符号即：若 S=r=>αAω=r=>α β ω是文法 G中的一个规范推导，则句柄是 β，因此不包含句柄的符号串为 αβ的前缀均为活前缀。
在上例中的识别过程中，还可以看出整个识别过程实际上是一个活前缀的变化过程。
为了识别方便，即发现识别符号就认为是接受状态，引进一个新的文法符号 S?它不在规则的右部出现，使 S?→S,其中 S原来的识别符号，一旦要将 S归约成 S?时，即为识别状态。
计算活前缀的直观方法是写出全部规范句型的符号串例：在上例中有：
S =r=>A=r=>aAb=r=>a2Ab2……= r=> anAbn=r=> ancbn 及
S =r=>B=r=>aBb=r=>a2Bb2……=r=> a nBbn=r=> andbn
则相应的活前缀为有：
ε,a,a2,a3……a n,anc,and,anA,anB,anAb,anBb,an-1A,an-1B,
an-1Ab,an-1Bb,……,A,B
4.2.3 LR(0)项目集族的构造根据 LR（ k）的定义,LR（ 0）就是不需要根据展望信息，
就可知道是移入还是归约，而且能知道归约成那一个非终结符号，换句话说，一但发现一些状态呈现“句柄”就可将它归约。
下面讨论 LR（ 0）文法的项目集族的构造以及其分析表的构造。
LR（ 0）项目定义 4.12 如果 A→αβ是文法的一个产生式。其中 α和 β可为 ε则
A→α·β称为 G的 LR（ 0）项目，简称项目或项。
例,G[E]：
E→E+T|T T→T*F|F F→(E)|i
有项目 E→·E+T E→E·+T E→E+·T E→E+T·
E→T·
F→(E·)
F→i·
等显然，若有产生式 A→α则可有 |α|+1个项目，产生式 A→ε只有项目 A→·
项目名称
·移入项目 圆点点在终结符前面的的项目称为“移入项目”，
即在该状态时，需将终结符移入符号栈
·待约项目 圆点点在非终结符前面的项目称为“待约项目”，
即等待该非终结符的归约
·归约项目 圆点点在整个产生式的右部的项目称为“归约项目”，表示该产生式相应的文法符号都已找到，可归约成相应的非终结符
·接受项目 设 S?是拓广文法的识别符号，如项 S?→α·，称为
“接受项目”
为了使“接受”状态易于识别，让识别符号不在产生式的左部出现，把文法添上一个产的产生式 S?→S或 S?→S#，这样就仅有唯一的“接受”状态。
定义 4.13 设 A→α·Xβ是文法 G的一个 LR（ 0）项目，其中
X∈ Vn∪ Vt,则 LR（ 0）项目 A→αX·β称为它的后继项目，其中 α、
β∈ （ Vn∪ Vt） *
定义 4.14 由 LR（ 0）组成的集合称为 LR（ 0）项目集，简称项集。
定义 4.15 识别文法 G活前缀的项目集的全体称为文法的 LR(0)
项目集规范族,简称项目集族。
1.构造文法 G的 LR(0)项目集族的方法之一从 LR(0)项目出发来构造识别文法所有活前缀的自动机。
其步骤是，首先构造出识别文法活前缀的 NFA，再将 NFA确定化和最小化，最终得到所需的 DFA。
由文法的 LR(0)项目构造识别文法所有活前缀的 NFA的算法如下：
(1) 令所有 LR(0)项目分别对应 NFA的一个状态，归约项目的
LR(0)项目对应一个终态。
(2) 接受项目的 LR(0)项目作为 NFA的唯一初态。
(3) 若状态 i是状态 j的后继项目,则从状态 i到状态 j引一条箭弧，
标记为 X。
(4) 若状态 i为待约项目（设为 X→α·Aβ），则从状态 i引箭弧到所有 A→·γ的状态，并标记为 ε。
例,设有文法 G[A]：
A→aA A→b
试构造识别文法 G的项目集族。
解,拓广文法
G[S?],(0) S?→A
(1) A→aA
(2) A→b
则 G[S?]的 LR(0)项目：
S? →·A
A→·aA
A→a·A
A→·b
A→b·
S? →A·
A→aA·
则将各状态命名后,如图,
状态 a A b
{1,2,4} {3,2,4} {6} {5}
{3,2,4} {3,2,4} {7} {5}
{6} Φ Φ Φ
{5} Φ Φ Φ
{7} Φ Φ Φ
将项目代入命名的状态后,如图,
图为识别文法 G的活前缀的 DFA,也是 LR(0)项目集族
2.构造文法 G的 LR(0)项目集族的方法之二如果把在识别过程中可能出现的项目放在一起组成的项目集，每一项目则表示成可能识别状态，识别程序可逻辑依次进入这些状态，这些状态的序列也就代表活前缀。一个状态集是由它的基本项集和基本项集的闭包组成的。
构造 I的闭包 CLOSURE（ I）的算法：
(1) I的任何项目都有属于 CLOSURE（ I）
(2) 若 A→α·Bβ属于 CLOSURE（ I），那么，任何关于 B的产生式 B→γ，项目 B→·γ添入 CLOSURE（ I）中
(3) 重复执行步骤 2直至 CLOSURE（ I）不再增大为止。
定义 4-16 GO（ Ii,X） =Ij
其中,Ii为包含某一项目集的状态
X为一文法符号，即 X ∈ Vn∪ Vt
Ij=CLOSURE（任何形如 A→αX·β的项目 | A→α·Xβ ∈ Ii ）
例：设 G[E]：
E→E+T|T T→T*F|F F→(E)|i
试构造项目 S?→·E的闭包解,CLOSURE（ S?→·E） ={ S?→·E,E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
文法 G的 LR（ 0）项目集族构造算法：
（ 1）初始项集 I0= CLOSURE（ S?→·S）是 G的项集，这里 S?是包含有规则 S?→S的拓广文法的开始符号
（ 2）如果 Ii中 G 的项集，则 Ii 的一切后继项集的闭包 Ij=GO(Ii,X)
均是 G的项集
（ 3）重复 2，直到再无新的项集可以添入为止例：试构造下列文法 G[S?],S?→S S→A S→B A→aAb A→c
B→aBb B→d
的 LR（ 0）项集解,I0= CLOSURE（ S?→·S） ={ S?→·S,S→·A,S→·B，
A→·aAb,A→·c,B→·aBb B→·d}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→A·） ={ S→A·}
I3= CLOSURE（ S→B·） ={ S→B·}
I4= CLOSURE（ A→a·Ab,B→a·Bb） ={ A→a·Ab,B→a·Bb
A→·aAb,A→·c,B→·aBb B→·d }
I5= CLOSURE（ A→c·） ={ A→c·}
I6= CLOSURE（ B→d·） ={ B→d·}
I7= CLOSURE（ A→aA·b） ={ A→aA·b}
I8= CLOSURE（ B→aB·b） ={ B→aB·b}
I9= CLOSURE（ A→aAb·） ={ A→aAb·}
I10= CLOSURE（ B→aBb·） ={ B→aBb·}
定义 4-17 若存在规范推导 S?=r=>αAω=r=>αβ1β2ω则称项目
A→β1·β2对活前缀 αβ1是有效的。
若项目 A→α·Xβ对活前缀 γ是有效的，则项目 A→αX·β对活前缀
γX是有效的。一般来说，同一个项目可能对好几个活前缀都是有效的。如：上例中，项目 B→aB·b对活前缀 aB,aaB,aaaB,
aaaaB,……anB 都是有效的。
若归约项目 A→β·对活前缀 αβ是有效的，则应把符号串 β归约成 A，即把活前缀 αβ变化成 αA；若移入项目 A→β1·β2对活前缀是有效的（ β2≠ε），则说不得明句柄尚未形成，因此下一步的动作应是移入，由于对于同一活前缀存在若干项目都是对它是有效的，如：项目 A→a·Ab,A→·aAb,A→·c,B→·aBb
B→·d都有对活前缀 aa是有效的，故其后继项目可能有好几个。
若待约项目 A→α·Bβ，这表明用产生式 A的右部归约时，应先归约 B；当归约项目 S?→S·对活前缀 ε是有效的，则说明整个识别符号已归约表明分析成功。
若项目中有既有移入项目也有归约项目或者有两个或两个以上的归约项目，这种情形就称为冲突。分别称为移入 /归约冲突和归约 /归约冲突。解决冲突的方法之一就是向搜索若干符号，
当然一些非 LR文法是无论搜索多少个符号也是无济于事的。如,
二义性文法都是非 LR文法,文法 S→Ac A→bAb|b是非 LR文法,
而 S→Ac A→Abb|b却是 LR文法,
定义 4-18 对于一个文法的 LR（ 0）项目集族中不存在移入 /归约，或归约 /归约冲突，称这个文法是 LR（ 0）文法。
LR（ 0）分析表的构造综上所述，只要对 LR（ 0）文法构造出对于每个活前缀的有效项目集，就可对符号串进行分析了。事实上从初始项集出发构造的全部项集正是所需的全部项集。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……,n 令包含项目
S?→S·的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a)若该项目为移入项，即为 A→α·aβ形式则置 ACTION[k.a]
为 Sj,其中 Ij=GO(Ii,a)
b)若该项目为归约项，即为 A→α·的形式，则对于任何
a∈ Vt∪ {#}，置 ACTION[k,a]=rj,其中 j为第 j个产生式
c)若该项目为待约项，即为 A→α·Bβ的形式则置 GOTO[k,B]
为 j，其中 B为待约项的第一个非终结符,Ij=GO（ Ik,B）
d)若项目为 S?→S·，则置 ACTION[k,#]为“接受”，即 acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 LR（ 0）分析表例：构造文法 S→(L)|a L→L,S|S 的 LR（ 0）分析表解：拓广文法：
（ 0） S?→·S （ 1） S→(L) （ 2） S→a （ 3） L→L,S
（ 4） L→S
I0= CLOSURE（ S?→·S） ={ S?→·S,S→·（ L）,S→·a}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→（ ·L ）） ={ S→（ ·L ）,L→·L,S,L→·S，
S→·（ L）,S→·a }
I3= CLOSURE（ S→a·） ={ S→a·}
I4= CLOSURE（ S→（ L·）,L→L·,S） ={ L→L·,S,S→
（ L·） }
I5= CLOSURE（ L→S·） ={ L→S·}
I6= CLOSURE（ L→L,·S） ={ L→L,·S,S→·（ L）,S→·a }
I7= CLOSURE（ S→（ L） ·） ={S→（ L） ·}
I8= CLOSURE（ L→L,S·） ={ L→L,S· }
其中,
GO(I0,S)=I1 GO(I0,()=I2 GO(I0,a)=I3
GO(I2L)=I4 GO(I2,S)=I5 GO(I2,()=I2 GO(I3,a)=I3
GO(I4,,)=I6 GO(I4,） )=I7
GO(I6,()=I2 GO(I6,a)=I3 GO(I6,S)=I8
其分析表为：
状态 ACTION GOTO
a （ ）,# S L
0 S3 S2 1
1 acc
2 S3 S2 5 4
3 r2 r2 r2 r2 r2
4 S7 S6
5 r4 r4 r4 r4 r4
6 S3 S2 8
7 r1 r1 r1 r1 r1
8 r3 r3 r3 r3 r3
4.2.4 SLR(1)分析
LR（ 0）是一类非常简单的文法。这种文法规定了每个状态中不含冲突的项目，在实际应用中这类文法较少。由于在 LR
（ 0）分析中，一旦在栈顶发现句柄，没有根据当前输入符号就进行归约，这样在同一个项目集中就不能有移入归约冲突或者归约归约冲突。那么是否能从右面的输入符号来解决冲突问题呢？回答是肯定的。当栈顶呈现句柄 α时，用产生式 A→α归约时，只有当前输入符号，恰好是属于 FOLLOW（ A）时，应该归约，否则不应归约。这种方法称为简单的 LR（ 1）分析法，
即 SLR（ 1）分析法。如果向右看非终结符 A后的 k个符号，则称为 SLR（ k）分析法。
为解决冲突问题，假定 LR（ 0）规范族中含有如下的一个项目集状态 I：
I={X→α·bβ,A→α·,B→α·}
其中，第一项目为移入项目，第二项目、第三项目是归约项目。
为此对于 SLR（ 1）要考察向右看的集合，当状态 I面临输入符号 a 时
(1) 若 a=b 则移入
(2) 若 a∈ FOLLOW(A),则用产生式 A→α进行归约
(3) 若 a∈ FOLLOW(B),则用产生式 B→α进行归约
(4) 此外，报错一般地，假定 LR（ 0）规范族的一个项目 I中有 m个移入项目,A1→α1·a 1β1,A2→α2·a 2β2,……,Am→αm·a mβm;同时含有 n
个归约项目,B1→α·,B2→α·,……B n→α·,如果移入集合
{a1,a2,……,a m},FOLLOW(B1),FOLLOW(B2),……,
FOLLOW(Bn)两两不相交，则可根据现行输入符号 a属于上述
n+1个集合中的哪一个集合而获得冲突的解决。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……,n 令包含项目
S?→S·的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a) 若该项目为移入项，即为 A→α·aβ形式则置
ACTION[k.a]为 Sj,其中 Ij=GO(Ik,a)
b)若该项目为归约项，即为 A→α·的形式，则对于任何
a∈ FOLLOW(A)，置 ACTION[k,a]=rj,其中 j为第 j个产生式
c)若该项目为待约项，即为 A→α·Bβ的形式则置 GOTO[k,B]
为 j，其中 B为待约项的第一个非终结符即为,Ij=GO（ Ik,B）
d) 若项目为 S?→S·，则置 ACTION[k,#]为“接受”，即 acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 SLR（ 1）分析表例：构造文法 G[S]：
（ 0） S?→E （ 1） E→E+T （ 2） E→T （ 3） T→T*F （ 4）
T→F （ 5） F→(E) （ 6） F→i
的 SLR分析表解：先求 LR（ 0）项目集族：
I0=CLOSURE（ S?→·E） ={ S?→·E,E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
I1=CLOSURE（ S?→E·） ={ S?→E·,E→E·+T }
I2= CLOSURE（ E→T·,T→T·*F） ={ E→T·,T→T·*F}
I3= CLOSURE（ T→F·） ={ T→F·}
I4= CLOSURE（ F→(·E)） ={ F→(·E),E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
I5= CLOSURE（ F→i·） ={ F→i·}
I6= CLOSURE（ E→E+·T） ={ E→E+·T,T→·T*F,T→·F，
F→·(E),F→·i }
I7= CLOSURE（ T→T*·F） ={ T→T*·F,F→·(E),F→·i }
I8= CLOSURE（ F→(E·),E→E·+T） ={ F→(E·),E→E·+T}
I9= CLOSURE（ E→E+T·,T→T· *F ） ={E→E+T·,
T→T· *F }
I10= CLOSURE（ T→T*F·） ={ T→T*F·}
I11= CLOSURE（ F→(E)·） ={ F→(E)·}
而其中,
GO(I0,E)=I1 GO(I0,T)=I2 GO(I0,F)=I3 GO(I0,（ )=I4 GO(I0,i)=I5
GO(I1,+)=I6
GO(I2,*)=I7
GO(I4,E)=I8 GO(I4,T)=I2 GO(I4,F)=I3 GO(I4,（ )=I4 GO(I4,i)=I5
GO(I6,T)=I9 GO(I6,F)=I3 GO(I6,（ )=I4 GO(I6,i)=I5
GO(I8,） )=I11 GO(I8,+)=I6
GO(I9,*)=I7
而
FOLLOW（ S?） ={#}
FOLLOW（ E） ={+,),#}
FOLLOW（ T） ={+,*,),#}
FOLLOW（ F） ={+,*,),#}
故其 SLR（ 1）分析表为：
状态
ACTION GOTO
+ * （ ） i # E T F
0 S4 S5 1 2 3
1 S6 acc
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 S4 S5 8 3 2
5 r6 r6 r6 r6
6 S4 S5 9 3
7 S4 S5 10
8 S6 S11
9 r1 S7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
LR(1)分析在 SLR方法中，若项目 Ik含有 A→α·。那么，在状态 K时，
只要所面临的输入符号 a∈ FOLLOW(A)就确定采取“用 A→α归约”的动作，但是，在某种情况下，当状态呈现于栈顶时，栈时的符号串所构成的活前缀 βα未必允许把 α归约为 A，因为可能就不存在 …β Aa… 的句型 (但可能存在 … γAa… 这样的句型 ) 这样对于 SLR方法中的移入符号集 {a1,a2,……,a m}和 FOLLOW（ A）
的交为非空时，还是有可能把该状态分开来判定是移入还是归约的。这种方法与 SLR比较对出错位置定位更精确。
例：对于文法 G[S],S→L=R S→R L→*R L→i R→L
这个文法的 LR（ 0）项目集族为：
I0= CLOSURE（ S?→·S） ={ S?→·S,S→·L=R,S→·R，
L→·*R,L→·i,R→·L}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→L·=R,R→L·） ={ S→L·=R,R→L· }
I3= CLOSURE（ S→R·） ={ S→R·}
I4= CLOSURE（ L→*·R） ={ L→*·R,R→·L,L→·*R,L→·i }
I5= CLOSURE（ L→i·） ={ L→i·}
I6= CLOSURE（ S→L=·R） ={ S→L=·R,R→·L,L→·*R，
L→·i }
I7= CLOSURE（ L→*R·） ={ L→*R·}
I8= CLOSURE（ R→L·） ={ R→L· }
I9= CLOSURE（ S→L=R·） ={ S→L=R·}
对于 I2，有移入归约冲突，而 FOLLOW（ R） =
{#,=}∩{=}≠Ф，则该文法不是 SLR，而当状态 2呈现于栈顶面临输入符号 =时，在这个文法中却不含以 R=…… 形式的句型。
因此，句型 L=……,中不能以 R→L归约。
为此，让每个状态含有更多的“展望”信息，这些信息将有助于克服动作的冲突、排除那种用 A→α的无效归约。设想，
如果能对每个状态附加一些信息，使 LR分析器的每个状态能够确切地指出，当 α后是哪些终结符时才允许将 α归约成 A，这样就不会产生无效的归约。为此需重新定义项目，使得每个项目都附带有 k个终结符。故其项目的形式为：
[A→α·β,a1a2a3……a k]
其中 A→α·β是一个 LR（ 0）项目，每个 a都有是终结符或 #，这种项目称为一个 LR（ k）项目。项目中的 a1,a2,a3……,ak
称它的搜索符串（或展望信息），向右搜索串仅对归约项目
[A→α·,a1a2a3……a k]有意义而对任何移进项目或待约项目
[A→α·Bβ,a1a2a3……a k]搜索串 a1,a2,a3……,ak不起作用。
归约项目 [A→α·,a1a2a3……a k]意味着：当它所属的状态呈现在栈顶且后续的 k个输入符号为 a1a2a3……a k时，才能把栈顶上的 α归约为 A。为简单起见，在这里只研究 k=1情形。
从项目对活前缀的有效的定义来看，若一个 LR（ 1）项目
[A→α·β,a]对于活前缀 γ是有效的，那么应该是：
S=r*=>δAω=r=>δαβω
其中 1） γ=δα 2） a是 ω的第一个符号,a为终结符或 #
显然项目 [T→T·*F,+],[T→T·*F,*]对活前缀 E+T和 E+（ T都有是有效的。
LR(1)项目集族的构造一个 LR（ 1）项目是由两部分组成的，一部分是和 LR（ 0）
项目相同的部分，称为心，另一部分是搜索符，因而，构造有效的 LR（ 1）项目集族的方法与构造 LR（ 0）的方法类似，下面逐一介绍 LR（ 1）的 CLOSURE和 GO的构造方法。
构造 LR（ 1）项目集的闭包函数。
构造 LR（ 1）项目集的闭包函数的算法：
（ 1） I的任何项目都有属于 CLOSURE（ I）
（ 2）若 [A→α·Bβ,a]属于 CLOSURE（ I）,B→γ是一个产生式，那么对于 FIRST（ βa）中的每个终结符 b,把项目 [B→·γ，
b]添入 CLOSURE（ I）中
（ 3）重复执行步骤 2直至 CLOSURE（ I）不再增大为止。
显然,[A→α·Bβ,a]属于对活前缀 λ=δα是有效的项目意味着存在一个规范推导
S=r*=>δAaθ=r=>δαBβaθ
若 βaθ可推导出 bω，则对于每个形如 B→γ的产生式，有
S=r*=>λB bω=r=>λγbω
换言之，项目 [B→·γ,b]对活前缀 λ是有效的，即 b∈ FIRST
（ βa）
LR（ 1）状态转换函数的构造定义 4-19 LR（ 1）状态转换函数 GO是一个二元函数，定义如下：
GO（ Ii,X） =Ij
其中 X为文法符号，即 X∈ Vt∪ Vn,Ii是项集，而
Ij=CLOSURE（ [A→αX·β,a]| [A→α·Xβ,a] ∈ Ii,a∈ Vt∪ {#}
当 Ii是对某个活前缀 γ有效的项目集合时,Ij= GO（ Ii,X）便是对活前缀 γX有效的项目集合。
文法 G的 LR（ 1）项集的构造算法
(1) 初始项集 I0= CLOSURE（ [S?→·S,#]）是 G的项集，这里
S?是包含有规则 S?→S的拓广文法的开始符号
(2) 如果 Ii中 G 的项集，则 Ii 的一切后继项集的闭包 Ij= GO(Ii,X)
均是 G的项集
(3) 重复 2，直到再无新的项集可以添入为止例：构造拓广文法
（ 0） S? →S (1)S→BB (2)B→aB (3)B→b
的 LR（ 1）项集
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·BB,#]，
[B→·aB,a/b],[B→·b,a/b]}
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2=CLOSURE（ [S→B·B,#]） ={[S→B·B，
#],[B→·aB,#],[B→·b,#]}
I3=CLOSURE（ [B→a·B,a/b]） ={[B→a·B,a/b],
[B→·aB,a/b],[B→·b,a/b]}
I4=CLOSURE（ [B→b·,a/b]） ={ [B→b·,a/b]}
I5=CLOSURE（ [S→BB·,#]） ={[S→BB·,#]}
I6=CLOSURE（ [B→a·B,#]） ={[S→a·B,#],
[B→·aB,#],[B→·b,#]}
I7=CLOSURE（ [B→b·,#]） ={ [B→b·,#]}
I8=CLOSURE（ [B→aB·,a/b]） ={[S→aB·,a/b]}
I9=CLOSURE（ [B→aB·,#]） ={[S→aB·,#]}
LR（ 1）分析表的构造现在已经有了构造了 LR（ 1）的项目集族和 GO函数的方法，下面可以构造成其分析表了，它的构造成算法与 LR（ 0）、
SLR（ 1）的方法其本相同。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……n,令包含项目 [S?→S·，
#]的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a) 若该项目为移入项，即为 [A→α·aβ,b]形式则置
ACTION[k.a]为 Sj,其中 Ij=GO(Ii,a)
b) 若该项目为归约项，即为 [A→α·,b]的形式，则置
ACTION[k,b]=rj,其中 j为第 j个产生式
c) 若该项目为待约项，即 [A→α·Bβ,b]则置 GOTO[k,B]为 j，
其中 B为待约项的第一个非终结符,Ij=GO（ Ik,B）
d)若项目为 [S?→S·,#]，则置 ACTION[k,#]为“接受”，即
acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 LR（ 1）分析表分析表中无冲突元素即为 LR（ 1）分析表例：试构造文法 G[S],S→L=R S→R L→*R L→i R→L的
LR（ 1）分析表拓广文法 G[S?]：
(0)S?→S (1)S→L=R (2)S→R (3)L→*R (4)L→i (5)R→L
先构造 LR（ 1）项目集族：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·L=R,#]，
[S→·R,#],[L→·*R,=/#],[L→·i,=/#],[R→·L,#] }
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2= CLOSURE（ [S→L·=R,#],[R→L·,#]） ={[S→L·=R，
#],[R→L·,#]}
I3= CLOSURE（ [S→R·,#]） ={ [S→R·,#]}
I4= CLOSURE（ [L→*·R,=/#]） ={ [L→*·R,=/#],[R→·L,=/#],
[L→·*R,=/#],[L→·i,=/#] }
I5= CLOSURE（ [L→i·,=/#]） ={[ L→i·,=/#]}
I6= CLOSURE（ [S→L=·R,#]） ={[S→L=·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#]}
I7= CLOSURE（ [L→*R·,= /#]） ={[ L→*R·,=/#]}
I8= CLOSURE（ [R→L·,=/#]） ={ [R→L·,=/#] }
I9= CLOSURE（ [S→L=R·,#]） ={[S→L=R·,#]}
I10= CLOSURE（ [R→L·,#]） ={ [R→L·,#] }
I11= CLOSURE（ [L→*·R,#]） ={ [L→*·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#] }
I12= CLOSURE（ [L→i·,#]） ={[ L→i·,#]}
I13= CLOSURE（ [L→*R·,#]） ={[ L→*R·,#]}
状态 ACTION GOTO
* i = # S L R
0 S4 S5 1 2 3
1 acc
2 S6
3 r2
4 S4 S5 8 7
5 r4 r4
6 S11 S12 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 S11 S12 10 13
12 r4
13 r3
LALR(1)分析从上例中可以看出 LR（ 1）分析表的状态一般较 SLR多，
而 SLR又不能处理 SLR冲突的文法。为此可采取了一种折衷方法，称为前视 LR分析法,LALR（ look a head-LR）技术。在实际应用中经常使用这种方法，因为由它产生的比 LR分析表要小得多，与 SLR,LR（ 0）表的大小相同，但能处理上例中的文法。它处理的文法弱于 LR（ 1）强于 SLR。一般的算法语言的 SLR和 LALR分析表有几百个状态，而 LR(1)分析表有上千个状态。
例：考虑拓广文法
（ 0） S? →S (1)S→BB (2)B→aB (3)B→b
的 LR（ 1）项集：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·BB,#]，
[B→·aB,a/b],[B→·b,a/b]}
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2=CLOSURE（ [S→B·B,#]） ={[S→B·B，
#],[B→·aB,#],[B→·b,#]}
I3=CLOSURE（ [B→a·B,a/b]） ={[B→a·B,a/b],
[B→·aB,a/b],[B→·b,a/b]}
I4=CLOSURE（ [B→b·,a/b]） ={ [B→b·,a/b]}
I5=CLOSURE（ [S→BB·,#]） ={[S→BB·,#]}
I6=CLOSURE（ [B→a·B,#]） ={[S→a·B,#],
[B→·aB,#],[B→·b,#]}
I7=CLOSURE（ [B→b·,#]） ={ [B→b·,#]}
I8=CLOSURE（ [B→aB·,a/b]） ={[S→aB·,a/b]}
I9=CLOSURE（ [B→aB·,#]） ={[S→aB·,#]}
显然其中 I3和 I6,I4和 I7,I8和 I9它们除了搜索符不同外，其余各部相同，能不能考虑把相类似的状态合并成一个状态呢？
为解决这个问题，首先来分析上述状态的作用，上述文法定义了 a*b a*b的整规集,I3是在第一个 b前找,B”，即 aB或 b所以它的搜索符为 a/b，而 I6是在已找到第一个,B”后，即在第一个 b
之后找,B”故它的搜索符号为 #。这样可以判断出 a*b和 a*b a*b
a*b不是上述文法定义的句子。如把状态 I3和 I6合并成一个状态为 {[S→a·B,a/b/#],[B→·aB,a/b/#],[B→·b,a/b/#]}，由于搜索符对移入项目不作用，故合并后不会产生问题。如把 I4和 I7全并为 { [B→b·,a/b/#]}这时识别 a*b中的也会归约成 B，同样 a*b a*b
a*b中第二个 b也会归约成 B。幸运的是当识别 a*b时，把它归约这 B时，没有 S→B这样的规则，此时会发生错误，同样 S a*b
的 S后不是 #也会发生错误。
定义 4-20 如果除去搜索符之后，这两个集合是相同的，称两个 LR（ 1）项目集具有相同的心。
由于 GO（ I,X）的心仅仅依赖于 I的心，因此 LR（ 1）项目集合并后的转换函数 GO（ I,X）自身的合并而得到的。如果一个文法是 LR（ 1）文法显然每个项目中无“移入” /“归约”
冲突，那么合并后肯定不会有“移入” /“归约”，至多有“归约” /“归约”冲突。只要合并后没有“归约” /“归约”冲突，就可以将它们所有同心集合并成新的状态集，即 LALR状态集。
LALR分析表构造算法之一：
(1)构造文法 G的 LR（ 1）项目集族 C={ I0,I1,……,I n}
把所有的同心集合并在一起，记作 C?={ J0,J1,……,J m}
为全并后的新族，含有项目 [S?→S·,#]的项集 Jk为分析表的初始状态集
(2)对于 C?构造 ACTION表：
a) 若该项目为移入项，即为 [A→α·aβ,b]形式则置
ACTION[k.a]为 Sj,其中 Jj=GO(Jk,a)
b) 若该项目为归约项，即为 [A→α·,b]的形式，则置
ACTION[k,b]=rj,其中 j为第 j个产生式
c) 若项目为 [S?→S·,#]，则置 ACTION[k,#]为“接受”，即
acc
(3) GOTO表的构造假定 Jk是 Ii1,Ii2,Ii3,……I it全并后的新集。由于所有这些 Ii同心，
那么 GO（ Ii1,X）,GO(Ii2,X),GO(Ii3,X),……GO(I it,X)也同心，于是将这些同心集合并起来，记为 Jj,则有 GO（ Jk,X） = Jj于是若 GO（ Jk,A） =Jj,则置 GOTO[k,A]=j,其中 A∈ Vn
(4) 分析表中空即为出错例：构造文法 G?的 LALR分析表：
G?[S?]：
(0)S?→S (1)S→L=R (2)S→R (3)L→*R (4)L→i (5)R→L
先构造 LR（ 1）项目集族：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·L=R,#]，
[S→·R,#],[L→·*R,=],[L→·i,=],[R→·L,#] }
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2= CLOSURE（ [S→L·=R,#],[R→L·,#]） ={[S→L·=R，
#],[R→L·,#]}
I3= CLOSURE（ [S→R·,#]） ={ [S→R·,#]}
I4= CLOSURE（ [L→*·R,=]） ={ [L→*·R,=],[R→·L,=],
[L→·*R,=],[L→·i,=] }
I5= CLOSURE（ [L→i·,=]） ={[ L→i·,=]}
I6= CLOSURE（ [S→L=·R,#]） ={[S→L=·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#]}
I7= CLOSURE（ [L→*R·,=]） ={[ L→*R·,=]}
I8= CLOSURE（ [R→L·,=]） ={ [R→L·,=] }
I9= CLOSURE（ [S→L=R·,#]） ={[S→L=R·,#]}
I10= CLOSURE（ [R→L·,#]） ={ [R→L·,#] }
I11= CLOSURE（ [L→*·R,#]） ={ [L→*·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#] }
I12= CLOSURE（ [L→i·,#]） ={[ L→i·,#]}
I13= CLOSURE（ [L→*R·,#]） ={[ L→*R·,#]}
令 J0=I0,J1=I1,J2=I2,J3=I3,J4=I4,11,J5=I5,12,J6=I6，
J7=I7,13,J8=I8,10,J9=I9
故有 GO函数：
故有 GO函数：
GO（ J0,S） =J1,GO（ J0,L） =J2,GO（ J0,R） =J3，
GO（ J0,*） =J4,GO（ J0,i） =J5
GO（ J2,=） =J6,GO（ J4,R） =J7,GO（ J4,L） =J8，
GO（ J4,*） =J4,GO（ J4,i） =J5
GO（ J5,R） =J9,GO（ J6,L） =J8,GO（ J6,*） =J4，
GO（ J6,i） =J5
状态 ACTION GOTO
* i = # S L R
0 S4 S5 1 2 3
1 acc
2 S6 r5
3 r2
4 S4 S5 8 7
5 r4 r4
6 S4 S5 8 9
7 r3 r3
8 r5 r5
9 r1
LALR分析表构造算法之二：
对于任何文法 G，通过构造它的 LR（ 1）项集，合并同心集，最后形成了 LALR（ 1）项目集，这是比较费时各占用较多的存储空间。在 LR（ 1）项集不考虑搜索符时即为 LR（ 0）项集，那么是否能通过构造 LR（ 0）项集，然后再构造 LALR项集呢，答案是肯定的。
定义 4-21 初始项目 S?→S和所有圆点不在左端的顶目，称为核心项，简称核。
一个 LR（ 0）项目集实际上是由核和非核项组成的，核是由前趋项目决定的，而非核是由求闭包得出的。
当一个项目集的核决定了，实际上相对于某文法的这个项目集也是唯一的。因此可以用核来代表项目集。
另外，所有归约项目 A→α.（除 α=ε外 )都在核内，即使 α=ε
核中也必然存在这样的规则 [B→β.Cγ,b],且 C=*r=>Aδ,及
a∈ FIRST(δγb),而满足 C=*r=>Aδ的所有非终结符 A也是可以预先计算出来的。
对于移入项目，则核中必须有项目 [A→β.aγ,b]或者
[A→β.Bγ,b]，其中 B=*r=>aω,这些 a预先也是可以计算出来的。
下面讨论如何从核构造 GOTO表。若 GO（ I,X） =J,I的核是 K,J的核是 L。那么，如果 [A→α.Xβ,a]∈ K,则
[A→αX.β,a]∈ L,另外 [A→β.Bγ,a]∈ K,C→Xη是一个产生式 K，
B=*r=>Cω和 b∈ FIRST(ωγa),而 C→Xη是一个产生式,则
[C→X.η,b]∈ L。
最后考虑为每个 LR（ 0）项目都配有相应的搜索符，使得这个核成为 LALR（ 1）的核。
先考虑搜索符是如何从集合 I传播到另一个集合 GO（ I,X）
的。
若 A→β.Bγ属于 LR（ 0）集 I的核 K,B=*r=>Cω且 C→Xη是一个产生式，那么如考虑 LR（ 1）项目集，其项目 [A→α.Xβ,
a]∈ K,GO（ I,X）中的核中的类似于 [C→X.η,b]∈ L的项目中的搜索符 b与 a有什么关系呢？
实际上，这个 b有两种可能的途径：其一,B=*r=>Cω，
b∈ FIRST(ωγa),但 ωγ不能推导出 ε，则搜索符 b不是 a，称为搜索符 b是自生的；其二,ωγ能推导出 ε，则搜索符 b就是 a,则搜索符 a是传播给 a的。
下面给出自生搜索符和搜索符传播的算法（其中,I的核为 K,@
为假想搜索符）：
for(K的每个项目的核 [B→α.β,@])
{ J=closure([B→α.β,@]);
if(项目 [A→γ.Xδ,a] ∈ J且 a≠@)
GO(I,X)中的项目 [A→γX,δ,a] 的搜索符是自生的 ;
if(项目 [A→γ.Xδ,a] ∈ J且 a=@)
GO(I,X)中的项目 [A→γX,δ,a] 的搜索符是传播的 ;
也就是搜索符从 I的 B→α.β传播到 GO(I,X)中的项目
A→γX,δ的
}
构造 LALR(1)项目集族的核的算法,
(1) 构造拓广文法 G’ 的 LR(0)项目集的核
(2) for(每个 LR(0)项目 )
for(每个文法符号 X)
求出 GO(I,X)的搜索符的自生集合和传播集合 ;
(3)为每个 LR(0)的核初始化自生搜索符 ;
(4) 当项目 [A→γ.Xδ,a]中的搜索符传播到核 L中的项目 C→X.η时,
将搜索符 a添入 C→X.η,a中
(5)重复 (4)直到再无新的搜索符添入为止。
例：构造文法 G’ 的 LALR分析表（用算法二）：
G’ [S’ ]：
(0)S’ →S (1)S→L=R (2)S→R (3)L→*R (4)L→i
(5)R→L
解,I0,S’ →.S,@ S→.L=R,@ S→.R,@ L→.*R,=/@
L→.i=/@ R→.L,@
I1,S’ →S.,@
I2,S→L.=R,@ R→L.,@
I3,S→R.,@
I4,L→*.R,@ R→.L,@ L→.*R,@ L→.i,@
I5,L→i.,@
I6,S→L=.R,@ R→.L,@ L→.*R,@ L→.i,@
I7,L→*R.,@
I8,R→L.,@
I9,S→L=R.,@
传播关系,
(I0,S?→.S,I1,S?→S,)
(I0,S?→.S,I2,S→L.=R)
(I0,S?→.S,I3,S→R,)
(I0,S?→.S,I4,L→*.R)
(I0,S?→.S,I5,L→i.)
(I2,S→L.=R,I6,S→L=.R)
(I4,L→*.R,I4,L→*.R)
(I4,L→*.R,I5,L→i.)
(I4,L→*.R,I7,L→*R.)
(I4,L→*.R,I8,R→L,)
(I6,S→L=.R,I4,L→*.R)
(I6,S→L=.R,I5,L→i.)
(I6,S→L=.R,I8,R→L,)
(I6,S→L=.R,I9,S→L=R.)
搜索符初始值 第一遍传播
I0,S’→.S # #
I1,S’→S,#
I2,S→L.=R #
I3,S→R,#
I4,L→*.R = =/#
I5,L→.i = =/#
I6,S→L=.R #
I7,L→*R,=/#
I8,R→L,=/#
I9,S→L=R,#
故有 GO函数：
GO（ I0,S） =I1,GO（ I0,L） =I2,GO（ I0,R） =I3,GO
（ I0,*） =I4,GO（ I0,i） =I5
GO（ I2,=） =I6，
GO（ I4,R） =I7,GO（ I4,L） =I8，
GO（ I4,*） =I4,GO（ I4,i） =I5
GO（ I5,R） =I9,GO（ I6,L） =I8,GO（ I6,*） =I4，
GO（ I6,i） =I5
则相应的 LALR分析表同前
4.2.6 二义性文法的应用任何二义性文法都不是 LR文法因为无论构造 SLR,LALR还是
LR分析表均有冲突。但二义性文法提供的说明往往要比一些非二义性文法要简单些，如表达式二义性文法：
G[E]:E→E+E|E*E|(E)|i和非二义性文法 G[E]:E→E+T|T
T→T*F|F F→ (E)|i 。事实上，虽然使用的文法是二义性的在加入一些其它的限制规则使对每个句子也只有一棵语法树，
这样，对整个语言说明仍然是无二义的,也就是也能用 LR分析考察文法,G[E]:E→E+E|E*E|(E)|i
构造 LR（ 0）项集：
I0=CLOSURE（ S?→·E） ={ S?→·E,E→·E+E,E→·E*E，
E→·(E),E→·i}
I1=CLOSURE（ S?→E·） ={ S?→E·,E→E·+T,E→E·*T }
I2=CLOSURE（ E→(·E)） ={E→(·E),E→·E+E,E→·E*E，
E→·(E),E→·i }
I3= CLOSURE（ F→i·） ={ F→i·}
I4= CLOSURE（ E→E+·E） ={ E→E+·E,E→·E+E,E→·E*E，
E→·(E),E→·i }
I5= CLOSURE（ E→E*·E） ={ E→E*·E,E→·E+E,E→·E*E，
E→·(E),E→·i }
I6= CLOSURE（ E→(E·),E→E·+E,E→E·*E） ={ E→(E·)，
E→E·+E,E→E·*E }
I7= CLOSURE（ E→E+E·,E→E·+E,E→E·*E） ={ E→E+E·，
E→E·+E,E→E·*E }
I8= CLOSURE（ E→E*E·,E→E·+E,E→E·*E） ={ E→E*E·，
E→E·+E,E→E·*E }
I9= CLOSURE（ E→(E)·） ={ E→(E)·}
而 FOLLOW（ S?） ={#}
FOLLOW（ E） ={+,*，）,#}
对于状态 I7，有项目 E→E+E·,E→E·+E,E→E·*E，对于归约项目 E→E+E·的 FOLLOW（ E） ={+,*，）,#}，面项目
E→E·+E和 E→E·*E为移入项即移入集为 {+,*}其交不为空，不是 SLR文法，当然如构造 LR（ 1）项目集也可说明它不是 LR
（ 1）文法。事实上，在栈顶是 E+E时，而下面的输入符号为 +
时，应前面的 +先做，即应先归约，在栈顶是 E+E时，而下面的输入符号为 *时，应先做 *，即为先移入。同样可以根据优先级和结合性来解决 I8的冲突问题。按这种方法构造出的分析表如下：
状态
ACTION GOTO
+ * （ ） i # E
0 S2 S3 1
1 S4 S5 acc
2 S2 S3 6
3 r4 r4 r4 r4
4 S2 S3 ７
5 S2 S3 ８
6 S4 S5 S9
7 r1 S5 r1 r1
8 r2 r2 r2 r2
9 r3 r3 r3 r3
可以看出这样的分析表比较简单。
考虑条件语句文法：
S?→S
S→iSeS|iS|a
它的状态集为,
I0=CLOSURE（ S?→·S） ={ S?→·S,S→·iSeS,S→·iS,S→·a}
I1=CLOSURE（ S?→E·） ={ S?→S·}
I2=CLOSURE（ S→i·SeS,S→i·S） ={ S→i·SeS,S→i·S,
S→·iSeS,S→·iS,S→·a }
I3=CLOSURE（ S→a·） ={ S→a·}
I4=CLOSURE（ S→iS·eS,S→i S·） ={ S→iS·eS,S→i S· }
I5=CLOSURE（ S→iSe·S） ={ S→iSe·S,S→·iSeS,S→·iS，
S→·a }
I6=CLOSURE（ S→iSeS·） ={ S→iSeS·}
对于状态 I4有移入项 S→iS·eS和归约项 S→i S·冲突；另外
follow(s)中有 e,又造成了 SLR冲突，根据一般原则删去了归约动作，其分析表如下：
状态
ACTION GOTO
i e a # S
0 S2 S3 1
1 acc
2 S2 S3 4
3 r3 r3
4 S5 r2
5 S2 S3 6
6 r1 r1
（程序），
自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法 (又称回溯法 )，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。
4.1 自顶向下的语法分析
4.1.1自顶向下的分析思想不确定的自顶向下分析思想主要是带回溯的自上而下的分析方法，所谓带回溯的自顶而下的分析方法是对任何输入串试图用一切可能的办法，从文法符号开始符号（根结点）出发，
自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻找一个最左推导。这种。这种过程本质上是一种试探过程，是反复使用不同的产生式谋求匹配输入串的过程。
例：设有文法 G[S]:
S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t
假定输入串为 abdet
显然上述分析法中不能有形如 P→Pα的规则，也不能有对某一非终结符 P存在 P=+=>Pα,即不能有规则左递归和文法左递归。
确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树，现举例说明：
例：若有文法 G1［ S］：
S→pA S→qB A→cAd A→a
若输入串 W=pccadd,自顶向下的推导过程为
S =>pA=>pcAd=>pccAdd=>pccadd
例：若有文法 G2[S]为：
S→Ap S→Bq A→a A→cA B→b B→dB
当输入串 W=ccap,那么试图推出输入串的推导过程为：
S=>Ap=>cAp=>ccAp=>ccap
例：若有文法 G3[S]：
S→aA S→d A→bAS A→ε
若输入串为 W=abd,则试图推导出 abd串的推导过程为：
S=>aA=>abAS=>abS=>abd
4.1.2 左递归和回溯性
1.左递归左递归在自顶向下的分析技术中是有害的，为此使用自顶向下的分析方法的文法中不能出现左递归,因此需要消去左递归。如果对于某非终结符 A存在着推导 A=+=>Aα，则称文法左递归或间接左递归；如果存在规则 A→Aα，则称规则左递归或直接左递归。对于规则左递归是可以消除的，
而对文法左递归只能对满足一定条的文法进行消去。
(1)规则左递归的消除
a.改写规则成右递归把 E→E+T|T 改写成 E→T+E|T
虽然在这里消去了左递归并不改变语言，但改变了结合性。
b.引进新的文法符号把 E→E+T|T T→T*F|F F→(E)|i 改写成
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
一般地：
A→Aα1|Aα2|Aα3|···|Aαm|β1|β2|β3|···|βn
改写成：
A→β1 A?|β2 A?|β3 A?|···|βnA?
A?→ α1 A?|α2 A?|α3 A?|···|αm A?|ε
例：消去 S→SS*|SS+|a中的左递归。
解,S→aS?
S?→ S*S?| S+S?|ε
(2)间接左递归的消除如果一个文法是无环的 (即 P=+=>P)和没有 ε产生式，那么可用下列算法消除。
a.以任意次序排列非终结符 A1,A2,A3,···,An
b.for(i=1;i<=n;i++)
{
for(j=1;j<=i-1;j++)
用产生式 Ai→δ1γ|δ2γ|δ3γ|···|δkγ代替每个形式为
Ai→Ajγ的产生式其中 Aj→δ1|δ2|δ3|···|δk是所有当前
Aj 产生式；
消去 Ai产生式中的直接左递归
}
c.除去那些从开始符号出发永远无法到达的非终结符的产生规则。
例：消去下列文法的左递归：
S→Aa|b A→Ac|Sd|ε
解：设 A1=S A2=A 则
S→Aa|b A→Ac|（ Aa|b） d|ε
S→Aa|b A→A（ c|ad） |bd|ε
S→Aa|b A→bdA?|A? A?→cA?|adA?|ε
2.回溯性在自顶向下的语法分析中，当前面临非终结符 P如存在规则
P→α1|α2|α3|···|αn，当前输入符号为 a时,究竟选用哪一个候选式，
如采用回溯则效率太低，现如能改变文法使每个候选式没有相同的“头符号”，则就能根据当前输入符号 a决定选用那一个产生式。
例,S→if E then S|if E then S else S|b
改写成：
S→if E then S S?|b
S?→else S|ε
一般地
A→δβ1|δβ2|δβ3|···|δβn|γ
改写成：
A→δA?|γ
A?→β1|β2|β3|···|βn
例：消去文法 G[S]:
S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t
的回溯性解,S→aBC B→ib|b C→dC?|c C?→eE? E?→h|G G→t
例：若有文法 G[S]：
S→aSd S→Ac A→aS A→b
解,S→aSd S→aSc S→bc
S→aSS? S→bc S?→d|c
但要注意不是所有的文法都能通过提左公因子消去回溯性的。
例：若有文法 G[S]：
S→Ap|Bq A→aAp|d B→aBq|e
解：上述文法的语言：
L[G]={andpn+1或 ameqm+1|m,n≥0}
由于不知道具体句子中 m和 n那一个大，也就无法知道应提多少个 a作为左因子递归下降分析法递归下降分析法又称递归子程序法简称递归下降法，它是一种无回溯的自顶向下分析技术，它的实现思想是让一个识别程序由一组过程（或函数）组成，其中每个过程对应于文法的一个非终结符号，由于文法的递归定义，故这些过程 往往是递归的，相应的程序称为递归下识别程序。
例：对于文法 G[E]：
E→E+T|T T→T*F F→（ E） |i
消去左递归和提左共因子后：
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
其递归子程序的流程图为：
其递归子程序为：
void E()
{T()； E?();
}
void E?()
{if(下一个符号 ==?+?)
{取下一个符号 ()；
T()； E?();
}
}
void T()；
{ F()； T?();
}
void T?()
{if(下一个符号 ==?*?)
{取下一个符号 ()；
F()； T?();
}
}
void F()
{
if(下一个符号 ==?i?)
取下一个符号 ();
else
if(下一个符号 ==?(?)
{取下一个符号 ()； E()；
if(下一个符号 ==?)?)
取下一个符号 ();
else 出错 ();
}
else 出错 ()；
}
在具体实现中,可以将写成拓广的 BNF,如下,
E→T{+T} T→F{*F) F→(E)|i
其递归子程序如下,
void E()
{T()；
while(下一个符号 ==?+?)
{取下一个符号 ()；
T();
}
}
void T()
{F()；
while(下一个符号 ==?*?)
{取下一个符号 ()；
F();
}
}
void F()
{
if(下一个符号 ==?i?)
取下一个符号 ();
else
if(下一个符号 ==?(?)
{取下一个符号 ()； E()；
if(下一个符号 ==?)?)
取下一个符号 ();
else 出错 ();
}
else 出错 ()；
}
递归下降分析法的优点：
(1)方法简单
(2)能灵活地在各过程中添加语义动作
(3)当能用某种程序设计语言写出所有这些过程或函数（包括递归过程或函数）时，可以由该语言的编译系统来生成整个识别程序。
4.1.4 预测分析法递归子程序是由一组递归过程组成的，它的实现极大程度地取决于递归过程的实现，如递归过程的允许嵌套调用层数，
但某些程序设计语言不允许递归,也有些程序设计语言递归的嵌套层数受限制,为此引进了一种新的自顶向下的分析方法 ——预测分析法。
预测分析法也是一种无回溯的自顶向下的分析技术，当然一般情况下，其文法也满足 LL（ 1）文法的条件。
所谓 LL（ K）分析法，这里的第一个 L表示从左到右扫描输入符号串，第二个 L表示分析过程中采用的是最左推导。括号中的 1表向前（向右）看 K个符号。
1.LL(1)分析器的逻辑结构和工作过程一个 LL（ 1）分析器是由一个总控程序，一个输入带、一张分析表和一个栈组成的，如图所示：
（ 1）分析表在 LL(1)分析器中使用了一张分析表。用 M[A,a]形式的矩阵（或二维数组）表示，其中 A 是文法的非终结符号,a是文法的终结符号或,#”（,#”是为分析方便而引入的一个特殊符号，把它作为输入符号串的结束符）。分析表矩阵元素
M[A,a]表示当前非终结符 A，面临输入符号 a时按存放关于符
A的产生式展开，如表中元素为空白时表示出错。
（ 2）分析栈用于存放分析过程中的文法符号。分析栈初始化时，在栈底压入一个,#”，然后再压入文法的开始符号，表示试图将开始符号推导出输入符号串。
（ 3）总控程序总控程序的功能是依据分析表、分析栈和输入符号串的状态进行分析和识别。它在任何时候都是根据当前分析栈的栈顶文法符号 X和当前的输入符号 a来决定采取相应的动作，从而达到语法分析的目的。
总控程序的具体算法如下：
分析开始时进行有关的初始化工作：把,#”及文法的开始符号
S依次压入分析栈，并把各指示器的指针调整至起始位置。
设分析到的某一步，分析栈当前的栈顶符号为 X，输入串分析指针当前指向的符号为 a，则：
a.若 X∈ Vt ∪ {#}
① X=a=“#”，表示分析成功，停止分析过程。
② X=a≠“#”，则从栈顶弹出 X，输入串指向下一个字符
③ X≠a，则表示发现错误，调相应的出错处理程序进行处理。
b.若 X∈ Vn：则根据 X与 a查分析表 M，根据 M[X,a]中的内容决定：
①若 M[X,a]中为一个规则，则将 X从分析栈中弹出，并将此规则右部的符号序列按倒序压入分析栈（若规则为 X→ε，则仅将 X从栈中弹出）。
②若 M[X,a]中为空白，则表示出错，调用相应的出错处理程序处理。
例,E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
的分析表如下：
i + * ( ) #
E E→TE ’ E→TE ’
E’ E→+TE ’ E’→ ε E’→ ε
T T→FT ’ T→FT ’
T’ T’→ ε T→*FT ’ T’→ ε T’→ ε
F F→i F→(E)
步骤 栈 剩余输入串 输出
0 #E i*(i+i)+i# E→TE?
1 #E?T i*(i+i)+i# T→FT?
2 #E?T?F i*(i+i)+i# F→i
3 #E?T?i i*(i+i)+i# i匹配
4 #E?T? *(i+i)+i# T? →*F T?
5 #E?T?F* *(i+i)+i# *匹配
6 #E?T?F (i+i)+i# F→(E)
7 #E?T?)E( (i+i)+i# (匹配
8 #E?T?)E i+i)+i# E→TE?
9 #E?T?)E?T i+i)+i# T→FT?
10 #E?T?)E?T?F i+i)+i# F→i
11 #E?T?)E?T?i i+i)+i# i匹配
12 #E?T?)E?T? +i)+i# T? →ε
13 #E?T?)E? +i)+i# E? →+TE?
14 #E?T?)E?T+ +i)+i# +匹配
15 #E?T?)E?T i)+i# T→FT?
16 #E?T?)E?T?F i)+i# F→i
17 #E?T?)E?T?i i)+i# i 匹配
18 #E?T?)E?T? )+i# T? →ε
19 #E?T?)E? )+i# E? →ε
20 #E?T?) )+i# )匹配
21 #E?T? +i# T? →ε
22 #E? +i# E? → +TE?
23 #E?T+ +i# +匹配
24 #E?T i# T→FT?
25 # E?T? F i# F→i
26 # E?T? i i# i 匹配
27 # E?T? # T? →ε
28 # E? # E?→ε
29 # # 接受
2.预测分析表的构造由于所有的 LL(1)分析器的输入带、栈和总控程序都是一样的，唯一区别的是分析表。下面介绍分析表的构造算法。
定义 4-1：
FIRST(α)={a|α=+=>a...,a∈ Vt}
特别地，若 α=*=>ε，则规定 ε∈ FIRST(α)
如果非终结符 A的所有选择的首符集两两不相交，即 A的任何两个不同的选择 αi和 αj有 FIRST(αi)∩ FIRST(αj)=Φ时，要求 A
匹配输入串时,A就能根据它所面临的第一个输入符号 a,准确地指派某一个选择前支执行任务，这个选择就是那个终结首符属于的 α。如果 ε∈ FIRST(α)，会使问题稍为复杂。由于某个非终结符 A如要推导成 ε，那么当输入符号 a不是 A中的符号而是 A
后面的符号，为此定义 FOLLOW集合。
定义 4-2
FOLLOW（ A） ={a|S=*=>...Aa...,a∈ Vt}
若 S=*=>...A，则规定 #∈ FOLLOW（ A）
如果,A的任何两个不同的选择 αi和 αj不同时能推导出 ε，
不失一般性设 αi=*=>ε。也能根据其 FIRST(αi)和
FIRST(α)∪ FOLLOW（ A）决定选择那一个产生式。
定义 4-3
对于产生式 A→α，若 α=*=>ε,
则 SELECT(A→α)=（ FIRST(α)-{ ε}） ∪ FOLLOW（ A）,否则
SELECT(A→α)= FIRST(α)
定理 一个上下文无关文法是 LL（ 1）文法的充分必要条件是，
对每个非终结符 A的任何两个不同产生式,A→αi和 A→αj，满足
SELECT（ A→αi ） ∩SELECT（ A→αj） =Φ
显然 αi和 αj不同时为 ε
LL（ 1）文法的性质：
（ 1）任何二义性文法都不是 LL（ 1）文法，任何 LL（ 1）文法都不是二义性的
（ 2）若一个文法中含有左公因子或左递归，则该文法必然不是 LL（ 1）文法，但不含左公因子和左递归的文法不一定是
LL（ 1）文法。
另外，存在算法能判定一个文法是否是 LL（ 1）文法；也存在能判定二个 LL（ 1）文法是否能产生相同的语言；但不存在能判定一个上下文无关的文法是否能变换成等价的 LL（ 1）
文法。
FIRST集合构造算法：
对于每一个文法符号 X∈ Vt∪ Vn,构造 FIRST（ X），可重复应用下列步骤直到再无终结符号或 ε能被添入到任何 FIRST集合中为止。
（ 1）若 X∈ Vt，则 FIRST（ X） ={X}
（ 2）若 X∈ Vn，且有产生式 X→a...则把 a加入到 FIRST（ X）
中；若 X→ε也是一条产生式，则把 ε也加到 FIRST（ X）中若 X→Y...是一个产生式且 Y∈ Vn，则把 FIRST（ Y）中的所有非
ε元素都加到 FIRST（ X）中，若 X→Y1Y2Y3...Yk是一个产生式，
Y1Y2Y3...Yi-1都 是非终结符，而且，对于任何 j,1≤j≤i-1,FIRST
（ Yi）都含有 ε（即 Y1Y2Y3...Yi-1=*=>ε）,则把 FIRST（ Yi）中的所有 FIRST（ Yi）中的所有非 ε元素加到 FIRST（ X）中去；特别是，若所有的 FIRST（ Yi）均有 ε,j=1,2,3...,k,则把 ε加到
FIRST(X)。
符号串 X1X2X3...Xn的 FIRST集合的算法：
把 FIRST（ X1）的非 ε元素加到 FIRST（ X1X2X3...Xn）中，如果 ε在 FIRST（ X1）中，那么加入 FIRST（ X2）中全部非 ε元素；
如果 FIRST（ X1）和 FIRST（ X2）中都有 ε则把 FIRST（ X3）中全部非 ε元素加到 FIRST（ X1X2X3...Xn）中，以此类推，最后对所有的 i，有 ε属于 FIRST（ Xi），那么把 ε加入 FIRST
（ X1X2X3...Xn）中。
对非终结的 FOLLOW算法：
对于文法 G的每个非终结符 A构造 FOLLOW（ A）的办法是重复应用下列步骤直到再无终结符号或 #能被添入到任何
FOLLOW（ A）中：
（ 1）对于文法的开始符号（识别符号） S，置 #于
FOLLOW（ A）中；
（ 2）若 A→αBβ是一个产生式，则把 FIRST（ β）中的非 ε的一切符号加至 FOLLOW(B)中；
（ 3）若 A→αB是一个产生式，或 A→αBβ是一个产生式，而
β=*=>ε(即 ε∈ FIRST（ β） )，则把 FOLLOW（ A）加入
FOLLOW（ B）中
SELECT构造算法：
对于每个产生式 A→α构造 SELECT（ A→α），当
ε∈ FIRST（ α），则 SELECT（ A→α） =（ FIRST(α)-{ε}）
∪ FOLLOW（ A）,否则 SELECT(A→α)= FIRST(α)
例：求文法 G[S],S→AB S→bC A→ε A→b B→ε B→aD
C→AD C→b D→aS D→c的 FIRST,FOLLOW和 SELECT
集。
(S)={a,b,ε}
FIRST(A)={b,ε}
FIRST(B)={a,ε}
FIRST(C)={a,b,c}
FIRST(D)={a,c}
FIRST(AB)={a,b,ε}
FIRST(bC)={b}
FIRST(ε)={ε}
FIRST(b)={b}
FIRST(aD)={a}
FIRST(b)={b}
FIRST(aS)={a}
FIRST(c)={c}
FOLLOW(S)={#}
FOLLOW(A)={a,#,c}
FOLLOW(B)={#}
FOLLOW(C)={#}
FOLLOW(D)={#}
SELECT(S→AB)={a,b,#}
SELECT(S→bC)={b}
SELECT(A→ε)={a,c,#}
SELECT(A→b)={b}
SELECT(B→ε)={#}
SELECT(B→aD)={a}
SELECT(C→AD)={a,b,c}
SELECT(C→b)={b}
SELECT(D→aS)={a}
SELECT(D→c)={c}
例：构造文法 G[E]：
E→TE? E?→+TE?|ε T→FT? T?→*FT?|ε F→(E)|i
的 FIRST,FOLLOW,SELECT集解,FIRST(E)={(,i}
FIRST(E?)={+,ε}
FIRST(T)={(,i}
FIRST(T?)={*,ε}
FIRST(F)= {(,i}
FOLLOW(E)={#,)}
FOLLOW(E?)={#,)}
FOLLOW(T)={#,),+}
FOLLOW(T?)={#,),+}
FOLLOW(F)={#,),+,*}
SELECT(E→TE?)={(,i}
SELECT(E?→+TE?)={+}
SELECT(E?→ε)= {#,)}
SELECT(T→FT?)={(,i}
SELECT(T?→*FT?)={*}
SELECT(T?→ε)= {#,),+}
SELECT(F→(E))= {(}
SELECT(F→i)={i}
构造预测分析表构造算法：
（ 1）先求出每个产生式的 SELECT集
（ 2）对于每个终结符或 #用 a表示。
若 a∈ SELECT(A→α),则把 A→α放入 M[A,a]中。
（ 3）把所有无定义的 M[A,a]标记为出错，用空白表示。
例：试构造上述文法的预测分析表。
解：先求 FIRST,FOLLOW和 SELECT集（略）
i + * ( ) #
E E→TE ’ E→TE ’
E’ E→+TE ’ E’→ ε E’→ ε
T T→FT ’ T→FT ’
T’ T’→ ε T→*FT ’ T’→ ε T’→ ε
F F→i F→(E)
二义性文法的应用虽然任何二义性文法都不是 LL（ 1）文法，但具体应用中，
可根据实际情况删减，也是能达到分析目的的。
例,G[S],S→if E then S S?|a
S?→else S|
E→b
解,FIRST(S)={if} FIRST(S?)={else,ε}
FIRST(E)={b}
FOLLOW(S)={else,#}
FOLLOW(S?)={else,#} FOLLOW(E)={then}
SELECT(S→if E then S S?)={if}
SELECT(S→a)={a}
SELECT(S?→else S)={else}
SELECT(S?→ε)={else,#}
SELECT(E→b)={b}
则分析表为
a b else if then #
S S→a S→if E then S S ’
S’ S’→else S
S’→ ε
S’→ ε
E E→b
可以根据实际情况在 M[s?,else]中删除 S?→ε即可。
4.2 自底向上的语法分析所谓自底向上的分析方法就是从输入符号出发逐步归约成识别符号,
4.2.1自底向上的分析法概述自底向上的分析法的思想方法主要是从左到右扫描输入符号串，从语法树的角度出发也就是从末端结点出发向根结点方向往上构造语法树，也就是说自底向上的分析方法是一个不断归约的过程。要实现自底向上的分析方法需要解决两个问题：
(1) 确定句型中将要归约的符号串
(2) 如果该子串能归约多个非终结符号，需决定归约成那一个符号由于栈在计算机中实现比较方便，在语法分析中往往使用栈，为更好地识别出输入串的结束，也引进了特殊符号 #，把它压入栈底以及放在输入符号后面，如：
栈 输入
# a1a2a3a4...an#
这样可以采用“移入 —归约”法，这种方法每移入一个字符判断是否可以归约，若能归约则归约到不能归约为止，否则再移入下一个字符。由于在“移入 —归约”中每次归约的是最左边的非终结符，应该就是最左归约即最右推导的逆过程，那么在没有二义性的前提下其最左归约是唯一的，也就是句柄是唯一的。如果在分析过程式中发现错误（找不到貌似句柄的符号串）或者呈下列情形结束栈 输入
#S #
其中 S是识别符号。
例：设 G[S],S→aAcBe A→b A→Ab B→d
识别符号串 abbcde
步骤 符号栈 输入符号串 动作
1 # abbcde# 移入
2 #a bbcde# 移入
3 #ab bcde# 归约（ A→b ）
4 #aA bcde# 移入
5 #aAb cde# 归约（ A→Ab ）
6 #aA cde# 移入
7 #aAc de# 移入
8 #aAcd e# 归约（ B→d ）
9 #aAcB e# 移入
10 #aAcBe # 归约（ S→aAcBe ）
11 #S # 接受
1,简单优先分析法概述简单优先分析法是按照每个文法符号之间的优先关系确定句柄的，这样如何找到这种优先关系也就是这种识别方法的关键。
优先关系定义 4-4
定义优先关系的定义：
X〧 Y 表示 X和 Y的优先 x级相等
X·>Y 表示 X优先级大于 Y的优先级
X<·Y 表示 X优先级小于 Y的优先级注意：〧 ·> <·与数学中的 =,>,< 不同定理：
X〧 Y 当且仅当 G中存在产生式规则Ａ →···XY···
X<·Y 当且仅当 G中存在产生式规则Ａ →···XB···,且 B=+=>Y···
X·>Y 当且仅当 G中存在产生式规则Ａ →···BD···,且 B=+=>···X
D=+=>Y···
例：若有文法 G[S]:
S→bAb A→(B|a B→Aa)
则,
根据上述文法符号之间的的关系，可以逐步列出其矩阵，
如下所示。
S b A ( B a ) #
S ·>
b 〧 <· <· ·>
A 〧 〧
( <· <· 〧 <·
B ·> ·>
a ·> ·> 〧
) ·> ·>
# <· <· 〧
显然用上述方法构造优先矩阵当文法较复杂时，就很难构造出全部元素，应采用 LAST,FIRST集合的算法。
定义 4-5
若一个文法是简单优先文法必须满足以下条件：
(1) 在文法符号集 V中，任意两个符号之间最多只有一种优先关系成立。
(2) 在文法中任意两个产生式没有相同的右部。
则称该文法是简单优先文法对于第一条件规定在任何时候都可以确切地找到形如 Sj-1<·Sj〧
Sj+1〧 … 〧 Si·> Si+1的“句柄”，第二条件就是找到上述符号串后能知道归约成那一个非终结符号。
简单优先分析法简优先分析法的思想方法是首先找出“句柄”的尾，然后再找句柄的头，找到貌似“句柄”的符号串寻求相应归约成的非终结符。算法如下：
2,算符优先分析法概述人们在计算表达式时习惯用先乘除后加减，因而在处理表达式 3+5*2时需先做 5*2，而处理 3+5-2时需先做 3+5，这时由于在运算符之间规定了优先级，计算表达式的过程和表达式的归约过程致相同，前者将子表达式的值代替子表达式，后者以非终结符代替。是否能将这种技术推广到具体的语言识别过程中呢？这就需要考虑运算符是什么？运算对象是什么？显然可以将终结符代表运算符，非终结符代表运算对象，这种公在终结符之间引进的优先关系的优先分析技术称为算符优先分析技术，在算符优先分析技术的讨论中，将术语“终结符号”视为
“运算符”，而把术语“非终结符”号视为“运算对象”。算符优分析过程式是自底向上的归约进程，但这种归约未必是严格的最左归约，也就是说，算符优先分析法不是一种规范归约法。
例：设 G[E]:E→E+E|E*E|(E)|i
其终结符号的优先关系表如下：
+ * （ ） i
+ ·> <· <· ·> <·
* ·> ·> <· ·> <·
( <· <· <· 〧 <·
) ·> ·> ·>
i ·> ·> ·>
下面利用其优先关系识别输入符号串 i+i+i*(i+i)
步骤 栈 输入符号串 动作
1 # i+i+i*(i+i)# 移入
2 #i +i+i*(i+i)# 归约 E→i
3 #E +i+i*(i+i)# 移入
4 #E+ i+i*(i+i)# 移入
5 # E+i +i*(i+i)# 归约 E→i
6 # E+E +i*(i+i)# 归约 E→E+E
7 # E +i*(i+i)# 移入
8 #E+ i*(i+i)# 移入
9 # E+i *(i+i)# 归约 E→i
10 # E+E *(i+i)# 移入
11 # E+E* (i+i)# 移入
12 # E+E*( i+i)# 移入
13 # E+E*(i +i)# 归约 E→i
14 # E+E*(E +i)# 移入
15 # E+E*(E+ i)# 移入
16 # E+E*(E+i )# 归约 E→i
17 # E+E*(E+E )# 归约 E→E+E
18 # E+E*(E )# 移入
19 # E+E*(E) # 归约 E→(E)
20 # E+E*E # 归约 E→E*E
21 # E+E # 归约 E→E+E
22 # E # 接受直观算符优先分析法从前面的例子可以看出其运算次序是先乘除后加减，而且加乘运算符都是左结合的。同样两个终结符之间的关系成这这种算法的关键。下面定义它的优先关系：
定义 4-6
a<·b 表示 a的优先级小于 b
a〧 b 表示 a的优先级等于 b
a·>b 表示 a的优先级大于 b
同样，〧 ·> <·与数学中的 =,>,< 不同这样可以根据运算符的优先级各结合性来构造出上述文法的算符优先分析表。
作为一种通用的分析技术，算符优先分析有它的缺点，它很难处理象减 /负这样的记号，因为它有不同的优先级。适用于算符优先分析技术的文法相对较小。
算符优先文法的定义算符优先技术能适用算符优先文法，那么是什么是算符优先文法，什么是算符文法呢？前面已经知道一般表达式中不能连续出二个运算对象。类似地，算符优先技术只能应用于规右部中任何两 个非终结符号之间必定出现终结符号的文法，这种文法就称为算符文法，为实现方便起间规定它不含有形如 P→ε
的产生式。
定义 4-7
如果某文法 G中没有形如 A→……BC…… 的产生式，其中
A,B,C∈ Vn,则文法称为算符文法，也称 OG文法。
算符文法的一些性质：
（ 1）对于算符文法，不存在包有两个相邻非终结符号的句型
（ 2）如果 aP出现在句型 α中，其 a∈ Vt,P∈ Vn，则 α中包含其 a
的短语必包含 P
（ 3）如果 Pa出现在句型 α中，其 a∈ Vt,P，则 α中包含其 a的短语必包含 P
（ 4）在算符文法的任何句型中，不存在其紧前或紧后是非终结符的短语例：对一些文法的讨论：
(1) 规则：
<如果子句 >→if <布尔表达式 > then
<如果语句 >→<如果子句 ><无条件语句 >
<条件语句 >→<如果语句 >|<如果语句 > else <语句 >
……
显然上述文法不是算符文法，为此可以不改变语言地改变文法使其成为算符文法，重新定义为：
<如果子句 >→if <布尔表达式 >
<如果语句 >→<如果子句 > then <无条件语句 >
<条件语句 >→<如果语句 >|<如果语句 > else <语句 >
(2)规则：
<左部 >→<变量 >:=|<函数标识符 >:=
<左部表 >→<左部 >|<左部表 ><左部 >
<赋值语句 >→<左部表 ><表达式 >
重新定义为：
<左部 >→<变量 >|<函数标识符 >
<左部表 >→<左部 >|<左部表 >:=<左部 >
<赋值语句 >→<左部表 >:=<表达式 >
定义 4-8
设文法 G是不含 ε产生式的算符文法,a,b是任意一对运算符
（终结符），而 A,B,C∈ Vn，其优先关系定义如下：
1.a〧 b 当且仅当 G中存在产生式Ａ →···ab···或Ａ →···aBb···
2.a<·b 当且仅当 G中存在产生式规则Ａ →···aB···,且
B=+=>b···或 B=+=>Cb···
3.a·>b 当且仅当 G中存在产生式规则Ａ →···Bb···,而 B=+=>···a
或 B=+=>···aC
定义 如果一个算符文法 G中的任何终结符对（ a.b）至多只满足下述三关系之一
a〧 b a<·b a·>b
则称 G是一个算符优先文法。
例：考虑文法 G[E]：
E→E+T|T T→T*F|F F→P↑F|P P→(E)|i
其中 Vt={+,*,↑，（，）,i}
根据规则 E→E+T和 T=+=>T*F可得 +<·*
根据规则 T→T*F和 F=+=>P↑F可得 *<·↑
根据规则 E→E+T和 E=+=>E+T可得 +·>+
根据规则 F→P↑F和 F=+=>P↑F可得 ↑<·↑
根据规则 P→(E)和
E=>E+T=>T+T=>T*F+T=>F*F+T=>P↑F*F+T=>i↑F*F+T
=>i↑F*F+T=>i↑F*F+T*F=>i↑F*F+F=>i↑F*F+T*i
可得：（ <·+ （ <·* （ <·↑ （ <·i +·>) *·>) i·>)
这种构造优先关系不仅复杂，而且很难全部构造出这运算符的优先关系，为此我们需研究构造 算符优先文法的优先关系表的算法。
算符优先关系的构造定义 4-9
FIRSTVT(B)={a|B=+=>a… 或 B=+=>Ca…}
LASTVT(B)={a|B=+=>…a 或 B=+=>…aC}
构造优先关系算法：
对于每个规则 A→…ab… 或 A→…aBb… 中的 a和 b置 a〧 b
对于每个规则 A→…aB… 的 FIRSTVT(B)中的每个终结符 b置
a<·b
对于每个规则 A→…Bb… 的 LASTVT(B)中的每个终结符 a置
a·>b
例：设有文法 G[E]:E→E+T|T T→T*F|F F→(E)|i
试构造其算符优先矩阵解：先求 FIRSTVT和 LASTVT集合：
FIRSTVT(E)={+,*,(,i}
FIRSTVT(T)={*,(,i}
FIRSTVT(F)={(,i}
LASTVT(E)={+,*,),i}
LASTVT(T)={*,),i}
LASTVT(F)={),i}
则：
+ * （ ） i
+ ·> <· <· ·> <·
* ·> ·> <· ·> <·
( <· <· <· 〧 <·
) ·> ·> ·>
i ·> ·> ·>
算符优先分析算法考虑算符优先文法，把句型括在二个 #之间的一般形式写成：
#N1a1N2a2……N n+1anNn+1#
其中，每个 ai都是终结符,Nj是可有可无的非终结符。
找出和归约的是满足如下条件的最左子串 Njaj……N iaiNi+1,
aj-1<·aj
aj〧 aj+1〧 ……a i-1〧 ai
ai·>ai+1
最左素短语在算符优先文法中，仅对终结符号引进优先关系，未对非终结符号定义算符优先关系，所以不能使用这些关系去查找由单个非终结符号组成的句柄。如文法 G[E],E→E+T|T
T→T*F|F F→(E)|i的句型 T+F，显然有 #<·+和 +·>#，但句柄却是 T而不是 T+F为此不能识别出句柄 T。下面将设计一种类似于规范分析的分析法，这种分析法仍然是自底向上的，但不是严格从左到右的，在每一步分析中，它将识别和最约那些所谓的
“最左素短语”（质短语）
定义 4-10
所谓最左素短语是这样的一个短语，它至少含有一个终结符，且除它本身外不包含其它素短语。
例：文法 G[E],E→E+T|T
T→T*F|F F→(E)|i的句型
T+T*F+i相应的语法树如图所示，显然有短语 T+T*F+i、
T+T*F,T,T*F,i。素短语为 T*F,i最左素短语为 T*F
例：句型 i+(i+i)*i的识别步骤 句型 关系 最左素短语 归约符号
1 #i+(i+i)*i# #<·i·>+ i F
2 #F+(i+i)*i# #<·+<·(<·i·>+ i F
3 #F+(F+i)*i# #<·+<·(<·+<·i·>) i F
4 #F+(F+F)*i# #<·+<·(<·+·>) F+F E
5 #F+(E)*i# #<·+<·(〧 )·>* (E) F
6 #F+F*i# #<·+<·*<·i·># i F
7 #F+F*F# #<·+<·*·># F*F T
8 #F+T# #<·+·># F+T E
9 #E# 接受从上述分析过程中可以看出了每个素短语所应归约成的非终结符号，但是请注意在查找所应归约的最左素短语的过程中，
全然没有用到非终结符。无论是 E+T,T+T,E+F,T+F、或
F+F都有归约成 E，这样的分析算法跳过了形如 P→Q的单规则的直接归约步骤，因此算符优先分析法速度稍快。但由于非终结符在识别过程中不起作用，甚至可以考虑非终结符用 N代表或者非终结符不进栈。这种忽略非终结符的归约有时会影响出错的位置，并且存在这样的危险性，可能导致把原来不是句子的输入串误认为句子，但这种缺陷容易从其它技术上加以弥补。
4.2.2 LR分析法的概念前面已经介绍了一些自顶向下的语法分析如：预测分析法、
递归子程序法以及自底向上的分析法，如：简单优先分析法、
算符优先文法。这些方法有一个共同的特点就是很能难适用自动构造,而且文法的适用范围比较小,这些方法往往需要人工构造，这种人工构造识别程序的方法不仅烦琐，而且很容易出错不利于编译程序的开发，为此希望有能够适应于自动构造类的识别程序。这类识别程序也是自底向上的分析的识别程序，其文法仍为上下文无关的文法，而且也是以“移入 —归约法”法为基础的，这种技术称为 LR（ K）分析技术。
LR（ K）分析方法是 1956年 Knuth提出的，其中 L指的是从左向右扫描输入,R指的是构造最右推导的逆,K指的是在决定分析动作时间前看的符号个数。括号和 K省略时，表示 K是 1。
这种方法比自顶向下的 LL（ K）分析方法和自底向上的优先分方法对文法的限制要少得多，也就是说对于绝大多数上下文无关的文法描述的语言都有可以用 LR分析方法进行识别。规范归约的的关键问题是寻找句柄，在一般的“移入 —归约法”过程中，当一串貌似句柄的符号呈现在栈顶时，如何知道它是不是句柄,LR方法就是根据已扫过的符号（用若干状态表示）及以后可能的输入符号判断是归约还是移入，并在归约时决定归约成哪一个非终结符号。 LR自左到右扫描输入串时就能发现其中的错误，并能指出其位置，这种分析法的缺点是若用手工构造成分析程序则工作量很大，需求助于自动产生这些分析程序的产生器。
一个 LR分析器是由三个部分组成的：
(1) 总控程序，也称驱动程序。对所有的 LR分析器总控程序都是一样的
(2) 分析表，不同的文法其分析表是不同的，因此分析表是整个 LR识别方法的核心。它是由两部分组成的，一是“动作” atction,另一是“状态转换” goto。
(3) 分析栈，包括文法符号栈和状态栈它们均是前进后出地处理已获得的信息。
分析器的动作就是由栈顶状态和当前输入符号所决定（ LR（ 0）
可以不由当前输入符号就可决定移入还是归约 )。
LR分析器如图如示。
ACTION[Si,a］规定了栈顶状态为 Si时遇到输入符号 a应执行的动作。动作有 4种可能：
（ l）移进,
把 Sj=GOTO[Si,a］移入到状态栈，把 a移入到文法符号栈。
其中 i,j表示状态号。
（ 2）归约,
当在栈顶形成句柄为 β时，则用 β归约为相应的非终结符 A，
即文法中有 A→β的产生式，若 β的长度为 r（即 |β|=r），则从状态栈和文法符号栈中自栈顶向下去掉 r个符号,即栈指针 SP减去 r。
并把 A移入文法符号栈内,Sj=GOTO[Si,A]移进状态栈，其中
Sj 为修改指针后的栈顶状态。
（ 3）接受 acc:
当归约到文法符号伐中只剩文法的开始符号 S?时，并且输入符号串已结束即当前输入符是‘＃’，则为分析成功。
（ 4）报错当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，
则报错，说明输入串不是该文法能接受的句子。
从上面可以看出 LR分析器的关键部分是分析表的构造，后边将针对每种不同的 LR分析器详细介绍其构造思想及方法。
例：设有文法 G[S]为：
(1) S→A
(2) S→B
(3) A→aAb
(4) A→c
(5) B→aBb
(6) B→d
有分析表：
状态
ACTION GOTO
a b c d # S A B
0 S4 S5 S6 1 2 3
1 acc
2 r1 r1 r1 r1 r1
3 r2 r2 r2 r2 r2
4 S4 S5 S6 7 8
5 r4 r4 r4 r4 r4
6 r6 r6 r6 r6 r6
7 S9
8 S10
9 r3 r3 r3 r3 r3
10 r5 r5 r5 r5 r5
现用移入归约法对输入串 aaaadbbbb＃进行分析：
步骤 状态栈 符号栈 输入串 ACTION GOTO
1 0 # aaaadbbbb＃ S4
2 04 #a aaadbbbb＃ S4
3 044 #aa aadbbbb＃ S4
4 0444 #aaa adbbbb＃ S4
5 04444 #aaaa dbbbb＃ S6
6 044446 #aaaad bbbb＃ r6 8
7 044448 #aaaaB bbbb＃ S10
8 04444810 #aaaaBb bbb＃ r5 8
9 04448 #aaaB bbb＃ S10
10 0444810 #aaaBb bb＃ r5 8
11 0448 #aaB bb＃ S10
12 044810 #aaBb b＃ r5 8
13 048 #aB b＃ S10
14 04810 #aBb # r5 1
15 03 #B # r2 1
16 01 #S # acc
从上例中可以看出在符号栈中的符号串为一个规范句型的前缀，
由于采用的是所谓“移入 —归约法”,即一旦发现句柄就将句柄归约，因此在栈中是不会含句柄后任何符号，为此指导把这些在栈中可以出现的符号串给一个定义。
定义 4-11：活前缀是指范句型的一个前缀,它不含句柄之后的任何符号即：若 S=r=>αAω=r=>α β ω是文法 G中的一个规范推导，则句柄是 β，因此不包含句柄的符号串为 αβ的前缀均为活前缀。
在上例中的识别过程中，还可以看出整个识别过程实际上是一个活前缀的变化过程。
为了识别方便，即发现识别符号就认为是接受状态，引进一个新的文法符号 S?它不在规则的右部出现，使 S?→S,其中 S原来的识别符号，一旦要将 S归约成 S?时，即为识别状态。
计算活前缀的直观方法是写出全部规范句型的符号串例：在上例中有：
S =r=>A=r=>aAb=r=>a2Ab2……= r=> anAbn=r=> ancbn 及
S =r=>B=r=>aBb=r=>a2Bb2……=r=> a nBbn=r=> andbn
则相应的活前缀为有：
ε,a,a2,a3……a n,anc,and,anA,anB,anAb,anBb,an-1A,an-1B,
an-1Ab,an-1Bb,……,A,B
4.2.3 LR(0)项目集族的构造根据 LR（ k）的定义,LR（ 0）就是不需要根据展望信息，
就可知道是移入还是归约，而且能知道归约成那一个非终结符号，换句话说，一但发现一些状态呈现“句柄”就可将它归约。
下面讨论 LR（ 0）文法的项目集族的构造以及其分析表的构造。
LR（ 0）项目定义 4.12 如果 A→αβ是文法的一个产生式。其中 α和 β可为 ε则
A→α·β称为 G的 LR（ 0）项目，简称项目或项。
例,G[E]：
E→E+T|T T→T*F|F F→(E)|i
有项目 E→·E+T E→E·+T E→E+·T E→E+T·
E→T·
F→(E·)
F→i·
等显然，若有产生式 A→α则可有 |α|+1个项目，产生式 A→ε只有项目 A→·
项目名称
·移入项目 圆点点在终结符前面的的项目称为“移入项目”，
即在该状态时，需将终结符移入符号栈
·待约项目 圆点点在非终结符前面的项目称为“待约项目”，
即等待该非终结符的归约
·归约项目 圆点点在整个产生式的右部的项目称为“归约项目”，表示该产生式相应的文法符号都已找到，可归约成相应的非终结符
·接受项目 设 S?是拓广文法的识别符号，如项 S?→α·，称为
“接受项目”
为了使“接受”状态易于识别，让识别符号不在产生式的左部出现，把文法添上一个产的产生式 S?→S或 S?→S#，这样就仅有唯一的“接受”状态。
定义 4.13 设 A→α·Xβ是文法 G的一个 LR（ 0）项目，其中
X∈ Vn∪ Vt,则 LR（ 0）项目 A→αX·β称为它的后继项目，其中 α、
β∈ （ Vn∪ Vt） *
定义 4.14 由 LR（ 0）组成的集合称为 LR（ 0）项目集，简称项集。
定义 4.15 识别文法 G活前缀的项目集的全体称为文法的 LR(0)
项目集规范族,简称项目集族。
1.构造文法 G的 LR(0)项目集族的方法之一从 LR(0)项目出发来构造识别文法所有活前缀的自动机。
其步骤是，首先构造出识别文法活前缀的 NFA，再将 NFA确定化和最小化，最终得到所需的 DFA。
由文法的 LR(0)项目构造识别文法所有活前缀的 NFA的算法如下：
(1) 令所有 LR(0)项目分别对应 NFA的一个状态，归约项目的
LR(0)项目对应一个终态。
(2) 接受项目的 LR(0)项目作为 NFA的唯一初态。
(3) 若状态 i是状态 j的后继项目,则从状态 i到状态 j引一条箭弧，
标记为 X。
(4) 若状态 i为待约项目（设为 X→α·Aβ），则从状态 i引箭弧到所有 A→·γ的状态，并标记为 ε。
例,设有文法 G[A]：
A→aA A→b
试构造识别文法 G的项目集族。
解,拓广文法
G[S?],(0) S?→A
(1) A→aA
(2) A→b
则 G[S?]的 LR(0)项目：
S? →·A
A→·aA
A→a·A
A→·b
A→b·
S? →A·
A→aA·
则将各状态命名后,如图,
状态 a A b
{1,2,4} {3,2,4} {6} {5}
{3,2,4} {3,2,4} {7} {5}
{6} Φ Φ Φ
{5} Φ Φ Φ
{7} Φ Φ Φ
将项目代入命名的状态后,如图,
图为识别文法 G的活前缀的 DFA,也是 LR(0)项目集族
2.构造文法 G的 LR(0)项目集族的方法之二如果把在识别过程中可能出现的项目放在一起组成的项目集，每一项目则表示成可能识别状态，识别程序可逻辑依次进入这些状态，这些状态的序列也就代表活前缀。一个状态集是由它的基本项集和基本项集的闭包组成的。
构造 I的闭包 CLOSURE（ I）的算法：
(1) I的任何项目都有属于 CLOSURE（ I）
(2) 若 A→α·Bβ属于 CLOSURE（ I），那么，任何关于 B的产生式 B→γ，项目 B→·γ添入 CLOSURE（ I）中
(3) 重复执行步骤 2直至 CLOSURE（ I）不再增大为止。
定义 4-16 GO（ Ii,X） =Ij
其中,Ii为包含某一项目集的状态
X为一文法符号，即 X ∈ Vn∪ Vt
Ij=CLOSURE（任何形如 A→αX·β的项目 | A→α·Xβ ∈ Ii ）
例：设 G[E]：
E→E+T|T T→T*F|F F→(E)|i
试构造项目 S?→·E的闭包解,CLOSURE（ S?→·E） ={ S?→·E,E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
文法 G的 LR（ 0）项目集族构造算法：
（ 1）初始项集 I0= CLOSURE（ S?→·S）是 G的项集，这里 S?是包含有规则 S?→S的拓广文法的开始符号
（ 2）如果 Ii中 G 的项集，则 Ii 的一切后继项集的闭包 Ij=GO(Ii,X)
均是 G的项集
（ 3）重复 2，直到再无新的项集可以添入为止例：试构造下列文法 G[S?],S?→S S→A S→B A→aAb A→c
B→aBb B→d
的 LR（ 0）项集解,I0= CLOSURE（ S?→·S） ={ S?→·S,S→·A,S→·B，
A→·aAb,A→·c,B→·aBb B→·d}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→A·） ={ S→A·}
I3= CLOSURE（ S→B·） ={ S→B·}
I4= CLOSURE（ A→a·Ab,B→a·Bb） ={ A→a·Ab,B→a·Bb
A→·aAb,A→·c,B→·aBb B→·d }
I5= CLOSURE（ A→c·） ={ A→c·}
I6= CLOSURE（ B→d·） ={ B→d·}
I7= CLOSURE（ A→aA·b） ={ A→aA·b}
I8= CLOSURE（ B→aB·b） ={ B→aB·b}
I9= CLOSURE（ A→aAb·） ={ A→aAb·}
I10= CLOSURE（ B→aBb·） ={ B→aBb·}
定义 4-17 若存在规范推导 S?=r=>αAω=r=>αβ1β2ω则称项目
A→β1·β2对活前缀 αβ1是有效的。
若项目 A→α·Xβ对活前缀 γ是有效的，则项目 A→αX·β对活前缀
γX是有效的。一般来说，同一个项目可能对好几个活前缀都是有效的。如：上例中，项目 B→aB·b对活前缀 aB,aaB,aaaB,
aaaaB,……anB 都是有效的。
若归约项目 A→β·对活前缀 αβ是有效的，则应把符号串 β归约成 A，即把活前缀 αβ变化成 αA；若移入项目 A→β1·β2对活前缀是有效的（ β2≠ε），则说不得明句柄尚未形成，因此下一步的动作应是移入，由于对于同一活前缀存在若干项目都是对它是有效的，如：项目 A→a·Ab,A→·aAb,A→·c,B→·aBb
B→·d都有对活前缀 aa是有效的，故其后继项目可能有好几个。
若待约项目 A→α·Bβ，这表明用产生式 A的右部归约时，应先归约 B；当归约项目 S?→S·对活前缀 ε是有效的，则说明整个识别符号已归约表明分析成功。
若项目中有既有移入项目也有归约项目或者有两个或两个以上的归约项目，这种情形就称为冲突。分别称为移入 /归约冲突和归约 /归约冲突。解决冲突的方法之一就是向搜索若干符号，
当然一些非 LR文法是无论搜索多少个符号也是无济于事的。如,
二义性文法都是非 LR文法,文法 S→Ac A→bAb|b是非 LR文法,
而 S→Ac A→Abb|b却是 LR文法,
定义 4-18 对于一个文法的 LR（ 0）项目集族中不存在移入 /归约，或归约 /归约冲突，称这个文法是 LR（ 0）文法。
LR（ 0）分析表的构造综上所述，只要对 LR（ 0）文法构造出对于每个活前缀的有效项目集，就可对符号串进行分析了。事实上从初始项集出发构造的全部项集正是所需的全部项集。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……,n 令包含项目
S?→S·的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a)若该项目为移入项，即为 A→α·aβ形式则置 ACTION[k.a]
为 Sj,其中 Ij=GO(Ii,a)
b)若该项目为归约项，即为 A→α·的形式，则对于任何
a∈ Vt∪ {#}，置 ACTION[k,a]=rj,其中 j为第 j个产生式
c)若该项目为待约项，即为 A→α·Bβ的形式则置 GOTO[k,B]
为 j，其中 B为待约项的第一个非终结符,Ij=GO（ Ik,B）
d)若项目为 S?→S·，则置 ACTION[k,#]为“接受”，即 acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 LR（ 0）分析表例：构造文法 S→(L)|a L→L,S|S 的 LR（ 0）分析表解：拓广文法：
（ 0） S?→·S （ 1） S→(L) （ 2） S→a （ 3） L→L,S
（ 4） L→S
I0= CLOSURE（ S?→·S） ={ S?→·S,S→·（ L）,S→·a}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→（ ·L ）） ={ S→（ ·L ）,L→·L,S,L→·S，
S→·（ L）,S→·a }
I3= CLOSURE（ S→a·） ={ S→a·}
I4= CLOSURE（ S→（ L·）,L→L·,S） ={ L→L·,S,S→
（ L·） }
I5= CLOSURE（ L→S·） ={ L→S·}
I6= CLOSURE（ L→L,·S） ={ L→L,·S,S→·（ L）,S→·a }
I7= CLOSURE（ S→（ L） ·） ={S→（ L） ·}
I8= CLOSURE（ L→L,S·） ={ L→L,S· }
其中,
GO(I0,S)=I1 GO(I0,()=I2 GO(I0,a)=I3
GO(I2L)=I4 GO(I2,S)=I5 GO(I2,()=I2 GO(I3,a)=I3
GO(I4,,)=I6 GO(I4,） )=I7
GO(I6,()=I2 GO(I6,a)=I3 GO(I6,S)=I8
其分析表为：
状态 ACTION GOTO
a （ ）,# S L
0 S3 S2 1
1 acc
2 S3 S2 5 4
3 r2 r2 r2 r2 r2
4 S7 S6
5 r4 r4 r4 r4 r4
6 S3 S2 8
7 r1 r1 r1 r1 r1
8 r3 r3 r3 r3 r3
4.2.4 SLR(1)分析
LR（ 0）是一类非常简单的文法。这种文法规定了每个状态中不含冲突的项目，在实际应用中这类文法较少。由于在 LR
（ 0）分析中，一旦在栈顶发现句柄，没有根据当前输入符号就进行归约，这样在同一个项目集中就不能有移入归约冲突或者归约归约冲突。那么是否能从右面的输入符号来解决冲突问题呢？回答是肯定的。当栈顶呈现句柄 α时，用产生式 A→α归约时，只有当前输入符号，恰好是属于 FOLLOW（ A）时，应该归约，否则不应归约。这种方法称为简单的 LR（ 1）分析法，
即 SLR（ 1）分析法。如果向右看非终结符 A后的 k个符号，则称为 SLR（ k）分析法。
为解决冲突问题，假定 LR（ 0）规范族中含有如下的一个项目集状态 I：
I={X→α·bβ,A→α·,B→α·}
其中，第一项目为移入项目，第二项目、第三项目是归约项目。
为此对于 SLR（ 1）要考察向右看的集合，当状态 I面临输入符号 a 时
(1) 若 a=b 则移入
(2) 若 a∈ FOLLOW(A),则用产生式 A→α进行归约
(3) 若 a∈ FOLLOW(B),则用产生式 B→α进行归约
(4) 此外，报错一般地，假定 LR（ 0）规范族的一个项目 I中有 m个移入项目,A1→α1·a 1β1,A2→α2·a 2β2,……,Am→αm·a mβm;同时含有 n
个归约项目,B1→α·,B2→α·,……B n→α·,如果移入集合
{a1,a2,……,a m},FOLLOW(B1),FOLLOW(B2),……,
FOLLOW(Bn)两两不相交，则可根据现行输入符号 a属于上述
n+1个集合中的哪一个集合而获得冲突的解决。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……,n 令包含项目
S?→S·的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a) 若该项目为移入项，即为 A→α·aβ形式则置
ACTION[k.a]为 Sj,其中 Ij=GO(Ik,a)
b)若该项目为归约项，即为 A→α·的形式，则对于任何
a∈ FOLLOW(A)，置 ACTION[k,a]=rj,其中 j为第 j个产生式
c)若该项目为待约项，即为 A→α·Bβ的形式则置 GOTO[k,B]
为 j，其中 B为待约项的第一个非终结符即为,Ij=GO（ Ik,B）
d) 若项目为 S?→S·，则置 ACTION[k,#]为“接受”，即 acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 SLR（ 1）分析表例：构造文法 G[S]：
（ 0） S?→E （ 1） E→E+T （ 2） E→T （ 3） T→T*F （ 4）
T→F （ 5） F→(E) （ 6） F→i
的 SLR分析表解：先求 LR（ 0）项目集族：
I0=CLOSURE（ S?→·E） ={ S?→·E,E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
I1=CLOSURE（ S?→E·） ={ S?→E·,E→E·+T }
I2= CLOSURE（ E→T·,T→T·*F） ={ E→T·,T→T·*F}
I3= CLOSURE（ T→F·） ={ T→F·}
I4= CLOSURE（ F→(·E)） ={ F→(·E),E→·E+T,E→·T，
T→·T*F,T→·F,F→·(E),F→·i}
I5= CLOSURE（ F→i·） ={ F→i·}
I6= CLOSURE（ E→E+·T） ={ E→E+·T,T→·T*F,T→·F，
F→·(E),F→·i }
I7= CLOSURE（ T→T*·F） ={ T→T*·F,F→·(E),F→·i }
I8= CLOSURE（ F→(E·),E→E·+T） ={ F→(E·),E→E·+T}
I9= CLOSURE（ E→E+T·,T→T· *F ） ={E→E+T·,
T→T· *F }
I10= CLOSURE（ T→T*F·） ={ T→T*F·}
I11= CLOSURE（ F→(E)·） ={ F→(E)·}
而其中,
GO(I0,E)=I1 GO(I0,T)=I2 GO(I0,F)=I3 GO(I0,（ )=I4 GO(I0,i)=I5
GO(I1,+)=I6
GO(I2,*)=I7
GO(I4,E)=I8 GO(I4,T)=I2 GO(I4,F)=I3 GO(I4,（ )=I4 GO(I4,i)=I5
GO(I6,T)=I9 GO(I6,F)=I3 GO(I6,（ )=I4 GO(I6,i)=I5
GO(I8,） )=I11 GO(I8,+)=I6
GO(I9,*)=I7
而
FOLLOW（ S?） ={#}
FOLLOW（ E） ={+,),#}
FOLLOW（ T） ={+,*,),#}
FOLLOW（ F） ={+,*,),#}
故其 SLR（ 1）分析表为：
状态
ACTION GOTO
+ * （ ） i # E T F
0 S4 S5 1 2 3
1 S6 acc
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 S4 S5 8 3 2
5 r6 r6 r6 r6
6 S4 S5 9 3
7 S4 S5 10
8 S6 S11
9 r1 S7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
LR(1)分析在 SLR方法中，若项目 Ik含有 A→α·。那么，在状态 K时，
只要所面临的输入符号 a∈ FOLLOW(A)就确定采取“用 A→α归约”的动作，但是，在某种情况下，当状态呈现于栈顶时，栈时的符号串所构成的活前缀 βα未必允许把 α归约为 A，因为可能就不存在 …β Aa… 的句型 (但可能存在 … γAa… 这样的句型 ) 这样对于 SLR方法中的移入符号集 {a1,a2,……,a m}和 FOLLOW（ A）
的交为非空时，还是有可能把该状态分开来判定是移入还是归约的。这种方法与 SLR比较对出错位置定位更精确。
例：对于文法 G[S],S→L=R S→R L→*R L→i R→L
这个文法的 LR（ 0）项目集族为：
I0= CLOSURE（ S?→·S） ={ S?→·S,S→·L=R,S→·R，
L→·*R,L→·i,R→·L}
I1= CLOSURE（ S?→S·） ={ S?→S·}
I2= CLOSURE（ S→L·=R,R→L·） ={ S→L·=R,R→L· }
I3= CLOSURE（ S→R·） ={ S→R·}
I4= CLOSURE（ L→*·R） ={ L→*·R,R→·L,L→·*R,L→·i }
I5= CLOSURE（ L→i·） ={ L→i·}
I6= CLOSURE（ S→L=·R） ={ S→L=·R,R→·L,L→·*R，
L→·i }
I7= CLOSURE（ L→*R·） ={ L→*R·}
I8= CLOSURE（ R→L·） ={ R→L· }
I9= CLOSURE（ S→L=R·） ={ S→L=R·}
对于 I2，有移入归约冲突，而 FOLLOW（ R） =
{#,=}∩{=}≠Ф，则该文法不是 SLR，而当状态 2呈现于栈顶面临输入符号 =时，在这个文法中却不含以 R=…… 形式的句型。
因此，句型 L=……,中不能以 R→L归约。
为此，让每个状态含有更多的“展望”信息，这些信息将有助于克服动作的冲突、排除那种用 A→α的无效归约。设想，
如果能对每个状态附加一些信息，使 LR分析器的每个状态能够确切地指出，当 α后是哪些终结符时才允许将 α归约成 A，这样就不会产生无效的归约。为此需重新定义项目，使得每个项目都附带有 k个终结符。故其项目的形式为：
[A→α·β,a1a2a3……a k]
其中 A→α·β是一个 LR（ 0）项目，每个 a都有是终结符或 #，这种项目称为一个 LR（ k）项目。项目中的 a1,a2,a3……,ak
称它的搜索符串（或展望信息），向右搜索串仅对归约项目
[A→α·,a1a2a3……a k]有意义而对任何移进项目或待约项目
[A→α·Bβ,a1a2a3……a k]搜索串 a1,a2,a3……,ak不起作用。
归约项目 [A→α·,a1a2a3……a k]意味着：当它所属的状态呈现在栈顶且后续的 k个输入符号为 a1a2a3……a k时，才能把栈顶上的 α归约为 A。为简单起见，在这里只研究 k=1情形。
从项目对活前缀的有效的定义来看，若一个 LR（ 1）项目
[A→α·β,a]对于活前缀 γ是有效的，那么应该是：
S=r*=>δAω=r=>δαβω
其中 1） γ=δα 2） a是 ω的第一个符号,a为终结符或 #
显然项目 [T→T·*F,+],[T→T·*F,*]对活前缀 E+T和 E+（ T都有是有效的。
LR(1)项目集族的构造一个 LR（ 1）项目是由两部分组成的，一部分是和 LR（ 0）
项目相同的部分，称为心，另一部分是搜索符，因而，构造有效的 LR（ 1）项目集族的方法与构造 LR（ 0）的方法类似，下面逐一介绍 LR（ 1）的 CLOSURE和 GO的构造方法。
构造 LR（ 1）项目集的闭包函数。
构造 LR（ 1）项目集的闭包函数的算法：
（ 1） I的任何项目都有属于 CLOSURE（ I）
（ 2）若 [A→α·Bβ,a]属于 CLOSURE（ I）,B→γ是一个产生式，那么对于 FIRST（ βa）中的每个终结符 b,把项目 [B→·γ，
b]添入 CLOSURE（ I）中
（ 3）重复执行步骤 2直至 CLOSURE（ I）不再增大为止。
显然,[A→α·Bβ,a]属于对活前缀 λ=δα是有效的项目意味着存在一个规范推导
S=r*=>δAaθ=r=>δαBβaθ
若 βaθ可推导出 bω，则对于每个形如 B→γ的产生式，有
S=r*=>λB bω=r=>λγbω
换言之，项目 [B→·γ,b]对活前缀 λ是有效的，即 b∈ FIRST
（ βa）
LR（ 1）状态转换函数的构造定义 4-19 LR（ 1）状态转换函数 GO是一个二元函数，定义如下：
GO（ Ii,X） =Ij
其中 X为文法符号，即 X∈ Vt∪ Vn,Ii是项集，而
Ij=CLOSURE（ [A→αX·β,a]| [A→α·Xβ,a] ∈ Ii,a∈ Vt∪ {#}
当 Ii是对某个活前缀 γ有效的项目集合时,Ij= GO（ Ii,X）便是对活前缀 γX有效的项目集合。
文法 G的 LR（ 1）项集的构造算法
(1) 初始项集 I0= CLOSURE（ [S?→·S,#]）是 G的项集，这里
S?是包含有规则 S?→S的拓广文法的开始符号
(2) 如果 Ii中 G 的项集，则 Ii 的一切后继项集的闭包 Ij= GO(Ii,X)
均是 G的项集
(3) 重复 2，直到再无新的项集可以添入为止例：构造拓广文法
（ 0） S? →S (1)S→BB (2)B→aB (3)B→b
的 LR（ 1）项集
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·BB,#]，
[B→·aB,a/b],[B→·b,a/b]}
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2=CLOSURE（ [S→B·B,#]） ={[S→B·B，
#],[B→·aB,#],[B→·b,#]}
I3=CLOSURE（ [B→a·B,a/b]） ={[B→a·B,a/b],
[B→·aB,a/b],[B→·b,a/b]}
I4=CLOSURE（ [B→b·,a/b]） ={ [B→b·,a/b]}
I5=CLOSURE（ [S→BB·,#]） ={[S→BB·,#]}
I6=CLOSURE（ [B→a·B,#]） ={[S→a·B,#],
[B→·aB,#],[B→·b,#]}
I7=CLOSURE（ [B→b·,#]） ={ [B→b·,#]}
I8=CLOSURE（ [B→aB·,a/b]） ={[S→aB·,a/b]}
I9=CLOSURE（ [B→aB·,#]） ={[S→aB·,#]}
LR（ 1）分析表的构造现在已经有了构造了 LR（ 1）的项目集族和 GO函数的方法，下面可以构造成其分析表了，它的构造成算法与 LR（ 0）、
SLR（ 1）的方法其本相同。
构造拓广文法 G的分析表的算法：
(1) 将状态 I0,I1,……,I n记作 0,1,……n,令包含项目 [S?→S·，
#]的项集为初始状态集
(2) 对于状态集 Ik中的每一个项目做：
a) 若该项目为移入项，即为 [A→α·aβ,b]形式则置
ACTION[k.a]为 Sj,其中 Ij=GO(Ii,a)
b) 若该项目为归约项，即为 [A→α·,b]的形式，则置
ACTION[k,b]=rj,其中 j为第 j个产生式
c) 若该项目为待约项，即 [A→α·Bβ,b]则置 GOTO[k,B]为 j，
其中 B为待约项的第一个非终结符,Ij=GO（ Ik,B）
d)若项目为 [S?→S·,#]，则置 ACTION[k,#]为“接受”，即
acc
(3) 分析表中空即为出错
(4) 分析表中无冲突元素即为 LR（ 1）分析表分析表中无冲突元素即为 LR（ 1）分析表例：试构造文法 G[S],S→L=R S→R L→*R L→i R→L的
LR（ 1）分析表拓广文法 G[S?]：
(0)S?→S (1)S→L=R (2)S→R (3)L→*R (4)L→i (5)R→L
先构造 LR（ 1）项目集族：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·L=R,#]，
[S→·R,#],[L→·*R,=/#],[L→·i,=/#],[R→·L,#] }
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2= CLOSURE（ [S→L·=R,#],[R→L·,#]） ={[S→L·=R，
#],[R→L·,#]}
I3= CLOSURE（ [S→R·,#]） ={ [S→R·,#]}
I4= CLOSURE（ [L→*·R,=/#]） ={ [L→*·R,=/#],[R→·L,=/#],
[L→·*R,=/#],[L→·i,=/#] }
I5= CLOSURE（ [L→i·,=/#]） ={[ L→i·,=/#]}
I6= CLOSURE（ [S→L=·R,#]） ={[S→L=·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#]}
I7= CLOSURE（ [L→*R·,= /#]） ={[ L→*R·,=/#]}
I8= CLOSURE（ [R→L·,=/#]） ={ [R→L·,=/#] }
I9= CLOSURE（ [S→L=R·,#]） ={[S→L=R·,#]}
I10= CLOSURE（ [R→L·,#]） ={ [R→L·,#] }
I11= CLOSURE（ [L→*·R,#]） ={ [L→*·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#] }
I12= CLOSURE（ [L→i·,#]） ={[ L→i·,#]}
I13= CLOSURE（ [L→*R·,#]） ={[ L→*R·,#]}
状态 ACTION GOTO
* i = # S L R
0 S4 S5 1 2 3
1 acc
2 S6
3 r2
4 S4 S5 8 7
5 r4 r4
6 S11 S12 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 S11 S12 10 13
12 r4
13 r3
LALR(1)分析从上例中可以看出 LR（ 1）分析表的状态一般较 SLR多，
而 SLR又不能处理 SLR冲突的文法。为此可采取了一种折衷方法，称为前视 LR分析法,LALR（ look a head-LR）技术。在实际应用中经常使用这种方法，因为由它产生的比 LR分析表要小得多，与 SLR,LR（ 0）表的大小相同，但能处理上例中的文法。它处理的文法弱于 LR（ 1）强于 SLR。一般的算法语言的 SLR和 LALR分析表有几百个状态，而 LR(1)分析表有上千个状态。
例：考虑拓广文法
（ 0） S? →S (1)S→BB (2)B→aB (3)B→b
的 LR（ 1）项集：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·BB,#]，
[B→·aB,a/b],[B→·b,a/b]}
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2=CLOSURE（ [S→B·B,#]） ={[S→B·B，
#],[B→·aB,#],[B→·b,#]}
I3=CLOSURE（ [B→a·B,a/b]） ={[B→a·B,a/b],
[B→·aB,a/b],[B→·b,a/b]}
I4=CLOSURE（ [B→b·,a/b]） ={ [B→b·,a/b]}
I5=CLOSURE（ [S→BB·,#]） ={[S→BB·,#]}
I6=CLOSURE（ [B→a·B,#]） ={[S→a·B,#],
[B→·aB,#],[B→·b,#]}
I7=CLOSURE（ [B→b·,#]） ={ [B→b·,#]}
I8=CLOSURE（ [B→aB·,a/b]） ={[S→aB·,a/b]}
I9=CLOSURE（ [B→aB·,#]） ={[S→aB·,#]}
显然其中 I3和 I6,I4和 I7,I8和 I9它们除了搜索符不同外，其余各部相同，能不能考虑把相类似的状态合并成一个状态呢？
为解决这个问题，首先来分析上述状态的作用，上述文法定义了 a*b a*b的整规集,I3是在第一个 b前找,B”，即 aB或 b所以它的搜索符为 a/b，而 I6是在已找到第一个,B”后，即在第一个 b
之后找,B”故它的搜索符号为 #。这样可以判断出 a*b和 a*b a*b
a*b不是上述文法定义的句子。如把状态 I3和 I6合并成一个状态为 {[S→a·B,a/b/#],[B→·aB,a/b/#],[B→·b,a/b/#]}，由于搜索符对移入项目不作用，故合并后不会产生问题。如把 I4和 I7全并为 { [B→b·,a/b/#]}这时识别 a*b中的也会归约成 B，同样 a*b a*b
a*b中第二个 b也会归约成 B。幸运的是当识别 a*b时，把它归约这 B时，没有 S→B这样的规则，此时会发生错误，同样 S a*b
的 S后不是 #也会发生错误。
定义 4-20 如果除去搜索符之后，这两个集合是相同的，称两个 LR（ 1）项目集具有相同的心。
由于 GO（ I,X）的心仅仅依赖于 I的心，因此 LR（ 1）项目集合并后的转换函数 GO（ I,X）自身的合并而得到的。如果一个文法是 LR（ 1）文法显然每个项目中无“移入” /“归约”
冲突，那么合并后肯定不会有“移入” /“归约”，至多有“归约” /“归约”冲突。只要合并后没有“归约” /“归约”冲突，就可以将它们所有同心集合并成新的状态集，即 LALR状态集。
LALR分析表构造算法之一：
(1)构造文法 G的 LR（ 1）项目集族 C={ I0,I1,……,I n}
把所有的同心集合并在一起，记作 C?={ J0,J1,……,J m}
为全并后的新族，含有项目 [S?→S·,#]的项集 Jk为分析表的初始状态集
(2)对于 C?构造 ACTION表：
a) 若该项目为移入项，即为 [A→α·aβ,b]形式则置
ACTION[k.a]为 Sj,其中 Jj=GO(Jk,a)
b) 若该项目为归约项，即为 [A→α·,b]的形式，则置
ACTION[k,b]=rj,其中 j为第 j个产生式
c) 若项目为 [S?→S·,#]，则置 ACTION[k,#]为“接受”，即
acc
(3) GOTO表的构造假定 Jk是 Ii1,Ii2,Ii3,……I it全并后的新集。由于所有这些 Ii同心，
那么 GO（ Ii1,X）,GO(Ii2,X),GO(Ii3,X),……GO(I it,X)也同心，于是将这些同心集合并起来，记为 Jj,则有 GO（ Jk,X） = Jj于是若 GO（ Jk,A） =Jj,则置 GOTO[k,A]=j,其中 A∈ Vn
(4) 分析表中空即为出错例：构造文法 G?的 LALR分析表：
G?[S?]：
(0)S?→S (1)S→L=R (2)S→R (3)L→*R (4)L→i (5)R→L
先构造 LR（ 1）项目集族：
I0=CLOSURE（ [S? →·S,#]） ={[S? →·S,#],[S→·L=R,#]，
[S→·R,#],[L→·*R,=],[L→·i,=],[R→·L,#] }
I1=CLOSURE（ [S? →S·,#]） ={[S? →S·,#]}
I2= CLOSURE（ [S→L·=R,#],[R→L·,#]） ={[S→L·=R，
#],[R→L·,#]}
I3= CLOSURE（ [S→R·,#]） ={ [S→R·,#]}
I4= CLOSURE（ [L→*·R,=]） ={ [L→*·R,=],[R→·L,=],
[L→·*R,=],[L→·i,=] }
I5= CLOSURE（ [L→i·,=]） ={[ L→i·,=]}
I6= CLOSURE（ [S→L=·R,#]） ={[S→L=·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#]}
I7= CLOSURE（ [L→*R·,=]） ={[ L→*R·,=]}
I8= CLOSURE（ [R→L·,=]） ={ [R→L·,=] }
I9= CLOSURE（ [S→L=R·,#]） ={[S→L=R·,#]}
I10= CLOSURE（ [R→L·,#]） ={ [R→L·,#] }
I11= CLOSURE（ [L→*·R,#]） ={ [L→*·R,#],[R→·L,#],
[L→·*R,#],[L→·i,#] }
I12= CLOSURE（ [L→i·,#]） ={[ L→i·,#]}
I13= CLOSURE（ [L→*R·,#]） ={[ L→*R·,#]}
令 J0=I0,J1=I1,J2=I2,J3=I3,J4=I4,11,J5=I5,12,J6=I6，
J7=I7,13,J8=I8,10,J9=I9
故有 GO函数：
故有 GO函数：
GO（ J0,S） =J1,GO（ J0,L） =J2,GO（ J0,R） =J3，
GO（ J0,*） =J4,GO（ J0,i） =J5
GO（ J2,=） =J6,GO（ J4,R） =J7,GO（ J4,L） =J8，
GO（ J4,*） =J4,GO（ J4,i） =J5
GO（ J5,R） =J9,GO（ J6,L） =J8,GO（ J6,*） =J4，
GO（ J6,i） =J5
状态 ACTION GOTO
* i = # S L R
0 S4 S5 1 2 3
1 acc
2 S6 r5
3 r2
4 S4 S5 8 7
5 r4 r4
6 S4 S5 8 9
7 r3 r3
8 r5 r5
9 r1
LALR分析表构造算法之二：
对于任何文法 G，通过构造它的 LR（ 1）项集，合并同心集，最后形成了 LALR（ 1）项目集，这是比较费时各占用较多的存储空间。在 LR（ 1）项集不考虑搜索符时即为 LR（ 0）项集，那么是否能通过构造 LR（ 0）项集，然后再构造 LALR项集呢，答案是肯定的。
定义 4-21 初始项目 S?→S和所有圆点不在左端的顶目，称为核心项，简称核。
一个 LR（ 0）项目集实际上是由核和非核项组成的，核是由前趋项目决定的，而非核是由求闭包得出的。
当一个项目集的核决定了，实际上相对于某文法的这个项目集也是唯一的。因此可以用核来代表项目集。
另外，所有归约项目 A→α.（除 α=ε外 )都在核内，即使 α=ε
核中也必然存在这样的规则 [B→β.Cγ,b],且 C=*r=>Aδ,及
a∈ FIRST(δγb),而满足 C=*r=>Aδ的所有非终结符 A也是可以预先计算出来的。
对于移入项目，则核中必须有项目 [A→β.aγ,b]或者
[A→β.Bγ,b]，其中 B=*r=>aω,这些 a预先也是可以计算出来的。
下面讨论如何从核构造 GOTO表。若 GO（ I,X） =J,I的核是 K,J的核是 L。那么，如果 [A→α.Xβ,a]∈ K,则
[A→αX.β,a]∈ L,另外 [A→β.Bγ,a]∈ K,C→Xη是一个产生式 K，
B=*r=>Cω和 b∈ FIRST(ωγa),而 C→Xη是一个产生式,则
[C→X.η,b]∈ L。
最后考虑为每个 LR（ 0）项目都配有相应的搜索符，使得这个核成为 LALR（ 1）的核。
先考虑搜索符是如何从集合 I传播到另一个集合 GO（ I,X）
的。
若 A→β.Bγ属于 LR（ 0）集 I的核 K,B=*r=>Cω且 C→Xη是一个产生式，那么如考虑 LR（ 1）项目集，其项目 [A→α.Xβ,
a]∈ K,GO（ I,X）中的核中的类似于 [C→X.η,b]∈ L的项目中的搜索符 b与 a有什么关系呢？
实际上，这个 b有两种可能的途径：其一,B=*r=>Cω，
b∈ FIRST(ωγa),但 ωγ不能推导出 ε，则搜索符 b不是 a，称为搜索符 b是自生的；其二,ωγ能推导出 ε，则搜索符 b就是 a,则搜索符 a是传播给 a的。
下面给出自生搜索符和搜索符传播的算法（其中,I的核为 K,@
为假想搜索符）：
for(K的每个项目的核 [B→α.β,@])
{ J=closure([B→α.β,@]);
if(项目 [A→γ.Xδ,a] ∈ J且 a≠@)
GO(I,X)中的项目 [A→γX,δ,a] 的搜索符是自生的 ;
if(项目 [A→γ.Xδ,a] ∈ J且 a=@)
GO(I,X)中的项目 [A→γX,δ,a] 的搜索符是传播的 ;
也就是搜索符从 I的 B→α.β传播到 GO(I,X)中的项目
A→γX,δ的
}
构造 LALR(1)项目集族的核的算法,
(1) 构造拓广文法 G’ 的 LR(0)项目集的核
(2) for(每个 LR(0)项目 )
for(每个文法符号 X)
求出 GO(I,X)的搜索符的自生集合和传播集合 ;
(3)为每个 LR(0)的核初始化自生搜索符 ;
(4) 当项目 [A→γ.Xδ,a]中的搜索符传播到核 L中的项目 C→X.η时,
将搜索符 a添入 C→X.η,a中
(5)重复 (4)直到再无新的搜索符添入为止。
例：构造文法 G’ 的 LALR分析表（用算法二）：
G’ [S’ ]：
(0)S’ →S (1)S→L=R (2)S→R (3)L→*R (4)L→i
(5)R→L
解,I0,S’ →.S,@ S→.L=R,@ S→.R,@ L→.*R,=/@
L→.i=/@ R→.L,@
I1,S’ →S.,@
I2,S→L.=R,@ R→L.,@
I3,S→R.,@
I4,L→*.R,@ R→.L,@ L→.*R,@ L→.i,@
I5,L→i.,@
I6,S→L=.R,@ R→.L,@ L→.*R,@ L→.i,@
I7,L→*R.,@
I8,R→L.,@
I9,S→L=R.,@
传播关系,
(I0,S?→.S,I1,S?→S,)
(I0,S?→.S,I2,S→L.=R)
(I0,S?→.S,I3,S→R,)
(I0,S?→.S,I4,L→*.R)
(I0,S?→.S,I5,L→i.)
(I2,S→L.=R,I6,S→L=.R)
(I4,L→*.R,I4,L→*.R)
(I4,L→*.R,I5,L→i.)
(I4,L→*.R,I7,L→*R.)
(I4,L→*.R,I8,R→L,)
(I6,S→L=.R,I4,L→*.R)
(I6,S→L=.R,I5,L→i.)
(I6,S→L=.R,I8,R→L,)
(I6,S→L=.R,I9,S→L=R.)
搜索符初始值 第一遍传播
I0,S’→.S # #
I1,S’→S,#
I2,S→L.=R #
I3,S→R,#
I4,L→*.R = =/#
I5,L→.i = =/#
I6,S→L=.R #
I7,L→*R,=/#
I8,R→L,=/#
I9,S→L=R,#
故有 GO函数：
GO（ I0,S） =I1,GO（ I0,L） =I2,GO（ I0,R） =I3,GO
（ I0,*） =I4,GO（ I0,i） =I5
GO（ I2,=） =I6，
GO（ I4,R） =I7,GO（ I4,L） =I8，
GO（ I4,*） =I4,GO（ I4,i） =I5
GO（ I5,R） =I9,GO（ I6,L） =I8,GO（ I6,*） =I4，
GO（ I6,i） =I5
则相应的 LALR分析表同前
4.2.6 二义性文法的应用任何二义性文法都不是 LR文法因为无论构造 SLR,LALR还是
LR分析表均有冲突。但二义性文法提供的说明往往要比一些非二义性文法要简单些，如表达式二义性文法：
G[E]:E→E+E|E*E|(E)|i和非二义性文法 G[E]:E→E+T|T
T→T*F|F F→ (E)|i 。事实上，虽然使用的文法是二义性的在加入一些其它的限制规则使对每个句子也只有一棵语法树，
这样，对整个语言说明仍然是无二义的,也就是也能用 LR分析考察文法,G[E]:E→E+E|E*E|(E)|i
构造 LR（ 0）项集：
I0=CLOSURE（ S?→·E） ={ S?→·E,E→·E+E,E→·E*E，
E→·(E),E→·i}
I1=CLOSURE（ S?→E·） ={ S?→E·,E→E·+T,E→E·*T }
I2=CLOSURE（ E→(·E)） ={E→(·E),E→·E+E,E→·E*E，
E→·(E),E→·i }
I3= CLOSURE（ F→i·） ={ F→i·}
I4= CLOSURE（ E→E+·E） ={ E→E+·E,E→·E+E,E→·E*E，
E→·(E),E→·i }
I5= CLOSURE（ E→E*·E） ={ E→E*·E,E→·E+E,E→·E*E，
E→·(E),E→·i }
I6= CLOSURE（ E→(E·),E→E·+E,E→E·*E） ={ E→(E·)，
E→E·+E,E→E·*E }
I7= CLOSURE（ E→E+E·,E→E·+E,E→E·*E） ={ E→E+E·，
E→E·+E,E→E·*E }
I8= CLOSURE（ E→E*E·,E→E·+E,E→E·*E） ={ E→E*E·，
E→E·+E,E→E·*E }
I9= CLOSURE（ E→(E)·） ={ E→(E)·}
而 FOLLOW（ S?） ={#}
FOLLOW（ E） ={+,*，）,#}
对于状态 I7，有项目 E→E+E·,E→E·+E,E→E·*E，对于归约项目 E→E+E·的 FOLLOW（ E） ={+,*，）,#}，面项目
E→E·+E和 E→E·*E为移入项即移入集为 {+,*}其交不为空，不是 SLR文法，当然如构造 LR（ 1）项目集也可说明它不是 LR
（ 1）文法。事实上，在栈顶是 E+E时，而下面的输入符号为 +
时，应前面的 +先做，即应先归约，在栈顶是 E+E时，而下面的输入符号为 *时，应先做 *，即为先移入。同样可以根据优先级和结合性来解决 I8的冲突问题。按这种方法构造出的分析表如下：
状态
ACTION GOTO
+ * （ ） i # E
0 S2 S3 1
1 S4 S5 acc
2 S2 S3 6
3 r4 r4 r4 r4
4 S2 S3 ７
5 S2 S3 ８
6 S4 S5 S9
7 r1 S5 r1 r1
8 r2 r2 r2 r2
9 r3 r3 r3 r3
可以看出这样的分析表比较简单。
考虑条件语句文法：
S?→S
S→iSeS|iS|a
它的状态集为,
I0=CLOSURE（ S?→·S） ={ S?→·S,S→·iSeS,S→·iS,S→·a}
I1=CLOSURE（ S?→E·） ={ S?→S·}
I2=CLOSURE（ S→i·SeS,S→i·S） ={ S→i·SeS,S→i·S,
S→·iSeS,S→·iS,S→·a }
I3=CLOSURE（ S→a·） ={ S→a·}
I4=CLOSURE（ S→iS·eS,S→i S·） ={ S→iS·eS,S→i S· }
I5=CLOSURE（ S→iSe·S） ={ S→iSe·S,S→·iSeS,S→·iS，
S→·a }
I6=CLOSURE（ S→iSeS·） ={ S→iSeS·}
对于状态 I4有移入项 S→iS·eS和归约项 S→i S·冲突；另外
follow(s)中有 e,又造成了 SLR冲突，根据一般原则删去了归约动作，其分析表如下：
状态
ACTION GOTO
i e a # S
0 S2 S3 1
1 acc
2 S2 S3 4
3 r3 r3
4 S5 r2
5 S2 S3 6
6 r1 r1
