杭電編譯原理試卷三及復習資料

試卷（三一、選擇下面說正確的是A一個正規(guī)文法也一定是二型文法一個二型文法也一定能有一個等價的正規(guī)文法文法G[A]A→bA→ABB→AbB→a是A)二型文法正規(guī)文法下面說正確的()lex一個詞法分析器yacc一個語法分析器的生成器一個LR（）文法合并同心集后如果不是LALR(1)法必定存在(B)移進--歸約沖突歸約--歸約沖突PL/0語言編程序使用遞歸子程序法進行語法分析，他的文法必須滿(A)ALL（1）文法BSLR(1)文法二、問答問答第（6分試對repeatx:=buntilor(b<aandb=d)的四元式序列給出第四區(qū)段應回填的指令地址，并指出真假出口鏈和鏈頭及回填的次序。應回填的值回的次序x:=bifb>a()()()()ifb<a()()()()ifgoto()()()()解：

真鏈頭E.true=真出口鏈()真出口鏈()假鏈頭假出口鏈()應回填的值

回填的次序

真鏈頭E.true=x:=bifb>a(8(6)(4)(ifgoto(6)(2)(1)(if((5)(1)(

真出口鏈()假鏈頭E.false=7假出口鏈()/9問答第2題分)某語言的拓廣文法為(0)S→SSDd|εB→Ba|證明G不文法而是SLR(1)文法，請給出分析表。解：拓廣文法G'增加產(chǎn)生式S'在項目集I0：有移進項目D→·d歸約項目D和B存在移進歸約和歸約-約沖突，所以G不是文法。若產(chǎn)生式排序為：(0)S'SSDdDεB→BaB→G的LR(0)項目集族及識別活前綴DFA如圖：識別G活綴的DFA/9由產(chǎn)生式知：Follow(S)={#}Follow(D)=Follow(B)=,#}在中Follow(D)∩xgnzgp7=∩lbbmvvb=Follow(B)∩gp2nbin={,#}∩p7oc7wf=Follow(D)∩Follow(B)=∩{a,#}=在中Follow(S)所以在I0中移進歸約和歸歸約沖突可以由Follow集決,以G是文,構(gòu)造的分析表如下表。分析表問答第3題分給出文法G[S]的LR(1)目集規(guī)范族中I0項目集的全體項目。為：VA→b(S)|εI0:/9解：I0:問答第4題分文法及其分表如下，請給出對串的分析過程。G[M]:1)S→VdB2)→e3)ε4)B→a5)→Bda6)B→解：對串dada#分析過程如下表對輸入串dada#分析過程步驟

狀態(tài)文符剩輸入棧號棧符

動作0dada#0240245#Vdada#0246#VdB02467#VdBd

用Vε歸約移進移進用→a歸移進移進/9024678#VdB0246#S

用→Bda歸用S→VdB歸約接受問答第5題分(1)給出下列示意程序中當程序執(zhí)到D過調(diào)用A過程執(zhí)A過體時）的棧式存儲分配布局和用顯表時A過最新活記錄的內(nèi)容。說表全局的用。示意程序為：varx;A;varbegin(*A*)(*A*);B;n=7;vare,g;D;varbegin(*D*)callA;;(*D*)begin(*B*)callD;;(*B*)begin(*main*)read(x);callB;end.(*main*)解）示意程序中當程序執(zhí)行到過調(diào)A程后（即執(zhí)行A程體時）的棧式存儲分配布局和用Display顯表時棧中過程最新活動記錄的內(nèi)容如下圖。棧式存儲分配布局和棧中過程最新活動記錄的內(nèi)容/9（2）表全局Display的用是：·Display表作用是對嵌套過程語言實現(xiàn)對非局部變量的引用而設置的依存放著包圍它的外過程的最新活動記錄的基地址值由于，嵌套層次為i+1程中的非局部變量可能在i局變量的引用是通它的Display表素d[i]d[i-1]d[0]而得包圍它的外過程的最新活動記錄的基地址SP，再加上變量在該過程（第i層的偏移量。如若非局部變量a是第i層那么引用，首先從當前棧頂過程的表中元素d[i]中出存放的第i層新活動記錄基地址值后加上所在過第i）的偏移量，就得到的存放地址。全存放本過程表起始地址，其作用是把Display地作連接數(shù)據(jù)之一，如過程P1調(diào)過程時，這時先從的局到的Display表始地址，然后從P1的Display中自底向上地抄錄I2個單元（I2為的層數(shù)）再添上進入P2后新建立的P2的sp值就構(gòu)成了的Display表問答第分給出問答第題PL/0示程序編譯到過體時表內(nèi)。其中TABLE表的格式可為下表。表格式：levelvaladr解：問答第5題PL/0示意程序編譯到D過體時的內(nèi)容如下表。表內(nèi)容/9由于A并列過程，當編譯到B過時A程體已經(jīng)編譯結(jié)束A所義的標識符不會再被使用，所以由B過定的標識符覆蓋。問答第7題（6）按指定類型給出下列語言的文法。L1={candbm|n}用規(guī)文法。L2={1nbmcm|n>0m用型文法（1解：描述L1語言的正規(guī)文法如下：S→cA→dDD→bD|ε（2解：描述L2語言的二型文法如下：S→AB→0A1|0a1→bBc|ε問答第8題（5）文法G[S]：→SdTT→T<G|GG→(S)|試給出句型(SdG)<a短語、簡單直)語、句柄和最左素短語。解：句型(SdG)<a短語：）、SdG、G、簡單直接短語G、句柄：G最左素短語：問答第9題（5）給出正規(guī)式R＝（aba*）等的NFA/9abab問答第1題分將下圖的確化為。解：用子集法確定化如下表II

I

狀態(tài){X,0,1,3}{2,3,Y}{2,3,Y}{2,3,Y}{1,3}{Y}{1,3}{2,Y}{2,Y}{1,3}{Y}{Y}確定化后如下圖

XY問答第題分將文法G[S]改為等價的G'[S]，使不含左遞歸和左公共因子。：S→B]|AS解：文法改寫為等價的不含左遞歸和左公共因子G'[S]為：S→[AA→B]A→SA′|→aBB問答第1題分)判下面文法是否為LL(1)文法，若是，請構(gòu)造相的LL(1)分表。S→aDD→STe|εT→bMM→bH/9H→M|ε解：文法的集FOLLOW非終結(jié)符集{a}D，ε}

FOLLOW集{#，b}{#，b}