复习-编译原理第4章

2025/1/7编译原理1计算机学院厚德和谐砺学创新编译原理

CompilerPrinciples

任课教师：郑丽萍2014－2015第2学期2025/1/7编译原理2句型分析：就是识别一个符号串是否为某文法的句型，是某个推导（归约）的构造过程。分析程序(识别程序)：在语言的编译实现中，完成句型分析的程序。从左到右的分析算法：总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。

语法分析的方法一、基本概念2025/1/7编译原理3自上而下分析法从文法的开始符号出发，反复使用文法的产生式，为待识别句子建立一个最左推导，以寻找与输入符号串匹配的推导。自下而上分析法从输入符号串开始，逐步进行归约，从叶子节点，由底上向上逐步建立一棵完整的语法树，直至归约到文法的开始符号（树根）。二、语法分析的两种方法2025/1/7编译原理4自顶向下分析方法的基本缺点不能处理具有左递归性的文法文法G，存在U∈VN，ifU==>U…,则G为左递归文法+

一、左递归文法

左递归文法回溯问题一般方法面临问题及解决2025/1/7编译原理5

要实行自顶向下分析，必须要消除文法的左递归，不仅消除直接左递归，而且消除间接左递归。

直接左递归

若P→P

α|β

α、β∈V*且β不以P开头串的特点 βα...α

间接左递归若P=>Pα

例如：S→Aa

A→Sb|b

*如果文法具有间接左递归，则也将发生上述问题。2025/1/7编译原理6二、回溯问题1什么是回溯?

分析工作要部分地或全部地退回去重做叫回溯。

严重的效率低，只有在理论上的意义而无实际意义。U::=aβ1|a

β

2|a

β

32造成回溯的条件?3回溯带来的问题?

文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。2025/1/7编译原理71)语法分析要重做2)语法处理工作要推倒重来

因此自顶向下的一般分析方法不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低。欲采用此方法，必须：1、消除左递归；

2、消除回溯4效率低的原因2025/1/7编译原理8消除文法的左递归产生式方法：改写产生式，使产生式不含左递归。法一：P→Pα|β产生式的符号串为βα...α引入一元语言符号｛｝，{x}表示x可出现任意次。则：P→Pα|β改写为P→β{α}例1：S→AcA→Aa|b

改为：S→AcA→b{a}一、消除直接左递归例2：E→E+T|TT→T*F|F

消除左递归：

E→T{+T}T→F{*F}2025/1/7编译原理9法二：对左递归

A→Aα|β的非终结符A，引入一个新的非终结符A’，使得：

A→Aα|β

等价写成：一般地：若其中βi均不以A打头，则：A→βA’

A’→αA’|ε2025/1/7编译原理10i)已知U→xy|xw|…|xz

解：U→x(y|w|…|z)

得：U→xU’U’→y|w|…|zii)已知U→x|xy

解：U→x(y|ε)法二步骤总结

使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。Step1：提因子2025/1/7编译原理11若：P→P

|

则可改写为：P→

P’P’→

P’|ε例

E

E+T|T T

T*F|F F

(E)|id消除左递归后文法

E

TE

E

+TE

|

T

FT

T

*FT

|

F

(E)|id注意：此方法只能消除出现在产生式的全部直接左递归，不能消除经两步或多步推导所出现的一切间接左递归。Step1：将左递归规则改为右递归2025/1/7编译原理12二、消除间接左递归1间接左递归产生原因产生式右边首符号为非终结符；(存在回路)前面非终结符引用后面非终结符，后面非终结符引用前面非终结符。例1：S→Ac|c(1)

A→Bb|b(2)B→Sa|a(3)对例1：

B→Sa|a带入(2)，得A→Sab|ab|b

带入S产生式，得S→Sabc|abc|bc|c

对S消除直接左递归得：

S→(abc|bc|c)S’S’→abcS’|ε2消除方法

找出所有引用前面非终结符的产生式进行代换，即先变换成直接左递归。2025/1/7编译原理13一、消除回溯的途径

改写文法对具有多个候选式右部反复提取左因子，使其具有不同首符号例1U→xV|xWU,V,W∈Vn,x∈Vt改写为：

U→x(V|W)

更清楚表示

U→xZZ→V|W注意：要进一步检查V和W的首符号集是否相交，若相交，则要再次提取左因子。回溯的消除及LL(1)文法2025/1/7编译原理14一般的，对于有公共左因子的文法A

a

