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

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

回填的次序

真鏈頭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)文法，請(qǐng)給出分析表。解：拓廣文法G'增加產(chǎn)生式S'在項(xiàng)目集I0：有移進(jìn)項(xiàng)目D→·d歸約項(xiàng)目D和B存在移進(jìn)歸約和歸約-約沖突，所以G不是文法。若產(chǎn)生式排序?yàn)椋?0)S'SSDdDεB→BaB→G的LR(0)項(xiàng)目集族及識(shí)別活前綴DFA如圖：識(shí)別G活綴的DFA/9由產(chǎn)生式知：Follow(S)={#}Follow(D)=Follow(B)=,#}在中Follow(D)∩mgaqgqo=∩muucsiu=Follow(B)∩aggsuka={,#}∩ocgwooe=Follow(D)∩Follow(B)=∩{a,#}=在中Follow(S)所以在I0中移進(jìn)歸約和歸歸約沖突可以由Follow集決,以G是文,構(gòu)造的分析表如下表。分析表問答第3題分給出文法G[S]的LR(1)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。為：VA→b(S)|εI0:/9解：I0:問答第4題分文法及其分表如下，請(qǐng)給出對(duì)串的分析過程。G[M]:1)S→VdB2)→e3)ε4)B→a5)→Bda6)B→解：對(duì)串dada#分析過程如下表對(duì)輸入串dada#分析過程步驟

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

動(dòng)作0dada#0240245#Vdada#0246#VdB02467#VdBd

用Vε歸約移進(jìn)移進(jìn)用→a歸移進(jìn)移進(jìn)/9024678#VdB0246#S

用→Bda歸用S→VdB歸約接受問答第5題分(1)給出下列示意程序中當(dāng)程序執(zhí)到D過調(diào)用A過程執(zhí)A過體時(shí)）的棧式存儲(chǔ)分配布局和用顯表時(shí)A過最新活記錄的內(nèi)容。說表全局的用。示意程序?yàn)椋簐arx;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*)解）示意程序中當(dāng)程序執(zhí)行到過調(diào)A程后（即執(zhí)行A程體時(shí)）的棧式存儲(chǔ)分配布局和用Display顯表時(shí)棧中過程最新活動(dòng)記錄的內(nèi)容如下圖。棧式存儲(chǔ)分配布局和棧中過程最新活動(dòng)記錄的內(nèi)容/9（2）表全局Display的用是：·Display表作用是對(duì)嵌套過程語言實(shí)現(xiàn)對(duì)非局部變量的引用而設(shè)置的依存放著包圍它的外過程的最新活動(dòng)記錄的基地址值由于，嵌套層次為i+1程中的非局部變量可能在i局變量的引用是通它的Display表素d[i]d[i-1]d[0]而得包圍它的外過程的最新活動(dòng)記錄的基地址SP，再加上變量在該過程（第i層的偏移量。如若非局部變量a是第i層那么引用，首先從當(dāng)前棧頂過程的表中元素d[i]中出存放的第i層新活動(dòng)記錄基地址值后加上所在過第i）的偏移量，就得到的存放地址。全存放本過程表起始地址，其作用是把Display地作連接數(shù)據(jù)之一，如過程P1調(diào)過程時(shí)，這時(shí)先從的局到的Display表始地址，然后從P1的Display中自底向上地抄錄I2個(gè)單元（I2為的層數(shù)）再添上進(jìn)入P2后新建立的P2的sp值就構(gòu)成了的Display表問答第分給出問答第題PL/0示程序編譯到過體時(shí)表內(nèi)。其中TABLE表的格式可為下表。表格式：levelvaladr解：?jiǎn)柎鸬?題PL/0示意程序編譯到D過體時(shí)的內(nèi)容如下表。表內(nèi)容/9由于A并列過程，當(dāng)編譯到B過時(shí)A程體已經(jīng)編譯結(jié)束A所義的標(biāo)識(shí)符不會(huì)再被使用，所以由B過定的標(biāo)識(shí)符覆蓋。問答第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短語、簡(jiǎn)單直)語、句柄和最左素短語。解：句型(SdG)<a短語：）、SdG、G、簡(jiǎn)單直接短語G、句柄：G最左素短語：?jiǎn)柎鸬?題（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]改為等價(jià)的G'[S]，使不含左遞歸和左公共因子。：S→B]|AS解：文法改寫為等價(jià)的不含左遞歸和左公共因子G'[S]為：S→[AA→B]A→SA′|→aBB問答第1題分)判下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相的LL(1)分表。S→aDD→STe|εT→bMM→bH/9H→M|ε解：文法的集FOLLOW非終結(jié)符集{a}D，ε}

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