編譯原理復(fù)習(xí)例題

1、編譯原理復(fù)習(xí)例題(有些內(nèi)容沒有覆蓋，比如優(yōu)化、slr（1）、lr（1）、lalr（1）等。但要求至少要按照作業(yè)題的范圍復(fù)習(xí)。)一 選擇題1編譯的各階段工作都涉及 。a詞法分析 b表格管理 c語(yǔ)法分析 d語(yǔ)義分析2 型文法也稱為正規(guī)文法。a 0 b 1 c 2 d 33 文法不是ll(1)的。a遞歸 b右遞歸 c2型 d含有公共左因子的4文法ee+e|e*e|i的句子i*i+i*i有 棵不同的語(yǔ)法樹。a 1 b 3 c 5 d 75文法 saas|abc 定義的語(yǔ)言是 。aa2kbc|k>0 bakbc|k>0 ca2k-1bc|k>0 dakakbc|k>06若b為非終

2、結(jié)符，則 aa.bb 為 。a移進(jìn)項(xiàng)目 b歸約項(xiàng)目 c接受項(xiàng)目 d待約項(xiàng)目7同心集合并可能會(huì)產(chǎn)生新的 沖突。 a二義 b移進(jìn)/移進(jìn) c移進(jìn)/歸約 d歸約/歸約8代碼優(yōu)化時(shí)所依據(jù)的是 。a語(yǔ)法規(guī)則 b詞法規(guī)則 c等價(jià)變換規(guī)則 d語(yǔ)義規(guī)則9表達(dá)式a-(-b)*c的逆波蘭表示（為單目減）為 。aa-bc* babc*- cab- dabc-*10過程的display表是用于存取過程的 。a非局部變量 b嵌套層次 c返回地址 d入口地址二 填空題1詞法分析階段的任務(wù)式從左到右掃描 字符流 ，從而逐個(gè)識(shí)別 一個(gè)個(gè)的單詞 。2對(duì)于文法ge：et|e+t tf|t*f fpf|p p(e)|i，句型t+t*

3、f+i的句柄是 。3最右推導(dǎo)的逆過程稱為 規(guī)范歸約 ，也稱為 最左歸約 。4符號(hào)表的每一項(xiàng)是由名字欄和 兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是 的依據(jù)。三 判斷題（認(rèn)為正確的填“t”，錯(cuò)的填“f”）【 】1同心集的合并有可能產(chǎn)生“歸約/歸約”沖突?！?】2一個(gè)文法所有句子的集合構(gòu)成該文法定義的語(yǔ)言?！?】3非終結(jié)符可以有綜合屬性，但不能有繼承屬性?！?】4逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)?！?】5一個(gè)有窮自動(dòng)機(jī)有且只有一個(gè)終態(tài)?！?】6若過程p第k次被調(diào)用，則p的display表中就有k+1個(gè)元素。四 解答題1給定文法g和句型(t+f)*i+t, g: ee+t | t tt*f |

4、f f(e) | i （1）畫出句型的語(yǔ)法樹； （2）寫出句型的全部短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解：（略）2設(shè)有文法g：ss+s|s*s|i|(s)。（1）對(duì)于輸入串i+i*i 給出一個(gè)最左推導(dǎo)；（2）該文法是否是二義性文法？請(qǐng)證明你的結(jié)論。解：（1）i+i*i的最左推導(dǎo)：s => s+s => i+s => i+s*s => i+i*s => i+i*i （2）該文法是二義性的。因?yàn)閷?duì)于句子i+i*i可以畫出兩棵語(yǔ)法樹（語(yǔ)法樹略）。3給出語(yǔ)言ambmcn|m1,n0的上下文無(wú)關(guān)文法（2型）。解： g: sab|a aaab|abbcb|c4給出語(yǔ)言akbmcn|k,m

5、,n1的正規(guī)文法（3型）。解： g: aaa|ab bbb|bcccc|c5將文法g改寫成等價(jià)的正規(guī)文法（3型）。 g: sdab aaa|abbb|b解： g: sda aaa|abbbb|b6構(gòu)造一文法產(chǎn)生任意長(zhǎng)的a，b串，使得 |a|b|2|a|其中，“|a|”和“|b|”分別表示串中的字符a和b的個(gè)數(shù)。解：b的個(gè)數(shù)在a的個(gè)數(shù)和其2倍之間，串的結(jié)構(gòu)形如asbs和bsas，其中b為1或2個(gè)b。故得文法 g: sasbs|bsas|bb|bb7設(shè)有字母表a，b上的正規(guī)式r=(ab|a)*。（1）構(gòu)造r的相應(yīng)有限自動(dòng)機(jī)；解：0123baa-+（2）構(gòu)造r的相應(yīng)確定有限自動(dòng)機(jī)；解：將（1）所得的

