第5章 自下而上语法分析方法

编译原理第5章自下而上语法分析方法安庆师范学院计算机与信息学院本章目标阐明自下而上语法分析的一般思想和面临的问题讨论自下而上分析的核心问题及其分析方法介绍短语、直接短语、句柄、素短语和最左素短语的概念及其求解方法介绍算符文法和算符优先文法的概念介绍FIRSTVT集和LASTVT集的含义及其构造方法阐述算符优先分析算法并探讨其局限性解释LR分析器的工作原理介绍LR(0)分析表、SLR分析表、LR(1)分析表、LALR分析表的构造方法简要介绍二义文法在LR分析中的应用概述语法分析器的自动产生工具教学内容5.1自下而上分析的一般思想和面临的问题5.2算符优先分析法5.3LR分析法5.4语法分析器的自动产生工具——YACC5.5本章小结5.1自下而上分析的一般思想和面临的问题归约和“移进-归约”分析法

1短语、句柄和最左素短语

2规范归约与规范推导

3语法分析栈的使用与语法树的表示

5自下而上分析的核心问题和分析方法

41、归约和“移进-归约”分析法（1）归约

所谓归约就是推导的逆过程。

若是一条产生式，则其中推导归约1、归约和“移进-归约”分析法（2）“移进—归约”分析法

我们所讨论的自下而上分析法是一种“移进-归约”法，其一般思想为：采用一个寄存符号的先进后出栈，称为分析栈，用来保存分析的历史信息和指示分析的下一步动作。分析时，从左至右扫描输入符号串，并将输入符号逐个移进分析栈中，边移进边分析，一旦栈顶出现可归约串（也就是栈的顶端符号串形成某个产生的右部）时，就将这个可归约串归约为相应产生式的左部，即把栈顶部构成可归约串的那个符号串用相应产生式的左部替代。接着，再检查栈的顶部是否又形成了新的可归约串，若是，则再进行归约，若未形成新的可归约串，则再从输入串中移进新的符号，如此继续下去，重复以上分析过程，即一边移进一边归约，直至输入串分析完毕，此时，若栈中只剩下文法的开始符号，则表明所分析的输入串是合法的，报告分析成功；否则，输入串是不合法的。1、归约和“移进-归约”分析法（3）算法流程

实际分析时，为了便于识别符号串，一般首先将“#”压入分析栈，当分析成功时，分析栈中只剩下文法的开始符号和“#”。这里，将“#”作为输入串的结束符，并非文法中的符号。1、归约和“移进-归约”分析法1、归约和“移进-归约”分析法（4）举例【例5.1】

设有文法：

给出输入串aabbbc的“移进-归约”分析过程。

1、归约和“移进-归约”分析法SABABa a b b b c #语法树ip#分析栈abaAAbcSBB返回2、短语、句柄和最左素短语（1）短语和直接短语 令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有 且则称β是句型ɑβδ相对于非终结符A的短语。 其中A∈VN，α，β，δ∈（VT∪VN）*。2、短语、句柄和最左素短语（1）短语和直接短语

特别地，如果有 且

则称β是句型ɑβδ相对于规则A→β的直接短语，也称为简单短语。【注意】

作为“短语”的两个条件均是不可缺少的。仅仅有，未必意味着β就是句型αβδ的一个短语。因为，还需要这一条件。2、短语、句柄和最左素短语（2）句柄 一个句型的最左直接短语称为该句型的句柄。（3）素短语 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。（4）最左素短语

最左素短语是指处于句型最左边的那个素短语。2、短语、句柄和最左素短语（5）通过语法分析树来寻找一个句型的短语、直接短语和句柄子树和简单子树 语法树的子树是由该树的某个结点（称为子树的根）及其所有分支构成的部分树称为原树的一棵子树。语法树的简单子树是只有单层分支的子树——这棵子树只有且必须有父子两代，没有第三代。2、短语、句柄和最左素短语（5）通过语法分析树来寻找一个句型的短语、直接短语和句柄

【结论】每个句型（句子）都对应一棵语法树。每棵语法树的叶子结点自左至右排列构成一个句型（句子）。每棵子树的叶子结点自左至右排列构成一个相对于子树根的短语。每棵简单子树的叶子结点自左至右排列构成一个直接短语。最左简单子树的叶子结点自左至右排列构成一个句柄。2、短语、句柄和最左素短语【例5.2】

文法：

计算句子i*(i+i)的所有短语、直接短语、句柄、素短语和最左素短语。解：为了加以区分，对句子i*(i+i)中的i加上下标，即i1*(i2+i3)，其语法分析树如右图所示。①短语：i1*(i2+i3)，i1，(i2+i3)，i2+i3，i2，i3②直接短语：i1，i2，i3③句柄：i1④素短语：i1，i2，i3⑤最左素短语：i1ETTF*Fi1E()E+TTFi2Fi3返回3、规范归约与规范推导（1）规范推导与规范句型

在形式语言中，最右推导通常被称为规范推导。由规范推导所得的句型称为规范句型。（2）规范归约 假定α是文法G的一个句子，如果序列 满足以下条件，则称这个序列是α的一个规范归约：αn=α；α0为文法的开始符号，即α0=S；对任何i，0<i≤n，αi-1是αi从经把句柄替换为相应产生式的左部符号而得到的。3、规范归约与规范推导

容易看出，规范归约是关于α的一个最右推导的逆过程。因此，规范归约也称为最左归约。如果文法G是无二义的，则规范推导和规范归约是一个互逆过程。（3）规范归约的实质 对于规范句型来说，句柄的后面不会出现非终结符号（即句柄的后面只能出现终结符）。基于这一点，可用句柄来刻画“移进-归约”过程中的“可归约串”。规范归约的实质 在移进过程中，当发现栈顶呈现句柄时就用相应产生式的左部符号进行替换。规范归约的中心问题 如何寻找或确定一个句型的句柄。3、规范归约与规范推导（4）修剪语法分析树寻找规范归约序列【方法】找出句子的一个推导，并画出语法树。将当前句型的句柄归约为相应产生式的左部，得到新的句型。剪去语法树的最左简单子树的叶子结点和分支，保留根结。重复步骤和，直至只剩下开始符号为止。3、规范归约与规范推导【例5.3】

设有文法：

