計算機編譯原理課后習題及答案詳細解析在此深情而熱烈的感謝沈仲秋同學的大力支持和幫助，同時希望本文檔對各位有些幫助。1、畫出編譯程序的總體結構圖，簡述其部分的主要功能。［答案］編譯程序的總框圖見下圖。圖編譯程序的總體結構圖其中詞法分析器，又稱掃描器，它接受輸入的源程序，對源程序進行詞法分析，識別出一個個的單詞符號，其輸出結果上單詞符號。語法分析器對單詞符號串進行語法分析（根據語法規則進行推導或歸納），識別出程序中的各類語法單位，最終判斷輸入串是否構成語語義分析及中間代碼產生器，按照語義規則對語法分析器歸納出（或推導出）的語法單位進行語義分析并把它們翻譯成一定形式的中間優化器對中間代碼進行優化處理。一般最初生成的中間代碼執行效率都比較低，因此要做中間代碼的優化，其過程實際上是對中間代碼目標代碼生成器把中間代碼翻譯成目標程序。中間代碼一般是一種與機器無關的表示形式，只有把它再翻譯成與機器硬件相關的機器能表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進展狀況。編譯程序各個階段所產生的中間結果都記錄在表格出錯處理程序對出現在源程序中的錯誤進行處理。如果源程序有錯誤，編譯程序應設法發現錯誤，把有關錯誤信息報告給用戶。編譯程2、計算機執行用高級語言編寫的程序有哪些途徑?它們之間的主要區別是什么？［答案］計算機執行用高級語言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic之類的語言，屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語言進行全盤翻譯，將其變為機器代碼，而是每讀總而言之，是邊翻譯邊執行。像C,Pascal之類的語言，屬于編譯型的高級語言。它們的特點是計算機事先對高級語言進行全盤翻譯，將其全部變為機器代碼，再統.文法G［S］為：S->Ac|aBA->abB->bc寫出L(G［S］)的全部元素。［答案］S=>Ac=>abc或S=>aB=>abc所以L(G［S］)={abc}.文法G［N］為：N->D|NDD->0|l|2|34|5|67|8|9G［N］的語言是什么？［答案］G［N］的語言是V+.V={0,1,2,3,4,5,6,7,8,9)N=>ND=>NDD….=>NDDDD...D=>D D.已知文法G［S］：SfdABAfaA|a ebB問：相應的正規式是什么？G［S］能否改寫成為等價的正規文法？［答案］正規式是daa*b*；相應的正規文法為(由自動機化簡來)：G［S］:S-dAA-a|aBB-aBa|b|bCC-bCb也可為(觀察得來)：G［S］:SfdAA-a|aA|aBB-bBe.已知文法G［Z］：Z->aZb|ab寫出L(G［Z］)的全部元素。［答案］Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G［Z］)={ab|n>=l}nn.給出語言{abc|n>=l,m>=0}的上下文無關文法。nnm［分析］本題難度不大，主要是考上下文無關文法的基本概念。上下文無關文法的基本定義是:A->B,AGVn,BG(VnUVt)*,注意關鍵問題［答案］構造上下文無關文法如下：S->AB|AA->aAb|abB->Bc|c［擴展］凡是諸如此類的題都應按此思路進行，本題可做為一個基本代表。基本思路是這樣的:nnmm要求符合abc,因為a與b要求個數相等，所以把它們應看作一個整體單元進行,而c做為另一個單位，初步產生式就應寫為S->AB,.寫一文法，使其語言是偶正整數集合。要求：(1)允許0開頭：(2)不允許0開頭。［答案］(1)允許0開頭的偶正整數集合的文法，注意：0E->NT|G|SFMT->NT|GN->0|l|2|34|5|67|8|9D->0|2|4|6|8G->2|4|6|8S->NSIeF->1||2|34|5|6|7|89M->MO|0(2)不允許0開頭的偶正整數集合的文法不是正數。E->NT|DT->FT|GN->D|1|3|5,7|9D->2|4|6|8F->N|0G->D|0.已知文法G：E->E+T|E-T|TT->T*F|T/FFF->(E)|i試給出下述表達式的推導及語法樹(l)i;(2)i*i+i(3)i+i*i(4)i+(i+i)［答案］(1)(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i).為句子i+i*i構造兩棵語法樹，從而證明下述文法G［〈表達式>］是二義的。《表達式》->《表達式〉(運算符》《表達式)|(〈表達式))|i〈運算符)->+|-|*|/［答案］可為句子i+i*i構造兩個不同的最右推導：最右推導1

