編譯原理期末總復習題(含答案)編譯原理期末總復習題(含答案)編譯原理期末總復習題(含答案)xxx公司編譯原理期末總復習題(含答案)文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度第八節習題一、單項選擇題1、將編譯程序分成若干個“遍”是為了b。a．提高程序的執行效率b．使程序的結構更加清晰c．利用有限的機器內存并提高機器的執行效率d．利用有限的機器內存但降低了機器的執行效率2、構造編譯程序應掌握d。 a．源程序 b．目標語言c．編譯方法 d．以上三項都是3、變量應當c。a．持有左值 b．持有右值c．既持有左值又持有右值 d．既不持有左值也不持有右值4、編譯程序絕大多數時間花在b上。 a．出錯處理 b．詞法分析c．目標代碼生成 d．管理表格5、d不可能是目標代碼。 a．匯編指令代碼 b．可重定位指令代碼c．絕對指令代碼 d．中間代碼6、使用a可以定義一個程序的意義。a．語義規則 b．詞法規則c．產生規則 d．詞法規則7、詞法分析器的輸入是a。a．單詞符號串 b．源程序c．語法單位 d．目標程序8、中間代碼生成時所遵循的是-d。a．語法規則 b．詞法規則c．語義規則 d．等價變換規則9、編譯程序是對d。a．匯編程序的翻譯 b．高級語言程序的解釋執行c．機器語言的執行 d．高級語言的翻譯10、語法分析應遵循b。 a．語義規則 b．語法規則c．構詞規則 d．等價變換規則解答1、將編譯程序分成若干個“遍”是為了使編譯程序的結構更加清晰，故選b。2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。3、對編譯而言，變量既持有左值又持有右值，故選c。4、編譯程序打交道最多的就是各種表格，因此選d。5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，并且語義規則可以定義一個程序的意義。因此選a。7、b8、c9、d10、c二、多項選擇題1、編譯程序各階段的工作都涉及到bc。 a．語法分析 b．表格管理 c．出錯處理d．語義分析 e．詞法分析2、編譯程序工作時，通常有abce階段。 a．詞法分析 b．語法分析 語義分析 c．中間代碼生成中間代碼優化d．語義檢查 e．目標代碼生成解答1．b、c2.a、b、c、e三、填空題1、解釋程序和編譯程序的區別在于是否生成目標程序（解釋不產生目標程序，邊翻譯邊執行。2、編譯過程通?？煞譃?個階段，分別是詞法分析、語法分析語義分析中間代碼生成、代碼優化和目標代碼生成。 3、編譯程序工作過程中，第一段輸入是源程序，最后階段的輸出為目標程序程序。4、編譯程序是指將源程序程序翻譯成目標程序程序的程序。 解答是否生成目標程序2、詞法分析中間代碼生成3、源程序 目標代碼生成 4、源程序目標語言 一、單項選擇題1、文法G：S→xSx|y所識別的語言是c。 a.xyx b.(xyx)* c.xnyxn(n≥0) d.x*yx*（是指多個x）2、文法G描述的語言L(G)是指ab。 a.L(G)={α|Seq\o(\s\up3(+),\s\do1(?))α,α∈VT*} b.L(G)={α|Seq\o(\s\up3(*),\s\do1(?))α,α∈VT*}c.L(G)={α|Seq\o(\s\up3(*),\s\do1(?))α,α∈(VT∪VN*)} d.L(G)={α|Seq\o(\s\up3(+),\s\do1(?))α,α∈(VT∪VN*)} 3、有限狀態自動機能識別。 a.上下文無關文法 b.上下文有關文法c.正規文法 d.短語文法 4、設G為算符優先文法，G的任意終結符對a、b有以下關系成立。 a.若f(a)>g(b)，則a>b b.若f(a)<g(b)，則a<bc.a~b都不一定成立 d.a~b一定成立 5、如果文法G是無二義的，則它的任何句子α。 a.最左推導和最右推導對應的語法樹必定相同b.最左推導和最右推導對應的語法樹可能不同c.最左推導和最右推導必定相同d.可能存在兩個不同的最左推導，但它們對應的語法樹相同 6、由文法的開始符經0步或多步推導產生的文法符號序列是。 a.短語 b.句柄 c.句型 d.句子 7、文法G：E→E+T|TT→T*P|PP→(E)|I則句型P+T+i的句柄和最左素短語為。 a.P+T和i b.P和P+T c.i和P+T+i d.P和T8、設文法為：S→SA|AA→a|b則對句子aba，下面是規范推導。 a.SSASAAAAAaAAabAabab.SSASAAAAAAAaAbaabac.SSASAASAaSbaAbaabad.SSASaSAaSbaAbaaba9、文法G：S→b|∧(T)T→T,S|S則FIRSTVT(T)。 a.{b,∧,(} b.{b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}10、產生正規語言的文法為。a.0型 b.1型 c.2型 d.3型11、采用自上而下分析，必須。a.消除左遞歸 b.消除右遞歸 c.消除回溯 d.提取公共左因子12、在規范歸約中，用來刻畫可歸約串。a.直接短語 b.句柄 c.最左素短語 d.素短語13、有文法G：E→E*T|T

T→T+i|i句子1+2*8+6按該文法G歸約，其值為。a.23B.42c.30d.1714、規范歸約指。a.最左推導的逆過程 b.最右推導的逆過程 c.規范推導d.最左歸約的逆過程 [解答]1、選c。2、選a。3、選c。4、雖然a與b沒有優先關系，但構造優先函數后，a與b就一定存在優先關系了。所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原來的a與b之間是否存在優先關系：故選c。5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對于d，如果有兩個不同的是了左推導，則必然有二義性。故選a。6、選c。7、由圖2-8-1的語法樹和優先關系可以看出應選b。EEE+FE+TPTiP#<·+·>+<·i·>#圖2-8-1句型P+T+I的語法及優先關系8、規范推導是最左推導，故選d。9、由T→T,…和T→(…得FIRSTVT(T))={(,，)}；由T→S得FIRSTVT(S)?FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即 FIRSTVT(T)={b,∧,(,，}；因此選c。10、d11、c12、b13、b14、b二、多項選擇題1、下面哪些說法是錯誤的。 a.有向圖是一個狀態轉換圖 b.狀態轉換圖是一個有向圖c.有向圖是一個DFA d.DFA可以用狀態轉換圖表示2、對無二義性文法來說，一棵語法樹往往代表了。a.多種推導過程 b.多種最左推導過程 c.一種最左推導過程d.僅一種推導過程 e.一種最左推導過程3、如果文法G存在一個句子，滿足下列條件之一時，則稱該文法是二義文法。 a.該句子的最左推導與最右推導相同b.該句子有兩個不同的最左推導c.該句子有兩棵不同的最右推導d.該句子有兩棵不同的語法樹e.該句子的語法樹只有一個4、有一文法G：S→AB A→aAb|ε B→cBd|ε它不產生下面集合。a.{anbmcndm|n,m≥0} b.{anbncmdm|n,m>0}c.{anbmcmdn|n,m≥0} d.{anbncmdm|n,m≥0}e.{anbncndn|n≥0}5、自下而上的語法分析中，應從開始分析。a.句型 b.句子 c.以單詞為單位的程序 d.文法的開始符 e.句柄6、對正規文法描述的語言，以下有能力描述它。a.0型文法 b.1型文法 c.上下文無關文法 d.右線性文法 e.左線性文法解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e三、填空題1、文法中的終結符和非終結符的交集是。詞法分析器交給語法分析器的文法符號一定是，它一定只出現在產生式的部。2、最左推導是指每次都對句型中的非終結符進行擴展。3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、采用語法分析時，必須消除文法的左遞歸。5、樹代表推導過程，樹代表歸約過程。6、自下而上分析法采用、歸約、錯誤處理、等四種操作。7、Chomsky把文法分為種類型，編譯器構造中采用和文法，它們分別產生和語言，并分別用和自動機識別所產生的語言。解答1、空集終結符右2、最左3、自上而上自下而上4、自上而上5、語法分析6、移進接受7、42型3型上下文無關語言正規語言下推自動機有限四、判斷題1、文法S→aS|bR|ε描述的語言是(a|bc)* ()R→cS2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （）3、二義文法不是上下文無關文法。 （）4、語法分析時必須先消除文法中的左遞歸。 （）5、規范歸約和規范推導是互逆的兩個過程。 （）6、一個文法所有句型的集合形成該文法所能接受的語言。 （）解答1、對2、錯3、錯4、錯5、錯6、錯五、簡答題1、句柄 2、素短語 3、語法樹 4、歸約 5、推導[解答]1、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個終結符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個條件的樹稱之為文法G[S]的一棵語法樹。 ①每一終結均有一標記，此標記為VN∪VT中的一個符號；②樹的根結點以文法G[S]的開始符S標記；③若一結點至少有一個直接后繼，則此結點上的標記為VN中的一個符號；④若一個以A為標記的結點有K個直接后繼，且按從左至右的順序，這些結點的標記分別為X1,X2,…,XK，則A→X1,X2,…,XK，必然是G的一個產生式。4、歸約：我們稱αγβ直接歸約出αAβ，僅當A→γ是一個產生式，且α、β∈(VN∪VT)*。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。5、推導：我們稱αAβ直接推出αγβ，即αAβαγβ，僅當A→γ是一個產生式，且α、β∈(VN∪VT)*。如果α1α2…αn，則我們稱這個序列是從α1至α2的一個推導。若存在一個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。六、問答題1、給出上下文無關文法的定義。[解答]一個上下文無關文法G是一個四元式（VT,VN,S,P），其中：●VT是一個非空有限集，它的每個元素稱為終結符號；●VN是一個非空有限集，它的每個元素稱為非終結符號，VT∩VN=Φ；●S是一個非終結符號，稱為開始符號；●P是一個產生式集合（有限），每個產生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。開始符號S至少必須在某個產生式的左部出現一次。2、文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc（1）它是Chomsky哪一型文法？

（2）它生成的語言是什么？[解答]（1）由于產生式左部存在終結符號，且所有產生式左部符號的長度均小于等于產生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關文法。（2）按產生式出現的順序規定優先級由高到低（否則無法推出句子），我們可以得到：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc……于是得到文法G[S]生成的語言L={anbncn|n≥1}3、按指定類型，給出語言的文法。L={aibj|j＞i≥1}的上下文無關文法。【解答】（1）由L={aibj|j＞i≥1}知，所求該語言對應的上下文無關文法首先應有S→aSb型產生式，以保證b的個數不少于a的個數；其次，還需有S→Sb或S→bS型的產生式，用以保證b的個數多于a的個數；也即所求上下文無關文法G[S]為：G[S]：S→aSb|Sb|b4、有文法G：S→aAcB|Bd

A→AaB|c

B→bScA|b（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）寫出句子acabcbbdcc的最左推導過程?！窘獯稹浚?）分別畫出對應兩句型的語法樹，如圖2-8-2所示句柄:AaBBdSSa

A

c

B

A

a

BbScABdcb(a)SSaAcBBScABd

c(b)圖2-8-2語法樹（2）句子acabcbbdcc的最左推導如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5、對于文法G[S]：S→（L）|aS|aL→L,S|S（1）畫出句型（S,（a））的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。S（L）S（L）L，S

S

(L)Sa圖2-8-3句型（S,（a））的語法樹（1）句型（S,（a））的語法樹如圖2-8-3所示（2）由圖2-8-3可知：①短語：S、a、(a)、S,(a)、(S,(a))；②直接短語：a、S；③句柄：S；④素短語：素短語可由圖2-8-3中相鄰終結符之間的優先關系求得，即；##·（·，

·（

·a·）·）·#因此素短語為a。6、考慮文法G[T]： T→T*F|F F→F↑P|P P→（T）|i

T

T

T*F

F

↑

P

P（

T

）

T*F圖2-8-4句型T*P↑（T*F）的語法樹【解答】首先構造T*P↑（T*F）的語法樹如圖2-8-4所示。由圖2-8-4可知，T*P↑（T*F）是文法G[T]的一個句型。直接短語有兩個，即P和T*F；句柄為P。一、單項選擇題1、詞法分析所依據的是。a.語義規則 b.構詞規則 c.語法規則 d.等價變換規則2、詞法分析器的輸出結果是。a.單詞的種別編碼 b.單詞在符號表中的位置c.單詞的種別編碼和自身值 d.單詞自身值3、正規式M1和M2等價是指。a.M1和M2的狀態數相等 b.M1和M2的有向弧條數相等c.M1和M2所識別的語言集相等 d.M1和M2狀態數和有向弧條數相等4、狀態轉換圖（見圖3-6-1）接受的字集為。00

10圖3-6-1Ya.以0開頭的二進制數組成的集合b.以0結尾的二進制數組成的集合c.含奇數個0的二進制數組成的集合d.含偶數個0的二進制數組成的集合5、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此，。a.詞法分析器應作為獨立的一遍b.詞法分析器作為子程序較好c.詞法分析器分解為多個過程，由語法分析器選擇使用d.詞法分析器并不作為一個獨立的階段解答1、b2、c3、c4、d5、b二、多項選擇題1、在詞法分析中，能識別出。a.基本字 b.四元式 c.運算符d.逆波蘭式 e.常數2、令∑={a,b}，則∑上所有以b開頭，后跟若干個ab的字的全體對應的正規式為。a.b(ab)* b.b(ab)+ c.(ba)*bd.(ba)+b e.b(a|b)解答1、a、c、e2、a、b、d三、填空題1、確定有限自動機DFA是的一個特例。2、若二個正規式所表示的相同，則認為二者是等價的。3、一個字集是正規的，當且僅當它可由所。解答1、NFA2、正規集3、DFA（NFA）所識別四、判斷題1、一個有限狀態自動機中，有且僅有一個唯一終態。 （）2、設r和s分別是正規式，則有L（r|s）=L(r)|L(s)。 （）3、自動機M和M′的狀態數不同，則二者必不等價。 （）4、確定的自動機以及不確定的自動機都能正確地識別正規集。 （）5、對任意一個右線性文法G，都存在一個NFAM，滿足L(G)=L(M)。 （）6、對任意一個右線性文法G，都存在一個DFAM，滿足L(G)=L(M)。 （）7、對任何正規表達式e，都存在一個NFAM，滿足L(G)=L(e)。 （）8、對任何正規表達式e，都存在一個DFAM，滿足L(G)=L(e)。 （）解答1、2、3、錯4、5、6、7、8、正確五、基本題1、設M＝（{x,y},{a,b},f,x,{y}）為一非確定的有限自動機，其中f定義如下：f（x,a）＝{x,y} f（x,b）＝{y}f（y,a）＝φ f（y,b）＝{x,y}試構造相應的確定有限自動機M′。解答：對照自動機的定義M=(S,Σ,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，所以是一非確定有限自動機，先畫出NFAM相應的狀態圖，如圖3-6-2所示。aabbb圖3-6-2NFAMXY用子集法構造狀態轉換矩陣表3-6-3所示。IIaIb{x}{x,y}{y}{y}—{x,y}{x,y}{x,y}{x,y}將轉換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態轉換矩陣。表3-6-4狀態轉換矩陣ab0211—2222aa,bbb圖3-6-5DFAMaa,bbb圖3-6-5DFAM′021aa,bb圖3-6-6化簡后的DFAM′01將圖3-6-5的DFAM′最小化。首先，將M′的狀態分成終態組{1，2}與非終態組{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}?aa,bb圖3-6-6化簡后的DFAM′012、對給定正規式b*（d|ad）（b|ab）+，構造其NFAM；aadεεb*b*(d|ad)(b|ab)(b|ab)*Xaadεεb*b*(d|ad)(b|ab)(b|ab)*XYX123YX4135Y678(d|ad)(b|ab)(b|ab)*2εdbadabεεb|abbX4135Y2bεdbεεbabb圖3-6-7的NFAM1、構造下面文法的LL（1）分析表。D→TLT→int|realL→idRR→,idR|ε解答：LL（1）分析表見表4-3-1分析雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。FIRST（D）=FIRST（T）={int,real} FOLLOW（D）=FOLLOW（L）={#}FIRST（L）={id} FOLLOW（T）={id}FIRST（R）={，,ε} FOLLOW（R）={#}有了上面每個非終結符的FIRST集合，填分析表時要計算一個產生式右部α的FIRST（α）就不是件難事了。填表時唯一要小心的時，ε是產生式R→ε右部的一個開始符號，而#在FOLLOW（R）中，所以R→ε填在輸入符號#的欄目中。表4-3-1LL（1）分析表非終結符輸入符號intrealid，#DD→TLD→TLTT→intT→realLL→idRRR→,idRR→ε2、下面文法G[S]是否為LL（1）文法？說明理由。S

→AB|PQx A

→xy B

→bcP

→dP|ε Q

→aQ|ε解答：該文法不是LL（1）文法，見下面分析中的說明。分析只有三個非終結符有兩個選擇。1、P的兩個右部dP和ε的開始符號肯定不相交。2、Q的兩個右部aQ和ε的開始符號肯定不相交。3、對S來說，由于x∈FIRST(AB)，同時也有x∈FIRST(PQx)（因為P和Q都可能為空）。所以該文法不是LL（1）文法。3、設有以下文法：G[S]：S→aAbDe|d A→BSD|e B→SAc|cD|ε D→Se|ε（1）求出該文法的每一個非終結符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構造C[S]的LL（1）分析表。解答：（1）求文法的每一個非終結符U的FOLLOW集的過程如下：因為：①S是識別符號，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）應包含FIRST(D)∪FIRST(Ac)∪FIRST(e)∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}②又因為A→BSD和D→ε，所以FOLLOW中還包含FOLLOW(A)。因為S→aAbDe和B→SAc,所以FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}綜合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}因為A→BSD，所以FOLLOW（B）=FIRST（SD）={a,d}因為S→aAbDe|d、A→BSD|e和B→SAc|cD，所以 FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）