1|a

2|…

a

k|γ，其中γ不以a开头，

a∈V。提左因子：判断adeS

aA

adA‘ade例：A

d|de|f改为：A

dA’|fA’

ε|e

A

aA

|γA

1|

2

|…

k若

1

2…

k还有某些候选式有相同首符号，则依次提取，直到每个候选式的首符号不同为止。注意：提取公因子会引入大量非终结符和ε产生式。回溯的消除及LL(1)文法2025/1/7编译原理151定义

FIRST(X)={a|a∈VT且Xa，X，∈V*}

特别的：X

，则

FIRST(X)

对文法G的所有非终结符的每个候选式X其首符号集为FIRST(X)。对A的任何两个不同的选择

i

和

j，希望有

FIRST(

i)

FIRST(

j)=

此时，当要求A匹配输入串时，A就可根据所面临第一个输入符号a，准确指派某个候选式推导，该候选式即为a∈FIRST(X)的X候选式。二、FIRST集**回溯的消除及LL(1)文法2025/1/7编译原理162FIRST（X）构造方法1).若X

V

，则FIRST(X)={X}；2).若X

VN，且有X

a…，则{a}∪FIRST(X)；a可为；3).若有X

Y1Y2…YK

，Yi

VN

(1≤i≤K)，则

(FIRST(Y1)－{

})

∪

FIRST(X);

若

FIRST(Y1)，则(FIRST(Y2)－{

})

∪

FIRST(X)；同样，若

FIRST(Yj)(1≤j<K)，(FIRST(Yj＋1)－{

})

∪

FIRST(X)；特别的，若所有的FIRST(Yj)(j=1,2,…,K)均含有

，则把

加到FRIST(X)中。反复使用上述2、3步，直到每个符号的FIRST集不再增大为止。2025/1/7编译原理171定义

FOLLOW(A)={a|S

…Aa…，a

VT}

特别的：若S

…A，则#

FOLLOW(A)

FOLLOW(A)={aS=>A且a∈

FRIST(),∈V*,

∈V*

}若S=>

uA，且

=>ε，则#∈FOLLOW(A)三、FOLLOW集对文法G的所有含有ε产生式的非终结符A定义它的FOLLOW(A)。对含有ε的A的所有候选式

i

，希望有

FIRST(

i

)

FOLLOW(A

)=

*****2025/1/7编译原理181).文法的开始符号S，置{#}∪FOLLOW(S)；当A∈VN为句型的尾符号时，则#∈FOLLOW（A）2).对于B

αAβ，则

(FIRST(β)－{})∪

FOLLOW(A)；3).对于B

αA，或B

αAβ而

FIRST(β)，则把FOLLOW（B）加至FOLLOW（A）中。反复使用2、3步，直到每个非终结符的FOLLOW集不再增大为止。2FOLLOW(A)构造方法2025/1/7编译原理19

四、LL(1)文法2、若β==>ε,则FIRST(α)∩FOLLOW(A)=Ф*定理：文法G是LL(1)文法的充分必要条件是：对于G的每一个非终结符A的任意两条规则A→α|β,下列条件成立：1、FIRST(α)∩FIRST(β)=Ф2025/1/7编译原理20

1LL(1)含义：

L：从左至右顺序扫描输入串；

L：按最左推导方式；

1：每一次推导均向前查看一个输入符号准确指派产生式。

2LL(1)文法性质:

没有公共左因子；无二义性；不含左递归。对LL(1)文法，可构造一个无回溯自顶向下语法分析程序，方法为：预测分析法（LL(1)分析法）2025/1/7编译原理21LL(1)分析方法是一种比递归子程序法更有效的自顶向下分析方法。LL(1)分析使用一个下推栈而不是递归调用来完成分析。名称中第一个L表示自左向右顺序扫描输入符号串，第二个L表示分析过程产生一个句子的最左推导。括号中的1表示每进行一步推导，只需要向前查看一个输入符号，便能确定当前所应选用的规则。

预测分析法2025/1/7编译原理22LL(1)分析器由一个总控程序（表驱动程序）、一张分析表（预测分析表、LL(1)分析表）和一个分析栈组成。输入符号串：分析栈a1a2…………an#

