编译原理第6章LR分析

规范归约回顾在自下而上的分析方法中，每一步都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”为此引入：短语、直接短语、句柄等概念问题的关键：如何找句柄？----从规范推导出发，探寻句柄的生成过程及时机。规范归约的逆过程；我们对它认识很清楚刻画“可归约串”---短语、直接短语、句柄G[E]：E→E+T|T

T→T*F|F

F→(E)|I句型：i*i+i

短语：

直接短语：

句柄：如何识别句柄？观察？行不通！设法识别它！文法G[S]，SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄

EETTFTFFi1*i2+i3

第六章LR分析方法LR分析法具有更强的吸引力：(1)应用面广，程序设计语言的结构基本上都能被LR分析器所识别；(2)分析速度快，能有效实现，是最一般的移进—归约方法；(3)能够及时发现语法错误和准确指出错误位置；LR(k)指自左向右扫描输入规范归约决定当前分析动作时向前看的符号个数(4)分析构造工作量大，通常借助工具自动生成分析器。目录6.1LR分析方法的基本思路6.2LR(0)分析表的构造6.3SLR(1)分析表的构造6.4LR(1)分析表6.5LALR(1)分析6.6二义性文法在LR分析中的应用6.7分析器的生成器6.1LR分析方法的基本思路一、活前缀和可归前缀通过规范归约的逆过程---规范推导考察句柄的生成过程和时机。对于G[S]：

SaAcBe

Ab

AAb

Bd拓广：加S’S(0)S’S

(1)SaAcBe

(2)Ab

(3)AAb

(4)BdrrrrrS’SaAcBeaAcdeaAbcdeabbcde每步推出的都是文法的规范句型使用拓广文法，识别符号只出现在产生式左边，当归约到识别符号时，肯定结束对输入串abbcde：1.定义：(,V+,VT*,AVN)，若是符号串的前缀，则称是G的一个活前缀，如果符号串是含句柄的活前缀，则称是文法的可归前缀。对应语法树：SaAcBeAbbdS’规范归约是规范推导的逆过程，考察移进-归约过程中分析栈中的内容与句柄、与规范句型的关系：ab|bcdeaAb|cdeaAcd|eaAcBe|S|S’设有文法G[S],若S*rA是文法G的一个规范推导,rA为当前句型(A)中最右边的非终结符文法G中有产生式A；当前句型()的句柄是什么？活前缀的右端不会超过该句型句柄的末端句柄是的后缀，即活前缀中最长的一个Abbcde的可归前缀与活前缀文法G[S]：

(1)S→aAcBe[1]

(2)A→b[2]

(3)A→Ab[3]

(4)B→d[4]SaAcBe[1]

aAcd[4]e[1]

aAb[3]cd[4]e[1]

ab[2]b[3]cd[4]e[1]可归约前缀：

ab[2]bcde

aAb[3]cde

aAcd[4]e

aAcBe[1]规范句型的句柄之前部分的前缀—活前缀：,a,ab

,a,aA,aAb

,a,aA,aAc,aAcd

,a,aA,aAc,aAcB,aAcBe每个可归约前缀都是经过有限步逐步得到的。归约时机可归约前缀与剩下的输入连接到一起构成规范句型句柄是可归前缀的后缀---栈式记录例：对于G[S’]

S’S

SaAcBe

Ab

AAb

Bd

输入串：abbcde在移进-归约过程中的任何时刻，符号栈中的串均为规范句型的活前缀。符号栈#输入串abbcde#ab若符号栈的内容，正好是当前句型的可归前缀，则栈顶肯定已经形成一个句型的句柄。Ab算法的关键转化为识别可归前缀语法成分之间是嵌套关系2.可归前缀之间的关系可归约前缀的推导：对任一文法，若xUy为可归前缀，且文法中有产生式Uu，则xu也是文法的可归前缀。通过文法已知的可归前缀，可推出新的可归前缀SnXnSkXkS0#历史—活前缀，规范句型前缀句柄前缀—候选式前缀aiai+1…