试通过修剪语法树的方法来分析句子abbcde的规范归约过程。3、规范归约与规范推导SaBeAbdb规范推导：规范归约：Ac返回4、自下而上分析的核心问题和分析方法（1）引例

自下而上分析是一种“移进-归约”分析法，在移进的过程中一旦发现栈顶端出现“可归约串”，即进行“归约”。这里，我们认为可归约串即为某个产生式的右部。 例如，针对以下文法，分析输入串abbcde的“移进-归约”过程。4、自下而上分析的核心问题和分析方法语法树分析栈a b b c d e #ipA#abABSAbb和Ab都可以是可归约串，如何归约？方案一：按A→b进行归约。方案二：按A→Ab进行归约。AcdBe输入串已到“#”，而栈内并非“#S”，因此，分析失败！bAcdBeS分析成功！分析失败！4、自下而上分析的核心问题和分析方法（2）核心问题与分析方法

核心问题：如何寻找或界定“可归约串”？

最左素短语句柄自下而上分析方法什么是可归约串？算符优先分析法LR分析法规范归约非规范归约返回5、语法分析栈的使用与语法树的表示（1）“移进-归约”分析器基本构成

分析器一般由分析栈、分析表、分析程序和输入缓冲区组成。（2）分析器的结构模型分析程序分析栈输入串输出分析表一般情形初始时刻成功结束X1Xm#.....S5、语法分析栈的使用与语法树的表示（3）分析器的四种动作移进：将输入串的一个符号移进分析栈。归约：发现栈顶呈“可归约串”，并用适当的相应符号去替换这个串。接受：宣布最终分析成功，可看作是归约的一种特殊形式。报错：发现栈顶内容与输入串相悖，调用出错处理程序进行诊察和校正，并对栈顶内容和输入符号进行调整。（4）“移进-归约”分析法用栈实现的特点可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。栈内符号串与剩余输入串正好构成一个句型。（5）语法分析树的表示 具体实现时可以采用不同的数据结构，如“穿线表”方法。作业5.1习题五（P150）：1（1）至（6）34（3）返回5.2算符优先分析法

算符优先分析是一种分析过程比较迅速的自下而上的分析方法，特别适用于表达式的分析，易于手工实现。算符优先分析不是一种严格的最左归约，即不是一种规范归约方法。在算符优先分析方法中，可归约串就是最左素短语。 所谓算符优先就是借鉴了表达式运算不同优先顺序的概念，在终结符之间定义某种优先归约的关系，从而在句型中寻找可归约串。由于终结符关系的定义和普通算术表达式的算符（如加减乘除）运算的优先关系相似，所以得名算符优先分析方法。这种方法可以用于一大类上下文无关文法，GNUGCC中的Java编译器GCJ就采用了算符优先分析方法。5.2算符优先分析法算符文法和算符优先文法

1FIRSTVT集和LASTVT集

2算符优先关系表及优先函数

3算符优先分析中的出错处理

5算符优先分析算法及其特点

41、算符文法和算符优先文法（1）算符文法

如果一个文法G中的任何产生式的右部候选项都不含两个连续的非终结符，即不含形如

的产生式，其中，则称该文法为算符文法。 根据以上定义，算符文法的句型的一般形式显然可写成：

其中，；，可能出现也可能不出现。1、算符文法和算符优先文法（2）终结符之间的关系

在下面的定义中，a、b代表任意的终结符；P、Q、R代表任意非终结符；“…”代表由终结符和非终结符组成的任意序列，包括空串。 假定G是一个不含ε产生式的算符文法，对任意一对终结符a,b，我们定义：

a=b，当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；

a<b，当且仅当G中含有形如P→…aR…的产生式，而或；

a>b，当且仅当G中含有形如P→…Rb…的产生式，而或。1、算符文法和算符优先文法（2）终结符之间的关系

【注意】

=、<、>称为算符优先关系（简称为优先关系），它们表示算符文法G中任意两个终结符之间的关系，与非终结符无关。优先关系a=b表示a和b的归约优先关系相等，它们属于同一个可归约串，同时被某个非终结符替换掉；优先关系a<b表示a的归约优先级比b的要低，只有b所在符号串归约完之后，才能归约包含a的符号串；优先关系a>b则表示a的归约优先级比b的要高，在包含a的符号串归约完之后，才能归约包含b的符号串。1、算符文法和算符优先文法（2）终结符之间的关系

【注意】

算符优先关系是有序的，但不满足对称性和传递性，即对于文法G的终结符a、b和c：如果a<b，并不意味着b>a；如果存在a=b和b=c，不一定有b=a或a=c；如果存在a<b和b<c，也不能得出a<c。1、算符文法和算符优先文法（3）算符优先文法

如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三种关系之一：

=，>，<

则称G是一个算符优先文法。返回2、FIRSTVT集和LASTVT集（1）FIRSTVT(P)

对算符文法G的每个非终结符P，定义（2）集合FIRSTVT(P)的构造方法规则一：若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)；规则二：若a∈FIRSTVT(Q)且有产生式P→Q…，则a∈FIRSTVT(P)；规则三：反复使用以上两条规则，直到FIRSTVT(P)不再增大为止。2、FIRSTVT集和LASTVT集（3）LASTVT(P)

对算符文法G的每个非终结符P，定义（4）集合LASTVT(P)的构造方法规则一：若有产生式P→…a或P→…aQ，则a∈LASTVT(P)；规则二：若a∈LASTVT(Q)且有产生式P→…Q，则a∈LASTVT(P)；规则三：反复使用以上两条规则，直到LASTVT(P)不再增大为止。2、FIRSTVT集和LASTVT集【例5.4】