XZS#LL（1）总控程序分析表输出流栈中存放文法的符号串，栈底符号是#待分析串，从左到右扫描是一个两维数组M[A,a],A是非终结符，a是终结符或#LL(1)分析的基本方法2025/1/7编译原理23输入符号串:指要分析的输入符号串，它以右界符#作为结尾。分析栈：用来存放一系列文法符号。分析开始时，先将#入栈，然后再将文法的开始符号入栈。输出流：分析过程中使用的产生式序列。总控程序：分析器对输入串的分析靠总控程序完成.根据分析栈的栈顶符号X和当前的输入符号a，总控程序按照分析表的指示来决定分析器的动作。工作过程如下：2025/1/7编译原理24第一步初始化:分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置，如图1所示。然后，反复执行第二步的操作。

输入符号串：

a1a2…………an#分析栈：

S#图1分析开始时状况第二步假设分析的某一步，分析栈及余留的符号串如图2：aiai+1…………an##X1X2…Xm-1Xm

图2分析进行中的状况2025/1/7编译原理25(1)若Xm∈Vn，则查分析表的Xm行ai列，假设M[Xm，ai]为产生式Xm→Y1Y2…Yk，则将Xm出栈，并将Y1Y2…Yk反序入栈，如图3；若M[Xm，ai]为ERROR，则出错。aiai+1…………an##X1X2…Xm-1YkYk-1…Y1

图3反序入栈(2)若Xm=ai≠#，表示栈顶与扫描的符号匹配，则栈顶符号Xm出栈，输入指示器指向下一个符号，否则(即Xm≠ai)出错。(3)若Xm=ai=#，表示输入串完全匹配，分析成功。2025/1/7编译原理261分析表：可用一个二维数组表示，它的每一行与文法的一个非终结符相关联，每一列则与文法的一个终结符号或界符“#”相关联。元素：M[A，a]＝文法产生式|error（A∈VN，a∈VT∪{#}）基本思想

当文法中某一非终结符呈现在栈顶时,根据当前的输入符号，分析表应指示要用该非终结符的哪一条候选式匹配输入串(即进行下一步最左推导)

根据这个思想，我们可以构造分析表算法!预测分析表的构造2025/1/7编译原理27

分析表元素M[A,a](A∈VN,a∈VT∪#)，按下述规则确定：对于文法中的每个产生式A→γ1|γ2|……|γm1）若a∈First(γi)，则置M[A,a]=“A→γi”2）若

∈First(γj)，且a∈Follow(A)，则M[A,a]=“A→

”3）除上述两种情况外，其余的一切表元素均置为error。2预测分析表构造算法预测分析表各元素含义为：或指出当前推导所应使用的产生式，或指出输入符号串中存在着语法错误.2025/1/7编译原理28注：1）用分析表构造算法可以为任意文法G构造其分析表M2）若文法为非LL(1)文法，则构造出的M包含有多重元素。则分析过程有回溯。可以证明：一个文法G的预测分析表不含多重元素，当且仅当该文法是LL(1)的。2025/1/7编译原理29五、结论对LL(1)文法，总能构造预测分析表，且表中不含多重元素。对非LL(1)文法，尽管可为其建立预测分析表，但表中必出现多重元素。非LL(1)文法所造表中,必有冲突元素。事实上,是否有冲突元素也是判别一文法是否是LL(1)文法的方法之一。对某些非LL(1)文法，可通过消除左递归，反复提取左因子等方法将其改造成LL(1)文法。但是，并非所有的非LL(1)文法都能改造为LL(1)文法。六、非LL(1)文法的改造2025/1/7编译原理30从输入串开始，进行最左归约，直到到达文法的开始符号为止。大致过程：把输入符号逐个移进到一个栈里，当栈顶形成某个产生式的右部（句柄）时，把栈顶的这一部分替换成（归约为）它的左部符号。称作“移进—归约”分析。

自下而上分析过程语法分析程序查找规约串依据

a+b……#输出带#2025/1/7编译原理31“移进-归约”分析对符号栈的使用有四类操作：移进、归约、接受和出错处理。“移进一归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。工作过程：自左至右将串w的符号依次入栈，一旦栈顶形成句柄即归约。归约可持续多次，直至栈顶不再呈现句柄为止。然后，继续移进符号，重复这个过程，直至最终形成如下格局：

栈

输入

#S

#分析过程的每一步，栈中符号串与剩余输入符号串恰是一个规范句型。且栈中符号串为该句型的一个活前缀。总结活前缀：是规范句型的一个前缀，且不含句柄之后的任何符号

，则称为该规范句型的一个活前缀。2025/1/7编译原理32算符优先分析法一、算符文法定义

算符文法CFGG=（VN,VT,P,S）,U,V,W均为非终结符，x,y均为终结符。如果CFG(不含空产生式)G中没有形如U

…VW…的产生式，则称G为算符文法（OG）。推论：

算符文法的任何句型都不含两个相邻的非终结符。终结符号a与b之间的优先关系有三种：

a

b表示a的优先级低于ba

b表示a的优先级等于b

a

b表示a的优先级大于b2025/1/7编译原理33二、算符优先关系定义

在OG（算符优先文法）中x•=y

G中有形如U

…xy…或U

…xVy…的产生式。x<•y

G中有形如U

…xW…的产生式,

而Wy….或WVy…x•>y

G中有形如U

…Wy…的产生式,

而W…x或W…xV规定：若Sx…或SVx…则#<•x

若S…x或S…xV则x•>#2025/1/7编译原理34三、算符优先关系计算及其表示1定义

FIRSTVT(W)={y|Wy…WVy…}LASTVT(W)={x|W…xW…xV}2三种关系计算x•=y：U

…xy…或U

…xVy…x<•y：每个非终结符B的FIRSTVT(B)，形如U

…xB…中，每个y∈FIRSTVT(B)，则有x<•y成立。x•>y：每个非终结符B的LASTVT(B)，形如U

…By…中，每个x∈LASTVT(B)，则有x•>y成立。2025/1/7编译原理35对文法的每一非终结符号构造FIRSTVT集和LASTVT集，算法分别如下ⅰ)构造FIRSTVT集，置FIRSTVT(A)=φ

