資源描述:
《編譯原理復(fù)習(xí)例題》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、編譯原理復(fù)習(xí)例題(有些內(nèi)容沒有覆蓋,比如優(yōu)化、SLR(1)、LR(1)、LALR(1)等。但要求至少要按照作業(yè)題的范圍復(fù)習(xí)。)一選擇題1.編譯的各階段工作都涉及。[A]詞法分析[B]表格管理[C]語法分析[D]語義分析2.型文法也稱為正規(guī)文法?!A]0[B]1[C]2[D]33.文法不是LL(1)的?!A]遞歸[B]右遞歸[C]2型[D]含有公共左因子的4.文法E→E+E
2、E*E
3、i的句子i*i+i*i有棵不同的語法樹?!A]1[B]3[C]5[D]75.文法S→aaS
4、abc定義的語言是。[A
5、]{a2kbc
6、k>0}[B]{akbc
7、k>0}[C]{a2k-1bc
8、k>0}[D]{akakbc
9、k>0}6.若B為非終結(jié)符,則A→a.Bb為。[A]移進(jìn)項(xiàng)目[B]歸約項(xiàng)目[C]接受項(xiàng)目[D]待約項(xiàng)目7.同心集合并可能會產(chǎn)生新的沖突。[A]二義[B]移進(jìn)/移進(jìn)[C]移進(jìn)/歸約[D]歸約/歸約8.代碼優(yōu)化時(shí)所依據(jù)的是。[A]語法規(guī)則[B]詞法規(guī)則[C]等價(jià)變換規(guī)則[D]語義規(guī)則9.表達(dá)式a-(-b)*c的逆波蘭表示(@為單目減)為。[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-
10、*10.過程的DISPLAY表是用于存取過程的。[A]非局部變量[B]嵌套層次[C]返回地址[D]入口地址-8-二填空題1.詞法分析階段的任務(wù)式從左到右掃描 字符流 ,從而逐個(gè)識別一個(gè)個(gè)的單詞 。2.對于文法G[E]:E→T
11、E+TT→F
12、T*FF→P^F
13、PP→(E)
14、i,句型T+T*F+i的句柄是 。3.最右推導(dǎo)的逆過程稱為規(guī)范歸約,也稱為最左歸約。4.符號表的每一項(xiàng)是由名字欄和兩個(gè)欄目組成。在目標(biāo)代碼生成階段,符號表是的依據(jù)。三判斷題(認(rèn)為正確的填“T”,錯(cuò)的填“F”)【】1.同心集的合并有可
15、能產(chǎn)生“歸約/歸約”沖突?!尽?.一個(gè)文法所有句子的集合構(gòu)成該文法定義的語言?!尽?.非終結(jié)符可以有綜合屬性,但不能有繼承屬性。【】4.逆波蘭表示法表示表達(dá)式時(shí)無需使用括號?!尽?.一個(gè)有窮自動機(jī)有且只有一個(gè)終態(tài)。【】6.若過程p第k次被調(diào)用,則p的DISPLAY表中就有k+1個(gè)元素。四解答題1.給定文法G和句型(T+F)*i+T,G:E→E+T
16、TT→T*F
17、FF→(E)
18、i(1)畫出句型的語法樹;(2)寫出句型的全部短語、簡單短語和句柄。解:(略)2.設(shè)有文法G:S→S+S
19、S*S
20、i
21、(S)。(
22、1)對于輸入串i+i*i給出一個(gè)最左推導(dǎo);(2)該文法是否是二義性文法?請證明你的結(jié)論。解:(1)i+i*i的最左推導(dǎo):S=>S+S=>i+S=>i+S*S=>i+i*S=>i+i*i(2)該文法是二義性的。因?yàn)閷τ诰渥觟+i*i可以畫出兩棵語法樹(語法樹略)。3.給出語言{ambmcn
23、m≥1,n≥0}的上下文無關(guān)文法(2型)。-8-解:G:S→AB
24、AA→aAb
25、abB→cB
26、c4.給出語言{akbmcn
27、k,m,n≥1}的正規(guī)文法(3型)。解:G:A→aA
28、aBB→bB
29、bCC→cC
30、c5.將文
31、法G改寫成等價(jià)的正規(guī)文法(3型)。G:S→dABA→aA
32、aB→bB
33、b解:G:S→dAA→aA
34、aBB→bB
35、b6.構(gòu)造一文法產(chǎn)生任意長的a,b串,使得
36、a
37、≤
38、b
39、≤2
40、a
41、其中,“
42、a
43、”和“
44、b
45、”分別表示串中的字符a和b的個(gè)數(shù)。解:b的個(gè)數(shù)在a的個(gè)數(shù)和其2倍之間,串的結(jié)構(gòu)形如aSBS和BSaS,其中B為1或2個(gè)b。故得文法G:S→aSBS
46、BSaS
47、εB→b
48、bb7.設(shè)有字母表{a,b}上的正規(guī)式R=(ab
49、a)*。(1)構(gòu)造R的相應(yīng)有限自動機(jī);解:0123baaεε-+(2)構(gòu)造R的相應(yīng)確
50、定有限自動機(jī);解:將(1)所得的非確定有限自動機(jī)確定化εab-01131221+3ab-8--+013123+12312313+13123012aaba-+++(3)構(gòu)造R的相應(yīng)最小確定有限自動機(jī);解:對(2)得到的DFA化簡,合并狀態(tài)0和2為狀態(tài)2:12aab-++(4)構(gòu)造與R等價(jià)的正規(guī)文法解:令狀態(tài)1和2分別對應(yīng)非終結(jié)符B和AG:A→aB
51、a
52、εB→aB
53、bA
54、a
55、b
56、ε可化簡為:G:A→aB
57、εB→aB
58、bA
59、ε8.寫出如圖所示的自動機(jī)描述的語言的正規(guī)式1324babab-+0aa+解:abb
60、*
61、abb*aa*b
62、aaa*b9.寫出在{a,b}上,不以a開頭,但以aa結(jié)尾的字符串集合的正規(guī)式(并構(gòu)造與之等價(jià)的最簡DFA)。解:依題意,“不以a開頭”,則必以b開頭,又要“以aa結(jié)尾”,故正規(guī)式為:b(a
63、b)*aa(構(gòu)造與之等價(jià)的最簡DFA,此略)-8-10.寫一個(gè)LL(1)文法G,使其語言是L(G)={ambnc2n
64、m>=0,n>0}并證明文法是LL(1)。解:文法G(S):S?aS
65、EE?bE’E’?Ecc
66、ccSelect(S?aS)∩