={e}∪{b,c}∪{a,d}={a,b,c,d,e}（2）G[S]不是LL（1）文法。因為產生式B→SAc|cD|ε中FIRST（SAc）∩FOLLOW（B）={a,d}≠?（3）構造G[S]的LL（1）分析表。按照LL（1）分析表的構造算法構造方法G[S]的LL（1）分析表如表4-3-2所示。表4-3-2G[S]的LL（1）分析表abcde#SaAbDedABSDBSDBSDeBSac/εcDSac/εDSe/εεεSe/εε4、將文法G[V]改造成為LL(1)的。G[V]：V→N|N[E]E→V|V+EN→i解答：對文法G[V]提取公共左因子后得到文法：G′[V]：V→NAA→ε|[E]E→VBB→ε|+EN→i求出文法G′[V]中每一個非終結符號的FIRST集： FIRST(V)={i} FIRST(A)={[,ε} FIRST(E)={i} FIRST(B)={+,ε} FIRST(N)={i}求出文法G′[V]中每一個非終結符號的FOLLOW集： FOLLOW(V)={#}∪FIRST(B)\{ε}∪FOLLOW(E)={#,+,]} FOLLOW(A)=FOLLOW(V)={+,,#} FOLLOW(E)=FIRST(])\{ε}∪FOLLOW(B)=FIRST(])\{ε}∪FOLLOW(E)={]} FOLLOW(B)=FOLLOW(E)={]} FOLLOW(N)=FIRST(A)\{ε}∪FOLLOW(V)={[,],+,#}可以看到，對文法G′[V]的產生式A→ε|[E]，有 FIRST([E])∩FOLLOW(A)={[}∩{+,],#}=?對產生式B→ε|+E，有FIRST(+E)∩FOLLOW(B)={+}∩{]}=?而文法的其他產生式都只有一個不為ε的右部，所以文法G′[V]是LL(1)文法。5、已知文法： G[A]： A→aAa|ε（1）該文法是LL（1）文法嗎為什么