若文法中有形如A→b…或A→Bb…的规则，则b∈FIRSTVT(A)

若文法中有形如A→B…的规则，则FIRSTVT(B)∈FIRSTVT(A)2025/1/7编译原理36ⅱ)构造LASTVT集，置LASTVT(A)=φ

若文法中有形如A→…a或A→…aB的规则，则a∈LASTVT(A)

若文法中有形如A→…B的规则，则LASTVT(B)∈LASTVT(A)(2)ⅰ)形如…aA…的规则右部，a<FIRSTVT(A)ⅱ)形如…Ab…的规则右部，LASTVT(A)>bⅲ)形如…ab…或…aAb…的规则右部，a=b(3)#<FIRSTVT(S)LASTVT(S)>#2025/1/7编译原理373、

算符优先文法在OG文法G中，若任意两个终结符间至多只有三种算符优先关系=、<和>中的一种算符优先关系存在，则称G为算符优先文法(OPG)。

算符优先文法是无二义的。2025/1/7编译原理381素短语：至少含有一个终结符号，并且除自身之外不再含有任何更小的带有终结符号的短语，则称为素短语。2最左素短语：句型最左边的素短语。算符优先文法句型的最左素短语是唯一的。EE+TE+TTT*FFi句型T+T*F+i的语法树最左素短语不一定是当前句型的句柄最左素短语可能不是相应文法的任何产生式的右部。按算符优先关系所确定的归约串恰好是当前句型的最左素短语2025/1/7编译原理39LR分析器概述一、LR分析器构成总控程序(驱动程序)。对所有LR分析器都相同。分析表(分析函数)。不同文法分析表不同，同一文法采用的LR分析器不同时，分析表也将不同。分析栈。包括文法符号栈和相应的状态栈。总控程序outputInput(#)LR分析表ACTIONGOTOS0#SmXm……

状态栈符号栈2025/1/7编译原理401分析表构成

动作表(ACTION)

ACTION[S,a]：表示在当前状态S下，面临扫描符号a所应采取的动作。动作有四种：移进、归约、出错、接受。

转向表(GOTO)

GOTO[S，X]：若XVT，表示在当前状态下，读入a应转向什么状态；若XVN，表示当前栈顶句柄归约成X后，应转向什么状态。

移进ai和s=goto[sm,ai]进栈action[sm,ai]=归约rj:AXm-r+1Xm-r+2…Xm

接受s=goto[sm-r,A]

出错2025/1/7编译原理41注：对于终结符的转向动作，可与其移进动作合并在一起填在动作表中，这样转向表可进行压缩，只保留非终结符转向部分。ACTIONGOTOa1a2…anS0S1…SkA1A2…AmS5r4acc282025/1/7编译原理422LR分析器的总控程序

总控程序的动作由当前栈顶状态Sm和扫描符号ai查表决定。1）移进

把(Sm,ai)的下一状态S‘=GOTO[Sm，ai]连同扫描符号进栈，栈顶成(S’,ai)，扫描指针后移；2）归约

用产生式A

进行归约。若

的长度为，则弹出栈顶

项，使栈顶状态变为Sm-，然后将(Sm-,A)的下一状态S’=GOTO[Sm-,A]连同A一起入栈，栈顶变为(S’,A)。扫描指针不动，即不改变现行输入符号。3）接受

4）报错注：不管哪一类分析程序，总控程序的动作都一样。2025/1/7编译原理43LR分析总结

特征规范的；符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)；分析决策依据――栈顶状态和现行输入符号。识别活前缀的DFA.