6、非確定有限自動(dòng)機(jī)確定化ab-01131221+3ab-+013123+12312313+13123012aaba-+（3）構(gòu)造r的相應(yīng)最小確定有限自動(dòng)機(jī)；解：對(duì)（2）得到的dfa化簡(jiǎn)，合并狀態(tài)0和2 為狀態(tài)2：12aab-+（4）構(gòu)造與r等價(jià)的正規(guī)文法解：令狀態(tài)1和2分別對(duì)應(yīng)非終結(jié)符b和ag: aab|a| bab|ba|a|b|可化簡(jiǎn)為：g: aab| bab|ba|8寫出如圖所示的自動(dòng)機(jī)描述的語(yǔ)言的正規(guī)式1324babab-+0aa+解：abb*|abb*aa*b|aaa*b9寫出在a,b上，不以a開頭，但以aa結(jié)尾的字符串集合的正規(guī)式（并構(gòu)造與之等價(jià)的最簡(jiǎn)dfa）。解：依題意，“不以a開

7、頭”，則必以b開頭，又要“以aa結(jié)尾”，故正規(guī)式為：b(a|b)*aa（構(gòu)造與之等價(jià)的最簡(jiǎn)dfa，此略）10寫一個(gè)ll(1)文法g，使其語(yǔ)言是l(g)= ambnc2n | m>=0,n>0 并證明文法是ll(1)。解：文法g（s）：s ® as | ee ® bee® ecc | ccselect(s ® as)select (s ® e)= select(e® ecc)select (e® cc) =故文法為ll(1)的11將文法g改寫成等價(jià)的ll(1)文法，并構(gòu)造預(yù)測(cè)分析表。 g：ss*at|at|*at

8、t+at|+a（編寫遞歸下降子程序）解：消除左遞歸后的文法g: sats|*atss*ats|t+at|+a提取左公因子得文法g:sats|*atss*ats|t+attt|select(sats)=aselect(s*ats)=*select(sats)select(s*ats)=select(s*ats)=*select(s)=follow(s)=#select(s*ats)select(s)= select(t+at)=+select(tt)=first(t) =+select(t )=follow(t)=*,#select(tt)select(t)= 所以該文法是ll(1)文法。預(yù)測(cè)分

9、析表：*+a#ssta, ntst, nssta, n, ptta, nt, pt, p, pa, n#ok（遞歸下降子程序，略）12對(duì)文法gs: s asb | pp bpc | bqcq qa | a構(gòu)造簡(jiǎn)單優(yōu)先關(guān)系表。該文法是否是簡(jiǎn)單優(yōu)先文法？解：簡(jiǎn)單優(yōu)先關(guān)系矩陣如下：sabpqcs=a=< ><<>b<< >= <p>=q=c>>由于矩陣中有元素存在多種優(yōu)先關(guān)系，故不是簡(jiǎn)單優(yōu)先文法。13考慮文法 g: s as | b a sa | a（1）構(gòu)造文法的可歸前綴圖（活前綴的dfa）；（2）判斷文法是否是lr(0)文法

10、，并說(shuō)明理由。解：（1）可歸前綴圖（2）因?yàn)榇嬖跊_突，所以不是lr(0)文法。14文法g及其lr分析表如下，請(qǐng)給出對(duì)串dada#的分析過程。g: s vdbv ev b ab bdab 狀態(tài)actiongotodea#sbv0r3 s3  1 21   acc   2s4      3r2      4r6 s5r6 6 5r4  r4&

11、#160;  6s7  r1   7  s8    8r5  r5   解：對(duì)輸入串dada#的分析過程步驟狀態(tài)棧符號(hào)棧剩余輸入符號(hào)動(dòng)作1234567890020240245024602467024678024601#v#vd#vda#vdb#vdbd#vdbda#vdb#sdada#dada#ada#da#da#a#用v 歸約移進(jìn)移進(jìn)用b a歸約移進(jìn)移進(jìn)用b bda 歸約用s vdb 歸約接受15對(duì)傳值、傳地址和傳

12、名3種參數(shù)傳遞方法分別寫出下列程序的輸出：void p(int x, int y, int z) y *= 3;z += x;void main() int a=5, b=2;p(a*b,a,a);printf(“%dn”, a);這些參數(shù)傳遞機(jī)制如何實(shí)現(xiàn)？解：（1）傳值 5； （2）傳地址 25； （3）傳名 45（參數(shù)傳遞機(jī)制，略）16將下面程序劃分為基本塊，并畫出其程序流圖。b := 1b := 2if w <= x goto l2e := bgoto l2l1:goto l3l2:c := 3b := 4c := 6l3:if y <= z goto l4haltl4:g := g + 1h :