LALR分析表的构造

4.7.4LALR分析表的构造

LALR(lookahead-LR)技术。这种方法在实际中是经常使用的。

定义4.14

如果两个LR(1)项目集去掉搜索符之后是相同的,则称这两个项目集具有相同的心(core)。

一个心就是一个LR(0)项目集。

定义4.15

除去初态项目集外，一个项目集的核(kernel)是由此集中那些圆点不在最左端的项目组成。LR(1)初态项目集的核含有也仅含有[S'→·S,$]。1[S´S,$][SCC,$][CcC,c/d][Cd,c/d]I0S[S´S,$]I1C[SCC,$][CcC,$][Cd,$]I2c[CcC,c/d][C

cC,c/d][Cd,c/d]I3d[Cd,c/d]I4C[SCC,$]I5c[CcC,$][CcC,$][Cd,$]I6C[CcC,$]I9d[Cd,$]I7cdcC[CcC,c/d]I8d2改进思路：合并同心集可达到缩小构造分析表的状态数目；利用核代替项目集可以达到缩小项目集所占用的存储空间。介绍两种方法：第一种方法：对于G，构造LR(1)项目集规范族(DFA)，然后，合并同心集，若合并后的同心集中没有移进归约冲突，则用其构造LR分析表,这种分析表称作LALR分析表。图4.27中

I3

和I6I4和I7I8和I93[S´S,$][SCC,$][CcC,c/d][Cd,c/d]I0S[S´S,$]I1C[SCC,$][CcC,$][Cd,$]I2c[CcC,c/d][C

cC,c/d][Cd,c/d]I3d[Cd,c/d]I4C[SCC,$]I5c[CcC,$][CcC,$][Cd,$]I6C[CcC,$]I9d[Cd,$]I7cdcC[CcC,c/d]I8dc[CcC,c/d/$][CcC,c/d/$][Cd,c/d/$][Cd,c/d/$]I47[CcC,c/d/$]I89I36I474讨论：1.由于go(I，X)仅仅依赖于I的心，因此LR(1)

项目集合并后的转换函数go(I，X)随自身的合并而得到。2.动作action应当进行修改，使得能反映各被合并集合的既定动作。3.

把同心的项目集合并为一，有可能导致冲突，这种冲突不会是移进-归约冲突;但可能引起归约-归约冲突。

Ik:{[A,u1][Ba,b]}au1=

Ij:{[A,u2][Ba,c]}au2=

Ikj:[A,u1/u2][Ba,b/c]a{u1,u2}=5例：下面文法是LR(1)的，但不是LALR(1)的。

S´

SSaAdbBdaBebAeAcBc[S´

S，$][SaAd,$][SbBd,$][SaBe,$][SbAe,$][S´

S，$][S

aAd,$][S

aBe,$][A

c,d][Bc,e]aS[S

b

Bd,$][S

b

Ae,$][A

c,e][Bc,d]bA[S

aAd,$]B[S

aBe,$]c[A

c,d][B

c,e][A

c,e][B

c,d]c6LR(1)和LALR(1)分析上的差别输入：ccd$LR:0c3c3d4

报错

LALR:0c36c36d470c36c36C890c36C890C2

报错7LALR分析表的有效构造方法用LR(0)的项目集的核项目代替项目集，为每个核项目配上搜索符号,得到LALR项目集族的每个项目集的核项目。

可行性

1.用项目集的核构造go函数若[BX,b]Ikernel

X{XTXN}

则go(I,X)kernel:=[BX,b]

若[BC,b]Ikernel

且

CAAXP

则[AX,a]go(I,X)

aFIRST(b)*rm8

CA

存在规则链:

CC11

C1C22

CnAn2.用项目集的核构造action表(a)action[I,a]:=rA

A

Ikernel

若[BC,b]Ikernel

且

CA

aFIRST(b)

则action[I,a]:=rA存在规则链:CC11