〈表達式〉=＞〈表達式〉〈運算符〉〈表達式〉=＞〈表達式〉〈運算符〉i=＞〈表達式〉*i=＞〈表達式〉〈運算符〉〈表達式〉*i=＞〈表達式〉〈運算符〉i*i=＞〈表達式〉+i*i=>i+i*i最右推導2〈表達式〉=＞〈表達式〉〈運算符〉〈表達式〉〈表達式〉=＞〈表達式〉〈運算符〉〈表達式〉=＞〈表達式〉〈運算符〉=＞〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉=＞〈表達式〉〈運算符〉=＞〈表達式〉〈運算符〉=＞〈表達式〉〈運算符〉〈表達式〉〈運算符〉i〈表達式〉*i=＞〈表達式〉〈運算符〉i*i=＞〈表達式〉=＞〈表達式〉〈運算符〉i*i=＞〈表達式〉+i*i=>i+i*i所以，該文法是二義的。9.文法G［S］為:S-＞Ac|aBA-＞abB-＞bc該文法是否為二義的？為什么？［答案］對于串abc(l)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導所以，該文法是二義的。.考慮下面上下文無關文法：S->SS*|SS+|a(1)表明通過此文法如何生成串aa+a*,并為該串構造語法樹。G［S］的語言是什么？［答案］(1)此文法生成串aa+a*的最右推導如下：S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)該文法生成的語言是即加法和乘法的逆波蘭式，.令文法G［法為:E->E+T|E-TT->T*F|T/F|FF->(E)|I證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。［答案］此句型對應語法樹如右，故為此文法一個句型。或者：因為存在推導序列：E=>E+T=>E+T*F,所以E+T*F句型。此句型相對于E的短語有:E+T*F；相對于T的短語有T*F,直接短語為：T*F。句柄為：T*F。T?F.已知文法法G：EfET+|TTTF*|FF-F'Ia試證：FF-~*是文法的句型，指出該句型的短語、簡單短語和句柄。［答案］該句型對應的語法樹如下：ETIf*fP,F3,該句型相對于E的短語有FF"*；相對于T的短語有FF"*,F;相對于F的短語有F*;F簡單短語有F;F.;句柄為F.一個上下文無關文法生成句子abbaa的推導樹如下：(1)給出串abbaa最左推導、最右推導。(2)該文法的產生式集合P可能有哪些元素？(3)找出該句子的所有短語、直接短語、句柄。［答案］(1)串abbaa最左推導:S=>ABS->aBS=>aSBBS=>aeBBS->a￡bBS=>aebbS=>aebbAa=>aebbaa最右推導：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aebbaa=>aebbaa(2)產生式有：SfABS|Aa|eA-*aB-SBBb(3)該句子的短語有alblb2a2a3、al、bl,b2、blb2、a2a3、a2；直接短語有al、bl、b2、a2；句柄是al=.給出生成下列語言的上下文無關文法。nnmm(l){abab|n>m>=0}nmmn(2){1010|n,m>=0}rr(3){WaWW屬于{0|a}*,W表示W的逆}［答案］{ababn,m>=0}S->AAA->aAb|enmmn(2){1010|n,m>=0}S->1SO|AA->OA1|er(3){WaWW屬于{0|a}*,Wr表示W的逆}S->OSO|1S1e.給出生成下列語言的三型文法。n(l){a|n>=0}nm(2){abn,m>=l}nmk(3){abc|n,m,k>=0}［答案］(1){an>=0}的三型文法為：S->aS|enm(2){abln,m>=l}的三型文法為：S->aAA->aA|bBB->bB|enmknInnmm(3){abc|n,m,k>=0}的三型文法為：A->aA|bB|cC|eB->bB|cC|eC->cC|e.構造一文法產生任意長的a,b串，使得|a|<=|b|<=2|a|其中，“|a|"表示a字符的個數；“|b字表示b字符的個數。［分析］b的個數在a與2a之間，所以應想到形如aSBS和BSaS的形式，B為1到2個b,即可滿足條件。［答案］如分析中所述，可得文法如下：S-aSBS|BSaS|eB->bb|b第1個產生式為遞歸定義，由于在第2個產生式中B被定義為1或2個b,所以第1個產生式可以保證b的個數在㈤與21al之間，而.下面的文法產生a的個數和b的個數相等的非空a,b串S->aB|bAB->bS|aBBbA->aS|bAA|a其中非終結符B推出b比a的個數多1個的串，A則反之。說明該文法是二義的。對上述文法略作修改，使之非二義，并產生同樣的語言。(略做修改的含義是：不增加非終結符。)［答案］句子aabbab有兩種不同的推導。S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbabS=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab即它可以產生兩棵不同的語法樹，故它是二義的。修改后的無二義文法如下：S->aBS|bAS|aB|bAB->aBB|bA->bAA|a.給出0,1,2,3型文法的定義。［答案］喬姆斯基(Chomsky)把文法分成類型，即0型，1型，2型和3型，0型強于1型，1型強于2型，2型強于3型。如果它的每個產生式a->0的結構是aG(VnUVt)*且至少含有一個非終結符，而PG(VnUVt)*,我們說G=(Vt,Vn,S,8)是一個0型文法也稱短語文法。一個非常重要的理論結果是，0型文法的能力相當于圖靈(Tunring)機。或者說，任何0型語言都是遞歸可枚舉如果把0型文法分別加上以下的第i條限制，則我們就得i型文法為：G的任何產生式a->0均滿足a|<=|0|；僅僅S-的例外，但S不得出現在任何產生式的右部。G的任何產生式為A->B,AGVn,PG(VnUVt)*G的任何產生式為A->aB或A->a,其中A,BGVn1型文法也稱上下文有關文法。這種文法意味著，對非終結符進行替換時務必考慮上下文，而且，一般不允許替換成空串。2型文法對非終結符進行替換時無須考慮上下文，文法也稱線性文法。1.構造正規式1(0|1)*101相應的DFA。先構造NFA重新命名，令AB為B、AC為C、ABY為DD02.將下圖確定化:重新命名，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。01SABACBBDECFFDFECEFFFDFA：

