编译原理讲义 (第五章:语法分析-- 自底向上分析技术) 编译原理讲义 (第五章:语法分析-- 自底向上分析技术) 南京大学计算机系 赵建华

概论 从输入符号出发，试图把它归约成识别符号。每一步都寻找特定得某个类型的短语（一般是简单短语）进行归约。 在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。 从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。

基本问题 如何找出进行直接归约的简单短语？ 将找到的简单短语归约到哪个非终结符号？

讨论前提 和自顶向下技术同样，不考虑符号的具体构成方式。 文法是压缩了的。 识别过程是从左到右，自底向上进行的。一般都采用规范归约：每一步都是对句柄进行归约（特例除外）。

基本方法 基本都采用移入-归约方法。 使用一个栈来存放归约得到的符号。 在分析的过程中，识别程序不断地移入符号。移入的符号暂时存放在一个栈中。一旦在栈中已经移入的（或者归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。

基本方法（续） 归约中的动作有4类 移入：读入一个符号并把它归约入栈。 归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。 接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。 当识别程序觉察出错误的时候，表明输入符号串不是句子。进行错误处理。

例子 文法G5.1[E]: E::=E+E|E*E|(E) 输入符号串：i*i+i 已处理符号 未处理符号 句型 句柄 规则 已处理符号 未处理符号 句型 句柄 规则 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

例子的解释 当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。 一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。将句柄出栈，然后将归约得到的非终结符号压栈。 如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。 在例子中，发现句柄和归约是人为干预的结果。所以移入-归约不是实际可运行的技术，而是技术的模板。

简单优先分析技术 基本思想： 每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。 S0…Sj-1SjSj+1Sj+2… …Si-1SiSi+1…Sn U

简单优先分析技术(基本思想续） 我们要通过两个相邻符号SiSi+1之间的关系来找到句柄： SiSi+1在句柄内：必然有规则U::=…SiSi+1… Si在句柄内部，但是Si+1在句柄之后：必然有规则U::=…Si，且存在规范句型…USi+1…。 如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型…SiU…，且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::=bMb M::=(L | a L::=Ma) 识别过程(例子) 文法: 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 ( M a ) b # < < < = = > 句柄: Ma) 归纳为L # b ( L b # < < = > 句柄: (L 归纳为M # b ( M a ) b # < < < = = > 句柄: Ma) 归纳为L # b ( L b # < < = > 句柄: (L 归纳为M # b M b # < = = > 句柄: bMb 归纳为Z

优先关系的定义 SjSi：当且仅当G中有规则U::=…SjSi… SjSi：当且仅当U::=…SjV…，且V HEAD+ Si； SjSi：当且仅当U::=…VW…，其中V和 W分别满足V TAIL+ Sj和W HEAD* Si且Si为终结符号。

HEAD和TAIL U TAIL+ S当且仅当U::=…U1，U1::=…U2，…，Un::= …S 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…Xn，都有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联接运算结果。 关系闭包：Sj R+ Si当且仅当Sj R Sj1, Sj1 R Sj2, …, Sjn R Si。其中可以要求对于任何k和l，Sjk != Sjl

关系闭包和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] } 对于外层循环，当i=K的循环结束的时候，满足：如果Si和Sj满足Si R Si1, Si1 R Si2, … Sin R Sj， 并且im<K, 那么现在 A[i,j] = 1;

使用矩阵计算优先关系 步骤1：构造优先关系矩阵B  步骤2：构造关系HEAD的矩阵BHEAD 步骤3：使用Warshall算法计算BHEAD+ 步骤4：计算 B BHEAD+

使用矩阵计算优先关系 步骤1：计算TAIL的布尔矩阵BTAIL 步骤2：计算BTAIL+，并将该矩阵转置得到(BTAIL+)T。 步骤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排列。 0100 0110 0000 0110 0000 BHEAD= BHEAD+= 0100 0110 0000 0010 0011 0000 (BTAIL+)T= BTAIL=

计算优先关系的例子(续) 0000 0011 1110 0110 0010 0001 B = B I+HEAD+= 0000 B =B BHEAD+= 0000 0011 B =(BTAIL+ ) TB BI+HEAD+=