四种技术

LR(0)SLR(1)LR(1)2025/1/7编译原理44

在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。

归态活前缀

活前缀尾部正好是句柄之尾，这时可进行归约。归约后又会成为另一句型的活前缀。

非归态活前缀

句柄尚未形成，需要继续移进若干符号后才能形成。

活前缀2025/1/7编译原理45一、LR(0)分析表的基本策略

状态DFA状态的转换构造文法G的一个DFA，用于识别所有活前缀。由若干LR(0)项目所组成的集合(项目集)来表示。由分析过程中的移进－归约操作引发。LR(0)分析表的构造2025/1/7编译原理46定义：对文法G的每个产生式右部添加一个圆点，称为G的一个LR(0)项目(简称项目)。Aα•

或Aα•χβ

注：添加位置不同，叫做不同项目。用圆点“•”表示识别一个产生式右部符号到达的位置，项目记录了当前活前缀状况。1文法G的LR(0)项目2025/1/7编译原理47LR(0)项目分类移进待归约归约接受接受项目：S’SS’S•归约项目：A•待归约项目：A•BBVN移进项目：A•aaVT2025/1/7编译原理481）定义项目集是相关项目的集合。是通过对某个基本项目集I通过closure(I)运算求得。2）closure(I)构造设I是文法G的一个LR(0)项目集,

closure(I)是从I出发用下面三个规则构造的项目集:1I中每一个项目都属于closure(I)；2若项目A→α·Bβ

closure(I)且B∈VN，B→ηP，则将B→·η加进closure(I)中。3重复执行(2)直到closure(I)不再增大为止。

2文法G的LR(0)项目集2025/1/7编译原理49

其中，I:项目集，x∈V，J={A

x•

|A

•

x

I}。含义：对于任意项目集I，转换到项目J，是由于I中有A

•X

，J中有A

X•

，表示识别的活前缀增加了X。XAα•XβI：AαX•βJ:go(I,X)=Jclosure()1）定义3状态转换函数GO(I，X)2025/1/7编译原理50二、识别所有规范句型全部活前缀的DFA1由项目构成识别文法活前缀的DFA

1）对于一个文法G，可构造一个DFA，由它的状态（项目集）记住当前活前缀状况，该DFA能识别G的所有活前缀。

若状态中项目为Aα•，则表示它已处于归态活前缀。若为Aα•χβ则表示它处于非归态活前缀。

2）DFA的整个状态集称为LR(0)项目集规范族。

项目、项目集、项目集规范族。目的：构造LR(0)的项目集规范族。2025/1/7编译原理51Step1拓广文法G，形成新的文法G’。即增加产生式S’S，并令S’