013.把下圖最小化:答案初始分戈U彳等廠[口；老冬態組（OJ,mE2冬態組（In2只寸m歸冬冬者組進行審交s{1J2m3,35}巨u{o,1,3,5}TTn{Om1,3,5}JW{O}n JS^3~￡1,2j3?「bOmUto],所以不導新分龍U■a.n1= 3, ￡4},d2qa5]對CLm2,3,5}迸行市占：,-,d5jBu{4}{Z_3}but1,2^3=5].古紀得新分卻n2= {◎}, <4}, {1.5}, {2,3}￡1. 5】=ufl.5J{2』3}、u□,3},型吠態2不口供態3不等價-￡Xri3M{O}, f21, {3}, <4J. {L, 5}5^是尾^信^^戈U丁刁、DFA=4.構造一個DFA,它接收￡={0,1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規式和正規文法。［答案］按題意相應的正規表達式是0*(0|10)*0*或0*(100*)*0*構造相應的DFA,首先構造NFA為用子集法確定化iiilii「rrirTinn{x,0,1,3,Y}（0,l,3,Y）{2}123{0,l,3,Y）（0,l,3,Y）{2}223⑵/34/{1,3,Y）{1,3,Y）{2}4135.給出下列文法所對應的正規式：S->OA|1BA->1S|1B->OS|O［答案］解方程組S的解：S=OA|1BA=1S|1B=OS|0將A、B產生式的右部代入S中S=01S|01|10S|10=(01|10)S|(01|10)所以:S=(01,10)*(01110)6.為下邊所描述的串寫正規式，字母表是{a.b}.a)以ab結尾的所有串b)包含偶數個b但不含a的所有串c)包含偶數個b且含任意數目a的所有串d)只包含一個a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串［答案］注意正規式不唯一(a|b)*ab(bb)*(a*ba*ba*)*b*ab*(a|b)*ab(a|b)*f)b*a*7.請描述下面正規式定義的串.字母表S={0,1}.0*(10+)*0*(0|1)*(00|11)(01)*l(0|1)*0［答案］a)每個1至少有一個0跟在后邊的串b)所有含兩個相繼的0或兩個相繼的1的串c)必須以1開頭和0結尾的申8.構造有窮自動機.a)構造一個DFA,接受字母表b)構造一個DFA,接受字母表c)構造一個NFA,接受字母表d)構造一個NFA,接受字母表換為等價的一可DFA.以及最小狀態DFA［答案］b)一{0,1}上的以01結尾的所有串{0,1}上的不包含01子串的所有串.{x,y}上的正規式x(x|y)*x描述的集合{a,b}上的正規式(ab|a)*b+描述的集合并將其轉「o戶c)DFANFA：DFA［答案］可通過消結法得出正規式R=(01)*((00|1)(01)*|0)也可通過轉換為正則文法，解方程得到正規式。10.已知正規式：(1)((a|b)*aa)*b；(2)(a|b)*b.試用有限自動機的等價性證明正規式(1)和(2)是等價的，并給出相應的正規文法。［分析］基本思路是對兩個正規式，分別經過確定化、最小化、化簡為兩個最小DFA,如這兩個最小DFA一樣，也就證明了這兩個正規式是等價