（2）若采用LL（1）方法進行語法分析，如何得到該文法的LL（1）分析表？（3）若輸入符號串“aaaa”，請給出語法分析過程。解答：（1）因為產生式A→aAa|ε有空產生式右部，而 FOLLOW(A)={#}∪FIRST(a)={a,#}造成FIRST(A)∩FOLLOW(A)={A,ε}∩{a,#}≠?所以該文法不是LL（1）文法。（2）若采用LL（1）方法進行語法分析，必須修改該文法。因該文法產生偶數（可以為0）個a，所以得到文法 G′[A]： A→aaA|ε此時對產生式A→aaA|ε，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因而 FIRST(A)∩FOLLOW(A)={a,ε}∩{#}=?所以文法G′[A]是LL（1）文法，按LL（1）分析表構造算法構造該文法的LL（1）分析表如表4-3-3所示。表4-3-3 文法G′[A]的LL(1)分析表A#AA→aaAA→ε（3）若采用LL(1)方法進行語法分析，對符號串“aaaa”的分析過程如表4-3-4所示。表4-3-4 對符號串“aaaa”的分析過程步驟分析棧輸入串產生式/動作1#Aaaaa#A→aaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#A→aaA5#Aaaaa#匹配6#Aaa#匹配7#A#A→ε8##接受第七節習題設有文法G[S]為： S→a|b|(A)A→SdA|S完成下列算符優先關系表，見表5-7-1，并判斷G[S]是否為算符優先文法。表5-7-1算符優先關系表ab()d#a??b??(????)??d#????（2）給出句型（SdSdS）的短語、簡單短語、句柄、素短語和最左素短語。（3）給出輸入串（adb）#的分析過程。解答：（1）先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|(A)得：FIRSTVT(S)={a,b,();由A→Sd…得：FIRSTVT(A)=yho5c0z;又由A→S…得：FIRSTVT(S)?FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};由S→a|b|(A)得；LASTVT(S)={a,b,}};由A→…dA得：LASTVT(A)=4s2wuhp,又由A→S得：LASTVT(S)?LASTVT(A)，即LASTVT(A)={d,a,b,)}。構造優先關系表方法如下：①對P→…ab…，或P→…aQb…，有a?b;②對P→…aR…，而b∈FIRSTVT(R)，有a?b;③對P→…Rb…，而a∈FIRSTVT(R)，有a?b。由此得到：①由S→(A)得：(?);②由S→(A…得：(?FIRSTVT(A)，即：(?d,(?a,(?b,(?(;由A→…dA得：d?FIRSTVT(A)，即：d?d,d?a,d?b,d?(;③由S→A)得，LASTVT(A)?)，即：d?),a?),b?),)?);由A→Sd…得：LASTVT(S)?d，即：a?d,b?d,)?d;此外，由#S#得：#?#；由#?FIRSTVT(S)得：#?a,#?b,#?(；脂由LASTVT(S)?#得：d?#,a?#,b?#,)?#。最后得到算符優先關系表，見表5-7-2。表5-7-2算符優先關系表ab()d#a???b???(????)???d??????#????由表5-7-2可以看出，任何兩個終結符之間至少只滿足?、?、?三種優先關系之一，故G[S]為算符優先文法。SASASASASd（）ASd圖5-7-3句型（SdSdS）的語法樹短語：S，SdS，SdSdS，（SdSdS）簡單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS，它同時也是該句型的最左素短語。（3）輸入串（adb）#的分析過程見表5-7-4表5-7-4輸入串（adb）#的分析過程符號棧輸入串說明#(adb)#移進#（adb)#移進#（adb)#用S→a歸約#（Sdb)#移進#（Sdb)#移進#（Sdb)#用S→b歸約#（SdS)#用A→S歸約#（SdA)#用A→SdA歸約#（A)#移進#（A）#用S→（A）歸約#S#分析成功第四節習題一、單項選擇題1、若a為終結符，則A→α·aβ為項目a.歸約 b.移進 c.接受 d.待約2、若項目集Ik含有A→α·，則在狀態k時，僅當面臨的輸入符號a∈FOLLOW(A)時，才采取“A→α·”動作的一定是。a.LALR文法 b.LR（0）文法 c.LR（1）文法 d.SLR（1）文法3、就文法的描述能力來說，有。a.SLR（1）?LR（0）b.LR（1）?LR（0）c.SLR（1）?LR（1）d.無二義文法?LR（1）4、在LR（0）的ACTION子表中，如果某一行中存在標記“rj”的欄，則。a.該行必定填滿rj b.該行未填滿rjc.其他行也有rj d.goto子表中也有rj5、一個指明了在分析過程中的某時刻所能看到產生式多大一部分。a.活前綴 b.前綴 c.項目 d.項目集解答：1、A→α·稱為歸約項目，對文法開始符S′的歸約項目，如S′→α·稱為接受項目，A→α·aβ（a為終結符）稱為移進項目。在此選b.2、當用產生式A→α歸約時，LR（0）無論面臨什么輸入符號都進行歸約；SLR（1）則僅當面臨的輸入符號a∈FOLLOW(A)時進行歸約；LR（1）則當在把α歸約為A的規范句型的前綴βAa前提下，當α后跟終結符a時，才進行歸約；因此選d。3、由于LR（0）?SLR（1）?LR（1）?無二義文法，故選c。4、選a。5、選c。二、多項選擇題1、一個LR分析器包括。a.一個總控程序 b.一個項目集 c.一個活前綴d.一張分析表 e.一個分析棧2、LR分析器核心部分是一張分析表，該表包括等子表。a.LL(1)分析 b.優先關系 c.GOTOd.LR e.ACTION3、每一項ACTION[S，a]所規定的動作包括。a.移進 b.比較 c.接受 d.歸約 e.報錯4、對LR分析表的構造，有可能存在動作沖突。a.移進 b.歸約 c.移進/歸約 d.移進/移進 e.歸約/歸約5、就文法的描述能力來說，有。a.SLR（1）?LR（1） b.LR（1）?SLR（1） c.LR（0）?LR（1）d.LR（1）?無二義文法 e.SLR（1）?無二義文法6、對LR分析器來說，存在等分析表的構造方法。a.LALR b.LR（0） c.SLR（1） d.SLR（0） e.LR（1）7、自上而下的語法分析方法有。a.算符優先分析法 b.LL（1）分析法 c.SLR（1）分析法d.LR（0）分析法 e.LALR（1）分析法解答：1、一個LR分析器包括一個總控程序和一張分析表，選a、d。2、選c、e。3、選a、c、d、e。4、在LR分析表的構造中有可能存在“移進”/“歸約”和“歸約”/“歸約”沖突；故選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。三、填空題1、對于一個文法，如果能夠構造。使得它的均是唯一確定的，則稱該文法為LR文法。2、字的前綴是指該字的。3、活前綴是指的一個前綴，這種前綴不含之后的任何符號。4、在LR分析過程中，只要的已掃描部分保持可歸約成一個，則掃描過的部分正確。5、將識別的NFA確定化，使其成為以為狀態的DFA，這個DFA就是建立的基礎。6、A→α·稱為項目；對文法開始符S′→α·為項目；若a為終結符，則稱A→α·aβ為項目；若B為非終結符，則稱A→α·aβ為項目。7、LR（0）分析法的名字中“L”表示，“R”表示，“0”表示。解答：1、一張分析表每個入口2、任意首部3、規范句型句柄4、輸入串活前綴5、活前綴項目集合LR分析算法6、歸約接受移進待約7、自左至右分析采用最右推導的逆過程即最左歸約向右查看0個字符四、綜合題1、對于文法G[S]：S→AS|bA→SA|a（1）列出所有LR（0）項目（2）列出構成文法LR（0）項目集規范族。解答：首先將文法G拓廣為G[S′]： S′→S S→AS|b A→SA|a（1）文法G[S′]的LR（0）項目是：1、S′→·S 5、S→AS· 9、A→S·A 2、S′→S· 6、S→·b 10、A→SA· 3、S→·AS 7、S→b· 11、A→·a 4、S→A·S 8、A→·SA 12、A→a·2、列出構成文法LR（0）項目集規范族。用ε-CLOSURE（閉包）辦法構造文法G′的LR（0）項目集規范族如下：I0：1、S′→·S I3： 9、A→S·A I6：12、A→a·3、S→·AS 8、A→·SA I7：7、S→b·8、A→·SA 3、S→·AS 11、A→·a 6、S→·b6、S→·b 11、A→·aI1：2、S′→S· I4：10、A→SA·9、A→S·A 4、S→A·S 8、A→·SA 3、S→·AS11、A→·a 6、S→·b3、S→·AS 8、A→·SA 6、S→·b 11、A→·aI2：4、S→A·S I5： 5、S→AS·3、S→·AS 9、A→S·A 6、S→·b 8、A→·SA 8、A→·SA 11、A→·a11、A→·a 3、S→·AS 6、S→·b注意：I1中的S′→S·和A→·SA是由狀態I0中的1和3讀入一個S字符后得到的下一個項目；，而I4中的A→SA和A→A·S則是由I3中的9和3讀入一個A字符后得到的下一個項目；I5中的S→AS·和A→S·A 則是由I4中的4和8讀入一個S字符后得到的下一個項目。狀態全體構成了文法G′的LR（0）規范族。第八節習題一、單項選擇題1、中間代碼生成所依據的是。a.語法規則 b.詞法規則 c.語義規則 d.等價變換規則2、四元式之間的聯系是通過實現的。a.指示器 b.臨時變量 c.符號表 d.程序變量3、后綴式ab+cd+/可用表達式來表示。a.a+b/c+d b.(a+b)/(c+d) c.a+b/(c+d) d.a+b+c/d4、表達式（┓A∨B）∧（C∨D）的逆波蘭表示為。a.┓AB∨∧CD∨ b.A┓B∨CD∨∧c.AB∨┓CD∨∧ d.A┓B∨∧CD∨5、中間代碼的樹型表示++AB++ABCD+a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D)6、四元式表示法的優點為。a.不便于優化處理，但便于表的更動 b.不便于優化處理，但節省存儲空間c.便于優化處理，也便于表的更動 d.便于表的更動，也節省存儲空間7、終結符具有屬性。a.傳遞 b.繼承 c.抽象 d.綜合解答1、選c。2、四元式之間的聯系是通過臨時變量實現的，故選b。3、選b。4、選b。5、選d。6、四元式表示法的優點與間接三元式相同，故選c。7、選d。二、多頂選擇題1、中間代碼主要有 。 a．四元式 b．二元式 c．三元式 d．后綴式 e．間接三元式2、下面中間代碼形式中，能正確表示算術表達式a+b+c的有 。+a++a+bc++cab a．ab+c+ b．abc++ c． d．e．a+b+c3、在下面的 語法制導翻譯中，采用拉鏈-回填技術。 a．賦值語句 b．goto語句c．條件語句 d．循環語句4、下列 中間代碼形式有益于優化處理。 a．三元式 b．四元式 c．間接三元式 d．逆波蘭表示法 e．樹形表示法5、在編譯程序中安排中間代碼生成的目的是 。 a．便于進行存儲空間的組織 b．利于目標代碼的優化c．利于編譯程序的移植 d．利于目標代碼的移植e．利于提高目標代碼的質量+a*ab*+cab6、下面的中間代碼形式中，+a*ab*+cab a．ab+c* b．abc*+ c．a+b*c d．e．7、三地址代碼語句具體實現通常有 表示方法。 a．逆波蘭表示 b．三元式 c．間接三元式 d．樹形表示 e．四元式解答1、選a、c、d、e。2、b、d的中間代碼不能正確表示a+b+c，而e不是中間代碼：故選a、c。3、凡涉及到跳轉的語句都需要采用拉鏈——回填技術，故選b、c、d。4、選b、c。5、選b、d。6、選b、e。7、選b、c、e。三、填空題1、中間代碼有等形式，生成中間代碼主要是為了使。2、語法制導翻譯既可以用來產生代碼，也可以用來產生指令，甚至可用來對輸入串進行。 3、當源程序中的標號出現“先引用后定義”時，中間代碼的轉移地址須持時才能確定，因而要進行。 4、文法符號的屬性有兩種，一種稱為，另一種稱為。5、后綴式abc-/所代表的表達式是，表達式(a-b)*c可用后綴式表示。 6、用一張輔以的辦法來表示中間代碼，這種表示法稱為間接三元式。解答1、逆波蘭記號、樹形表示、三元式、四元式 目標代碼的優化容易實現2、中間 目標 解釋執行3、標號定義 回填4、繼承屬性 綜合屬性5、a/(b-c) ab-c*6、間接碼表 三元式表四、綜合題1、給出下列表達式的逆波蘭表示（后綴式）：①a*(-b+c)②(A∨B)∧(C∨┑D∧E)2、寫出算術表達式：A+B*(C-D)+E/(C-D)↑N的①四元式序列；②三元式序列；③間接三元式序列解答1、①ab@c+*;②AB∨CD┑E∧∨∧2、2、①表達式的四元式序列： ②表達式的三元式序列③間接三元式序列 （1）(-,C,D,T1) （1）(-,C,D)⑴（1）(-,C,D) （2）(*,B,T1,T2) （2）(*,B,(1))⑵（2）(*,B,(1)) （3）(+,A,T2,T3) （3）(+,A,(2))⑶（3）(+,A,(2)) （4）(-,C,D,T4) （4）(-,C,D)⑴⑷(↑,(1),N) （5）(↑,T4,N,T5) （5）(↑,(4),N)⑷⑸(/,E,(4))⑹(/,E,T5,T6)⑹(/,E,(5))⑸⑹(+,(3),(5))⑺(+,T3,T6,T7)⑺(+,(3),(6))⑹第三節習題一、單項選擇題1、編譯程序使用區別標識符的作用域。a.說明標識符的過程或函數名 b.說明標識符的過程或函數的靜態層次c.說明標識符的過程或函數的動態層次d.標識符的行號2、在目標代碼生成階段，符號表用于。a.目標代碼生成 b.語義檢查 c.語法檢查 d.地址分配3、過程信息表不包含。a.過程入口地址 b.過程的靜態層次 c.過程名 d.過程參數信息4、下列關于標識符和名字敘述中，正確的是。a.標識符有一定的含義 b.名字是一個沒有意義的字符序列c.名字有確切的屬性 d.a~c都不正確解答：1、b2、d3、b4、c二、多項選擇題1、符號表的每一項均包含。a.名字欄 b.類型欄 c.信息欄 d.值欄 e.a~d均包含2、對編譯程序所用到的符號表，涉及的操作有。a.填寫或更新信息欄內容 b.填入新名 c.給定名字，訪問它的有關信息d.雜湊技術 e.線性表和排序二叉樹3、源程序中的錯誤一般有。a.詞法錯誤 b.語法錯誤 c.語義錯誤d.編譯錯誤 e.違反環境限制的錯誤解答：1、a、c2、a、b、c3、a、b、c、e三、填空題1、符號表中名字欄內容有兩種填寫方式，它們是填寫和填寫。2、詞法分析階段的錯誤主要是，可通過的辦法糾正錯誤。3、符號表中名字的有關信息在和過程中陸續填入。4、在目標代碼生成階段，符號表是的依據。解答：1、標識符標識符地址及長度2、拼寫錯誤最小距離匹配3、詞法分析語法語義分析4、地址分配四、問答題：1、在編譯過程中為什么要建立符號表？解答：在編譯過程中始終要涉及到對一些語法符號的處理，這就需要用到語法符號的相關屬性。為了在需要時能找到這些語法成分及其相關屬性，就必須使用一些表格來保存這些語法成分及其屬性，這些表格就是符號表。第四節習題一、單項選擇題1、程序所需的數據空間在程序運行前可確定，稱為管理技術。a.動態存儲 b.棧式存儲 c.靜態存儲 d.堆式存儲2、堆式動態分配申請和釋放存儲空間遵守原則。a.先請先放 b.先請后放 c.后請先放 d.任意3、靜態分配允許程序出現。a.遞歸過程 b.可變體積的數據項目 c.靜態變量 d.待定性質的名字4、在編譯方法中，動態存儲分配的含義是。a.在運行階段對源程序中的數組、變量、參數等進行分配b.在編譯階段對源程序中的數組、變量、參數進行分配c.在編譯階段對源程序中的數組、變量、參數等進行分配，在運行時這些數組、變量、參數的地址可根據需要改變d.以上都不正確5、在編譯時有傳名功能的高級程序語言是。a.Fortran b.Basic c.Pascal d.ALGOL6、棧式動態分配與管理在過程返回時應做的工作有。a.保護SP b.恢復SP c.保護TOP d.恢復TOP解答1、c2、d3、c4、a5、d6、b二、多項選擇題1、下面需要在運行階段分配存儲空間。a.數組 b.指