C1C22CnAnA*rm*rm9

(b)若

[BC,b]Ikernel

且

Ca（最后一步不使用-产生式）

则action[I,a]:=Sgo(I,a)Ca

P

或

CC11C1C22Cna

例示构造方法

G[S´]:(0)S´S

(1)SL=R(2)SR

(3)L*R(4.23)(4)Lid

(5)RL*rm10

G[S´]:(0)S´S

(1)SL=R(2)SR

(3)L*R(4)Lid

(5)RL1.构造G[S´]的LR(0)项目集的核S´S

I0SS´S

I1SL=RRLLI2SR

RI3L*R*I4Lid

idI5=SL=RI6RL*RI7RLLI8*idRSL=RI9L*idI5112.根据I的核和X,确定go(I,X)的核项目的搜索符号。它分成自生的还是传播的。

看用项目集的核构造go函数的过程：若[BX,b]Ikernel

X{XTXN}

则go(I,X)kernel:=[BX,b]项目[BX,b]把b传播给[BX,b]。

若[BC,b]Ikernel

且

CAAXP

则[AX,a]go(I,X)

aFIRST(b)

若，则[AX,a]中的a是自生的；若=，则[AX,a]中的a=b是传播的。*rm12项目[S´S,$]中的$是自生的。算法4.11确定搜索符的方法(#是测试符号）

FORBKDO

{J´:=closure({[B,#]});IF[AX,a]J´且a#THEN

go(I,X)K中[AX,a]的

搜索符a是自生的。

IF[AX,#]J´THEN

搜索符从I中的B传播到

go(I,X)K中AX}13例示算法4.11G[S´]:S´SSL=R

SR

L*R

Lid

RL[S´S,#][SL=R,#][SR,#][L*R,=/#][Lid,=/#][RL,#]S[S´S,#][SL=R,#][RL,#]LR[SR,#]*[L*R,=/#]id[Lid,=/#]14S´S

I0SS´S

I1SL=RRLLI2SR

RI3L*R*I4Lid

idI5=SL=RI6RL*RI7RLLI8*idRSL=RI9L*idI53-4根据（2）得到的信息，开始，给每个核项目加上自生的搜索符；然后，反复传播搜索符，直到每个核项目的搜索符不再增大为止。$==$$$$$$==$$$$154.8

LR分析方法对二义文法的应用

E→E＋E|E*E|(E)|id

(4.25)E´EEE+EEE*EE(E)EidE´EEE+EEE*EEE(E)EE+EEE*EE(E)Eid(Eididid(+EE+EEE+EEE*EE(E)EidEEE+EEE+EEE*E16

LR(k)和LL(k)的比较1.A12LL(k)根据FIRST(i)确定使用哪条产生式；而LR(k)是在识别出整个后,再往后看k个符号,然后确定使用哪条产生式。wAwA17

LL(k)文法都是LR(k)文法。2.都能用形式化方法实现；3.非LR结构例：L={wwR

w{a,b}*}G[S]:SaSabSb4.LR(k)分析用手工构造是不可能的。类

Pascal语言的LR(1)分析表，估计要数千个状态；由于有软件工具，LR分析受到广范重视。184.9

分析器的生成器Yacc

一.用生成器Yacc构造翻译器的过程

Yacc编译器yacc源程序translate.yy.tab.cC编译器y.tab.ca.outa.out源程序输出19二.Yacc源程序有三部分组成

声明

％％

翻译规则

％％

C写的支持例程

三.例4.21台式计算器

G[E]:EE+TTTT*FFF(E)digit

读入一个整表达式，计算它的值并输出。20%{#

include<ctype.h>%}%tokendigit%%line:

expr´\n´{printf(“%d\n”,$1);};expr

:expr´+´term{$$=$1+$3;}:term;21term

:

term´*´facter{$$=$1*$3;}

:

facter

;facter

:

´(´expr´)´{$$=$2;}: