編譯原理期末范圍

一、填空題（每空3分，共36分）設(shè)X={ad,c}、Y={b,a}，則XY={adb,ada,cb,ca}。2.上下文無關(guān)文法G[B]=S→0|1|S0|S1生成所有無符號二進(jìn)制整數(shù)。3.設(shè)αβδ是文法G[S]的一個句型，如果且A=>β，則稱β是句型αβδ相對于A→β的直接短語（簡單短語）。4.設(shè)正規(guī)式x和y所表示的正規(guī)集分別為{ab}、{b,c}，則正規(guī)式(x|y)y所表示的正規(guī)集為{abb,abc,bb,bc,cb,cc}。5.正規(guī)式a{a|b}*定義與正規(guī)文法G[S]={S→aA|a,A→aA|bA|a|b}相同的語言。6.如果規(guī)范句型aAAbBccD的句柄為bB，則該句型的可歸前綴為aAAbB。7.表達(dá)式a*(b+c*(d+e))的逆波蘭記號為abcde+*+*。8.LR(0)文法G的產(chǎn)生式A→cA對應(yīng)的歸約項(xiàng)目為A->cA.，待約項(xiàng)目為a->c.A。9.如果算符優(yōu)先文法G中存在產(chǎn)生式A→…Bb…且a∈LASTVT(B)，則有a>b。10.設(shè)∑={a,b}，則正規(guī)式a{a|b}*所表示的正規(guī)集為∑上所有以a為首的串的集合。二、簡答題（1）寫一上下文無關(guān)文法，使得該文法生成的語言是所有能被5整除的整數(shù)。（12分）（2）已知文法G[E]={E→T|E+T|E-T,T→F|T*F|T/F,F→(E)|i}，寫出句子(i+i)/(i*i-i)的規(guī)范推導(dǎo)過程（12分）。三、把圖二表示的DFA最小化（20分）。四、根據(jù)以下文法及其LR(0)分析表完成對輸入串a(chǎn)cccd#的LR(0)分析過程。要求具體寫出狀態(tài)棧、符號棧、輸入串的變化過程及每一步的Action和Goto值（20分）。LR(0)分析表文法：狀態(tài)ActionGotoabcd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6→EE→aAE→bBA→cAA→d或S→AB(4分)A→aA|a(3分)B→bB|b(3分)（2）所有以a為首的串的正規(guī)式為a(a|b)*（4分）改寫的正規(guī)文法為：G=({S,A},{a,b},{S→aA,A→ε,A→aA,A→bA},S)（6分）二、共20分畫出轉(zhuǎn)換過程表（每行2分，共10分）DFSA圖（6分）化簡后：三、各非終結(jié)符的FIRST集合如下：(10分，每個2分)FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝各非終結(jié)符的FOLLOW集合為：(10分，每個2分)FOLLOW(E)=｛),$｝FOLLOW(E′)=｛)，$｝FOLLOW(T)=｛＋，)，$｝FOLLOW(T′)=｛＋,)，$}FOLLOW(F)=｛*,＋，),$}四、共20分試卷二一、填空題（每空2分，共22分）詞法分析的任務(wù)是掃描源程序，根據(jù)語言的詞法規(guī)則，分解和識別出單詞，構(gòu)造符號表、常數(shù)表以及將源程序轉(zhuǎn)換成中間語言程序。語言學(xué)家喬姆斯基(Chomsky)把文法分成以下四種類型，其中正規(guī)文法能夠被有限自動機(jī)識別。令Σ={a,b}，表示{Σ上所有以a為首的串}的正規(guī)式為a(a|b)*。LL(1)文法的是自上而下的分析方法，其中第二個L表示最左推導(dǎo)。最右推導(dǎo)的逆過程最左規(guī)約。算符優(yōu)先分析法只考慮終結(jié)符之間的優(yōu)先關(guān)系。若U是文法的識別符號，則FOLLOW(U)一定包含$。若要消除U→Ux|y的左遞歸，則應(yīng)將文法改寫為U→yU’和U’→xU’|ε兩個產(chǎn)生式。將正規(guī)文法A→xA|y改寫成的正規(guī)式為A=x*y。簡單優(yōu)先分析方法中可歸約串必須為句柄二、簡答題（10分）1．構(gòu)造生成{anbm|n,m>=1}語言的文法。（5分）S→aA(1分)A→aA|B(2分)B→bB|b(2分)2．描述文法G[S]:SabS|bS|ε表示的語言（5分）三、綜合題1.(16分)文法G[E]: E→E+T|TT→T*F|FF→(E)|i寫出句子i1*i2+i3的語法樹的最左推導(dǎo)、最右推導(dǎo)畫出該句型的語法樹寫出該句子的短語、直接短語、句柄答：最左推導(dǎo)：E→E+T→T+T→T*F+T→F*F+T→i1*F+T→i1*i2+T→i1*i2+F→i1*i2+i3(2分)最右推導(dǎo)：E→E+T→E+T→E+F→E+i3→T+i3→T*F+i3→T*i2+i3→F*i2+i3→i1*i2+i3(2分)短語：i1，i2，i3，i1*i2，i1*i2+i3(2分)直接短語i1，i2，i3(2分)句柄i1(2分)2．（16分）將下面NDFSA狀態(tài)轉(zhuǎn)換圖，轉(zhuǎn)換為DFSA狀態(tài)轉(zhuǎn)換圖，并化簡。ＥＥASＢＣaba(10分)-closure(I)-closure(move(I,a))-closure(move(I,b))[S,A,C]0[B,Z]1[B,Z]1[A,C]2[A,C]2[B,Z]1化簡后1Ｅ1Ｅ02Ｃaba1Ｅ1Ｅ0ba3．(18分)設(shè)有文法：G[S]:SaBc|bABAaAb|bBb|(1)寫出每個非終結(jié)符的FIRST集和FOLLOW集；(2)判斷文法是否為LL(1)文法，若是LL(1)文法，試構(gòu)造它的分析表。答：FIRST(S)={a,b}FIRST(A)={a,b}FIRST(B)=F0LLOW(S)={$}F0LLOW(A)={a,b}所以是LL(1)文法（1分）abc$SSaBcSbABAAaAbAbBBbBB4．（18分）設(shè)有文法G[R]:Ri|(T)TT,R|R寫出非終結(jié)符R和T的FIRSTVT和LASTVT集填寫下面算符優(yōu)先關(guān)系表i（），#i（），#答案：FIRSTVT(R)={i,(}FIRSTVT(T)={i,(,,}LASTVT(R)={i,)}LASTVT(T)={),i,,}填寫下面算符優(yōu)先關(guān)系表i（），#i>>>（<<=<>）>>>，<<>>>#<<<<=概念題：1.翻譯程序：把某一種語言程序（稱為源語言程序）等價(jià)地轉(zhuǎn)換成另一種語言程序（稱為目標(biāo)語言程序）的程序。2.編譯程序：把某一種高級語言程序等價(jià)地轉(zhuǎn)換成另一種低級語言程序（如匯編語言或機(jī)器語言程序）的程序。3.解釋程序：把源語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序那么此推導(dǎo)稱為最左推導(dǎo)。9.最右推導(dǎo):在xUy=>xuy直接推導(dǎo)中，若yVT*,UVN,即U是符號串xUy中最右非終結(jié)符，則稱此直接推導(dǎo)為最右直接推導(dǎo)。若一個推導(dǎo)的每一步直接推導(dǎo)都是最右直接推導(dǎo)，那么此推導(dǎo)稱為最右推導(dǎo)。10.文法的分類及特點(diǎn):文法分為以下四類0型短語文法……對任一產(chǎn)生式α→β，都有α(VN∪VT)+，β(VN∪VT)*。α至少含有一個非終結(jié)符。1型上下文有關(guān)文法……對任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外。2型上下文無關(guān)文法……除有可能S→ε,對任一產(chǎn)生式A→δ，都有AVN，δ(VN∪VT)+3型正規(guī)文法……除S→ε外,所有產(chǎn)生式α→β的形式都為A→aB或A→a，其中AVN，BVN，aVT11.句型……如果符號串x是從識別符號推導(dǎo)出來的，即Sx，則稱x是文法G[S]的句型。開始符號S也是文法G的句型。12.句子……如果符號串x是終結(jié)符號構(gòu)成，即Sx，xVT*，則稱x是文法G[S]的句子13.語言……設(shè)S是文法G的開始符號，文法G的語言L(G)={u|S+u,uVT*}，即文法的語言是文法的所有句子構(gòu)成的集合。14.語法樹與二義性…在自然語言中，句子結(jié)構(gòu)借助一種樹形表示來進(jìn)行分析，該樹形稱為語法樹。一個文法，如果它的一個句子有兩棵或兩棵以上的語法樹，則稱此句子具有二義性。15.有窮自動機(jī)及分類：有窮自動機(jī)(也稱有限自動機(jī))作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合。有窮自動機(jī)分為兩類：確定的有窮自動機(jī)(DeterministicFiniteStateAutomata)和不確定的有窮自動機(jī)(NonDeterministicFiniteStateAutomata)。16.開始狀態(tài)集和終止?fàn)顟B(tài)集：一個非確定的有窮自動機(jī)是一個五元組，NDFA=Q，，t，Q0，F(xiàn)，其中Q為狀態(tài)的有窮非空集，為有窮輸入字母表，t為Q到Q的子集(多值映射)，Q0Q是初始狀態(tài)集，F(xiàn)Q為終止?fàn)顟B(tài)集。17.自動機(jī)的等價(jià)：如果兩個自動機(jī)M和M’識別相同的語言，即L（M）和L(M’)，稱它們是語法上等價(jià)的。19.下推自動機(jī)：是上下文無關(guān)文法的識別器。一個下推自動機(jī)由一條輸入帶,一個讀頭,一個有限控制器和一個后進(jìn)先出下推棧組成.2