优先关系的冲突 当优先矩阵中出现值不唯一的元素时，文法不适合使用优先识别技术来识别句型。

简单优先文法 定义5.2 如果某个文法满足： 那么称这个文法为简单优先文法。 第一点保证可以识别出句柄. 定义5.2 如果某个文法满足： 字汇表中的任意两个符号之间至多有一种优先关系成立。 任何两个重写规则的右部不相同。 那么称这个文法为简单优先文法。 第一点保证可以识别出句柄. 第二点保证可以确定归约到哪个非终结符号。

Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡Si-1≡Si≥Si+1 定理5.4 一个简单优先文法是无二义性的，且其任何一个句型Sm…Sn的唯一句柄是满足条件： Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡Si-1≡Si≥Si+1 的最左子符号串SjSj+1Sj+2… …Si-1Si。

Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡Si-1≡Si≥Si+1（句柄1） 定理5.4的证明 首先用反证法证明任何规范句型的句柄是唯一的。 句型必然有句柄，且这个句柄必然满足 Sj-1≤Sj≡Sj+1≡Sj+2≡… …≡Si-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…Sj-1SjSj+1Sj+2… …Si-1SiSi+1…Sn U

应用优先技术的困难与克服 简单优先技术只适应于简单优先文法。实际上，一般的程序设计语言的文法都不是简单优先文法。比如四则运算表达式的文法。 可能的解决办法是：分离法（成层法）

简单优先分析技术的实现 识别过程:从左到右地扫描输入符号。已经扫描或归约得到的符号被存放在一个栈中。 每次扫描的时候，将当前符号a和栈顶符号S相比较。如果S≥a表示已经碰到了一个句柄的尾。然后在栈里面向前（下）找，直到找到句柄的头。此时找到右部为该句柄的规则进行归约。

简单优先分析技术流程图 开始 初始化 R=下一个输入符号 否 把R入栈 栈顶Si≥R? 是 找出栈中第一个满足Sj-1≤Sj的值 A B

简单优先分析技术流程图(续) A B 寻找其右部和句柄匹配的规则 将句柄中的符号退去，将规则的左部入栈。 是 存在这样的规则 否 否 是句子？ 出错处理 是 停止

例子 1 #b ≤ ( aa)b# 移入 2 #b( a a)b# 3 #b(a ≥ )b# 归约 4 #b(M ≡ 5 #b(Ma ) 7 #b(L b # 8 #bM 9 #bMb 10 #Z 接受 (aa)b# 移入　 步骤 栈 关系 Next 余下部分 动作 6 #b(Ma)

优先函数 对于一个实际的程序设计语言的文法，优先矩阵将会非常大。对于有n个字汇的文法，矩阵的大小是nn 解决的方法是引入优先函数，将矩阵线性化。这里介绍的方法称为双线性优先函数法。

定义5.3 优先函数 对于某个优先矩阵M，如果存在两个函数f和g，它满足下列条件： 那么f和g称为M的线性优先函数。 注意： 如果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 ( ) 1 7 8 9 4 2 5 f g Z M L a b ( ) = > <

优先函数的例子 下面的矩阵没有优先函数 ≡ ≡ ≡ ≥

优先函数的构造（逐次加一法） 步骤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 f g 考虑关系≤ Z M L a b ( ) 1 2 f g

逐次加一法例子（例子） 考虑关系≥ Z M L a b ( ) 1 3 2 f g … … … … 最后结果 Z M L a b ( ) 1 4 2 f g