am#规范句型（若所给串无错）一个LR分析器的工作过程实质上就是一个逐步产生（或识别）所给文法的规范句型的活前缀过程。每个可归约前缀与一个产生式相关联，该可归前缀的每个活前缀也就与这个产生式相关联。活前缀反映了已经得到了产生式的多大一部分，还期望得到什么，可归前缀表明已经得到产生式的全部，应该归约了。有三种情况：活前缀与产生式的关系活前缀已含有句柄的全部符号，表明产生式A→α的右部α已出现在栈顶活前缀只含句柄的一部分符号，表明A→α1α2的右部子串α1已出现在栈顶，期待从输入串中看到α2推出的符号活前缀不含有句柄的任何符号，此时期望A→α的右部所推出的符号串SnxnSlxlSmxmS1X1S0#①aiai+1…

ak#………………活前缀句柄②③α1α2归约α1已出现在栈顶，期待从余留串中得到α2若A->α1α2期望从余留串中得到某一产生式A->α的右部α活前缀与句柄关系的三种情况活前缀与产生式的关系描述----项目加标志的产生式叫LR(0)项目。显然对给定的文法，项目是有限的，项目之间是相互关联的。可把每个项目作为一个状态，一个文法的项目就构成一个自动机---识别活前缀的自动机。为刻划在识别可归前缀过程中，文法G的每一个产生式的右部已有多大一部分被识别（出现在栈顶）的情况，我们在产生式的右部加一标志，标志前的部分表示在活前缀中已经得到的部分，后面的部分表示为得到句柄期待得到的部分。A→α．刻划A→α的右部α已出现在栈顶A→α1．α2刻划A→α1α2的右部子串α1已出现在栈顶，期待从输入串中看到α2推出的符号串A→．α刻划没有句柄的任何符号在栈顶，此时期望α所推出的终结符号串0qXq0q1X10qq2X根据项目的定义，每个项目为识别活前缀的NFA的一个状态。1.NFA的构造原则(1)NFA的状态集：由每个项目所对应的状态组成；(2)输入字符集合：包括终结符、非终结符和；(3)初态：S’S(4)终态：形如Uu的项目(5)转换函数f：若有项目i：Xx1x2…xi-1xi…xn项目j：Xx1x2…xi-1xixi+1…xn项目j的圆点在项目i的基础上后移一个符号的位置则从项目i到j连接一条标记为xi的有向弧，即f(i,xi)=j若xi为非终结符号

项目i：XAAVN项目k：A则从i到k连接一条标记为的弧SaAcBeSaAcBecSaAcBeBSaAcBeBd分析栈的状态不发生变化二、识别活前缀的自动机2.举例：G[S]：

(1)S→aSb(2)S→ab拓广文法G[S’]：(0)S’→S(1)S→aSb(2)S→ab文法G[S’]的项目有：1.S’S

2.S’S3.SaSb

4.SaSb

5.SaSb

6.SaSb7.Sab

8.Sab9.Sab12*37a4S65a8b9bS终态为可归前缀的识别态；或句柄的识别态第一个产生式对应的可归前缀识别态为句子的识别态I0

：S´•SS

•aSb

S•abaI1：S´SSI2

：Sa•SbSa•bS•aSbS•abI3

：SaS•bSaI4

：SaSb•bI5

：Sab•b三、LR分析器的逻辑结构：1.整体结构：总控程序a1a2…aiai+1…an#动作表状态转换表Im

.

.

.

I1

I0Xm

.

.

.

X1

#分析表（自动机）输出sp(1)在总控程序的控制下，从左到右扫描输入串，根据分析栈和输入符号，查分析表确定分析动作；(2)分析表是LR分析器的核心，与文法相关，包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作；(3)分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分，LR分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。2.分析表的组成：分析表由分析动作表和状态转换表两部分组成：(1)分析动作表Action中，行标代表栈顶状态，列标代表当前的文法符号，Action[Ii,Xj]表示所应执行的分析动作。

文法符号状态X1…Xn#I0I1Im…共有4种动作：移进：新状态和输入进栈；移进归约：r5接受：当归约到只剩下识别符，且输入为#，分析成功；acc报错：当状态栈顶为某一状态下，出现了不该出现的文法符号时。执行移进动作表示用第5个产生式进行归约表示接受表示出错(2)状态转换表Goto：Goto[Ii,Xj]表示当栈顶状态为Ii，而移进文法符号为Xj时，应进入的新状态