•S作为G’的初态I0的基本项目2DFA构造过程Step2定义和构造项目集的闭包。设I是G’的一个项目集，构造I的闭包CLOSURE(I)Step3确定状态转移。利用转换函数GO实现。Step3构造LR(0)项目集规范族Q。将所有项目集，以及所有状态间转移构造出来。构造算法：2025/1/7编译原理52DFAM=(

VT∪VN∪{S},Q{项目集规范族}，I0=closure{S’→•S}，Q，

=go(I,X))DFA中每个状态为终态，从I0出发，沿着有向边可使DFA所经历的任何状态终止其工作，将从I0出发到达该状态所经过的弧上的标记依次连接，即可得到DFA到达该状态时，所识别的某规范句型的一个活前缀。因此该DFA可识别所有活前缀。注意：当M到达只含有归约项目的项目集时，表明活前缀中已含有相应句柄的全部符号，这些状态称为句柄的识别状态。2025/1/7编译原理53三、LR(0)分析表的构造假定C={I0,I1,……，In}，用整数0，1，……，n表示状态I0,I1,……，In，因此，G’的LR(0)分析表含有状态0，1，……，n。令含有项目S’→．S的Ik的下标k为初态。ACTION和GOTO可按如下方法构造：若项目A→α．aβ属于Ii且GO(Ii,a)=Ij,a∈VT，则置ACTION[i,a]为“把状态j和符号a移进栈”，简记为“sj”；若a∈VN，则置GOTO(i,a)=j;若规约项目A→α．∈Ii,则对任何终结符a,置ACTION[i,a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式；若接受项目S’→S．属于Ik,则置ACTION[k,#]为“接受”，简记为“acc”;分析表中凡不能用上述规则填入信息的空白格均置上“出错标志”。2025/1/7编译原理54注意：一个LR(0)项目集中不能有下列情况存在：

1、移进和归约项目同时存在(移进-归约冲突)

形如：A→α·aβ，a∈VTB→γ·

2、归约和归约项目同时存在(归约-归约冲突)

形如：A→α·B→γ·§

4.4.2LR(0)分析表的构造2025/1/7编译原理55

对于冲突状态I中的归约项目A

，不管当前输入符号，都把ACTION表中的状态行所有非终结符列置为rj，其中j为A产生式编号。产生冲突的根本原因？

构造分析表时根据不同的扫描符号a，将I中各项目对应的分析动作加以区别，冲突即可解决。

SLR(1)是LR(0)的一种改进，对有冲突的状态向前查看一个符号，以确定作何种动作。如何解决？一、问题分析SLR(1)分析表的构造2025/1/7编译原理56

定义：对于文法中的非终结符U∈VNFOLLOW(U)={a|S’⇒…Ua…，a∈VT∪{#}}

对含冲突的项目集I={X

b，A

，B}，若{b}、FOLLOW(A)、FOLLOW(B)两两不相交，则面对当前读入符号a，状态I的解决方法：

1.若a=b，则移进。

2.若aFOLLOW(A)，则用A进行归约。3.若aFOLLOW(B)，则用B进行归约。4.此外，报错。具体解决过程*2025/1/7编译原理57二、构造SLR(1)分析表的算法

设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的k作为状态序号，并以包含S`•S的项目集作为初始状态，同时将产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：

1）若项目A

•a

属于Ik状态且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]=Sj；即：移进a，并转向Ij状态。

2）若项目A

•Ik，则对任何终结符a

Follow(A)，置ACTION[k,a]=rj；其中j是产生式A

的编号，即按该产生式进行归约。

3）若项目S`S•属于Ik，则置ACTION[k,＃]=acc;4）若GO(Ik,A)=Ij，A是非终结符，则置GOTO[k,A]=j5）分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。2025/1/7编译原理58注意！1)若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是SLR(1)文法。

2)若项目集中存在A

•

项目，不应设计相应GO函数以转到其他项目集，因为A

•和A

•

是同一项目，都是A

•项目，是归约项目。

3)二义文法决不是LR文法。

4)每个SLR(1)文法都不是二义的，但是有很多非二义的文法，包括一些程序设计语言结构，都不是SLR(1)的，这说明SLR(1)文法的描述能力有限。原因是SLR分析器的构造方法没有记住足够多的上下文。2025/1/7编译原理59失效原因：SLR(1)规则仅孤立地考察输入符号是否属于与归约项目Aα·相关联的集合FOLLOW(A)以确定是否应按产生式Aα归约，没有考察符号串α所在规范句型的“环境”——没有考察L在规范句型中的“上下文”，这就具有一定的片面性。请阅读课本例4.82025/1/7编译原理601）当出现移进-归约冲突时，可选取移进，这样，这是一个自然的消除二义性的规则。

2）当出现归约-归约冲突时（如课本例4.8）情形就较复杂，需要有新的解决方法——LR（1）。解决方法

给每个LR(0)项目添加展望信息，即：添加句柄之后可能跟的终结符，这些终结符确实跟在规范句型句柄之后。2025/1/7编译原理61一、LR(1)项目定义1LR(1)项目：形如(A

•

，a)的二元式称为LR(1)项目。其中A

是文法的一个产生式，a是终结符，称为搜索符。

(A

•

，a）的含义：预期当栈顶句柄

形成后，若扫描到符号a，即可进行归约。此时，

在栈内，

还未入栈，即它展望了句柄后的一个符号。对于多数程序设计语言，向前展望一个符号就足以决定归约与否，所以只研究LR(1)。

在LR(1)项目中有效的项目并不多。