Bell有向图法 利用有向图构造优先函数。 基本思想： 用2n个点来表示fi和gi总共2n个值。 利用有向图的弧表示各个值之间应该具有的大小关系：从点a到点b有一个弧表示a代表的值不小于b。 优先函数通过计算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有向图的例子 f: M ) Z L a b ( g: 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)。 B≥≡ g (B ≤ ≡)T

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 ( L≥a, L≥b, a ≥a, a≥b, )≥a, ) ≥b b≤a, b≤(, (≤M, (≤a, (≤(

Martin算法例子 M ) Z L a b ( M≡a, M≡b, a ≡), b ≡M, (≡L 上面的图只给出了部分弧。 注意：对于≡，必须不断重复知道没有新的弧加入为止。

Martin算法的矩阵方法 I B ≡ 步骤1：构造布尔矩阵B≤≥。此时的矩阵相当于画图时的第一步得到的图。 B≤≥为： 0 B ≥ (B ≤ )T 0 步骤2：计算B=C+B≤≥。其中C为 I B ≡ (B ≡)T I 注释：点A到点B有一条弧 iff 有一个点C，使得A ≡ C且CB

Martin算法的矩阵方法 步骤3：计算B+。 步骤4：计算各个行中的1的个数。如果对于某个i， B[i][i]=1表示图存在回路，优先函数不存在。

Martin算法的正确性说明 在算法中，从节点A到节点B有弧表示优先关系要求A对应的优先函数值大于B对应的值。 如果Si ≡Sj，那么fi的后继同时也是gj的后继，gj的后继也是fi的后继。所以最后得到的Si和Sj的后继个数相同。 如果存在回路，那么表示优先关系要求某个函数值大于自己，显然不行。

优先函数的缺点 信息的丢失，原来两个符号之间有4中关系（大于，小于，等于，无关），引入优先函数之后，只有3种关系。 信息的丢失错误的延迟发现。 见P188页例子。

简单优先技术的局限性 文法的适用范围小。 虽然使用成层法可以使一些文法变成简单优先文法，但是 成层法的技术非常复杂。 当两个关系既有≤又有≥时，成层法无能为力。 如果使用高阶矩阵，将使得算法的内存需求更加大。

算符优先分析技术 简单优先技术对字汇表中的所有符号之间建立优先关系。但是，有些情况下，不需要对所有两个符号之间建立优先关系。 算符优先分析技术只在部分符号（终结符号）之间建立优先关系。

算符优先分析技术基本思想 对于算术表达式，只需要按照操作符之间的优先关系，就可以确定运算的顺序。不需要考虑操作数就可以对表达式进行分析。 例如：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…[Ni-1]Ti-1[Ni]Ti…[Nj]Tj[Nj+1]Tj+1…[Nk]Tk[Nk+1] 算符优先关系的直观意义 算符优先分析技术的基本思想是通过终结符号之间的优先关系，确定句型的句柄。 对于句型 [N1]T1…[Ni-1]Ti-1[Ni]Ti…[Nj]Tj[Nj+1]Tj+1…[Nk]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。 E + T Z F i * 短语有T+T*F+i，T+T*F，T*F，最左边的T，i。 其中，质短语为T*F，i。 T+T*F+i，T+T*F不是质短语，因为其中包含了T*F。 T不是质短语，因为其中没有终结符号。

[N1]T1…[Ni-1]Ti-1[Ni]Ti…[Nj]Tj[Nj+1]Tj+1…[Nk]Tk[Nk+1] 定理5.14 定理5.14：句型 [N1]T1…[Ni-1]Ti-1[Ni]Ti…[Nj]Tj[Nj+1]Tj+1…[Nk]Tk[Nk+1] 中满足关系Ti-1≮Ti ≈Ti+1≈…≈Tj≯Tj+1的最左子符号串[Ni]Ti…[Nj]Tj[Nj+1]就是句型的质短语。

句型识别过程 关系 质短语 符号 句型 1 # ≮i ≯+ i F i+(i+i)*i 2 # ≮+≮(≮i≯+ F+(i+i)*i 3 F+(F+i)*i 4 #≮+≮(≮+ ≯) F+F E F+(F+F)*i 5 #≮+≮(≈) ≯* (E) F+(E)*i 6 #≮+≮*≮i≯# F+F*i 7 #≮+≮*≯# F*F T F+F*F 8 #≮+≯# F+T Z

E + T * F ) ( i Z 识别得到的语法树 F Z + T * E i ) (

算符优先技术的说明 在算符优先技术的应用中，分析过程并不考虑非终结符号。可以认为：编译程序不考虑具体符号的名字，只考虑它的意义。 需要有处理质短语的语义处理子程序。 在使用算符优先技术的过程中，我们可以使用同一个符号N来表示归约得到的非终结符号，分析过程照样可以进行。

识别算法流程图 开始 i=1; S[i]=# R=Next Symbol N Y S[i]VT或S[i]=# j=i-1 j=i Y 否 i=i+1;S[i]=R A S[j]>R

识别算法流程图(续) A Q=S[j];j=j-1 N j=i-1 S[j]VT Y S[j]<Q N N 调用语义处理子程序,判断是否质短语? 出错处理 已经归约完成? Y 归约

语义处理子程序 语义处理子程序需要根据栈里面的符号（和其它信息）分析是否是一个质短语。 建议归约的时候，遵照以下法则： 对于质短语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)文法定义的上下文无关语言都能用一个确定的下推自动机以自底向上方式识别。

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驱动程序算法流程 开始 执行ACTION[TOP(S),y] 初始化 R:=下一个输入符号 y:=向前看k个符号 移入 接受 报错 归约

LR分析表例子 状态 i E + # ) * ( F T S5 1 S4 3 2 S6 acc r2 S7 r4 4 8 5 r6 6 9 S5 1 S4 3 2 S6 acc r2 S7 r4 4 8 5 r6 6 9 7 10 S11 r1 11 r5 r3

LR分析例子 步骤 栈 输入 动作 说明 1 i+i*i S5 移入i 2 0i5 +i*i r6 归约i 3 0F3 +i*i r4 i+i*i S5 移入i 2 0i5 +i*i r6 归约i 3 0F3 +i*i r4 归约F 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 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 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 →F或者T →T*F。 要把输入的头归约到T，首先要归约得到F。而得到F可以使用的规则为F →i，或者F →(E)。 现在，第一个符号为i。只有F →i可能归约这个符号。所以，第一次归约的规则为F →i。

LR(K)分析技术的思想(例子) 经过归约，第一个符号为F，得到句型F+i。此时，有可能进行归约的规则为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。 #U →u后继项集：项集中有U →u.项时，该项集对应于这个项的后继为：#U →u后继，简称为规约后继。 项集和项集闭包： 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的终止状态。

特征自动机的例子 # #Z::=E# 12 E 1 + T #E::=E+T 6 9 #E::=T #T::=T*F 2 F T * 7 1 + T #E::=E+T 6 9 #E::=T #T::=T*F 2 F T * 7 10 13 #T::=F F 3 #F::=(E) ) ( E 4 8 11 i #F::=i 5

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 0：初始项：Z →.E#；闭包：E →.aA E →.bB E_后继：1 a_后继：2 b_后继：3 1：Z→E.# #_后继：12 2：Z →a.A；闭包：A→.cA A→.d A_后继：4 c_后继：5 d_后继：6 3：E → b.B；闭包：B→.cB B →.d B_后继：7 a_后继：8 b_后继：9 4：E→aA. #E::=aA_后继：13 5：A →c.A；闭包：A→.cA A→.d A_后继：10 c_后继：5 d_后继：6

相应的CFSM E # #Z::=E# 1 12 a A #E::=aA 2 4 A #A::=cA c 5 10 d #A::=d 13 2 4 A #A::=cA c 5 10 d #A::=d 13 6 b B #E::=bB 3 7 #B::=cB B 8 11 c d #B::=d d 9

识别过程 步骤 栈 其余输入部分 accd# 1 0a2 ccd# 2 0a2c5 cd# 3 0a2c5c5 d# 4 0a2c5c5d6 accd# 1 0a2 ccd# 2 0a2c5 cd# 3 0a2c5c5 d# 4 0a2c5c5d6 # 5 0a2c5c5A10 # 6 0a2c5A10 # 7 0a2A4 # 8 0E1 #

SLR(K)文法 如果某个文法不是LR(0)的，它的特征自动机就存在不适定状态。 SLR(K)技术就是依靠简单向前看k的符号来确定是否进行归约。 我们要求掌握K=1的情况。

简单向前看1集合（示例） 2 #E::=T * 7 13 2’ 7’ 13’ {*} {+)#} #E::=T * 7 13

简单向前看1集合 定义5.25：一个简单向前看1集合是某些文法符号组成的集合，它和CFSM中的一个不适定状态的各个转换相关。 对于文法符号下的转换，X_转换的简单向前看1就是{X}。 对于#U::=u转换，简单向前看1集合F (U)就是FOLLOW(U)。其中FOLLOW(U)={T|T∈VT∪{#}, Z→…UT…}

简单向前看1集合(构造例子) 对于前面的CFSM，状态2是不适定状态，对于它的简单向前看1集合，存在两个转换：*_转换和#E::=T转换。 对于*_转换，简单向前看集合就是{*}。 对于#E::=T转换，简单向前看1集合就是FOLLOW(E)={(, + , #)}。

SLR(1)文法的定义 一个文法是SLR(1)的，当且仅当其CFSM的每个不适定状态的各个T_转换和#U::=u转换的简单向前看1集合不相交。

SLR(K)文法 对于CFSM中的不适定状态N，出自N的T_转换和#U::=u转换相关联的各个简单向前看K集合互不相交。 简单向前看K集合： 对于#U::=u转换，F(U)={x|Z=>*uUv, x是v的长度<=k的头符号串，且x∈(VT+{#})* 对于T转换，{Xv∈ VT* | X是到状态N的转换，v属于一个简单向前看k-1集合，这个集合和某个从N来的T_转换或#转换相关，T∈VT}

SLR(1)识别程序的构造(简单描述） 对于CFSM的修改：把不适定状态修改为向前看状态，使得对于每个在符号X下的状态从N到M的转换，以及从相联系的简单向前看1集合L，都存在有从N’到M’的一个转换，并且从M’到M就是原来的转换。 识别算法的修改：当栈顶符号为一个不适定状态的时候，算法查看下一个符号，从而确定进入哪一个状态（新状态不入栈）。然后由新的状态确定下一步的动作。

活前缀和有效项 活前缀：规范句型的一个头符号串，并且不包含句柄右部的任何符号。 比如：句型E+T*i+i的活前缀有E, E+T, E+T*, E+T*i。 E+T*i+不是活前缀，因为句柄为i，并且+在i的右面。

活前缀和有效项 LR识别过程中，栈里面的符号就是一个活前缀。栈里面的符号添加上适当的终结符号串就可以得到一个句型。 有效项：设有文法G[Z]的增广文法。如果存在一个Z’到uUv再到uu1u2v的规范推导，那么项U→u1.u2对于活前缀uu1是有效的。

CFSM和活前缀，有效项 定理5.16 对于一个活前缀r的有效项集合恰好是从初始状态出发，沿着CFSM中标号为r的路径到达的状态所对应的项集。 在使用LR系列识别文法的句子的时候，其栈顶状态中项主干部分（不包含向前看符号串）的集合就是其所有有效项的集合。

SLR(1)分析表的构造 如果分析表中有多值元素，那么该文法不是SLR(1)的。 步骤1：扩充成为增广文法。 步骤2：构造CFSM。首先构造项集规范族作为状态集合，然后构造状态之间的转换(GO函数)。 构造SLR(1)分析表： 如果有移入项U→u.av∈Si，且GO(Si,a)=Sj，那么 A [i,a] = Sj。 如果有归约项U→u ∈Si.，那么对于每个a∈F(U)，A [i,a]=rj。 如果Z’ →Z.# ∈Si，A[i,#]=acc。 GO(Sj,U)=Sj，那么G[i,U]=j 其余的为error。 如果分析表中有多值元素，那么该文法不是SLR(1)的。

例子5.29 G[10]：G::=E# E::=E+T E::=T T::=T*F T::=F F::=(E) F::=i 项集规范族 S0={Z→.E#, E→.E+T, E→.T, T→.T*F, T→.F, F→.(E),F→.i} S1={Z→E.#, E→E.+T} S2={E→T., T→T.*F} S3={T→F.} S4={F→(.E), E →.E+T, E→.T, T→.T*F, T→.F, F→.(E),F→.i} S5 ={F→i.} S6={E→E+.T, T→.T*F, T→.F, F→.(E),F→.i} S7={T→T*.F, F→.(E), F→i} S8={F→(E.), E→E.+T} S9={E→E+T., T→T.*F} … … … ...

例子5.29（续） GO(S0,E)=S1, GO(S0,T)=S2 GO(S0,F)=S3, GO(S0,( )=S4 GO(S0,i )=S5, GO(S1,+)=S6 GO(S2,*)=S7, GO(S4,E)=S8 GO(S4,T)=S2, GO(S4,F)=S3 GO(S4,( )=S4, GO(S4,i )=S5 GO(S6,T)=S9, GO(S6,F)=S3 GO(S6,( )=S4, GO(S6,i )=S5 GO(S7,F)=S10, GO(S7,( )=S4 GO(S7,i)=S5, GO(S8,))=S11 GO(S8,+)=S6, GO(S9,*)=S7

例子5.29（续） 构造分析表： 也可以不写出GO函数而直接构造分析表。 A[0,(]=S4, A[0,i]=S5 G[0,E]=1 G[0,T]=2 A[1,#]=acc A[2,+]=A[2,)]=A[2,#]=r2 A[3,+]=A[3,*]=A[3,)]=r4 … 也可以不写出GO函数而直接构造分析表。

LALR(K)分析技术 SLR(K)技术的优点在于：状态个数比较少。因此，分析表也比较小。因此，使用SLR(K)技术使用的内存比较小。 SLR(K)技术的能力比LR(K)技术弱。原因在于：简单向前看集合不考虑归约的上下文关系。

SLR(1)技术不能分析的例子 文法：1) S::= L=R 2)S::=R 3)L::=*R 4)L::=i 5)R::=L 0：Z →.S# 闭包：S→.L=R S→.R L→.*R L→.i R→.L S_后继: 1 ; L_后继 2; R_后继: 3; *_后继:4; i_后继:5; 1：Z →S.# #_后继:10 2：S→L.=R R → L. =_后继: 6 归约_后继 11 … … … … 6：S →L=.R 闭包：R →.L L →.*R L →.i … … … … … … 11：归约

SLR(1)技术不能分析的例子(续) 项集2显然是一个不适定状态。 而且，由于=∈F(R)，而且另外一个转换(=_转换)的简单向前看1符号集合也是{=}。因此，分析表A[2,=]中会有两个值。所以，这个文法不是SLR(1)文法。 而且，对于任意的K，这个文法不可能是SLR(K)文法。原因在于：S→L=R→*R=R。因此，不管往前面看多少个，=R对应的字的前K个符号在FOLLOWk(R)中，同时，它也在=_转换的简单向前看k集合中。

LALR技术 目标是得到一个比较好的分析表，使得它的状态比较少，但是有比SLR更加强大的分析能力。 显然，对于每个移入项，它的向前看符号集合是不变的。 SLR技术的缺点在于，它生成归约项的向前看符号集合的时候，不考虑上下文。假设某个LR(0)项集中有归约项U→u.，那么它对应的将u归约后的活前缀为…U。 在活前缀…U对应的规范句型中，可能允许跟在U后面的符号是在所有句型中跟在U后面的符号的子集。 因此，我们可以考虑求出这样的子集。从而减少归约项的向前看符号集合和其它的向前看符号集合之间的冲突可能性。这就是LALR技术。

非SLR文法例子的分析 在状态2中，有两个项S→L.=R和R→L.。 从这个图中，我们可以看到：对应于状态2的活前缀只有符号串L。 而按照项L →R.进行归约后，得到的活前缀为R。以R为活前缀时，其后只可能跟#。 而=根本不可能跟在活前缀R后面。 因此，我们发现，实际上，如果下一个符号为=时，相应的动作应该时移入。

LALR的基本步骤 首先生成LR(1)项集规范族。 根据这个项集族，得到分析表。

LR(1)项集规范族的例子 I0={[Z →.S,#], [S→.L=R, #], [S→.R,#], [L→.*R,=], [L→.i, =|#], [R→.L,#]} I1=GO(I0,S)={[Z→S.,#]} I2=GO(I0,L)={[S →L.=R, #],[R→L.,#]} I3=GO(I0,R)={[S →R.,#]} I4=GO(I0,*)={[S →*.R, =|#], [R→.L,=|#], [L→.*R, =|#], [L→.i,=|#]} … … … ... I11=GO(I6,*)={[S →*.R, #], [R→.L, #], [L→.*R, #], [L→.i, #]}

同心项集 对于两个LR(1)项集，如果除了搜索符（向前看符号）外，其它完全相同，那么这两个项集被成为同心项集。 同心项集的T_后即仍然是同心项集。 合并同心项集： 合并后的项集的基本部分保持不变。基本部分相同项的搜索符被合并。 原来的同心项集之间的转换关系依然不变。

同心项集合并的例子 转换关系为： I4和I11是同心项集。 I4 ={[L →*.R, =|#], [R→.L,=|#], [L→.*R, =|#], [L→.i,=|#]} I11{[L →*.R,#], [R→.L,#], [L→.*R, #], [L→.i, #]} 合并后为： I4’= {[L →*.R, =|#], [R→.L,=|#], [L→.*R, =|#], [L→.i,=|#]} 转换关系为： GO(I4’, R)=I7’(I7,I13合并后的同心项） GO(I4’,L)=I8’(I8,I10合并） GO(I4’,*)=I4’ GO(I4’,i) = I5’(I5和I12合并）

合并可能引起的冲突 合并引起的冲突是指：本来的LR(1)项集没有冲突，而合并同心项集后有冲突。 不可能引入归约-移入型冲突。 假定归约后的有移入_归约冲突，就是说：有项[U→u., a]和项[V→v.aw,b]。显然，原来的项集中都有[V→v.aw, ?]。而[U→u., a]必然在某个原来的项集中。这样，[U→u., a]所在的项集必然已经冲突了。 但是可能引起归约_归约冲突。

引入归约_归约冲突的例子 G5.13[S]: S::=aAd|bBd|aBe|bAe A::=c B::=c。 I58 ={[A →c.，de]，[B →c.，de]} 0:{[S→.aAd,#] [S →.bBd,#] [S →.aBe] [S →.bAe]} a_后继：1，b_后继：2 0:{[L→a.Ad,#] [S →a.Be] [A →.c,d][B →.c, e] } c_后继：5。 2:{ [L →b.Bd,#] [S →b.Ae] [A →.c,e][B →.c,d]} c_后继：8。 5:{[A →c.,d][B →c.,e]} 8:{[A →c.,e][B →c.,d]} 1 5 1 58 2 8 2

LALR分析表构造算法 构造增广文法。 构造LR(1)项集规范族C={I0,I1,I2,…In}。 合并同心项集，并用合并后的项集替代C，得到C’={J0,J1,…,Jn}。 查看C’中有没有冲突。如果有冲突，文法不是LALR(1)文法。 给J中的每个项集编号，作为状态。并建立分析表如下： [U→u.av,?] ∈ Ji，a∈Vt，Go[Ji,a]=Jj，A[i,a]=Sj [U→u.,a] ∈ Ji，a∈Vt，A[i,a]=rj [Z’→Z.,#]在Ji中，则A[i,#]=acc. 建立GOTO表。

LR(k)分析表的修改 由于LR文法不是二义性的，因此，任何二义性文法都不是LR文法，SLR文法或者LALR文法。 所以在相应的分析表中，必然有冲突项。 在适当的时候，我们可以修改这些冲突项目，来消除分析的‘二义性’。比如删除不适定状态中的某些项目，或者修改向前看符号集合。 修改某个状态的时候，必须理解该项集的意义。

LR(k)分析表的修改（续） 文法：Z::=E# E::=E+E E::=E*E E::=(E) E::=i 项集转换关系如下： 7 9 10 E + 1 2 3 4 5 6 8 ( i * ) 修改如下：在状态7，如果下一个符号为+，归约。否则移入。