［答案］狀態轉換表1abX1241234124Y12341234124Y121Y1234124Y狀態轉換表2aB1 232233_23ab1239423aa由于2與3完全一樣，將兩者合并，即見下表而對正規式(2)可畫NFA圖，如圖所示。abX121212Y121212Y12Y1212Ya1bJ. 23_2 23可化簡得下表得DFA圖兩圖完全一樣，故兩個自動機完全一樣，所以兩個正規文法等價。對相應正規文法，令故為：A->aA|bB|bB->aA|bB|b即為S->aS|bS|B,此即為所求正規文法。A對應1,B對應2四1.文法S->a|'l(T)T->T,S|S(1)對(a,(a,a)和(((a,a)/，(a)),a)的最左推導。(2)對文法G改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。(3)經改寫后的文法是否為LL(1)的？給出它的預測分析表。(4)給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。［答案］⑴對(a,(a,a)的最左推導為：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=〉(a,(S,S))=>(a,(a,S))=>(a,(a,a))對(((a,a)J,(a)),a)的最左推導為：S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),",S),S)=>(((a,a)/，(T)),S)=>(((a,a),',(S)),S)=>(((a,a),",(a)),S)=>(((a,a),,(a)),a)(3)改寫文法為：0)S->as->"S->(T)T->SN2N2->,SN2N2->e對左部為N2的產生式可知:FIRST(->,SN2)={,}FIRST(->￡)="}FOLLOWN2)={)}({,}n{)}=0所以文法是LL（1）的。可見輸入串（a,a）#是文法的句子。.已知文法G[A]如下，試用類C或類PASCAL語言寫出其遞歸下降子程序.（主程序不需寫）G[A]:A-[BB-X]{A}Xf（a|b）{a|b}[答案]不妨約定:在進入一個非終結符號相應的子程序前，已讀到一個單詞.word：存放當前讀到的單詞，GetsymO為一子程序，每調用一次，完成讀取?單詞的工作。error。為出錯處理程序.FIRSTS）為終結符A的FIRST集.類C程序如下:

.文法：S->MH|aH->LSo|eK->dMLeL->eHfM->K|bLM判斷G是否為LL(1)文法，如果是,構造LL(1)分析表。［答案］源文法G展開為：0)S->MHS->aH->LSoH->￡K->dMLK->￡L->eHfM->KM->bLM；===：1.■I 一>>■_—二1二匚-」二二L一1.一I—s-2??????????—由預測分析表中無多重入口判定文法是LL(1)的。4.設有文法G[A]的產生式集為：A^BaClCbBB-*Ac|cC-*Bb|b試消除G[A]的左遞歸。[答案]提示：不妨以A、B、C排序.先將A代入B中，然后消除B中左遞歸：再將A、B代入C中。再消除C中左遞歸。最后結果為:G[A]:A-BaC|CbBB-CbBcB'cB'B'faCcB'|eC-cB'bC'|bC'C'fbBcB'bC'|e五1、對于文法S(L)aLL,S|S(1)給出句子(a,((a,a),(a,a)))的一個最右推導，并指出右句型的句柄:(2)按照(1)的最右推導，說明移進一歸約分析器的工作步驟。［答案］(1)S=>(L)=>(L,S)=>(L,(D)=>(L,(L,S))=>(L,(L,(L)))=>(L,(L,(L,S)))=>(L,(L,(L,a)))=>(L,(L,(S,a)))二〉(L, (L, (a, a))) =>(L,(S, (a,a)))=>(L, ((L),(a,a)))TOC\o"1-5"\h\z=> (L, ((L, S), (a, a))) => (L, ((L, a), (a, a)))二> (L, ((S, a), (a, a)))二)(L, ((a, a), (a, a)))=> (S, ((a, a), (a, a))) => (a, ((a, a), (a, a)))(注：句柄下面有下劃線)(2)

步驟棧輸入動作1(a,((a,a),(a,a)))#移進24(a,((a,a),(a,a)))*移進34(a,((a,a),(a,a)))#歸約，S->a4#(S,((a,a),(a,a)))#"I約.l+s5f(L,((a,a),(a,a)))#移進6f(L,((a,a),(a,a)))f移進L#(L,((a,a),(a,a)))#移進8#(L,?a.a),(a.a)))#移進9#(L,((a,a),(a,a)))#"I約.104(L,((S,a),(a,a)))#歸約，L玲S11#(L,((L,a),(a,a)))#移進12#(L,((L,ah(a,a)))#移進13#(L((L,a).(a,a)))#歸約，S->a14#(L,((L,S),(a,a)))#歸約，L1L,S15#(L,((L),(a,a)))#移進16*（L（<L）.(a.a-：#歸約，S今（L）17fd,(s,(a,a)))#歸約，L—S18*(L,(L,(a,a)))#移進19i(L,(L,(a,a)))#移進20#(L,(L,(a,a)))l移進21#(L,(L.(a,a)))#歸約，S-a22#(L,(L,(S,a)))#歸約，LfS1\一“一，一，一I」 、'、一 I」 ??? I

34#(L)歸約,S-?(L)35fS接受2、已知文法G［S］為：Sa|'l(T)TT,S|S(1)計算G［S］的FIRSTVT和LASTVTo(2)構造G［S］的算符優先關系表并說明G［S］是否未算符優先文法。⑶計算G［S］的優先函數。(4)給出輸入串(a,a)#和(a,(a,a))#的算符優先分析過程。［答案］(1)FIRSTVT和LASTVT|FIRSTVTLASTVT12__IIa、,、(a、\)Li__、d、J(,、a、"、)(2)算符優先關系a()**a>>(*=)>>

a()9.S212221T331131(3)對應的算符優先函數為:步驟棧優先關系當前符號剩余輸入串移進或歸勢1(a,a)#移進2*((?aa,a)#移進3#(aa4-,9a)>歸約4*(F(*,a)>移進5#(F,A)f移進(4)句子(a,a)#分析過程如下:6#(F,aA>))#歸約r#(F,F,?)#歸約8*(F(=))移進9*(F))>#歸約10#F#=#*接受句子(a,(a,a))分析過程如下:

步驟棧優先關系-2一IW符號剩余輸入申移進或歸約1*千(a.(a,a))#移進2*((?aa,(a,a))#移進3#(aa丸9(a,a))#歸約4*(F9(a,a))#移進5*(F,■:(a,a))#移進6#(F,((4aa,a))#移進#(F,(aa—a))#歸約8#(F,(F?9a))#移進9HF,(F,,?aa))1移進10#(F,(F.aa>))：)#歸約11#(F,(F.F,?))#打約12#(F,(F(=)))#移進13f(F,(F))?)UI約14#(F,F,?)歸約15*(F(=))移進16*(F))》#歸約17#F#=#接受(1)給出(a,(a,a))和(a,a)的最右推導和規范歸約過程。(2)將(1)和題2中的(4)進行比較給出算符優先歸約和規范歸約的區別。［答案］(a,(a,a))的最右推導過程：S=>(=>(T,(T,a))=>(T,(S,a))=>(T,(a,(a,a))的最右推導過程：S=>(T)=>(注：句柄下面有下劃線)(a,(a,a))的規范歸約過程。T)=>(T,S)=>(T,(T))=>(T,(T,S))a))=>(S,(a,a))(注：句柄下面有下劃線)(T,S)=>(T,a)=>(S,a)=>(a,(a,a))步驟棧輸入動作1(a,(a,a))#移進2#(a,(a,a))#移進3f(a,(a,a))#歸約，S->a4#(S,(a,a))#歸約,L-S5i(T,(a,a))#移進6#(T,(a,a))#移進7#(T.(a,a))f移進；8#(T.(a,a))1仃約,S玉—9#(T,(S.a))#歸約,T->S10i(T,(T,a))#移進111(T,(T,a))#移進rt(T,(T,a))1歸約,S->a13f(T,(T,S))4歸約，TTT,S14#(T,(T))1移進 .15t(T.(T))#歸約，S-XT)16#(T,S)4移進17#(T,S)歸約，TTT,S18#(T)歸約,S—(T)19#S接受

步驟棧輸入動作1*(a,a)i移進2#(a,a)*移進3#(a,a)#歸約，SJa(a,a)的規范歸約過程。4#(S,a)#歸約，T玲S5#(T,a)#移進6?(T,a)#移進r(XT,a)#UI約.S3a8#(T,S)#歸約，T玲T,S9?(T)#移進10#(T)歸約，ST(T)11fS#接受1IIi+*1()(2)算符優先文法在歸約過程中只考慮終結符之間的優先關系從而確定可歸約串，而與非終結符無關，只需知道把當前可歸約串歸約為某一個非終結符，不必知道該非終結符的名字是什么，因此去掉了單非終結符的歸約。規范歸約的可歸約串是句柄，并且必4、有文法G［S］：SVVT|ViTTF|T+FF)V*((1)給出(+(i(的規范推導。(2)指出句型F+Fi(的短語，句柄，素短語。G［S］是否為OPG?若是，給出(1)中句子的分析過程。［答案］(1)S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)句型F+Fi(的語法樹：短語：F,F+F,(,F+Fi(句柄：F素短語：((3)FIRSTVT和LASTVT(2)算符優先關系因為該文法是OP,同時任意兩個終結符的優先關系唯一，所以該文法為OPG。

(3)(+(i(的分析過程步驟棧優先關系當前符號剩余輸入(移進或歸約1#<(((+(i(#移進2#((4++(i(#歸約3#F+(i(f移進4#F++市((i(l移進5#F+((>ii(#歸約6#F+F+>ii(1歸約-1F*1(1移進8#Fii?((f移進9#Fi((>#歸約10#FiF歸約11#F#=#接受5、試為下列各文法建立算符優先關系表。［答案］算符優先關系我如下:truefalsenotandor()true>>false>not**>and*or*>*(**<*=)>><1、已知文法:A->aAd|aAb|e，判斷該文法是否SLR(1)文法，若是構造相應分析表，并對輸入串ab#給出分析過程。［答案］(1)拓廣文法(O)S->A(1)A->aAd(2)A->aAb(3)A->e(1)

FOLLOW(A)={d,b,#}對于狀態IO：FOLLOW(A)D{a}=?對于狀態II：FOLLOW(A)D{a}=?因為，在DFA中無沖突的現象，所以該文法是SLR(l)文法。(3)SLR(1)分析表(4)串ab#的分析過程步驟狀態棧102023023402355012,設文法G為SAABA|e⑴證明它是LR(1)文法;

(2)構造它的LR(1)分析表；(3)給出輸入符號串abab的分析過程。［答案］(1)拓廣文法G':(0)S'S(1)SA(2)ABA(3)AeFIRST(A)={e,a,b}FIRST(B)={a,b}構造的DFA如下：(4)BaB(.?.該文法是LR(1).?.該文法是LR(1)文法。狀態ActionGotoaBSAB0S4S5r31231acc2rl3S4S5r3634S4S5L5r5r5r56r2Lr4r4r4(3)輸入串abab的分析過程為:步驟狀態棧符號棧當前字符剩余字符串動《(1)0abab#移進(2)01?abab#移進(3)045?abab#歸約B-^b■，(4)"017IfaBab#歸約B->aB(5)03招ab#移進(6)034帕ab移進(7)0345?Bab*歸約B->b(8)0317IBaB歸約B玲aB(9)033IBB門約A->C(10)0336IBBA#仃約a+BA(11)036IBA*仃約A-BA(12)02?A#歸約S—A(13)01ISacc3、考慮文法SAS|bASA|a(1)構造文法的LR(O)項目集規范族及相應的DFAo(2)如果把每一個LR(0)項目看成一個狀態，并從每一個形如Ba-XP的狀態出發畫一條標記為X的箭弧刀狀態B aX?(3)構造文法的SLR分析表。(4)對于輸入串bab,給出SLR分析器所作出的動作。(5)構造文法的LR(1)分析表和LALR分析表。［答案］(1)令拓廣文法G'為(O)S'S(1)SAS(2)Sb(3)ASA(4)Aa其LR(0)項目集規范族及識別該文法活前綴的DFA如下圖所示：FOLLOW(S)=(#,a,b}FOLLOW(A)={a,b)(2)顯然，對所得的NFA求e閉包，即得上面的LR(O)項目集，即DFA中的狀態。故此NFA與(a)中DFA是等價的。(3)文法的SLR分析表如下：

狀態actiongotoAbSA0S4S3121S4S3acc652S4S3L23r2r2r24r4r4r45S4/r3S3/r3T26S4S365S4/rlS3/rlRl65因為15中：FOLLOW(A)Cl{a,b}#①，17中：FOLLOW(B)n{a,b}W①所以，該文法不是SLR(1)文法。或者：從分析表中可看出存在歧義，所以該文法不是SLR(1)文法。(4)對于輸入串bab,SLR分析器所作出的動作如F：步驟狀態棧符號棧當前字符剩余字符申動《(1)0#babf移義(2)03*ba歸約S(3)01*Sab#移立(4)014#Sab*歸約;(5)015#SAb歸約A(6)021Ab移式(7)0A2b3#Abi歸約S(8)027*ASI歸約S(9)01#S接另(在第5個動作產生歧義)(b)LR(l)項目集族為:10:SJ?S,#S?AS,#a|bS?SA,abIl:S,S?AS?A,a|bS,b,#|a|bA,a,abS,AS,a|bA,a,a|bS,b,aIb12:SA?S,#|a|b13:Sb?,#|a|bS?b,#|abS,AS,#|a|b14:Aa,,aIbA,SA,aIbA,a,a|b15:ASA?,a|b16:AS?SA,S,a|bA,SA,abS,AS,a|bA?a,a|bS?b,abS,AS,a|bA,SA,a|bS,b,a|bA,a,a|b17:SAS,,abAS,A,aIbA,SA,a|bA ,a,a|bS,AS,a|bS ,b,a|b??T6狀態集中存在“歸約一一移進”沖突，故無法構造LR(1)分析表，因而也就無法構造LALR分析表。4、對下面的文法:S->UTa|TbT->S|Sc|dU->US|e判斷是否為LR(0),SLR⑴，LALR(1),LR(1),說明理由，并構造相應的分析表。［答案］(1)拓廣文法：(O)S'->s(l)S->UTa(2)S->Tb(3)T->S

(4)T->Sc(5)T->d(6)U->US(7)U->e(2)構造識別LR(0)項目的DFA如下:因為II、18中存在沖突，所以該文法不是LR(0)文法。因為FOLLOW(S)={#,c,a,b,d,e},FOLLOW(T)={a,b},FOLLOW(U)={d,e}Il中FOLLOW(T)Cl{c}=0>18中FOLLOW(U)D{c}=①，FOLLOW(T)D{c}=中，FOLLOW(T)nFOLLOW(U)=II、18中沖突解決，所以該文法是SLR(1)文法。FIRSTFOLLOWSe,da,b,d,e,#,cTe,da,bUed,e構造識別LR⑴項目的DFA如下:因為不存在沖突，所以該文法是LR(1)文法。其中12、19可合并，Ill,113可合并，15、110可合并，16、114可合并，112、116可合并，17、115可合并，合并后無沖突，所以

ACTIONGOTO狀態abCdeSTU0S5S41321r3S6acc2S10S48L93Sil4r75r56r4S12SI38r3r3S14r6r69S10S4815910r5r511r2r2r212rlrlrl13r2r214r1r115SI6SI316rlrl

ACTIONGOTO狀態dbcdeST0S5,10SI131r3S6acc2,9S5,10S487,153Sll,134r7r75,10r5r56.14r4r47,15SI2,16Sil,138r3r3S6,14r6r611,13r2r2r2r2r212,16rlrlrlrlrl產生式語義規則L—>Eprint(E.va1)E->E+TE.val：=e'.va1+T.va1ifTE.val:=T.va1T->T*FT.va1:=T.va1*F.va1rfFT.va1:=F.valFf⑻F.val:=E.va1F->digitF.val:=(iigit.lexval七1、對于輸入的表達式(4*7+1)*2,根據下表的語法制導定義建立一棵帶注釋的分析樹。val:表示非終結符的整數值，綜合屬性,lexval是單詞digit的屬性語法制導定義［答案］

S.val=5.625)；S-*L.L|LL-LB|BB-0|1［答案］val為綜合屬性，代表值屬性語法制導定義產生式語義規則s+lAL?S.val:=L*.val+L:.val/2d0"S—LS.val:=L.val

L"BL.val:=L*.val*2+B.valL.length:=Ll.length^lL1BL.val:=B.valL.length:=lB今0B.val:=0B->1B.val:=l3,結果為整數，否則為EfE+T|TTfnum.num|num給出語法制導定義確定每個子表達式的類型。［答案］設type是綜合屬性，代表各非終結符的“類型”屬性|產生式語義規則E今E'+TIF(El.type=integer)and(T.type=integer)TEE.type:=integerELSEE.type:=realjE^TE.type:=T.typeT-^num.numT.type:=realT-^numT.type:=integer

［產生式語義規則S->EprintE.codeE-^E1+TIF(El.type=integer)and(T.type=inte{beginE.type:=integerE.code=，+'|區code||T.code;endELSEbeginE.type:=realIFEl.type=integerTHENbeginEl.type:=realEl.val:=inttoreal(El.val)4,利用下列文法E-E+T|TT-?num.numnum把表達式翻譯成前綴形式，并且決定類型。試用一元運算符inttoreal［答案］把整型值轉換為相等的實型值，以使得前綴表為綜合屬性，代表各非終結符的代碼屬性type為綜合屬性，代表各非終結符的類型屬性inttoreal把整型值轉換為相等的實型值vtochar將數值轉換為字符串語法制導定義設code

El.code=vtochar(KI.val)endIFT.type:=integerTHENbeginT.type:=realT.val:=inttoreal(T.val)T.code=vtochar(T.val)endE.code=，+'||Ei.code1|T.code;EndE-?TE.type:=T.typeE.val:=T.valE.code=vtochar(E.val)T->dldi.mnT.type:=realT.val:=nujn.num.lexvalT.code=vlochar(T.val)T-^mmT.type:=integerT.val:=nu]ft.lexvaT.code=vtochar(T.val)、請按語法制導的定義，將后綴表達式翻譯成中綴表達式。注意，不允許出現冗余括號，后續表達式的文法如下：E-EE+E-EE*E~id［答案］

1產生式語義規則S—EprintE.codeE-*EiEa+E.code=Ei.code|T+'||E:.code;E.op=>+'E—E&*IFE-op='+'ANDE：.op='+'THENE.code=*(*||Ei.code|「11'('1|E加co(ELSEIFEi.op='+'THENE.code="||Ei.codeIT)1IT*,||E2.co<ELSEIFE2.op='+'THENE.code=Ei.code|TITC1|E2.codeI：ELSEE.code=Ei.code|T**||Ej.code11;E-*idE.code:=id.lexeme;6、有文法：S-(L)|aLfL,S|S給此文法配上語義動作子程序(或者說為此文法寫一個語法制導定義)，它輸出配對括號的個數。如對于句子［答案］拓展文法：加入新開始符號s'和產生式S'-S設num為綜合屬性，代表值屬性語法制導定義產生式語義規則S'—Sprint(S.num)S-*(L)S.num:=L.nujn+1S-*aS.num:=0L-LI,SL.nun:=L1.nunt+S.numL-*SL.num:=S.num7、假設變量的說明是由下列文法生成的：DfiLLf,iL|:TT-integerreal1）建立一個語法制導定義，把每一個標志符的類型加在符號表中2）為1）構造一個預翻譯程序［答案］Dtype為綜合屬性，代表類型屬性，函數addtype實現向符號表中i對應項填類型信息。語法制導定義產生式語義動作D-iLD.Type:=L.Typeaddtype(i.entry,D.type)L-*,1L1L.Type:=L*.Typeaddtype(i.entry,L.type)l-*：tL.type:=T.typeT-*integerT.type:=integerT—realT.type:=realb）采用遞歸下降分析法編寫預翻譯程序:ProcedureD;beginiflookahead=idthenbeginmatch(id);D.type=L;addtype(id.entry,D.type)endelseerrorendFunctionL:DataType;beginiflookahead=','thenbeginmatch(\ ;iflookahead=idthenbeginmatch(id);L.Type=L;addtype(id.entry,L.type);return(L.type)endelseerrorendelseiflookahead='：'thenbeginmatch(i:9);L.Type=T;return(L.Type)endelseerrorendFunctionT:DataType;beginiflookahead=integerthenbeginmatch(integer);return(integer)endelseiflookahead=realthenbeginmatch(real);return(real)endelseerrorend8、文法G的產生式如下：Sf(L)|aL-L,S|S①試寫出一個語法制導定義，它輸出配對括號個數；②寫一個翻譯方案，打印每個a的嵌套深度。如((a),a),打印2,1［答案］①為S,L引入綜合屬性num,代表配對括號個數;

語法制導定義產生式語義動作D-iLD.Type:=L.Typeaddtype(i.entry,D.type)L-,iLIL.Type:=Ll.Typeaddtype(i.entry,L.type)L-*：TL.type:=T.typeT-integerT.type:=integerT-*realT.type:=real②引入繼承屬性f,代表嵌套深度s'Ts.f：=o}sSf'('{L.f:=S.f+1;}L')，S->a{print(S.f);}L->{Ll.f:=L.f;}LI,{S.f:=L.f}SL->{S.f:=L.f;}S9、對下面的文法，只利用綜合屬性獲得類型信息。D-*L,id|LL-TidT-*int|real［答案］D-L,idD.type:=L.typeaddtype(id.entry.L.type)D—LD.type:=L.typeL-*TidL.type:=T.typeaddtype(id.entry.T.type)T-intT.type:=integerT—realT.type:=real10+形成的。當兩個整數相加時,結果為整數，否則為E-TRR—+TR|eT—num.num|numa）給出語法制導定義確定每個子表達式的類型。b）把表達式翻譯成前綴形式，并且決定類型。試用一元運算符inttoreal把整型值轉換為相等的實型值［答案］a）設type是綜合屬性，代表各非終結符的“類型”屬性，設in是繼承屬性，翻譯方案［產生式語義規則E-TR{R.i:=T.type){E.Type:=R.s)R~+TRI{IF(R.i=integer)and(T.type=integer)THENRI.i:=integerELSERI.i:=real}{R.s:=Rl.s}R-*e{R.s：=R.i)T—?num.numT.type:=realT-*numT.type:=integer1a和b的每一次出現所應用的說明。programm(input,output);proceduren(u,v,x,y:integer);varm:recordm,n:intergerend;n:recordn,m:intergerend;beginwithmdobeginm:=u;n:=vend;withndobeginm:=x;n:=yend;writein(m.m,m.n,n.m,n.n)end;beginm(1,2,3,4)end.［答案］圖中用藍色數字下標相應標明。programml(input,output);procedurenl(u,v,x,y:integer);varm2:recordm3,n2:intergerend;n3:recordn4,m4:intergerend;beginwithm2dobeginm3:=u;n2:=vend;withn3dobeginm4:=x;n4:=yend;writein(m2,m3,m2.n2,n3.m4,n3.n4)end;beginml(1,2,3,4)end.2、當一個過程作為參數被傳遞時，我們假定有以下三種與此相聯系的環境可以考慮，下面的Pascal程序是用來說明這一問題的。一種是詞法環境(lexicalenvironment),如此這樣的一個過程的環境是由這?的各標識符的聯編所構成；一?種是傳遞環境(passingenvironment),是由這一過程作為參數被傳遞之處的各標識符的聯編所構成；另一種是活動環境(activationenvironment),是由這一過程活動之處的各標識符的聯編所構成。試考慮在第(11)行上的作為一個參數被傳遞的函數f。利用對于f的詞法環境、傳遞環境和活動環境，在第(8)行上的非局部(a)圖示出每個過程的活動記錄。(b)試為此程序畫出活動樹。(c)試給出程序的輸出。programparam(inout,output);procedureb(functionh(n:integer):integer)varm:integerbeginm:=3;writein(h(2))end{b}procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nend{f};procedurer;varm:integer;beginm:=7;b(f)end{r};beginm:=0;rend{c};begincend.［答案］(a)詞法環境傳遞環境活動環境(b)活動樹(c)詞法環境：2；傳遞環境：9；活動環境：5o3、己知程序段：BEGINintegeri;read(i);write(^value^^,func(i));...ENDintegerprocedurefunc(N)integerN；BEGINIFN==0THENfunc=l;ELSEIFN==l,THENfunc=l；ELSEfunc=N*func(N-l)END;求當輸入i=3時，本程序執行期間對運行棧的存儲分配圖。［答案］varx,y；4、某語言允許過程嵌套定義和遞歸調用(如Pascal語言)，若在棧式動態存儲分配中采用嵌套層次顯示表display解決對非局部PROCEDUREP；vara;PROCEDUREq；varb：BEGIN{q}b：=10；END{q};PROCEDUREs;varc,d；PROCEDUREr;vare,f;BEGIN{r}callq；END{r}；BEGIN{s}callr；END{s}；BEGIN{p}calls;END{p}；

BEGIN{main}callp；END{main}.［答案］5、試問下面的程序將有怎樣的輸出？分別假定：(a)傳值調用(call-by-value)；

(b)引用調用(call-by—reference)； (c)復制恢復(copy-restore)； (d)傳名調用(call-by-name)°programmain(input,output);procedurep(x,y,z);beginy：=y+1;end;begina:=2;b:=3;p(a+b,a,a);printaend.［答案］.傳地址：所謂傳地址是指把實在參數的地址傳遞給相應的形式參數。在過程段中每個形式參數都有一對應的單元，稱為式單元。形式單元將用來存放相應的實在參數的地址。當調用一個過程時，調用段必須領先把實在參數的地址傳遞到一個為被調段可以拿得到的地方。當程序控制轉入被調用段之后，被調用段首先把實參地址捎進自己相應的形式單元中，過程體對形式參數任何引用1或賦值都被處理成對形式單元的間接訪問。當調用段工作完畢返回時，形式單元(它們都是指示器)所指的實在參數單就持有所指望的值。.傳結果：和“傳地址”相似(但不等價)的另一種參數傳遞力法是所謂“傳結果”。這種方法的實質是，每個形式參數對有兩個申元，第1個單元存放實參的地址，第2個單元存放實參的值。在過程體中對形參的任何引用或賦值都看成是對它的第2單元的直接訪問。但在過程工作完畢返回前必須把第2個單元的內容行放到第1個單元所指的那個實參單元之中。.傳值：所謂傳值，是一種簡單的參數傳遞方法。調用段把實在參數的值計算出來并存放在一個被調用段可以拿得到的地方。被調用段開始丁作時，首先把這些值抄入形式中元中，然后就好像使用局部名一樣使用這些形式單元。如果實在參數不為指器，那末，在被調用段中無法改變實參的值。.傳名：所謂傳名，是一種特殊的形——實參數結合方式。解釋“傳名”參數的意義：過程調用的作用相當于把被調用段過程體抄到調用事現的地方，但把其中任一出現的形式參數都替換成相應的實在參數(文字替換)。它與采用“傳地址”或“傳值的方式所產生的結果均不相同。(a)2；(b)8；(c)7；(d)9.九1、翻譯算術表達式a*-(b+c)為a)一棵語法樹b)后綴式c)三地址代碼［答案］a)語法樹：b)后綴式：abc+uminus*c)三地址代碼：tl:=b+ct2:=-tlt3:=a*t22.翻譯算術表達式-(a+b)*(c+d)+(a+b+c)為a)四元式b)三元式c)間接三元式［答案］先寫出三地址代碼為：tl:=a+bt2:=-tlt3:=c+dt4:=t2*t3t5:=a+bt7:=t4+t6a）：對應的四元式為:oparglarg2result(0)+abtl(1)uminustlt2（2）+cdt3(3)*t2t3t4(4)+abt5(5)+r5IIct6(6)+IIt4IIt6t7b）：對應的三元式為:oparglarg2(0)+ab(1)U*inus(0)(2)+cd(3)*(1)(2)1(4)+ab(5)+(4)c(6)+(3)(5)c）：對應的間接三元式為:statementOParglarg2(0)1515+ab(1)1616umirms15(2)1717+cd(3)1818*1617(4)1519+15c(5)1920+1819(6)20WHILE(A<B)DOIF(C<D)THENX:=Y+Z;的四元式表示。[答案]100IFA<BGOTO102101GOTO107102IFC<DGOTO104103GOTO100104T:=Y+Z105X:=T106GOTO100107,,,,.將下列賦值語句譯成三地址代碼。A[i,j]:=B[i,j]+C[A[k,lH+D[i+j][答案]til:=i*20tl2:=tll+jtl3:=A-84;tl4:=4*tl2tl5:=tl3[tl4]//A[i,j]t21:=i*20t22:=t21+jt23:=B-84;t24:=4*t22t25:=t23[t24]//B[i,j]t31:=k*20TOC\o"1-5"\h\zt33 := A-84t34 := 4*t32t35 := t33[t34] //A[k, 1]t36 := 4*t35t37 := C-4t38 := t37[t36] //C[A[k, 1]]t41 := i+jt42 := 4*t41t43 := D-4t44 := t43[t42] //D[i+j]tl:=t25+t38t2:=tl+t44t23[t24]:=t2.寫出for語句的翻譯方案。［答案］

1產生式動作S->forEdoSIS.begin:=newlabelS.first:=newtempS.last:=newteapS.curr:=newtempS.code:=gen(S.first E.init)11gen(S.last“尸”E.final)11gen(**ifMS.first S.last"goto'11gen(S.curr"尸"s.first)11gen(S.begin":")11gen(°if"S.curr S.Last"goto'I|S1.code|gen(S.curr:=succ(S.curr))||gen(44gotoMS.begin)E-^v:=initi