[03_04(2)]《編譯原理》00本科班A卷(答案)

1、裝訂線20032004學(xué)年第二學(xué)期韶關(guān)學(xué)院計(jì)算機(jī)系編譯原理期末考試試卷（A卷答案）年級(jí)：00 專業(yè)：計(jì)算機(jī)科學(xué)技術(shù) 班級(jí)： 學(xué)號(hào)： 姓名： 題號(hào)一二三四五總分簽名得分注：1、共120分鐘，總分100分 。2、此試卷適用專業(yè)：計(jì)算機(jī)本科一得 分閱卷教師1、 判斷題：（每小題1分，共5分）*1、 每個(gè)文法都能改寫為L(zhǎng)L(1)文。 （×）2、符號(hào)表是上下文語(yǔ)義的合法性檢查的依據(jù)之一。 （）3、函數(shù)backpatch(p,t)的功能是指將字符p后退t格。 （×）4、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函。 （）5、“把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)表中”是用得最多的一種對(duì)符號(hào)表的總

2、體組織方法中。 （×）二得 分閱卷教師2、 填空題(每空1分，共20分)1、編譯過程一般分為：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六個(gè)階段。2、詞法分析的任務(wù)是：從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描，從而識(shí)別出一個(gè)個(gè)單詞。3、語(yǔ)法分析最常用的兩類方法是 自頂向下分析法 和自底向上分析法。4、一個(gè)上下文無關(guān)文法包含非終結(jié)符集、終結(jié)符集、產(chǎn)生式集和開始符號(hào)四個(gè)組成部分是。5、在有窮自動(dòng)機(jī)中，兩類狀態(tài)s和t等價(jià)的條件是：一致性條件和蔓延性條件。6、程序設(shè)計(jì)語(yǔ)言的語(yǔ)義分為：靜態(tài)語(yǔ)義和動(dòng)態(tài)語(yǔ)義兩類。7、喬姆斯把文法分成0型文法（短語(yǔ)文

3、法）、1型文法（上下文有關(guān)文法）、2型文法（上下文無關(guān)文法）和3型文法（正規(guī)文法）四種類型。三得 分閱卷教師三、名詞解釋(每題2分，共10分)1、句柄：令S是文法G的開始符，如果有SÞaAd且AÞb則稱b是句型abd相對(duì)于非終結(jié)符A的直接短語(yǔ)，其中最左直接短語(yǔ)為句柄。2、規(guī)范推導(dǎo)：如果在推導(dǎo)的任何一步aÞb，其中a，b是句型，都是對(duì)a中的最右非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最右推導(dǎo)，也稱為規(guī)范推導(dǎo)。*3、語(yǔ)法分析：是編譯程序的第二個(gè)階段，其任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語(yǔ)法短語(yǔ)，如“程序”、“語(yǔ)句”、“表達(dá)式”等。4、素短語(yǔ)：至少包含一個(gè)終結(jié)符，且不

4、包含其它短語(yǔ)的短語(yǔ)。5、句型：設(shè)GS是一文法，如果符號(hào)串是從識(shí)別號(hào)推導(dǎo)出來的，即有SÞ，則稱是文法GS的句型。四得 分閱卷教師四、簡(jiǎn)述題(每題5分，共25分)1、已知文法G：ET | E+T | E-T, TF | T*F | T/F, F(E) | i 試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹。 i+i*i i*(i+i)解：推導(dǎo)過程如下： EÞ E+T Þ E+T*F Þ E+T*i Þ E+F*i Þ E+i*I Þ T+i*I Þ F+i*iÞ i+i*i推導(dǎo)過程如下：EÞ T Þ T*

5、F Þ T*(E) Þ T*(E+T) Þ T*(E+F) Þ T*(E+i) Þ T*(T+i)Þ T*(F+i) Þ T*(i+i) Þ F*(i+i) Þ i*(i+i)和的語(yǔ)法樹如下： EE+TT*FTFFiii的語(yǔ)法樹FTFTETET*F(E)Fiii的語(yǔ)法樹+裝訂線2、給出語(yǔ)言anbnambm | n,m0的上下無關(guān)文法。 解：上下無關(guān)文法如下： GS: S®AB, A®aAb | ab | e , B®aBb | ab | e3、寫出表達(dá)式(ab*c)/(ab)

6、d的逆波蘭表示及三元式序列。 解：逆波蘭:abc*+ab+/d-三元式: (* b , c ) (+ a , ) (+ a , b ) (/ , ) (- , d )4、文法GN為：ND | NDD0 | 1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9GN的語(yǔ)言是什么？解：GN 的語(yǔ)言是: (0|1|2|3|4|5|6|7|8|9)n | n1 即為非負(fù)整數(shù)。5、構(gòu)造正規(guī)式b(ab)*|bb)*ab的NFA。 解：a,beebbebae4235106a五得 分閱卷教師五、綜合題(每題10分，共40分)1、已知文法GS： SMH |a HLSo | e KdML | e LeH

7、f MK | bLM判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。解：（1）求出能推出e的非結(jié)符為：S、H、K、M（2）計(jì)算FIRST集FIRST(S)=FIRST(MH) Ua=a,b,d,e,e FIRST(H)=FIRST(L)Ue=e,e FIRST(K)=d,e FIRST(L)=eFIRST(M)= FIRST(K) Ub=b,d,e （3）計(jì)算FOLLOW集FOLLOW(S)=o,# FOLLOW(H)=FOLLOW(S) Uf=f,o,# FOLLOW(K)=FOLLOW(M)=e,o,# FOLLOW(L)=FIRST(S)UoUFOLLOW(K)UFIRST(M

8、)UFOLLOW(M) =a,b,d,e,o,# FOLLOW(M)=FIRST(H)UFOLLOW(S)UFIRST(L) =e,o,# （4）計(jì)算SELECT集SELECT(S®MH)=FIRST(MH)UFOLLOW(S)=b,d,e,o,e,# SELECT(S®a)=aSELECT(H®LSo)=FIRST(L)=eSELECT(H®e)=FOLLOW(H) Ue=f,o,#,e SELECT(K®dML)=dSELECT(K®e)=FOLLOW(K)Ue=e,o,#,e SELECT(L®eHf)=eSELECT

9、(M®K)=FIRST(K)UFOLLOW(M)=d,e,o,#,e SELECT(M®bLM)=b（5）判斷G是否是LL(1)文法由于相同左部的產(chǎn)生式的SELECT集合的集為空，所以是LL(1)文法。裝訂線（6）構(gòu)造LL(1)分析表abdefo#S®a®MH®MH®MH®MH®MHH®LSo®e®e®eK®dML®e®e®eL®eHfM®bLM®K®K®K®K2、采用語(yǔ)法制導(dǎo)

10、翻譯思想，表達(dá)式E的“值”的描述如下： 產(chǎn)生式 語(yǔ)義動(dòng)作 (0)SE print E.VAL (1)EE1+E2 E.VAL:= E1.VAL + E2.VAL (2)EE1*E2 E.VAL:= E1.VAL * E2.VAL (3)E(E1) E.VAL:= E1.VAL (4)En E.VAL:= n.LEXVAL 如采用LR分析方法，給出表達(dá)式(5*4+8)*2的語(yǔ)法樹并在各結(jié)點(diǎn)注明語(yǔ)義值VAL。解：表達(dá)式(5*4+8)*2的語(yǔ)法樹如下：E(val=56)(E(val=28)+)(val=20)E+E(val=8)254S(val=28)E*E(val=2)T(val=5)E*E(va

11、l=4)83、已知文法GS為： Sa | Ù | (T) TT,S | S (1)計(jì)算GS的FIRSTVT和LASTVT。 (2)構(gòu)造GS的算符優(yōu)先關(guān)系表并說明GS是否為算符優(yōu)先文法。 (3)給出輸入串(a,a)# 的算符優(yōu)先分析過程。解：(1)給GS加入規(guī)則S'S，并求得FIRSTVT和LASTVT如下：FIRSTVT(S)= a ,Ù,( FIRSTVT(T)= ,a ,Ù,( LASTVT(S)= a ,Ù,) LASTVT(T)= ,a ,Ù,)(2)GS的算符優(yōu)先關(guān)系如下： (=) 、= 、 (<FIRSTVT(T) 、

12、,<FIRSTVT(S) 、<FIRSTVT(S) 、 LASTVT(T)>) 、LASTVT(T)>, 、LASTVT(T)>從而構(gòu)造優(yōu)先關(guān)系表如下：裝訂線aÙ(),a>>>Ù>>>(<<<=<)>>>,<<<>><<<=由于該文法GS中任何句型不包含兩個(gè)相鄰的非終結(jié)符，且任意兩個(gè)終結(jié)符對(duì)，之間至多只有、三種關(guān)系的一種成立，所以該文法是為算符優(yōu)先文法。(3)輸入串(a,a)# 的歸約過程如下：步驟棧S當(dāng)前輸入符剩余輸入

13、串動(dòng)作#(#(a#(S#(S,#(S,a#(S,S#(T#(T)#S(a,a)#a,a)#,a)#a)#a)#)#移進(jìn)移進(jìn)歸約移進(jìn)移進(jìn)歸約歸約移進(jìn)歸約接受4、若有定義二進(jìn)制數(shù)的文法如下：SL.L | LLLB | BB0 | 1(1)試為該文法構(gòu)造LR分析表，并說明屬哪類LR分析表。(2)給出輸入串101.110的分析過程。解：(1)首先對(duì)語(yǔ)言文法GS的產(chǎn)生式編號(hào)如下： SL.L SL LLB LB B0 B1畫出識(shí)別活前輟的有限自動(dòng)機(jī)DFA如下：01B10B01B1B0L.L0:S®·L.LS®·L L®·LB L®

14、83;B B®·0B®·11:S®L·.LS®L· L®L·B B®·0B®·12:S®L. ·LL®·LB L®·B B®·0B®·13:S®L.L·L®L·B B®·0B®·14:L®B · 5:B®0 · 6:B®1 · 7:L®LB · 構(gòu)造LR分析表如下：狀態(tài)ACTIONGOTO·01#LB裝訂線0S5S6141S2S5S6acc72S5S6343S5S6acc74r4r4r4r45r5r5r5r56r6r6r6r67r3r3r3r3(2)輸入串101.110的分析過程如下表：步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO10#101.110#S6206#101.110#r64304#B01.110#r41401#L01.110#S55015#L01.110#r576017#LB1.110#r31701#L1.110#S68016#L1.110#r6