构造以下文法的所有非终结符的FIRSTVT集和LASTVT集。（i+*↑（i↑（i*↑（i）i+*）i↑）i*↑）i↑2、FIRSTVT集和LASTVT集（5）构造FIRSTVT(P)的形式化算法描述数据结构二维布尔数组F[P,a]：F[P,a]=true，当且仅当a∈FIRSTVT(P)。栈STACK：压入符号对(P，a)，当且仅当F[P,a]=true。所有终结符所有非终结符数组值为真假，为真的条件是，a∈FIRSTVT(P)2、FIRSTVT集和LASTVT集（5）构造FIRSTVT(P)的形式化算法描述基本做法按规则一对每个数组元素F[P,a]赋初值。应用第二条规则修改数组F的元素值，其修改方法如下：将所有初值为真的数组元素F[P,a]的符号对(P，a)全部压入STACK之中。如果栈STACK不空，就将栈顶项弹出，记此项为(Q，a)。对每个形如P→Q…的产生式，若F[P,a]为假，则将其值变为真且将(P，a)压入STACK栈。重复步骤，直至STACK栈为空为止。从最终所得二维数组F中可得到任何非终结符P的FIRSTVT集，即2、FIRSTVT集和LASTVT集（5）构造FIRSTVT(P)的形式化算法描述形式化算法描述voidFIRSTVT(P)//计算非终结符P的FIRSTVT集{for(每个非终结符P和终结符a){ F[P,a]=FALSE; }for(每个形如P→a…或P→Qa…的产生式){ Insert(P,a); }while(!StackEmpty())//栈STACK非空{ Pop(Q,a); for(每条形如P→Q…的产生式) { Insert(P,a); }}}对数组初始化应用规则一应用规则二voidInsert(P,a){

if(F[P,a]==FALSE)