移进符号状态X1…Xn#I0I3I1IpImIk移进I0

：S´•SS

•aSb

S•abaI1：S´SSI2

：Sa•SbSa•bS•aSbS•abI3

：SaS•bSaI4

：SaSb•bI5

：Sab•bG[S]：(0)S’→S(1)S→aSb(2)S→abab#S0S，2S，11acc2S，2S，5S，33S，44r1r1r15r2r2r2现将两张表的内容合并对非终结符列，动作只有移进，只需保留应进入的新状态既可引入记号Si代表(S,i)简写为S2文法符号状态ACTIONGOTOab#S0S211acc2S2S533S44r1r1r15r2r2r2分析串：aaaabbb四、LR分析（算法）(1)将初始状态S0和输入串的左边界(#)分别进分析栈；(2)根据状态栈栈顶和当前输入符号查动作表进行如下工作：移进:当前输入符号进栈，新状态进栈，继续扫描；归约:若产生式右部的长度为n，则符号栈栈顶n个符号出栈，同时，状态栈顶的n个元素也出栈，归约后的非终结符进栈，并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。(3)重复以上(2)的工作直到接受或出错为止。ＬＲ分析特征:规范的符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号分析决策依据――栈顶状态和现行输入符号．？DFA.四种技术LR(0)SLR(1)LR(1)LALR(1)6.2LR(0)分析表的构造在LR分析算法中，所使用的“状态”是跟活前缀有关的，它就是能够识别文法所有活前缀的有限自动机的状态，每个状态由一个或多个项目构成。例如：

对于产生式SaAcBe有项目：SaAcBe

SaAcBe

SaAcBe

SaAcBe

SaAcBe

SaAcBe圆点的左部表示在分析过程中，要用该产生式归约时，句柄已识别的部分(进入符号栈)，右部表示等待识别的部分。

希望用产生式S的右部进行归约，当前的输入应为a用产生式SaAcBe进行归约时，a已经匹配，期待得到A句柄已经形成，可以归约了一、项目的分类：由于不同的项目反映了分析过程中栈顶的不同情况，因此可根据它的不同作用，将一个文法的全部LR(0)项目进行归类1.移进项目：圆点之后为终结符,Aa,

,V*,

aVT2.待约项目：圆点之后为非终结符，AB，,V*,BVN

3.归约项目：圆点在最后，A

V*4.接受项目：项目S’S是一个特殊的归约项目，它所对应的状态为接受状态。把符号a移进符号栈表明该状态等待着对非终结符B的分析已在栈顶，按相应的产生式归约举例：G[E]：

EaA|bB

AcA|d

BcB|d拓广文法G[S’]：S’E

EaA|bB

AcA|d

BcB|d文法G[S’]的项目有：1.S’E

2.S’E

3.EaA

4.EaA

5.EaA

6.AcA7.AcA

8.AcA

9.Ad

10.Ad

11.EbB

12.EbB13.EbB

14.BcB

15.BcB

16.BcB

17.Bd

18.Bd每个项目对应一个NFA的状态S’E对应的项目1为初态，终态有项目2,5,8,10,13,16,18根据转换函数，可画出NFA的状态图如下:1E2*1.S’E

2.S’E

3.EaA

4.EaA

5.EaA

6.AcA7.AcA

8.AcA

9.Ad

10.Ad

11.EbB

12.EbB13.EbB

14.BcB

15.BcB

16.BcB

17.Bd

18.Bd311a4A569c7A8d10b12B131417c15B16d18终态为可归前缀的识别态；或句柄的识别态第一个产生式对应的可归前缀识别态为句子的识别态二、获得识别活前缀的DFA：1.(1)求出所有项目，(2)构造识别活前缀的NFA，(3)将NFA确定化对拓广文法G[S’]

S’E

EaA|bB

AcA|d

BcB|d1、3、114、6、912、14、172.对上述过程进行归纳总结，可以发现，一个DFA状态对应一个项目集，它们的全体称这个文法的项目集规范族.(1)求项目集设Si是状态Sk输入符号x后到达的状态，则有：①Si状态中的基本部分为：BASIC(Si)={Ax|AxSk}②用闭包函数构造项目集CLOSURE(Si)：a.BASIC(Si)CLOSURE(Si)：b.若ABCLOSURE(Si),BVN,则BCLOSURE(Si)③重复②直到CLOSURE(Si)不再增加项目为止。(2)转换函数从一个状态出发，到达下一个状态的转换函数定义为：GO(I,X)=CLOSURE(J)I为某个项目集对应的状态X为输入符号XVJ={任何形如Ax的项目|AxI}3.DFA的形成过程举例：对拓广文法G[S’]

S’E

EaA|bB

AcA|d

BcB|d1.S’E

2.S’E

3.EaA

4.EaA

5.EaA

6.AcA7.AcA

8.AcA

9.Ad

10.Ad

11.EbB

12.EbB13.EbB

14.BcB

15.BcB

16.BcB

17.Bd

18.Bd有项目：

S0S’E肯定包含再S0中S’E求CLOSURE(S0)EaA

EbBES1:S’ES2aEaAAcA

AdbS3EbBBcB

BdcS4AcAAcA

AdAS6:EaAdS10:AdcS5BcBBcB

BdBS7:EbBdS11:BdAS8:AcAcdBS9:BcBcd活前缀的有效项目和有效项目集同一状态中不同的项目对应着不同的展望，不同的展望意味着不同的分析走向。所以说，不同的项目起着不同的作用，但他们都是与当前活前缀相关的项目。对当前活前缀而言，它们是有效项目。对某活前缀，在其最右推导过程中，最后一步推导所可能用到的项目，是这个活前缀的有效项目；反过来从归约看……项目A→β1·β2对活前缀γ=αβ1是有效的，其条件是存在规范推导：=>*rαAδS=>rαβ1β2δVt*有效项目的含义：αβ1β2ω存在构成规范句型，且有A→β1·β2显然，这三个项目代表了活前缀ac的最近的未来。对活前缀ac接下来用哪一个有效项目，取决于所分析串的下一个输入。对活前缀ac，其有效项目有三个：AcA

S’=>E=>aA=>acAAcAS’=>E=>aA=>acA=>accA

