编译原理-陈意云-课后答案3市公开课一等奖省赛课微课金奖课件

编译原理习题课(3)栾俊luanj@8/18/20248/18/20241luanj@第1页3.8(a)(a)消除3.1左递归

(b)在（a）基础上结构LL(1)分析表8/18/20242luanj@第2页3.8(a)(续)S->(L)|a

L->L,S|S只有直接左递归

S->(L)|a

L->SL’

L’->,SL’|ε8/18/20243luanj@第3页3.8(b)(续)S->(L)|a

L->SL’

L’->,SL’|εFIRST(S)={(,a}

FIRST(L)=FIRST(S)={(,a}

FIRST(L’)={,,ε}FOLLOW(S)=(FIRST(L’)-{ε})+FOLLOW(L)+FOLLOW(L’)+{$}={,,),$}

FOLLOW(L)={)}

FOLLOW(L’)=FOLLOW(L)={),$}8/18/20244luanj@第4页3.8(b)(续)(),a$SS->(L)S->aLL->SL’L->SL’L’L’->εL’->,SL’L’->ε8/18/20245luanj@第5页3.16给出接收文法

S->(L)|a

L->L,S|S

LR(0)活前缀DFA；而且在此基础上结构SLR(1)分析表.8/18/20246luanj@第6页3.16(续)拓展文法：

(1)S‘->S

(2)S->(L)

(3)S->a

(4)L->L,S

(5)L->S初态：I0=closure{S’->∙S}=

I0S’->∙SS->∙(L)S->∙a8/18/20247luanj@第7页3.16(续)Goto(I0,S)=Goto(I0,()=

Goto(I0,a)=I1S’->S∙I3S->a∙I2S->(∙L)L->∙L,S

L->∙SS->∙(L)S->∙a8/18/20248luanj@第8页3.16(续)Goto(I2,L)=

Goto(I2,S)=Goto(I2,()=I2Goto(I2,a)=I3I4S->(L∙)L->L∙,SI5L->S∙

8/18/20249luanj@第9页3.16(续)Goto(I4,))=

Goto(I4,,)=

I7L->L,∙SS->∙(L)S->∙aI6S->(L)∙8/18/202410luanj@第10页3.16(续)Goto(I6,

S)=Goto(I6,

()=I2Goto(I6,

a)=I3I8L->L,S∙8/18/202411luanj@第11页3.16(续)I8L->L,S∙I0S’->∙SS->∙(L)S->∙aI1S’->S∙I2S->(∙L)L->∙L,S

L->∙SS->∙(L)S->∙aI3S->a∙I4S->(L∙)L->L∙,SI6S->(L)∙S(aLSa((,I7L->L,∙SS->∙(L)S->∙aS(aI5L->S∙

8/18/202412luanj@第12页3.16(续)SLR(1)分析表结构

1)若A∙a∈I，且goto(I,a)=J，则action[I,a]=sJ

2)若A∙

∈I，则action[I,b]=rA,b∈Follow(A)

3)若S‘S∙

∈I，则action[I,$]=acc

4)若goto(I,B)=K，则GOTO[I,B]=K 5)其它为空白/error8/18/202413luanj@第13页3.16(续)状态actiongoto()a,$SL0s2s311s2s3acc2143r3r3r34s5s65r5r56r2r2r27s2s378r4r48/18/202414luanj@第14页3.16(续)S->(L)|a

L->L,S|S

FOLLOW(S)={$}+FOLLOW(L)={$,),,}

FOLLOW(L)={),,}8/18/202415luanj@第15页3.23证实下面文法不是SLR(1)文法

S->X

X->Ma|bMc|dc|bda

M->d8/18/202416luanj@第16页3.23(续) S->X

X->Ma|bMc|dc|bda

M->d存在移进-规约冲突

如句子dc，当d进栈后，面临c，此时项目[X->d∙c]要求移进，而c在FOLLOW(M)中，所以项目[M->d∙]要求规约8/18/202417luanj@第17页3.26一个非LR(1)文法以下：

L->MLb|a

M->ε

给出全部有移进-规约冲突规范LR(1)项目集8/18/202418luanj@第18页3.26(续)拓广文法：

L’->L

L->MLb|a

M->εI0

I0L’->∙L,$L->

∙MLb,$L->∙a,$M->

∙,$/a8/18/202419luanj@第19页3.26(续)I0L’->∙L,$L->

∙MLb,$L->∙a,$M->

∙,aI1

L’->L∙,$LI2L->

M∙Lb,$L->

∙MLb,bL->∙a,bM->∙,aMI3

L->a∙,$aI4L->

ML∙b,$LI5L->

M∙Lb,bL->

∙MLb,bL->∙a,bM->∙,aMI6L->a∙,baI7L->

MLb∙,$bI8L->

ML∙b,baLMI9L->

MLb∙,bb8/18/202420luanj@第20页3.26(续)I0,I2,I5面临a时存在移进-规约冲突8/18/202421luanj@第21页3.30下面哪个不是LR(1)文法？对非LR(1)文法给出全部冲突LR(1)项目集S->aAc

A->Abb|bS->aAc

A->bAb|b8/18/202422luanj@第22页3.30(续)第二个不是LR(1)文法

第二个文法在句子正中心按A->b规约，而只向后看一位是无法判断是否抵达句子中心位置存在冲突项目集：S->a∙Ac,$A->∙bAb,cA->∙b,cA->b∙Ab,cA->∙bAb,bA->∙b