{

F[P,a]=TRUE;

Push(P,a);

}}2、FIRSTVT集和LASTVT集（5）构造FIRSTVT(P)的形式化算法描述例如，求以下文法各非终结符的FIRSTVT集：111100000000000111T，*E，+F，(F，iT，i11T，(返回3、算符优先关系表及优先函数（1）算符优先关系表

为方便比较算符文法中各终结符对之间的优先关系，最简单的办法是先将各种可能相继出现的终结符的优先关系计算出来，并将其表示成一个矩阵形式，在分析过程中通过查询矩阵元素而获得终结符间的优先关系，这个矩阵称为算符优先关系表。所有终结符所有终结符矩阵值为>、<、=或为空白3、算符优先关系表及优先函数（2）算符优先关系表的构造方法

利用文法G中的每个非终结符P的FIRSTVT集和LASTVT集，我们就能方便地构造文法G的算符优先关系表，其构造方法如下： 规则一：对形如P→…ab…或P→…aQb…的产生式，有a=b；

规则二：对形如P→…aR…的产生式，若有b∈FIRSTVT(R)，则a<b；

规则三：对形如P→…Rb…的产生式，若有a∈LASTVT(R)，则a>b；

规则四：对于语句括号#，有#=#，且若a∈FIRSTVT(S)和b∈LASTVT(S)，则有#<a且b>#。3、算符优先关系表及优先函数（2）算符优先关系表的构造方法形式化算法描述voidOPRT()//构造文法G的算符优先关系表{ for(每条产生式P→X1X2…Xn) for(i=1;i<=n-1;i++) { if(Xi∈VT&&Xi+1∈VT)置Xi=Xi+1 if(i<=n-2&&Xi∈VT&&Xi+2∈VT&&Xi+1∈VN)置Xi=Xi+2 if(Xi∈VT&&Xi+1∈VN) for(每个a∈FIRSTVT(Xi+1))置Xi<a if(Xi∈VN&&Xi+1∈VT) for(每个a∈LASTVT(Xi))置a>Xi+1 }}3、算符优先关系表及优先函数（2）算符优先关系表的构造方法

【注意】

在以上算法描述中，为了能够计算#与其它终结符之间的关系，一般在文法的产生式中添加一个新的产生式

其中，且。 按照以上方法构造出来的算符优先关系表中的每一项，若至多只有一种关系，则文法G是算符优先文法。3、算符优先关系表及优先函数【例5.5】

构造文法G[E]的算符优先关系表。><=>>>><<<>>>><<<>><<<<<<<<>>>>><<<<<>>>>>=3、算符优先关系表及优先函数（3）优先函数

把每个终结符a与两个自然数f(a)和g(a)相对应，若根据一个文法的算符优先关系表，使得文法中每个终结符a和b满足下述条件:若存在a=b，则有f(a)=g(b)；若存在a>b，则有f(a)＞g(b)；若存在a<b，则有f(a)＜g(b)。 则称f和g为优先函数，其中，f称为入栈优先函数，g称为比较优先函数。3、算符优先关系表及优先函数（3）优先函数【注意】

对应一个优先关系表的优先函数f和g不唯一，只要存在一对，就存在无穷多对。也有许多优先关系表不存在对应的优先函数。 例如，以下优先关系表不存在优先函数。优先表中若存在f和g,则有 f(a)=g(a); f(a)＞g(b) f(b)=g(a); f(b)=g(b)这将导致如下矛盾: f(a)＞g(b)=f(b)=g(a)=f(a)3、算符优先关系表及优先函数（3）优先函数使用优先函数的好处节省空间；便于进行比较运算。使用优先函数的缺陷 原先不存在优先关系的两个终结符，由于与自然数相对应，变成可比较的了。因而，可能会掩盖输入串中的某些错误。但是，我们可以通过检查栈顶符号和输入符号的具体内容来发现那些不可比较的情形。3、算符优先关系表及优先函数（4）Bell方法构造优先函数

如果优先函数存在，则可以利用有向图来构造优先函数，这种方法称为Bell方法。其具体步骤如下： ①对每个终结符a（包括“#”）,令其对应两个符号fa和ga, 画一张以所有符号fa和ga为结点的方向图：若a>b或a=b，画一条从fa到gb的有向边;若a<b或a=b，画一条从gb到fa的有向边;fafbgagbab>或=<或=3、算符优先关系表及优先函数（4）Bell方法构造优先函数 ②对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点（包括出发结点自身）的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)； ③检查所构造的函数f和g，看它们同原来的关系表是否有矛盾。若没有矛盾，则f和g就是所求的优先函数；若有矛盾，则不存在优先函数。3、算符优先关系表及优先函数【例5.6】

求下述优先关系表的优先函数（不含“#”）。3、算符优先关系表及优先函数f＋f*fif)g＋g*gig(g)f( 解:①用Bell法构造的优先关系图如下:3、算符优先关系表及优先函数

②由上图求得优先函数如下:返回4、算符优先分析算法及其特点（1）定理

算符优先分析法是一种自下而上分析法，在其“移进-归约”过程中，以最左素短语来刻画“可归约串”，即在分析过程中一旦发现栈顶端出现当前句型的最左素短语，就立即采取归约动作。那么，算符优先分析器在分析过程中是如何识别最左素短语的呢？这主要基于以下定理：

定理5.1一个算符优先文法G的任何句型#N1a1N2a2…NmamNm+1#的最左素短语是满足如下条件的最左子串：Njaj…NiaiNi+1:（其中,ai是终结符,Ni是可有可无的非终结符）aj-1<ajaj=aj+1，aj+1=aj+2，…，ai-1=aiai>ai+14、算符优先分析算法及其特点（1）定理句型的一般形式

最左边： 中间： 最右边：

算符优先文法G的句型中的可归约串就是最左素短语。该定理说明了最左素短语与周围符号之间的关系。最左素短语4、算符优先分析算法及其特点（2）算符优先分析过程句型的一般形式分析的关键问题 寻找最左素短语（可归约串）。处理方法 从左向右扫描各符号，依次查看算符优先关系表，直至找到满足ai>ai+1的终结符为止，一直移进。再从ai开始往左扫描，直至找到满足关系aj-1<aj的终结符为止，进行归约。4、算符优先分析算法及其特点（3）算符优先分析算法数据结构符号栈S：寄存终结符和非终结符。k：代表符号栈S的使用深度S[k]：表示当前栈顶元素S[j]：表示栈顶端的终结符a：存储最新读入的输入符号S12…k-1k深度为k栈顶元素若S[k]∈VT,则S[j]=S[K]aiNi若S[k]∈VN,则S[j]=S[K-1]4、算符优先分析算法及其特点k=1;S[k]='#';//k代表栈S的使用深度do{ Read(a);//把下一个输入符号读入a中 if(S[k]∈VT)j=k;//j表示栈顶终结符位置 elsej=k-1;/*任何两终结符之间最多只有一个非终结符，故若S[k]∈VN，则S[k-1]∈VT*/ while(S[j]>a){//栈顶端已出现最左素短语，栈顶符号为其尾部 do{//自栈顶向栈底方向找出最左子串S[i]<S[i+1]…S[j]>a Q=S[j]; if(S[j-1]∈VT)j=j-1;//j从最左素短语末逐步移向首 elsej=j-2; }while(S[j]=Q);//S[j]<Q时表明找到了最左素短语的首部 把S[j+1]…S[k]归约为某个N;//S[j+1]…S[k]为最左素短语 k=j+1; S[k]=N;//将归约后的非终结符N置于原S[j+1]位置 } if((S[j]<a)||(S[j]=a)){//若栈顶S[j]<a或S[j]=a，则将a压栈 k=k+1; S[k]=a; } elseerror();//调用出错诊察程序

}while(a!='#');4、算符优先分析算法及其特点【注意】上述算法的工作过程中，若出现j减1后的值小于或等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现#N#。在上述算法中，当发现并找到最左素短语时，我们并未指出将其归约为哪一个非终结符号‘N’。实际上，我们在文法中寻找这样的产生式，它的右部形如:

其中每个终结符号与最左素短语对应位置上的终结符号完全相同，而每一个非终结符号Pk应与相应位置上的非终结符号Nk相对应，不必完全相同。

4、算符优先分析算法及其特点【例5.7】有文法：试构造句子i*i+i的算符优先分析过程。解题步骤计算所有非终结符的FIRSTVT集和LASTVT集构造算符优先关系表构造输入串的算符优先分析过程4、算符优先分析算法及其特点NNNNi*i+i#语法树ipN#1234kij1234QS[j]#i<N**#iiN++i成功结束S4、算符优先分析算法及其特点（4）算符优先分析的特点

对例5.7的文法的句子i*i+i的规范归约语法树和算符优先分析所得的语法树进行比较，可得以下结论：规范归约语法树算符优先语法树算符优先分析一般并不等价于规范归约并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了所有的单非产生式。可能将本来不是句子的输入串误认为是句子。返回5、算符优先分析中的出错处理（1）错误发生的情形

使用算符优先分析法时，可在以下两种情况下发现语法错误：栈顶终结符号与下一输入符号之间不存在任何优先关系；找到某一最左素短语，但不存在任一产生式，其右部与此最左素短语相匹配。（2）处理方法

在优先矩阵中的每一空项中，可填入指示器，指向处理该项错误的子程序。不同的空项可填同一指示器，也就是运用同样的错误处理方法。错误一处理方式：通过改变、插入或删除符号来使得栈顶符号和输入符号之间存在优先关系。错误二处理方式：打印错误信息，并确定该最左素短语与哪个产生式的右部最为相似。实验三语法分析器设计之二——算符优先分析程序（1）实验目的和要求理解自下而上分析算法的构造思想。理解算符文法和算符优先文法的概念。掌握FIRSTVT集、LASTVT集和算符优先关系表的构造方法。理解素短语和最左素短语的概念，并掌握其寻求方法。理解算符优先分析算法，能够使用某种高级语言实现一个算符优先分析程序。（2）实验内容

编写一个算符优先分析程序，能实现以下功能：输入文法，判断是否为算符文法；构造并输出该文法的每个非终结符的FIRSTVT集和LASTVT集；构造并输出算符优先分析表，判断是否为算符优先文法，若不是提示无法进行分析；任意输入一个输入串，可得到成功的分析或错误的提示，输出其分析过程或打印语法分析树。作业5.2习题五（P151）：56返回5.3LR分析法二义文法在LR分析中的应用

6LALR(1)分析器

5LR分析中的出错处理

7LR分析器的工作原理

1LR(0)分析器

2SLR(1)分析器

3LR(1)分析器

41、LR分析器的工作原理（1）LR分析法的基本思想

LR分析法的基本思想可以用12个字来概括：记住历史、展望未来、定夺现在。 在规范归约过程中，一方面记住已移进和归约的整个符号串，即记住“历史”；另一方面根据所用产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈栈顶时，根据“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成LR总控程序分析栈输入串分析表输出1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成分析栈 一个LR分析器实际上是一个带有先进后出栈的确定有限自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放这些状态，它们概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。状态栈：(S0,#)为预先放到栈中的初始状态和符号。符号栈：X1X2…Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成分析表

LR分析表是LR分析器的核心部分。

LR分析表由ACTION表和GOTO表构成。ACTION表：动作表，也称为动作函数GOTO表：状态转换表，也称为状态转换函数VT+#VNACTION[Si,aj]为一动作，表示当前状态Si面临输入符号aj时所完成的分析动作。GOTO[Si,Xj]为一状态，表示当前状态Si面临文法符号Xj时需转移的下一个状态。1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成分析动作

ACTION表中的元素ACTION[Si,aj]是一个动作，表示当前状态Si面临输入符号aj时所完成的分析动作。分析动作可分四类：移进：将下一状态Sk（Sk=GOTO[Si，aj]）和现行输入符号aj移进分析栈，下一输入符号aj+1变成现行输入符号。移进动作表示当前栈顶端符号串尚未形成句柄，正期待继续移进符号以形成句柄。Skajip1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成归约：指用某一个产生式A→β进行归约。假若β的长度为L（L=|β|），则归约的动作是去掉栈顶的L个项，即若当前栈顶状态为Sm，则将状态Sm-L变成栈顶状态，然后将状态Sk（Sk=GOTO[Sm-L，A]）和文法符号A（A∈VN）移进分析栈。归约动作不改变现行输入符号，执行归约动作意味着呈现于栈顶的符号串Xm-L+1…Xm（β=Xm-L+1…Xm）是一个相对于A的句柄。Xm…Sm-L+1Xm-L+1…SmAA→Xm-L+1…Xm为句柄SK1、LR分析器的工作原理（2）LR分析器的逻辑模型及其组成接受：宣布分析成功，停止分析器的工作。报错：发现源程序含有错误，调用出错处理程序进行处理。1、LR分析器的工作原理

相关约定用Sk的下标k表示状态s表示执行移进动作6=GOTO[1,+]，表示下一状态s6表示将(6,+)移进分析栈r表示执行归约动作2表示产生式编号r2表示按第2个产生式进行归约acc表示接受空白表示出错表示状态，即

GOTO[0,E]=11、LR分析器的工作原理总控程序 LR分析器的总控程序本身的工作十分简单，它的任何一步只需根据分析栈的栈顶状态s和现行输入符号a去执行所规定的动作即可。初始化：将（0，#）压入分析栈从输入串中读入当前的输入符号ai，根据当前状态栈栈顶状态m与输入符号ai查ACTION表：若ACTION[m,ai]=‘sj’，完成移进动作；若ACTION[m,ai]=‘rj’，以文法的第j条规则完成归约动作；若ACTION[m,ai]=‘acc’，分析成功，结束；若ACTION[m,ai]=‘error’，出错处理。重复②直到出错或接受为止。1、LR分析器的工作原理（3）LR分析器的工作过程 用三元式（状态栈，符号栈，输入串）表示分析过程中状态栈，符号栈，输入符号的变化。初始时刻：将初始状态0和#移进分析栈。三元式为：(0, #, a1a2…an#)接受时刻：(01 ,#S ,#)任一时刻：(01…m, #X1X2…Xm, aiai+1…an#)分析器的下一步动作是由栈顶状态m和当前面临的输入符号ai唯一确定的。1、LR分析器的工作原理（3）LR分析器的工作过程任一时刻的移进归约过程：(01…m, #X1X2…Xm, aiai+1…an#)查ACTION[Sm,ai]=?="sj"：移进（j，ai）(01…mj, #X1X2…Xmai, ai+1…an#)="rj"：按第j个产生式（A→Xm-L+1…Xm）归约，k=GOTO[m-L，ai](01…m-Lk, #X1X2…Xm-LA, ai…an#)=“acc”：分析成功，终止分析。三元式不再变化。(01, #S, #)=“error”或空白：则三元式的变化过程终止，报告错误。 一个LR分析器的工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。1、LR分析器的工作原理（4）LR分析器的分析流程及分析算法1、LR分析器的工作原理（4）LR分析器的分析流程及分析算法相关变量和过程说明SymbolStack数组为符号栈StateStack数组为状态栈k为栈的使用深度a存放当前读入的输入符号GetNextSymbol过程为将当前输入符号指针所指符号读入变量a中，并将输入指针指向下一个输入符号。ERROR为出错处理程序。1、LR分析器的工作原理voidLR_Analyze(){//LR分析算法k=1;StateStack[k]=0;SymbolStack[k]=#;//初始化，将初态0和#分别移进状态栈和符号栈a=GetNextSymbol();//将下一个输入符号读进a中;while(true){ s=StateStack[k];//s为当前状态栈栈顶状态 if(ACTION[s,a]=="sj"){//sj意味着执行移进动作

k=k+1;StateStack[k]=j;SymbolStack[k]=a;//将状态j和符号a分别移进状态栈和符号栈 a=GetNextSymbol();//将下一个输入符号读进a中; } elseif(ACTION[s,a]=="rj"){//rj意味着执行归约动作,第j个产生式为A→α，其中|α|=L， k=k-L;//状态栈和符号栈分别弹出L个符号 tateStack[k];//s为当前状态栈栈顶状态 S'=GOTO[S,A];k=k+1;StateStack[k]=S';SymbolStack[k]=A;//将S'和A分别移进状态栈和符号栈 } elseif(ACTION[s,a]=="acc")//acc意味着分析成功 return;//结束分析过程 else//ACTION[s,a]为空白或出错标志 ERROR();//调用出错处理程序进行处理}}1、LR分析器的工作原理【例5.10】

根据下述文法G[E]及其LR分析表，分析输入串i*i+i的LR分析过程。1、LR分析器的工作原理EE+TTT*FFiiFiip语法树0#5i1F3T27*i5F10E16+5iF3T9成功结束1、LR分析器的工作原理（5）LR文法 对于一个文法，如果能够构造一张LR分析表，使得它的每个入口均是唯一确定的，则称这个文法为LR文法。 一般而言，一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。但对多数的程序语言来说，k=0或1就足够了。因此，我们只考虑k≤1的情形。【结论】LR文法肯定是无二义的，一个二义文法决不会是LR文法。但是，LR分析技术可以进行适当修改以适用于分析一定的二义文法。存在不是LR的上下文无关文法。对于一个LR文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对其实行归约。LR分析法比预测分析法更加一般化。1、LR分析器的工作原理LR分析表是LR分析器的核心，主要有以下几种分析表：LR(0)表：局限性极大，是建立其它LR分析表的基础。SLR(1)表（即简单LR表）：比较容易实现又极有使用价值。LR(1)表（即规范LR表）：能力最强，适用于大多数上下文无关文法，但分析表体积庞大。LALR表（即向前LR表）：能力介于SLR(1)表和LR(1)表之间 应该指出，LR分析器分析时，不论采用上述哪一种分析表，其分析算法都是一样的，即其总控程序都是一样地工作。习惯上，我们说使用LR(0)表的分析器为LR(0)分析器，使用SLR(1)表的分析器为SLR(1)分析器，使用LR(1)表的分析器为LR(1)分析器，使用LALR表的分析器为LALR分析器。返回2、LR(0)分析器 我们希望仅由一种只概括“历史”资料而不包含推测性“展望”材料的简单状态就能识别呈现在栈顶的某些句柄。LR(0)分析法即是基于只根据“历史”资料即可决定当前分析栈是否已构成句柄，从而确定分析动作。（1）LR(0)分析器的实现原理前缀、活前缀与可归前缀字的前缀是指该字的任意首部。 如：字abc的前缀有ε、a、ab或abc。所谓活前缀是指规范句型的一个前缀，且这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些符号之后，就可以使它成为一个规范句型。2、LR(0)分析器

也就是说，若 是文法G的一个规范推导，并且符号串γ是αβ的前缀，则称γ是G的一个活前缀，即γ是规范句型αβω的一个前缀，但它的右端不超过该句型句柄β的末端。在LR分析中，实际上是把αβ的前缀放在符号栈中，一旦在栈中出现αβ，即形成句柄β，就用产生式A→β归约。2、LR(0)分析器活前缀与句柄间的三种关系：活前缀中已含有句柄的全部符号，这是一个特殊的活前缀，是当前句型的最长活前缀，通常称为可归前缀。活前缀中只含有句柄的一部分符号。活前缀中不包含句柄的任何符号。 对于一个文法G，我们可以构造一个有限自动机来识别G的所有活前缀，然后，我们再讨论如何把这种自动机转变成LR分析表。意味着期望从余留输入串中看到某一产生式A→α中的α符号串。意味着形如A→β1β2的产生式右部的左子串β1已出现在栈顶，正期待着从余留输入串中看到由β2推出的符号串。表明句柄β已出现在栈顶，分析动作应是用产生式A→β进行归约。2、LR(0)分析器LR(0)项目在文法G的每个产生式的右部适当位置添加一个圆点称为G的一个LR(0)项目。 例如，产生式对应有四个项目：若干个项目组成的集合称为项目集。例如：对于左边产生式的4个项目即构成一个项目集。2、LR(0)分析器

【注意】产生式只对应一个项目。从直观意义上讲，一个LR(0)项目指明了在分析过程中的某个产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。2、LR(0)分析器四类不同的项目 不同的LR(0)项目反映了分析栈的不同情况。我们根据LR(0)项目的作用不同，将其分为4类：2、LR(0)分析器【例5.11】

构造以下文法的所有LR(0)项目，并指出每个项目的类型。解：归约项目：(2)(5)(7)接受项目：(2)移进项目：(3)(6) 待约项目：(1)(4) 2、LR(0)分析器从LR(0)项目构造识别文法G的所有可归前缀的有限自动机 可以使用LR(0)项目作为状态构造一个NFA，用来识别这个文法的所有活前缀。其步骤如下：令S是文法G的开始符号，向文法加入一个产生式S΄→S，S΄为新的文法的开始符号。然后，令项目S΄→•S为NFA的唯一初态。令所有LR(0)项目分别对应NFA的一个状态，且LR(0)项目是归约项目的对应状态为终态。若状态i和状态j出自文法G的同一产生式且这两个状态的LR(0)项目的圆点只相差—个位置，即：若则从状态i引一条标记为Xi的弧到状态j。若Xi∈VN

，则从状态i引ε弧到所有Xi→•α的状态。

再使用第三章的方法将NFA确定化、最小化，得到一个识别该文法的最小化DFA。ij2、LR(0)分析器（2）LR(0)项目集规范族的构造 构成识别一个文法G可归前缀的最小化DFA项目集（状态）的全体称为文法G的LR(0)项目集规范族。其构造方法如下：拓广文法 文法G是一个以S为开始符号的文法，拓广G为G΄（包含整个G），增加一个不出现在G中的非终结符S΄，并加进一个新产生式S΄→S。S΄为G΄的开始符号，称G΄为G的拓广文法。定义和构造I的闭包

假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)的方法是：I中的任何项目都属于CLOSURE(I)；若A→α•Bβ（B∈VN）属于CLOSURE(I)，那么，对任何关于B的产生式B→γ，项目B→•γ也属于CLOSURE(I)；重复执行上述两步骤直至CLOSURE(I)不再增大为止。2、LR(0)分析器

例如，对于文法：若则2、LR(0)分析器GO函数（状态转换函数） 假设I是一个项目集，X是文法G的一个文法符号，则定义状态转换函数GO(I,X)如下：GO(I,X)=CLOSURE(J)其中J={任何形如A→αX•β的项目|A→α•Xβ属于I}

例如，对于文法： 设 则2、LR(0)分析器LR(0)项目集规范族的构造 通过函数CLOSURE和GO很容易构造一个文法的拓广文法的LR(0)项目集规范族C，步骤如下：

Step1：初始化：令C=CLOSURE({S΄→•S})；

Step2：对C中每一个项目集I和文法中任意文法符号X应用状态转换函数GO(I,X)，得到新的项目集J，若J非空且不在C中，则将其加入到C中；

Step3：重复Step2直到C不再增大为止。2、LR(0)分析器LR(0)项目集规范族的构造 为了能够有效地使用以上步骤计算LR(0)项目集规范族C，我们借助一个项目栈来存储构造过程中加入的每一个新的项目集，计算的每一步是先将栈顶项弹出，记为I，然后对文法中每个文法符号X，如果GO(I,X)非空且不属于C中，则将GO(I,X)加入到C中，并将其压入栈中，重复以上过程，直到栈空为止。形式化算法描述如下：2、LR(0)分析器形式化算法描述

voidItemSets(Gʹ){//计算文法的项目集规范族C I=CLOSURE({Sʹ→•S}); C={I}; //初始规范族C Push(I); //将项目集I压入栈中 while(!Empty(ItemStack)){ //只要栈不空就执行以下步骤 Pop(I); //将当前栈顶项目集弹出并置于I中 for(G中每个文法符号X){ J=GO(I,X);//计算GO函数 if(J非空且J不属于C中){ 将J加入到C中; Push(J);//将项目集J压入栈中 } } }}2、LR(0)分析器LR(0)分析表的构造“移进-归约”冲突和“归约-归约”冲突若同时存在移进项目和归约项目，即有形如A→α•aβ和B→γ•的项目，则称文法G含有移进-归约冲突。此时，当面临输入符号a时，分析程序的控制器不能确定是把a移进符号栈还是把γ归约成B。若同时存在一个以上的归约项目，即有形如A→ω•和B→γ•的项目，则称文法G含有归约-归约冲突。此时，不论面临什么样的输入符号，分析程序的控制器不能确定是把ω归约成A，还是把归γ约成B。 若一个文法G的拓广文法G΄的识别可归前缀的DFA的每一个状态（项目集）不存在任何冲突，即不存在移进-归约冲突和归约-归约冲突，则称G是一个LR(0)文法。2、LR(0)分析器LR(0)分析表的构造

假定C={I0,I1,…,In}，由于我们已经习惯用数字表示状态，因此，令每个项目集Ik的下标k作为分析器的状态。特别地，令那个包含项目S΄→•S的集合Ik的下标k为分析器的初态。分析表的ACTION子表和GOTO子表可按如下方法构造： 规则一：若项目A→α•aβ（a∈VT）属于Ik且GO(Ik,a)=Ij，则置ACTION[k,a]=sj，表示将(j,a)移进分析栈。 规则二：若项目A→α•属于Ik，且文法G΄中产生式A→α的编号为j，则对任何终结符a（包括输入串结束符#），置ACTION[k,a]=rj，表示按文法的第j个产生式（A→α）进行归约。 规则三：若项目S΄→S•属于Ik，则置ACTION[k,#]=acc，表示“接受”。 规则四：若GO(Ik,A)=Ij，A∈VN，则置GOTO[k,A]=j。 规则五：分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。2、LR(0)分析器 由于假定LR(0)文法规范族的每个项目集不含任何冲突项目，因此按上述方法构造的分析表的每个入口都是唯一的（即不含多重定义）。我们称如此构造的分析表是一张LR(0)表。使用LR(0)表的分析器叫做一个LR(0)分析器。【例5.12】

设文法G[S]为：试构造文法G[S]的LR(0)分析表。2、LR(0)分析器解：(1)拓广文法：将G[S]拓广为G[S΄]，并对各产生式进行编号：S΄→SS→aAS→bBA→cAA→dB→dBB→e2、LR(0)分析器(2)构造LR(0)项目集规范族C和GO函数:I0:S΄→•SS→•aAS→•bBI1:S΄→S•I2:S→a•AA→•cAA→•dI3:S→b•BB→•dBB→•eI4:S→aA•I5:A→c•AA→•cAA→•dI10:A→cA•I6:A→d•I7:S→bB•I8:B→d•BB→•dBB→•eI11:B→dB•I9:B→e•SabAcdAcdBdeedB①S΄→S②S→aA③S→bB④A→cA⑤A→d⑥B→dB⑦B→e2、LR(0)分析器(3)构造LR(0)分析表s2s31accs5s64s8s97r2r2r2r2r2r2s5s610r5r5r5r5r5r5r3r3r3r3r3r3s8s911r7r7r7r7r7r4r4r4r4r4r4r6r6r6r6r6r6r7①S΄→S②S→aA③S→bB④A→cA⑤A→d⑥B→dB⑦B→e返回3、SLR(1)分析器

LR(0)文法是一类非常简单的文法，它要求文法的识别可归前缀DFA的每一个状态（项目集）都不含冲突性的项目，这样才能构造出不含冲突动作的LR(0)分析表。因此，LR(0)文法的适用性受到很大的限制，对于通常的程序设计语言来说，一般都不能用LR(0)文法来描述。当某个项目集中存在冲突项，就需要向前展望部分材料（一般只需向前查看一个符号）来解决冲突，不同的解决方法就产生了不同的分析算法，主要有SLR(1)和LR(1)方法。

SLR(1)分析法是一种带有简单展望材料的分析法，其中，“S”表示简单的，“1”表示分析的每一步至多向前看一个输入符号。3、SLR(1)分析器（1）引例【例5.13】试构造文法的LR(0)分析表。解：(1)拓广文法 S΄→AA→aAA→a(2)构造LR(0)项目集规范族I0:S΄→•AA→•aAA→•aI1:S΄→A•I2:A→a•AA→a•A→•aAA→•aI3:A→aA•s21accr3r33s2r2r2aAAa(3)构造LR(0)分析表存在移进——归约冲突3、SLR(1)分析器（2）SLR(1)规则

一般而言，假定LR(0)项目集规范族的一个项目集I中含有m个移进项目：同时含有n个归约项目：3、SLR(1)分析器（2）SLR(1)规则

如果集合：{a1,a2,…,am}，FOLLOW(B1)，FOLLOW(B2)，…，FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有#），则隐含在I中动作冲突可通过检查现行输入符号a属于上述n+1个集合中的哪个集合而获得解决。这就是： 规则一：若a=ai（i=1,2,…,m），则置ACTION[I,a]=“移进”； 规则二：若a∈FOLLOW(Bj)（j=1,2,…,n），则置ACTION[I,a]=“用产生式Bj→α归约”； 规则三：其余情况，则置ACTION[I,a]=“出错标志”。 这种用来解决分析动作冲突的方法称为SLR(1)规则。3、SLR(1)分析器（3）SLR(1)分析表的构造

首先将文法G拓广为文法Gʹ，再对Gʹ构造LR(0)项目集规范族C和识别可归前缀DFA的转换函数GO。然后，使用C和GO按下面的算法构造SLR(1)分析表。 假定C={I0,I1,…,In}，令每个项目集Ik的下表k为分析器的一个状态，因此，Gʹ的SLR分析表含有状态0,1,…,n。令那个含有项目Sʹ→•S的Ik的下标k为初态。分析表的ACTION子表和GOTO子表可按如下方法构造：

规则一：若项目A→α•aβ（a∈VT）属于Ik且GO(Ik,a)=Ij，则置ACTION[k,a]=sj，表示将(j,a)移进分析栈。

3、SLR(1)分析器（3）SLR(1)分析表的构造

规则二：若项目A→α•属于Ik，且文法Gʹ中产生式A→α的编号为j，对任何终结符a（包括输入串结束符#），若a∈FOLLOW(A)，则置ACTION[k,a]=rj，表示按文法Gʹ的第j个产生式（A→α）进行归约。

规则三：若项目Sʹ→S•属于Ik，则置ACTION[k,#]=acc，表示“接受”。

规则四：若GO[Ik,A]=Ij，A∈VN，则置GOTO[k,A]=j。

规则五：分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。 按上述算法构造的LR分析表，如果每个入口不含多重定义，则称它为文法G的一张SLR(1)分析表，具有SLR(1)分析表的文法G称为一个SLR(1)文法。使用SLR(1)分析表的分析器叫做一个SLR(1)分析器。 3、SLR(1)分析器

【例5.14】

试构造表达式文法的SLR(1)分析表，并说明是否为SLR(1)文法。解：(1)拓广文法

①Eʹ→E ②E→E+T ③E→T ④T→T*F ⑤T→F ⑥F→(E) ⑦F→i

(2)构造LR(0)项目集规范族和GO函数3、SLR(1)分析器I0:E΄→•EE→•E+TE→•T

T→•T*FT→•FF→•(E)F→•iI1:E΄→E•E→E•+TI2:E→T•

T→T•*FI3:T→F•I5:F→i•I6:E→E+•TT→•T*FT→•FF→•(E)F→•iI9:E→E+T•T→T•*FI8:F→(E•)E→E•+TI10:T→T*F•I11:F→(E)•EFT(i+I7:T→T*•FF→•(E)F→•iI4:F→(•E)E→•E+TE→•T

T→•T*FT→•FF→•(E)F→•i*EFi(TF(iF(i)+*①E΄→E②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→iT3、SLR(1)分析器

(3)计算G[Eʹ]的每个非终结符的FOLLOW集3、SLR(1)分析器

(4)构造SLR(1)分析表①Eʹ→E ②E→E+T ③E→T ④T→T*F⑤T→F ⑥F→(E) ⑦F→is5s4123s6accs7r3r3r3r5r5r5r5s5s4r7r7r7r7823s5s493s5s410s6s11r2s7r2r2r4r6r4r6r4r6r4r6单击图片可放大缩小返回4、LR(1)分析器

在SLR(1)冲突解决方案中，若项目集Ik中含有归约项目“A→α•”，那么当状态k呈现于栈顶时，只要当前所面临的输入符号a满足条件a∈FOLLOW(A)，就确定采取“用产生式A→α进行归约”的动作。然而，在有些情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀未必允许将α归约为A，因为，可能没有一个规范句型含有前缀βAa。因此，在这种情况下，用A→α进行归约未必有效。 因此，我们需要让每个状态含有更多的“展望”信息，这些信息将有助于克服动作冲突和排除那种用A→α所进行的无效归约，在必要时对状态进行分裂，使得LR分析器的每个状态能够确切地指出当后跟哪些终结符时才允许把α归约为A。4、LR(1)分析器（1）LR(k)项目 令每个项目都附带有k个终结符，其一般形式为 此处，A→α•β是一个LR(0)项目，ai∈VT（i=1,2,…,k）。这样的项目称为一个LR(k)项目，项目中的a1a2…ak称为它的向前搜索符串（或展望串）。向前搜索符串仅对归约项目有意义。对于任何移进或待约项目[A→α•β,a1a2…ak]，β≠ε，搜索符串a1a2…ak不起作用。归约项目[A→α•,a1a2…ak]意味着当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2…ak时，才可以把栈顶的α归约为A。这里，我们只对k≤1的情形感兴趣，因为对多数程序语言的语法来说，向前搜索（展望）一个符号就基本可以确定“移进”或“归约”。4、LR(1)分析器（2）CLOSURE(I)的计算 假定I是一个LR(1)项目集，它的闭包CLOSURE(I)可按如下方法构造： ①I中的任何项目都属于CLOSURE(I)； ②若项目[A→α•Bβ，a]属于CLOSURE(I)，B→γ是一个产生式，那么，对于FIRST(βa)中的每个终结符b，如果项目[B→•γ，b]原来不在CLOSURE(I)中，则把它加进去。 ③重复执行步骤②，直至CLOSURE(I)不再增大为止。 【注意】 b可能是从β推出的第一个终结符，若，则b=a。4、LR(1)分析器（3）GO函数的计算 令I是一个LR(1)项目集，X是一个文法符号，则函数GO(I,X)定义为

其中

J={任何形如[A→αX•β，a]的项目|[A→α•Xβ，a]∈I}4、LR(1)分析器（4）LR(1)项目集规范族C的构造 通过函数CLOSURE和GO很容易构造一个文法G的拓广文法Gʹ的LR(1)项目集规范族C，步骤如下：①初始化：令C=CLOSURE({[Sʹ→•S，#]})；②对C中每一个项目集I和文法中任意文法符号X应用状态转换函数GO(I,X)，得到新的项目集J，若J非空且不在C中，则将其加入到C中；③重复步骤②直到C不再增大为止。 类似于计算LR(0)项目集规范族，我们仍然借助一个项目栈来存储每一个新的项目集，计算的每一步是先将栈顶项弹出，记为I，然后对文法中每个文法符号X，如果GO(I,X)非空且不在C中，则将其加入到C中并压入栈中，重复以上过程，直到栈空为止。4、LR(1)分析器形式化算法描述如下：voidItemSets(Gʹ){//计算文法Gʹ的项目集规范族C I=CLOSURE({[Sʹ→•S，#]}); C={I}; //初始规范族C Push(I); //将项目集I压入栈中 while(!Empty(ItemStack)){//只要栈不空就执行以下步骤 Pop(I);//将当前栈顶项目集弹出并置于I中 for(G中每个文法符号X){ J=GO(I,X);//计算GO函数 if(J非空且J不属于C中){ 将J加入到C中; Push(J);//将项目集J压入栈中 } } }}4、LR(1)分析器（5）LR(1)分析表的构造 假定C={I0,I1,…,In}，令每个项目集Ik的下标k作为分析器的状态。令那个包含项目[Sʹ→•S，#]的集合Ik的下标k为分析器的初态。分析表的ACTION子表和GOTO子表可按如下方法构造：规则一：若项目[A→α•aβ，b]（a∈VT）属于Ik且GO(Ik,a)=Ij，则置ACTION[k,a]=sj，表示将(j,a)移进分析栈。规则二：若项目[A→α•，a]