AdS’=>E=>aA=>acA=>acd状态是由项目构成的，状态中的所有项目正好是该状态所识别活前缀的所有有效项目。在LR分析中，栈顶状态即包括了历史，也体现了未来趋势。三、LR(0)文法：1.项目集的相容性：项目有4种类型，但在一个项目集中，不能有以下情况存在：(1)移进项目和归约项目并存；(2)多个归约项目并存；不知该移进还是归约不知该归约为哪个非终结符若项目集能满足以上条件，则称为相容的项目集。2.冲突：移进—归约冲突，归约—归约冲突。3.LR(0)文法：文法G的项目集规范族中的所有项目都相容四、LR(0)分析表的构造：1.构造方法：对于文法G[S]，按以下规则构造LR(0)分析表：(1)对于AxSi,GO(Si,x)=Sj,若xVT,则置Action[Si,x]=Sj;若xVN,则置Goto[Si,x]=j;(2)对于ASi,若A是G中第k个产生式，则对所有输入符号xVT(包括#),均置Action[Si,x]=rk;(3)若SSi,则置Action[Si,#]=acc

(#表示输入串右界符);(4)其它情况均置错。将x入符号栈，要转去的状态Sj进栈将归约后的非终结符x对应的状态Sj进栈按指定的产生式进行归约，将归约后的非终结符进栈对应分析动作为：报告分析成功例：对文法G[S’]

S’E

EaA|bB

AcA|d

BcB|d(0)S’E

(1)EaA

(2)EbB

(3)AcA(4)Ad

(5)BcB

(6)Bd状态ActionGotoabcd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6GO(Si,x)=Sj,若xVT,置Action[Si,x]=SjGO(Si,x)=Sj,若xVN,置Goto[Si,x]=j若SSi,则置Action[Si,#]=acc若ASi，且对应第k个产生式，则对所有符号，置Action[Si,x]=rk6.3SLR(1)分析表的构造一、问题的提出：如果文法所对应的LR(0)项目集规范族中，有的项目集中含有冲突，则无法按LR(0)分析法进行分析。通常的程序设计语言一般不能用LR(0)文法来描述，下面是一个实型变量说明的文法：1.文法：

<实型变量说明>Real<标识符表>

<标识符表><标识符表>,i|iSrDG[S]:

SrD

DD,i|i

将文法进行拓广，有如下项目:(0)S'S(1)SrD(2)DD,i(3)DiS'SS'SSrDSrDSrDDD,iDD,iDD,iDD,iDiDi2.构造项目集：S0:S'SSrDS1:S'S•S2:Sr•DD•D,iD•iS3:SrD•DD•,iS4:Di•S5:DD,•iS6:DD,i•3.用转换函数G0(I,x)=closure(J)，得DFAS

rDi,i结论：S3中有移进—归约冲突，不能用LR(0)分析方法SrD•为归约项目，它认为当前句柄已经形成，所以不管输入什么符号都应归约DD•，i为移进项目：已分析完一个非终结号D，若有输入符号“，”应移进，并转向状态S54.原因：决定分析动作仅仅根据到目前已经看到的东西，没有查看下一符号(Token)。S3:

SrD•DD•,i对于状态S3，如果要做归约动作，那么句柄rD已经形成，可归约为S。这时S之后不应有其他终结符号(只可以有#)。即文法中含有S的句型中，S之后只能有#。而对于移进项目DD,i，它只期待移进符号为’,’。所以可以这样处理：当有输入符号’,’时，移进，当有输入符号‘#’时归约。其它输入符号产生语法错误。句型：…rD,……S,…×Follow(S)二、SLR(1)分析表：将例中的情况一般化：根据不同的向前看符号将状态Si中的各个项目所对应的动作加以区分，从而解决冲突动作。1.设有一个LR(0)的规范族中有如下项目集(状态)

Si={xα.b,

Aγ.,Bδ.,α,,γ,δV*,bVT}可用下面方法解决冲突:2.求Follow(A)、Follow(B)、First(b)。若Follow(A)，Follow(B)和First(b)互不相交，则对于输入aVT{#}，i)对于xα.Si

若aFirst()且GO[Si,a]=Sj

则置Action[Si,a]=Sjii)对于Aγ.Si,若aFollow(A)且Aγ为文法的第j个产生式，则置Action[Si,a]=rjiii)对于Bδ.Si

若aFollow(B)且

Bδ是文法的第k个产生式，则置Action[Si,a]=rkiv)凡不能按上述方法填入的项，均置出错。三、SLR(1)分析表的构造规则1.对Aα.xSi，GO(Si,x)=Sj，若xVT，则置Action[Si,x]=Sj若xVN，则置Goto[Si,x]=j2.对Aα.Si和输入符号aFollow(A),置Action[Si,a]=rj3.若Sα.Si,则置Action[Si,#]=acc4.其他情况均置出错。文法(0)S'E(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi分析串为i+i*i移进——归约冲突移进—归约冲突移进——归约冲突Follow(S’)={#}Follow(E)={+,),#}构造SLR(1)分析表状态ActionGotoi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5DFA

(0)S'E(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi(5)对输入串i+i*i的SLR(1)分析过程：步骤状态栈S符号栈X输入串分析表10#i+i*i#S5205#i+i*i#r6,3303#F+i*i#r4,2402#T+i*i#r2,1501#E+i*i#S66016#E+i*i#S570165#E+i*i#r6,380163#E+F*i#r4,990169#E+T*i#S71001697#E+T*i#S511016975#E+T*i#r6,101201697(10)#E+T*F#r3,9130169#E+T#r1,11401#E#acc分析表

(0)S'E(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi用S'S.作为初态集的项目，构造识别文法活前缀的DFA如下：

S0:S'.SS.aAdS.bAcS.aecS.bedS1:S'S.SabS2:Sa.AdSa.ecA.eS3:Sb.AcSb.edA.eAeS4:SaA.dS5:Sae.cAe.AeS6:SbA.cS7:Sbe.dAe.dccdS8:SaAd.S9:Saec.S10:SbAc.S11:Sbed.

移进—归约冲突Follow(A)={c,d}

First(c)={c}相交移进—归约冲突Follow(A)={c,d}

First(d)={d}相交结论：冲突不能用SLR(1)

方法解决！有文法G[S’](0)S'S(3)Saec(1)SaAd(4)Sbed(2)SbAc(5)Ae6.4LR(1)分析表1.SLR(1)方式失效的原因：假设有规范句型αAa…和βAb…，则a和bfollow(A)。但是一旦求出follow(A)，其中的a就不再反映它的搭档α，而将α和β混为一谈--处理方式是不精确的。只顾后，不瞻前LR(1)分析表构造的思路对活前缀ae来说，在项目集:S5={Sae.c，Ae.}中，输入为c时，当前上文是ae，而在规范句型中对A而言，上文a要求的下文搭档是d而不是c。对输入c，将归约排除了。S'SaAdaedrrrrrS'Saec先看上例文法的两个规范推导：但在LR分析中，若有A->γ,则对活前缀αγ，仅当输入为a时才能归约；而对活前缀βγ，仅当输入为b时才能归约。换句话说，LR中的任何一个状态都处在具体的环境中，若当前环境（活前缀）是α而不是β，则只有输入a时才能进行归约显然，搜索符a只对归约项目Aαβ.有意义。问题是Aαβ.来自于Aα.

β，这样也就有必要为非归约项目加上搜索符。从而得到一般形式的LR(1)项目：[Aα.，a]---如果将当前环境下归约项目Ae.的下文d，附加在它的后面，问题就解决了。对处在环境中的归约项目，将能够导致其归约的输入---称为搜索符，附加在它的后面，构成LR(1)项目。接下来的问题是，如何求A.的搜索符a。这需要从项目之间的关系入手：若有xα.ASi

则A.Si，根据搜索符的含义，First()应作为用A进行归约的搜索符，从而得到LR(1)项目[A.,a]，aFirst()。现已知终点[S’S.，#]=>[S’.S，#]---即环境的构建起点。(1)闭包函数：i)Si中任何LR(1)项目都是属于Si的闭包CLOSURE(Si)ii)设项目：[Aα.B,a]CLOSURE(Si),BVN,V*,且B是产生式,bFirst(a)，则[B.,b]CLOSURE[Si]iii)重复ii)直到CLOSURE(Si)不再增大。显然，LR(1)项目与其后继项目有相同的向前搜索符，如[Aα•x,a]的后继为[Aαx•,a](2)转换函数：GO(Si,x)=CLOSURE(Sj)若则b=First()=则b=First(a)=aSi是LR(1)的项目集Sj={[Aαx•,a]|[Aα•x,a]Si}2.

LR(1)项目集的构造：LR(1)分析过程中的每个状态，是一个LR(1)项目集，特别，[S´.S,#]S0,是整个构造的出发点。它表示：若想用S´S进行归约，输入必须是‘#’。所以整个文法的LR(1)项目集的获得，就是从初始项目[S´.S,#]出发，通过求其闭包再用转换函数逐步求出。所涉及的算法如下：3举例：S0:S'.S,#S.aAd,#S.bAc,#S.aec,#S.bed,#S1:S'S.,#SaS4:SaA.d,#S5:Sae.c,#Ae.,dAeS8:SaAd.,#dS9:Saec.,#cS3:Sb.Ac,#Sb.ed,#A.e,cbAS6:SbA.c,#S10:

SbAc.,#cS7:Sbe.d,#Ae.,ceS11;Sbed.,#dFirst(#)={#}First(d#)={d}First(c#)={c}(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeS2:Sa.Ad,#Sa.ec,#A.e,d状态ActionGotoabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r4DFA(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)Ae可见：LR(1)与SLR(1)不同,

SLR(1)是出现冲突时才向前看符号,

而LR(1)始终向前看符号。6.5LALR(1)分析SLR分析器：功能较弱、实用价值不高；规模与LR(0)相同、易实现LR分析器：功能强大、实用价值高；规模远大于LR(0)、实现代价高LALR分析器：功能介于SLR和LR(k)之间、实用价值高；规模与LR(0)相同、实现难通常，同一个文法的LR(1)状态数要比LR(0)的多，而LALR(1)状态数与LR(0)的相同。[S´S,#][SBB,#][BaB,a/b][Bb,a/b]I0S[S´S,#]I1B[SBB,#][BaB,#][Bb,#]I5a[BaB,a/b][B

aB,a/b][Bb,a/b]I3b[Bb,a/b]I4B[SBB,#]I9a[BaB,#][BaB,#][Bb,#]I2B[BaB,#]I8b[Bb,#]I7abaB[BaB,a/b]I6b例LR(1)项目集规范族的构造G(S´)：(0)S´S(1)SBB(2)BaB(3)Bb若LR(1)的两个状态中的LR(0)项目完全相同，则称两个LR(1)状态为同心集。观察，合并会如何分析#aab#[S´S,#][SBB,#][BaB,a/b][Bb,a/b]I0S[S´S,#]I1B[SBB,#][BaB,#][Bb,#]I2a[BaB,a/b][B

aB,a/b][Bb,a/b]I3b[Bb,a/b]I4B[SBB,#]I5a[BaB,#][BaB,#][Bb,#]I6B[BaB,#]I9b[Bb,#]I7abaB[BaB,a/b]I8ba[BaB,a/b/#][BaB,a/b/#][Bb,a/b/#][Bb,a/b/#]I47[BaB,a/b/#]I89I36I47合并后不会产生新的移进—归约冲突，但可能产生归约—归约冲突LALR(1)分析表与语法分析总控程序称为LALR(1)分析器。构造LALR(1)分析表(0)S´S(1)SBB(2)BaB(3)Bb47b36a36a0#89B36a36a0#89B36a0#2B0#比较LR(1)与LALR(1)的识错时机和位置!分析#aab#讨论:合并同心集后会不会产生新的冲突：不会产生新的移进-归约冲突，但可能会产生归约-归约冲突。例S'–>SS–>aBc|bCc|aCd|bBdB–>eC–>eI0:S'–>•S,#S–>•aBc,#S–>•bCc,#S–>•aCd,#S–>•bBd,#I1:S'–>S•,#I2:S–>a•Bc,#S–>a•Cd,#B–>•e,cC–>•e,dI3:S–>b•Cc,#S–>b•Bd,#C–>•e,cB–>•e,dI4:S–>aB•c,#I5:S–>aC•d,#I6:B–>e•,cC–>e•,dI7:S–>bC•c,#I8:S–>bB•d,#I9:B–>e•,dC–>e•,cI10:S–>aBc•,#I11:S–>aCd•,#I12:S–>bCc•,#I13:S–>bBd•,#I69:C–>e•,c/dB–>e•,d/c6.6二义性文法在LR分析中的应用二义性文法描述句型简洁、自然，例如：

E→E+E|E*E|id

但是，二义性文法决不是LR文法，构造的项目集规范族一定会出现动作冲突。不过对某些二义性文法，通过人为地规定优先性和结合性解决冲突，可构造出更有效的LR分析器。分析表规定移进则右结合，否则为左结合E´EEE+EEE*EEidE´EEE+EEE*EEEE*EEE+EEE*EEidEididid+EE+EEE+EEE*EEidEE+EEE+EEE*E*EidEE*EEE+EEE*EE*++*I3I2I0I1I2I3I4I5I6语法规则(.y文件)yyparse()YaccLex词法规则(.l文件)yylex()输入输出6.7分析器的生成器可以是二义文法Yacc源程序有三部分组成：

声明

％％

翻译规则

％％

C写的支持例程

声明部分

有任选的两节。第一节处于分界符%{和%}之间，它是一些普通的C的声明；

第二节是文法记号的声明。翻译规则部分

每条翻译规则由一个文法产生式和有关的语义动作组成。

支持例程部分

一些C写的支持例程。例：词法分析器，错误恢复例程等。P157：spl/0解释器的YACC程序台式计算器：输入一个表达式并回车，显示计算结果（也可以输入一个空白行）。%{#include<ctype.h>#include<stdio.h>#defineYYSTYPEdouble/*将栈定义为double类型*/%}

%tokenNUMBER%left‘+’

‘’%left‘*’

‘/’%rightUMINUS%%lines:linesexpr‘\n’{printf(