編譯原理-著高等教育課后答案

編譯原理習題課 敘述由下列正規(guī) 2.3續(xù)以0開頭和結(jié)尾的長度至少是2的01所有的01倒數(shù)第三位是0的01含有3個1的01含有偶數(shù)個0和偶數(shù)個1的01串(習題集 由偶數(shù)個0和偶數(shù)個1組成的所有01由偶數(shù)個0和奇數(shù)個1組成的所有01 2.4續(xù)5個元音aeio不含5個元音的任意字符：[B-DF-HJ-NP-TV-Zb-df-hj-np-z]，記為不含/，*的任意字符記為 2.4續(xù)一種答案(續(xù)123031357106678031357 2.4續(xù)一種答案(續(xù)51230313571006678031357其中double_i表示相鄰的數(shù)字是double_0-> ->… 2.4續(xù)最多只有一處相鄰數(shù)字相同的所有數(shù)字串(續(xù)double_i-> -> ->……比如double_5->no_5->no_0_5->1|no_0-1_51)(no_0-1_51)*(no_0-1_5?)|no_0-1_5no_0-5-… 2.4續(xù)一種答案(續(xù)習題集習題集 2.4續(xù)一種答案(續(xù)當出現(xiàn)0后，1只能單獨出 2.7續(xù)

ε εε

εε

ε ababbab:s->4->0->1->5->6->7->8->4->1->5->6->7->6->7->8->4->0->1->5->7->8- 2.11續(xù)NFA-ε-closure({s})={s,4,f,0,2,3,5,6,8}=ε-closure(move(A,a))=ε-closure({1})={1,5,6,8,4,f,0,2,3}Bε-closure(move(A,b))=ε-closure({7})={7,6,8,4,f,0,2,3,5}=ε-closure(move(B,a))=ε-closure({1})=ε-closure(move(B,b))=ε-closure({7})=ε-closure(move(C,a))=ε-closure({1})=ε-closure(move(C,b))=ε-closure({7})=A

b 2.11續(xù)DFA->最簡劃分為接受狀態(tài)集合F={A,B,C}和非接受狀態(tài)ssb lanj 構(gòu)造表示0，1個數(shù)都是偶數(shù)的01字符習題集 能被5整除的二進習題集 謝謝編譯原理習題課 考慮文S->L->建立句子(a,(a,a))和(a,((a,a),(a,a)))為(a)為(a)這個文法產(chǎn)生的 3.1續(xù)S

S

S a (續(xù) S S

4 4a(續(xù)描述的語 考慮文S->為句子abab以說明此文法為abab構(gòu)造對應(yīng)的最右為abab構(gòu)造對應(yīng)的分這個文法產(chǎn)生的 (續(xù)(1)(2)S=>aSbS=>aSb=>abSaSb=>abSab=>abab ε

R->R’|’R|RR|R*|(R)|a|證明該文法產(chǎn)生字母表{a,b} 3.4續(xù)1）該文法產(chǎn)生的串是字母表{a,b}R->a和R->b產(chǎn)生a,b,而a,b是{a,b}上的符號，因此是正規(guī)式R->R1*產(chǎn)生正規(guī)式α*R->(R1b,可由R->b 3.4續(xù)R=>R|R=>a|R=>a|R*=>a|b*E->E’|’T|TT->TF|FF->F*|(E)|a| 3.4續(xù)二義R

非二義

b 下面的條件語句stmt->ifexprthenstmt|matched_stmt-ifexprthenmatched_stmtelsestmt 3.5續(xù)句型ifexprthenifexprthenmatched_stmtelseifthenmatched_stmtelsestmt期望的是ifexprifexprifexpr 3.5續(xù)=>=>ifexprthenmatched_stmtelse=>ifexprthenifexprthenmatched_stmtelsestmtelse=>ifexprthenifexprthenmatched_stmtelseifexprthenelse=>ifexprthenifexprthenmatched_stmtelseifexprmatched_stmtelseifexprifexprifexpr 3.5續(xù)=>ifexprthen=>ifexprthen=>ifexprthenifexprthenmatched_stmtelse=>ifexprthenifexprthenmatched_stmtelse=>ifexprthenifexprthenmatched_stmtelseifexprmatched_stmtelseifexprifexprifexpr 消除3.1的左 S->(L)|aL->L,S|S只有直接左S->L->L’-> 構(gòu)造下面文法的LL(1)D->T->L->R-> 3.10續(xù)FIRST(D)FIRST(T)int,real}FIRST(L)={id}FIRST(R)=FOLLOW(D)=FOLLOW(L)=FOLLOW(T)={id}FOLLOW(R)={$} 3.10續(xù),$DD->D->TT->T->LL->RR->R-> 下面文法是否LL(1)S->A->B->P->Q-> 3.11續(xù)FIRST()FIRST()若*，那么FIRST(FOLLOW() 3.15續(xù)(a)棧$棧$移移歸約:S-歸約:L-移移移歸約:S- 3.15續(xù)(a)b)續(xù)上棧棧歸約:L-移移歸約:S-歸約:L移歸約:S歸約:L 3.15續(xù)(a)b)續(xù)上棧棧移$歸約:S$接 3.15續(xù)棧棧$移移歸約:S-歸約:L-移移移歸約:S-S , 3.15續(xù)SLLSLLLSS棧歸約:L-移移歸約:S-歸約移歸約:S歸約S , 3.15續(xù)LSLLSLLLSSS棧移$歸約$接 , 謝謝編譯原理習題課 (a)消除3.1的左(b)在（a）的基礎(chǔ)上構(gòu)造LL(1) S->(L)|aL->L,S|S只有直接左S->L->L’-> S->(L)|aL->SL’L’->FIRST(S)={(,FIRST(L)=FIRST(S)={(,FIRST(L’)={,,FOLLOW(S)=(FIRST(L’)-{ε})+FOLLOW(L)FOLLOW(L’)+{$}={,,),$}FOLLOW(L)={)}FOLLOW(L’)=FOLLOW(L)= (),a$SS->S->LL->L->L’->L’->L’-> 給出接收S->(L)|L->L,S| 3.16續(xù)拓展文S‘->S->(LS->L->L,L->初態(tài)：I0closure{S’·SS’->·SS->S’->·SS->·(L)S->3.16續(xù)Goto(I0,S)S->(·L)L->·S->(·L)L->·L,SL->·SS->S->S’->SGoto(I0,a)S-> 3.16續(xù)Goto(I2,L)S->(L·L->L·,Goto(I2,L->SGoto(I2,Goto(I2, 3.16續(xù)Goto(I4,))S->(L)Goto(I4,L->L,·S->S-> 3.16續(xù)Goto(I6,S)L->L,SGoto(I6,()Goto(I6,a) 3.16續(xù)S’->S’->S->S->S->(L)S’->SL->SSS->S->(·L->·L,SL->·SS->S->S->(L·)L->L·,L L->L->L,·S->S->L->L,SSS->a 3.16續(xù)SLR(1)分析表構(gòu)若A·a∈I，且goto(I,a)=J若A·I，則action[I,b若S‘S·I，則action[I,$若goto(I,B)=K，則其它為空白 3.16續(xù)狀態(tài)()a,$SL0112143456778 3.16續(xù)S->(L)|aL->L,S|SFOLLOW(S)={$}+FOLLOW(L)={$,),,}FOLLOW(L)={),,} 證明下面文法不是SLR(1)S->X->Ma|bMc|dc|bdaM->d 3.23續(xù)S->X->Ma|bMc|dc|bdaM->d存在移進-規(guī)如句子dc，當d進棧后，c，此時項目[X->d·c]要求移進，而c在FOLLOW(M)中，因此項目[Md·]要求規(guī)約 一個非LR(1)的文法如L->MLb|M->給出所有有移進-規(guī) 的規(guī)范LR(1)項集 3.26續(xù)L’->L->MLb|M->L’L’->·L,L->·MLb,L->·a,M->·, 3.26續(xù)MaL->MaL->M·Lb,L->·MLb,L->·a,M->·,L’->·L,L->·MLb,L->·a,M->·,L->a·,L’->L·,MLMaaL->M·Lb,L->·MLb,L->·a,M->·,L->ML·b,L->a·,L->MLb·,LL->ML·b,bL->MLb·, 3.26續(xù) a時存在移進-規(guī) 3.30續(xù)第二個不是LR(1)第二個文法在句子的正中心按A->b存 的項目集

S->a·Ac,$A->·bAb,cA->·b,cb

A->b·Ab, A->·bAb,A->·b,bA->A->b·Ab,A->b·,A->·bAb,A->·b,A->b·Ab,A->b·,A->·bAb,A->·b,b謝謝編譯原理習題課 的每個出現(xiàn) 。程序輸出整數(shù)programa(inputprocedureb(u,v,x,y:integer);vara:recorda,b:integerend;b:recordb,a:integerend;withadobegina:=u;b:=vend;withbdobegina:=x;b:=yend;wrin(a.a,a.b,b.a,b.b)b(1,2,3, (續(xù)withawithb

b— 考慮下面的C程char*cp1,*cp2;cp1=“12345”;cp2=“abcdefghij”;strcpy(cp1,cp2);printf(“cp1=%s\ncp2=%s\n”,cp1,}該程序經(jīng)以前的某些C編譯器編譯后，運行結(jié)果為cp1=cp2=試分析為什么cp2被修 6.2續(xù) 12345\0abcdefghij abcdefghij\0fghij typedefstructcharc1;longI;charc2;double}typedefstructcharc1;charc2;longl;doublef;}b;printf(“Sizeofdouble,long,char=%d,%d,%d\n”,sizeof(double),printf(“Sizeofa,b=%d,%d\n”,sizeof(a),}Sizeofdouble,long,char=Sizeofa,b= (續(xù)

OXXXXXXXOOOOOOOOView->DebugWindows中GCC:(GNU)3.2.2(RedHat3.2.2-5)結(jié)果為 6.3續(xù)staticstruct_a{charc1;longi;charc2;double}a={'A',1,'B',VC6下，Debug模式Memory GCC:(GNU) staticlongaa=shortbb=20;staticlongcc=30;shortdd=40;} 6.4續(xù) .version

.align.align .globl

%esp,.globl.align

$4,$40,-

.value.align

.ident"GCC:(GNU)egcs- (續(xù) .version.align

30–cc.align.globl --aa分配在靜態(tài)數(shù)據(jù)用域為本文件，生存 --bb分配在靜態(tài)數(shù)據(jù)用域為全局，可以被其他文

%esp,$4,

生存期為整個.align

)func調(diào)用期，動態(tài)置初.align

.ident"GCC:(GNU)egcs- programmain(input,vara,b:procedurep(x,y,z:y:=y+z:=z+x;a:=b:=p(a+b,a,a);printa; (續(xù)x:=5;y:=2;z:=y:=y+1;z:=z+x; 調(diào)t:=a+a=a+aa 結(jié)果a為值-結(jié)果調(diào) 結(jié)果為換名a:=a 結(jié)果為 func(i1,i2,i3)longi1,i2,i3;{longj1,j2,printf(“Addressofi1i2i3=%o,%o,%o\n”,&i1,&i2,printf(“Addressofj1j2j3=%o,%o,%o\n”,&j1,&j2,}longi1,i2,func(i1,i2,}該程序在X86/Linux上運行結(jié)果為Addressofi1,i2,i3=Addressofj1,j2,j3=從結(jié)果看func的3個形參地址逐漸升高，而3試說明為 (續(xù)i2,i3)按i3，i2，i1的順序進棧而j1,j2,j3 的順序分 printf(“%d%d} (續(xù)所以得到了三個 func(i,j,f,shorti,j;floatf,{shorti1,j1;floatf1,printf(“Addressofi,j,f,e=%o,%o,%o,%o\n”,&i,&j,&f,&e);printf(“Addressofi1,j1,f1,e1=%o,%o,%o,%o\n”,&i1,&j1,&f1,&e1);}shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=35777772536,35777772542,Addressofi1,j1,f1,e1=35777772426,35777772426,35777772424,Sizeofshort,int,long,float,double= 6.8續(xù) (續(xù)i:short->jshortintf:longdoublee:long->

ishort2字節(jié)jshort2字節(jié)f:long4字節(jié)elong4 func(c,l)charclongl;{func(c,} 6.9續(xù) .version

12(%ebp), movsbl-1(%ebp),pushl.align.globl %ebp--將老的基指針

$8, %espebp--將當

func,.Lfe1-

$4esp--分配8(%ebp),%al,-

.ident"GCC:(GNU) 1.1.2 6.9續(xù)SomeAT&TASM寄存8個32-bit寄存器操作目-1(%ebp)：基址：%ebp，偏移：-加在指令后的符號表b(byte,8-bit)l(long,32-bits)movs：符號擴展指movsbl意味著movs（from）byte（to）long；movbw意味著（from）byte（to）word；movswl意味著movs（from）wordlongMore: (續(xù)

8(%ebp),%eax--取%al1(%ebp)--取其字節(jié)值，存入分配的 12(%ebp),%eax--取 movsbl-1(%ebp),%eax--取c，并轉(zhuǎn)換成longpushl%eax

$8,

--調(diào)用 (續(xù)PASCAL允許過程嵌套，執(zhí)行時，可非全局且非局部的變量，所以需要鏈幫不允許過程嵌套，只能全局和局部變量，所以不需要鏈。 programfact(input,varf,n:functionfactor(n:integer):integer;ifn=0thenfactor:=elsefactor:=n*(factor(n-beginn:=5;f:=factor(n);write(f) 6.11續(xù)122鏈n鏈n鏈n 畫出該程序執(zhí)行的活動樹 6.12續(xù)programret(input,varf:function(integer):functiona:function(integer):varm:functionaddm(n:integer):beginreturnm+nbeginm:=0;returnaddmprocedureb(g:function(integer):begin n(g(2))f:=a; (續(xù)應(yīng)的是第(4)m。

a

b (續(xù)參考 intn;intf(intintm;m=if(m== returnn=n-1;return}}n=5;printf(“%dfactorialis}該程序的運行結(jié)果不5factorialis而0factorialis試說明原因 (續(xù)n值壓棧，因而輸出“0factorialis120” long*pshort*p,并且將第22longk改成shortk后,loop中的循環(huán)main()}long*p;longi,}}addr()longk;} (續(xù) SPARC/SUN 一個C語言{printf(“Returnfromfunc}{char }在X86/Linux操作系統(tǒng)上的運行結(jié)果如下ReturnfromSegmentationfault(core試分析為什么會出現(xiàn)這樣的運行錯誤 6.16續(xù) 本題RedHatLinux3.2.2GCC:(GNU)3.2.2下 種可能的規(guī)定.第一種是使用詞法環(huán)境,即該過程激活時的計算環(huán)境是依據(jù)其定義點的靜態(tài)作用域得到.Pascal和C我們以下面的Pascal程序為例來解釋.考慮該程序第(11)局部名m分別在第(610)和(13)行的作用域內(nèi).在這三種情 6.17續(xù)programprocedureb(functionvarm:beginm:=3; n(h(2))procedurevarm:functionf(n:integer):beginf:=m+nprocedurevarm:beginm:=7;b(f)beginm:=0;rc

(續(xù)詞法環(huán)定義點m值為0，結(jié)果為傳遞環(huán)境活動環(huán)境第4行，在b的過程體中，h(2)激活fm值為3，因此結(jié)果為 謝謝編譯原理習題課 把算術(shù)表達式–(a+b)*(c+d)+(a+b-c)翻譯 (續(xù)(a)+

(b)+*+ *+ b

+ (續(xù)ab+cd+*-t1:=a+bt2:=c+dt3:=t1*t2t4:=-t3t5:=t1+ct6:=t4+ intinta[10];while(i<=10)a[i]=} (續(xù) i10<=aiarray0=

a

i 7.2續(xù) 三地址1:ifi<=10goto2:goto3:a[i]:=4:goto5:return 修改圖7.4中計 許名字表而不是單個名字出現(xiàn)在形式為D->id:T 中P- {offset=0;D->D->T->T->T->array[num]ofT1T->↑T1

{enter(,T.type,offset);offset+=T.width;}{T.type=T.width=4;{T.type=T.width=8;{T.type=array(num.val,T1.type);T.width=num.val*T1.width;}{T.type=T.width=4; 7.4續(xù)D->ID_LIST->D- ID_LIST->

{foreachnameinidtabledooffset:=offset+T.width;end;{Init(idtable2){merge(idtable1,idtable2,idtable){add(idtable,); (a)寫出a*-(b+c)的前綴形(c)給出把表達式翻 7.5續(xù)(a)*a-E->E+T|TT->T*F|FF->-F|(E)|L->E->E1+TE->TT->T1*FT->FF->-F->F->

{printf(E.string);{E.string=“+”+E1.string+T.string;{E.string=T.string;{T.string=“*”+T1.string+F.string;{T.string=F.string;{F.string=“-”+F1.string;{F.string=E.string;{F.string=id.value; EE1or {E.place:=emit(E.place,‘:=’,E1.place,‘or’,E2.place)EE1and {E.place:=emit(E.place,‘:=’,E1.place,‘a(chǎn)nd’,E2.place)Enot {E.place:=E1.placeE(E1

{E.place:=emit(E.place,‘:=’,‘not’,E1.place)Eid1relop {E.place:=emit(‘if’,id1.place,relop.op,nextstat+3emit(E.place,‘:=’,‘0’);emit(‘goto’,nextstat+2);emit(E.place,‘:=’,‘1’)}EE

{E.place:=newtemp;emit(E.place,‘:=’,‘1’)}{E.place:=emit(E.place,‘:=’,‘0’) 7.7續(xù)EE1orE2EE1andE2EnotE1E(E1Eid1relopEE指令解釋

{emit(‘or’){emit(‘a(chǎn)nd’){emit(‘not’){{emit(‘push‘||);emit(‘push’||);emit(‘relop’||relop.op)}{emit(‘1’){emit(‘0’)or:將棧頂和次棧頂值取出,進行或操作,將結(jié)果壓棧not:將棧頂值取出,進行非操作,將結(jié)果壓棧relopop:將棧頂和次棧頂值取出,判斷他們的op關(guān)系,將結(jié)果 ifid1<id2gotogoto可以用一個ifid1>=id2 EE1orE1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code[增加:||gen(‘goto’,E1.true)]gen(E1.false,‘:’)||EE1andE1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.codeE1.code[刪去||gen(E1.true|| 7.6續(xù)EnotE1.true:=E.false;E1.false:=E.true;E.code:=E1.codeE(E1E1.true:=E.true;E1.false:=E.false;E.code:=E1.codeEid1relop ‘goto’,E.true)||gen(‘goto’,E.false)[修改為:E.code:=gen('if',id1.place,not(relop.op),id2.place,'goto',EE.code:=gen(‘goto’,EE.code:=gen(‘goto’, inti,while((i||j)&&i=

>}} 7.9續(xù)….align.globl.type

$5,-8(%ebp)

%esp,$8,

.p2align .p2align

.p2align $0,-4(%ebp) $0,- .p2align

movl-8(%ebp),%eaxmovl%eax,-4(%ebp)jmp.L2.p2align 7.9續(xù)$0,-$0,-ifi!=0,goto$0,-ifj!=0,gotogoto$5,-ifj>5,gotogotogoto.p2align movl-8(%ebp),%eaxmovl%eax,-4(%ebp)jmp.L2

%eax=ji=%eaxgoto.L2

7.11續(xù)S

M,A[ELi]ELjLM,A[ELi]ELjL 7.11續(xù) L1=>Elist12]=>Elist11,E11]=>id[E12,E11]=>=>id[id,E11]=>id[id,L11]=>L11->idE11->L11L12->idE12->L12

L11.place=‘j’;L11.offset=E11.place=L12.place=‘i’;L12.offset=E12.place=Elist11-> Elist11.place=‘i’;Elist11.ndim:=Elist12->L1->t1:=i*n2At1:=t1+it2:=A–

t:=‘t1’;m:=1+1:=2;emit(‘t1:=i*emit(‘t1:=t1+i’);Elist12.array:=‘A’;Elist12.place=‘t1’;Elist12.ndim=2L1.place:=‘t2’;emit(‘t2:=A–(n2A+1)*w’);L1.offset:=‘t3’;emit(‘t3:=t1* t3:=t1* 7.11續(xù)B[i,j],類似地 L2.place:=‘t5’L2.offset:=‘t6’;t4:=i*n2Bt4:=t4+jt5:=B–t6:=t4*A[k,1]:L3=>…=>id[id,id]L3.place:=‘t8’L3.offset:=t7:=1*t7:=t7+t8:=A–t9:=t7* 7.11續(xù)E41->

E4=>L41=>Elist41]=>id[E41]=>id[L3]=>EList41-> Elist41.array:=L41->E4->t10:=t11:=C–t12:=t10*t13:=

L41.place:=emit(‘t11:=C–L41.offset:=‘t12’;enit(‘t12:=t10*E4.place: