1、(1課程名稱:德州學院期末考試試題學年第 學期)考試對象:試卷類型：(1)考試時間:分鐘一、填空題：(10分，第1小題每2個1分，其余每空1分)1、編譯程序一般含有八部分，分別是 2、編譯程序與解釋程序的根本區別是3、一個上下文無關文法G包括四個組成部分依次為：一組一組。4、 設G是一個文法，S是文法的開始符號，如果S* X,則稱X是 二、選擇題(本大題共15小題，每小題1分，共15分)1、 編譯程序生成的目標程序 是機器語言程序。A、一定B、不一定2、設有文法GS= (b,S,B,S,b|bB, BbS，該文法描述的語言是A、bi | i 0B、b2i | i 0C、b2i+1 | i 0D

2、、b2i+1 | i 13、 設有文法 GS:S S*S|S+S| (S) |a該文法二義性文法A、是B、不是C、無法判斷4、 匯編程序是將 羽譯成;編譯程序是將 A、匯編語言程序B、機器語言程序C、高級語言程序D、匯編語言或機器語言程序5、給定文法A bA|cc,下面符號串中，為該文法句子的是 cc bcbc bcbcc bccbcc bbbccA、B、C、D、E、6、 語法分析的常用方法是 。自頂向下自底向上自左向右A、B、C、7、已知語言L=crbbn|n 1，則下述文法中，、一個、一組翻譯成有人說，因為 FIRST(aABe)n FOLLOW( A)工并且 FIRST( Ba)n FO

3、LLOW( A)工，所以文法GA不是LL (1)文法。這種說法A、正確B、不正確14、 素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：A、B、C、D、E、F、G、15、表達式A* (B-C* (C/D)的逆波蘭式為A、 ABC-CD/*B、 ABCCD/*-*C、ABC-*CD/*D、都不正確三、簡答題(共35分)1、(10分)現有文法GE:E E+T|E-T|TT T*F|T/F|F F (E)|i畫出句型E+F* (E+i)的語法

4、樹，找出它的短語，直接短語， (5分)對下面的文法GS構造狀態轉換圖,并說明符號串句子：S aA S B A abS A bB B b B cC(10分)將下面具有的NFA確定化句柄和素短語aaba是否是該文法接受的C D D d D bBA、Z aZb|aAb|bA aAb|bB、A aAbC、ZAbB A aA|a B bB|bD、Z aAb8下列正規表達式中 與(a|b)*(c|d)等價。A、(a*|b* ) (c|d)B、(a*|b* ) *(c|d)自右向左D、可以產生語言LA bA aAb|bC、(ab)*(d|c)D、( a*b*)(cd)4、5、四、1、9、 算符優先分析法每次

5、都是對進行歸約。A、最左短語B、直接短語 C、句柄10、 簡單優先分析法每次都是對進行歸約A、最左短語B、直接短語 C、句柄D、D、素短語素短語E、E、11、下列文法GS: S AA A Aa|a不是LR (1)文法，理由是A.、FIRST(S FIRST( A)工 B、FIRST( A)n FOLLOW( A) C、FIRST(Aa)n FIRST( a)工D、都不是12、設有文法 GE: E E*E|E+E| (E) |a 該文法A、是B、不是C、無法判斷13、對于文法 GA:A aABe|Ba最左素短語最左素短語LR( 1)文法2、3、4、5、(5分)求出下列文法所產生語言對應的正規式。

6、S aA(5分)構造識別下面正規式的NFA (a|b ) *ba。 綜合題(共40分)(10分)下面的文法GS是否是LL( 1)文法，說明理由，構造LL( 1)分析表4 aBc|bABA aAb|BbB cB|(5分)消除下列文法的左遞歸，消除左遞歸后判斷是否是LL( 1)文法。4 SaB|bB A S|aB Ac(5分)構造下面算符文法的優先矩陣，判斷是否是算符優先文法4 AA A aA A BB a(10分)將表達式A+B*(C-D)-E/FT G分別表示為三元式、四元式、逆波蘭式序列 (10分)現有文法如下：4 aS|bS|a判斷該文法是哪一類LR文法，說明理由，并構造相應的分析表。A

7、bA|aB|bB aA。課程名稱:二、選擇題(本大題共1、匯編程序是將a、匯編語言程序德州學院期末考試試題學年第學期)考試對象:試卷類型:(1)考試時間: 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語 可選項有：20小題，每小題1分，共20分)翻譯成 ；編譯程序是將 翻譯成 Ob、機器語言程序C、高級語言程序d匯編語言或機器語言程序a、 b、C、d、e、f、g10、LR ( K文法是從左到右分析，從左到右分析，從左到右分析，從左到右分析，a、b、C、O共經過 K步的一種編譯方法。 每次向前預測K步的一種

8、編譯方法。每次向貌似句柄的符號串后看 每次走 K步的一種編譯方法。K個輸入符號的一種編譯方法。2、 描述一個語言的文法是 Oa、唯一的b、不唯一的C、個數有限的3、生成非0開頭的正偶數集的文法是a、Z:=ABCC:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9b、Z:=ABCC:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|94、設有文法Gl:It I0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有 ab0 a0c01 aaa bc10可選項有a、 b、 C、 d、5、 現有前綴表示的表達式文法G1:E:=-EE

9、E:=-E E:=a|b|c則文法的句子一a-bc的所有可能語法樹有OC、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|911、在編譯中產生語法樹是為了 a、語法分析b、語義分析12、文法的二義性和語言的二義性是兩個a、不同b、相同C、無法判斷13、 下述正規表達式中 與(a*+b)*(c+d)等價。a* (c+d)a* (c+d)a* (c+d)+b (c+d)*+b (c+d) *+b* (c+d)c、詞法分析概

10、念。d、產生目標代碼(a+b) *c+ (a+b) *d(a*+b ) *c+ ( a*+b) *dc、 d、 e、f、g可選項有：a、b、，這樣的語言，他們能被確定的有限自動機識別，但不能用正規表達式表示: b、不存在C、無法判定是否存在棵。、 1b、2 c、3 d、4、一個上下文無關文法 G包括四個組成部分依次為:a、字符串b、字母數字串C、產生式結符號 h、終結符號一組、一個、一組、一組Od、結束符號e、開始符號 f、文法 g、非終14、_a、存在15、 LL ( K)文法二義性的。a、都是b、都不是C、不一定都是16、 下面的文法是 O S:=aAa|aBb|bAb|bBa A:=x

11、B:=x可選項有：a、LR( 1)文法 b、LALR (1)文法 c、都不是 d、a和b17、編譯過程中，比較常見的中間語言有 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：a、7、語法分析的常用方法是自頂向下 可選項有：自底向上自左向右自右向左18、-a- (b*c/ (c-d) +a、abc*cd-b-a*+/-b、C、d、(-b) *a)的逆波蘭表示是b、a-bc*cd-b-a*+/-d、a-bc*/cd-b-a*+-b、c、二義文法a、8、下列文法E:=EiT|T T:=T+F|iF|F F:=E*|( 可選項有：a、是9、 素短語是指的短語。 至少包含一個符號 至少包含一個

12、非終結符號d、b、不是c、無法判斷。c、a-bc*cd-/b-a*+-19、在編譯程序中安排中間代碼生成的目的是 便于進行存儲空間的組織 利于目標代碼優化 利于編譯程序的移植 利于目標代碼的移植 利于提高目標代碼的質量可選項有：a、b、 cd、20、代碼優化的主要目標是 如何提高目標程序的運行速度 如何減少目標程序運行所需的空間。 如何協調和 如何使生成的目標代碼盡可能簡短 可選項有：、 b、C、 d、三、簡答題：(每小題5分，共35分)1、 證明下面文法是二義性的。S:=ibtSeS|ibtS|a2、現有文法 S:=SaA|A A:=AbB|B B:=cSd|e請證實是文法的一個句型，并寫出

13、該句型的所有短語、素短語以及句柄。3、求出下列文法所產生語言對應的正規式。S:=bS|aA A:=aA|bB B:=aA|bC|b C:=bS|aA4、將表達式(a*d+c)/d+e)*f+g分別表示三兀式、四兀式、逆波蘭式序列5、消除下列文法的左遞歸。S:=Sa P|Sf|PP:=Qb P|QQ:=cSd|e、給出與下圖的NFA等價的正規文法。(1) 構造該正規式所對應的(2) 將所求的NFA確定化。(3) 將所求的NFA最小化。4、若有文法G (S)的產生式如下: 族的DFA。(15分)(1)(2)(3)(4)判斷該文法是否是 判斷該文法是否是 判斷該文法是否是 判斷該文法是否是課程名稱:

14、NFA (畫出狀態轉換圖)。(畫出確定化的狀態轉換圖)。(畫出最小化后的狀態轉換圖)。(10分)S:=L=RS:=R L:=*RL:=iR:=L構造識別所有項目集規范LR ( 0)文法，說明理由。 SLR( 1)文法，說明理由。 LR( 1)文法，說明理由。LALR( 1)文法，說明理由德州學院期末考試試題考試對象:學年第試卷類型:學期)考試時間:DAG圖7、對基本塊B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CP畫出J:=H+IK:=B*5 L:=K+JM:=L 假定只有一、單項選擇題(20分，每小題1分)1、文法 G1: P aPQR| abR RCH Q

15、R, 型文法A、0型B、1型 C 2型2、編譯程序必須完成的工作有詞法分析語法分析語義分析代碼生成中間代碼生成代碼優化 B、 C D、3、 LR( K)文法義性的。A、都是B、都不是C、不一定都是4、語法分析的常用方法是 。自頂向下自底向上自左向右A5、A、6、A、BA bb, bR be, cR cc,它是 Chomsky 哪一D、3型自右向左B、C、D、用高級語言書寫的源程序都必須經過編譯，產生目標代碼后才能投入運行，這種說法 不正確B、正確生成非0開頭的正偶數集的文法是Z:=ABCC:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9B、Z:=ABC|2|4

16、|6|8C:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|9L在基本塊出口之后活躍，寫出優化后的四元式序列。四、問答題：(共計45分)已知文法 G A:=aABe|a B:=Bb|d(1) 給出與上述文法等價的LL ( 1)文法G(2) 構造預測分析表并給出輸入串aade#分析過程。(10分)設已給文法 G: E:=E+T E:=T T:=T*F T:=F F:=Pf F F:=P P:=(E) P:=i 構造此文法的算符優先矩陣。(10分)有正規式 b*abb*(abb*)*1、C Z:=ABCC:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|

17、5|6|7|8|9文法G所描述的語言是7、 A、 B CD、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9的集合文法G的字匯表V中所有符號組成的符號串 文法G的字匯表V的閉包V*中的所有符號串 由文法的開始符號推出的所有符號串2、3、D、由文法的開始符號推出的所有終結符號串。給定文法GI:I I1|I0|Ia|Ic|a|b|c,下面符號串中，為該文法句子的是。abO a0c01aaa bc10B、C、D、這樣的語言，他們能被確定的有限自動機識別，但不能用正規表達式表示： 存在B、不存在C、無法判定是否存在8、A、9、A、1、 (

18、10 分)已知文法 G (T):TTF|FFFT P|PP()|i(1) 寫出句型T *PT(T*F)推導過程，畫出語法樹；(2) 寫出句型T *PT(T*F)的短語、直接短語、句柄和素短語。2、(5分)構造識別下面正規式的NFA10、LR (K)文法是。A、從左到右分析，共經過 K步的一種編譯方法。B、 從左到右分析，每次向前預測K步的一種編譯方法。C、 從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。D、從左到右分析，每次走K步的一種編譯方法。11、-a- (b*c/ (c-d) + (-b) *a )的逆波蘭表示是 。A、a-bc*cd-/b-a*+-B、a-bc*/

19、cd-b-a*+-C、abc*cd-b-a*+/-D、a-bc*cd-b-a*+/-12、設有文法GS= (b,S,B,S, b|bB, B bS)該文法描述的語言是A、b2i+1| i 1B、b2i+1 | i 0C、bi 1 i0D、b2i |i 013、 素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：A、B、C、 D、E、F、 G、14、算符優先分析屬于A、自頂向下B、自底向上b (aa|bb) ab3、(5分)消除文法GS的左

20、遞歸GS: S ABA bB|AaB Sb|a三、(綜合題，共計30分)(1) 對下面的文法GZZ aBA aBB bB B aA B b構造狀態轉換圖，并說明符號串aaaabbb是否是該文法接受的句子(2) 寫出GZ文法相應的正規式：3、(10分)設有以下文法 GS: S aAbDeld(1) 求出文法中每個非終結符的 FOLLOW集A BSD|e 4 SAc|cD|D Se|分析方法。C 自左向右D、自右向左進行歸約B、直接短語 C、句柄S U15、簡單優先分析法每次都是對A、最左短語16、文法 GS: S aS其中的全部無用符且日A、W，V，U17、程序基本塊是指A、一個子程序C、一個沒

21、有嵌套的程序段D、一組順序執行的程序段，18、設有文法 GZ: Z Z*Z|Z+Z| (Z) |aA、是B、不是C、無法判斷19、 下列正規表達式中 與(a|b)*(c|d)等價。A、(a*|b* ) (c|d)B、(a*|b* ) *(c|d)C、(ab)*(d|c)D、(a*b* ) (cd)20、語法分析的任務是分析單詞是怎樣構成的分析單詞串是如何構成語句和說明的分析語句和說明是如何構成程序的分析程序的結構A、 B、C、 D、二、(簡答題，共計20分)D、素短語E、最左素短語Ua V bV V ac W aW號疋B、V,B、C、W,V, a, b ,c D、W, V, b, c一個僅有一

22、個入口和一個出口的語句僅有一個入口和一個出口該文法二義性文法(2) 該文法是LL (1)文法嗎構造LL( 1)分析表四、(綜合題，共計30分)1、(10分)將表達式(B*D+A) /E+D) *F+G分別表示為三元式、四元式、逆波蘭式序列2、(10分)對基本塊P畫出DAG圖B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本塊出口之后活躍，寫出優化后的四元式序列。3、 (10 分)對于文法 GS: 4aBb | aAa |bAb|bBaAx Bx(1) 判斷該文法是否是LR( 1)文法，構造LR( 1)分析

23、表(2) 判斷該文法是否是LALR( 1)文法，說明理由德州學院期末考試試題考試對象:學年第學期)試卷類型:(1)考試時間:20小題，每小題1分，共20 分)e、b、字母數字串h、終結符號G所描述的語言是 的集合G的字匯表V中所有符號組成的符號串G的字匯表V的閉包V*中的所有符號串6、a、b、c、d、最左素短語、一個、一組e、開始符號 f、文法、一組。g、非終二義性文法7、自左向右自右向左o共經過 K步的一種編譯方法。 每次向前預測K步的一種編譯方法。每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。每次走 K步的一種編譯方法。的短語。Ob、語義分析C、詞法分析與(a|b)*(c|d)等價

24、。b、(a*|b* ) *(c|d) c、(ab)*(d|c)d、(a*b* ) (cd)他們能被確定的有限自動機識別，但不能用正規表達式表示: 無法判定是否存在St UUf a g bV g ac W aWd、產生目標代碼C、V, a, b ,c) d、(W, V, b, c)d、 aaabbbc、d、b、(-b) *a)的逆波蘭表示是b、a-bc*cd-b-a*+/-d、a-bc*/cd-b-a*+-課程名稱:一、選擇題(本大題共：1、 描述一個語言的文法是 。a、唯一的b、不是唯一的C、個數有限的2、 簡單優先分析法每次都是對 進行歸約。a、最左短語b、直接短語C、句柄d、素短語3、設有

25、文法GI:It I0 |I1 |Ia |Ic |a |b |c下歹y符號串中是該文法的句子的有 1 b、b2i+1 | i 0c、bi | i 0d、b2i | i 0二、簡答題：(每小題5分，共30分)1、 證明下面文法是二義性的。Pt PaP|PbP |cP| Pe|f2、 設一文法EtT|E+T|E-T Tt F|T*F|T/FFt (E)|i證明E+T*(E-T)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產生語言對應的正規式。St bS|aAAt aA|bBBt aA|bC|bCt bS|aA4、將表達式(B*D+A) /E+D) *F+G分別表

26、示為二兀式、四兀式、逆波蘭式序列5、消除文法GS的左遞歸(GS)GS: 4 AB6、對下面的文法Zt aB At aB構造狀態轉換圖At bB|AaBt Sb|aGZBt bB Bt aA Bt b，并說明符號串aaaabbb是否是該文法接受的句子三、問答題：(共50分)1、已知文法 G S:=bBc|aAB A:=bAa|a B:=a|寫出所有非終結符號的 First集和Follow集，構造預測分析表并給出輸入串2、正規式 0 (0|1 ) *1構造該正規式所對應的 NFA (畫出狀態轉換圖)。將所求的NFA確定化和最小化。(分別畫出確定化和最小化的狀態轉換圖)3、 若有文法 G (S)的產

27、生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c 的 DFA。(20 分)判斷該文法是否是判斷該文法是否是判斷該文法是否是判斷該文法是否是abbaaa分析過程。(10分)。(10 分)構造識別所有項目集規范族4、簡述編譯的整個過程LR( 0)文法，說明理由。 SLR( 1)文法，說明理由。LR( 1)文法，說明理由。 LALR( 1)文法，說明理由。(10 分)。德州學院期末考試試題課程名稱:學年第學期)考試對象:試卷類型:考試時間:分鐘一、選擇題(本大題共1、要在某一臺機器上為某種語言構造一個編譯程序，必須找掌握下述三方面的內容: 高級語言機器語言可選項有a、20小題，每小

28、題1分，共20 分)源語言目標語言程序設計方法編譯方法O測試方法b、C、d、2、“用高級語言書寫的源程序都必須經過編譯，產生目標代碼后才能投入運行?！边@種說法Oa、不正確b、正確3、若一個文法是遞歸的，則它所產生的句子個數a、必定是無窮的b、是有限個的4、 下列文法二義文法E:=EiT|T T:=T+F|iF|F F:=ET|( 可選項有：a、是5、編譯程序的語法分析器接受以 項有：a、表達式6、文法 GZ:a、Zt Beb、產生式Zt Be At Ae|eb、At Ae|e7、算符優先文法屬于a、自頂向下語法分析法b、8、設有文法 GS= (a, S,B,a、aji 0 b、 a2i|i 0

29、oc、根據具體情況而定b、不是C、無法判斷。為單位的輸入，并產生有關信息供以后各階段使用?？蛇xC、 單詞 d、語句Bt AfDt f 中，_c、Bt Afd、Dt f是多余產生式LR分析法C、SLR分析法d、自底向上語法分析法S, Sta|aB, B t aS,該文法描述的語言是 c、 a2i+1|i 0 d、 a2i+1|i 19、描述語言L=ambn|n m 1的文法是a、ZtABbb、ZtABbc、ZtAbAt aA|aBt bB|b10、一個句型中的最左a、短語 b、直接短語c、素短語d、終結符號11、通常高級語言的詞法規則可用正規式描述，詞法分析器可用a、語法樹b、有限自動機C、棧

30、d、堆12、 文法 GS: StAAAtAa|a不是LR (1)文法，理由是FIRST(Sfr FIRST(A產FIRST(A)n FOLLOW(A產FIRST(Aa(r FIRST(a產都不是13、 素短語是指 的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：a、 b、C、d、e、f、g、14、 給定文法GS: 4 ACcat aA|SbCt DefDt hACDd|eC|Et bDe| 該文法是。( 1)右線性文法(2 )前后文無關文法(3)

31、左遞歸文法(4) LL ( 1)b、Zt ABbAt Aa|aBt aBb|b稱為該句型的句柄。c、素短語At aAb|ad、Zt aAbAtAb|aAb| 來實現a、b、C、d、文法可選項有：a、 b、15、算符文法是指c、d、的文法。 沒有形如Ut. VW的規則 (U、V、W為非終結符) 終結符號集中任意兩個符號對之間至多有一種優先關系成立 沒有相同的規則右部 沒有形如UT的規則可選項有a、b、16、下列正規表達式中 _a、(a*|b* ) (c|d) b、(a*|b* ) *(c|d)c、(ab)*(d|c) d、(a*b*) (cd)17、 若一個句型中出現了某一產生式的右部，則此右部

32、 是該句型的句柄a、一定b、不定18、前后文無關文法和正規文法所產生的語言類相比 a、前后文無關文法產生的語言類大b、正規文法產生的語言類大C、兩者產生的語言類一樣大d、無法比較19、編譯過程中，比較常見的中間語言有 波蘭表示 逆波蘭表示 三元式c、d、與(a|b)*(c|d)等價。b、(a*|b* ) *(c|d) 四元式 樹形表示可選項有：a、b、C、d、20、LL (1)文法的條件是_對形如 UX1|X2|Xn對形如 UX1|X2|Xna和b都不是a、b、c、d、o的規則，要求 FIRST(Xi) )n FIRST (Xj)=年 j)的規則 若 Xi* 則要求 FIRST(Xj) n F

33、OLLOW (U)=II1|I0|Ia|Ic|a|b|c，下列符號串中是該文法的句子的有(1) ab0a0c01aaa (4)bc104、一個上下文無關文法 G包含四個組成部分依次為：一組一個，以及一組_5、確定的有窮自動機是一個6、 編 譯 程 序是、，一組，通常表示為。般 含 有 八 部 分二、簡答題：(每小題5分，1、對于下面的文法 GSS Sa|Ab|b|cA Bc|aB Sb|b構造狀態轉換圖，并說明符號串bcbabcba是否是該文法接受的句子2、 設一文法 GT: T T*F|FF Ft P|PP (T)|i 證明T*P t (T*F)是它的一個句型，并指出該句型的全部短語，直接短

34、語，句柄和素短語。3、求出下列文法所產生語言對應的正規式。Z aZ|bZ|aAA aBB aA|b4、將表達式(A+B*D) /E+F) *F+GE分別表示為三元式、四元式、逆波蘭式序列。5、(5分)消除文法GS的左遞歸GS: 4 SA|AA SB|B|(S)|()B S | 6、(5分)對下面的文法 GEE E+T|T|T T T*F|F F Pt F|P P i(+、*、t、i 是終結符號)構造文法的算符優先矩陣表，判斷此文法是否是算符優先文法。三、問答題：(50分)1、 已知文法 GS S eT|RT T DR|R dR|D a|bd寫出所有非終結符號的 First集和Follow集，構

35、造LL(1)分析表，判斷此文法是否是 分)2、給出正規式 (a|b)*bb(a|b)*構造該正規式所對應的 NFA (畫出狀態轉換圖)。將所求的NFA確定化和最小化。(分別畫出確定化和最小化的狀態轉換圖)。(10分)3、 若有文法 G (S)的產生式如下：S aAD|aBe|bBS|bAeA g B g D d|，構造識別所有 LR(1) 項目集規范族的 DFAt (20分)判斷該文法是否是 LR( 1)文法，說明理由，構造判斷該文法是否是 LALR (1)文法，說明理由。4、簡述編譯的整個過程(10分)。德州學院期末考試試題共 30 分)LR (1)表。課程名稱:LL (1)文法。(10二、

36、簡答題(每題5分，共30分)1、已知文法GZ:Z U0|V1U Z1|1V Z0|0寫出全部由此文法描述的只含有四個符號的句子。2、文法GN為：N D|NDD 0|1|2|3|4|5|6|7|8|9GN的語言是什么3、設一文法GSS( AS)S( b)A( SaA)A( a)對于句子(b) a (a) (b)，寫出該句子的最左推導，畫出語法樹，寫出其全部短語, 直接短語和句柄。4、構造下述文法GS的自動機：S A0 A A0|S1|05、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列 &消除下列文法的左遞歸。S:=Sa P|Sf|PP:=Qb P|QQ:=cSd|

37、e學年第學期)考試對象:試卷類型:考試時間:分鐘三、綜合題(共計1、50分)把下圖確定化和最小化：(15分)bb一、填空題(每空1分，共20分)1、假設G是一個文法，S是文法的開始符號，如果S,則稱X 是.2、 喬姆斯基定義的四種形式語言分別為： 文法、文法、3、設有文法Gl:文法、文法。2、已知文法 G S:=bBc|aAB A:=bAa|a B:=a|寫出所有非終結符號的First集和Follow集，構造預測分析表并給出輸入串abbaaa分析過程。(15分)若有文法 G( S)的產生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構造 識別所有項目集規范族的DFA (20分

38、)3、判斷該文法是否是 判斷該文法是否是 判斷該文法是否是 判斷該文法是否是LR (0)文法，說明理由。 SLR( 1)文法，說明理由。LR (1)文法，說明理由。LALR( 1)文法，說明理由。德州學院期末考試試題a、是b、不是 c、無法判斷。課程名稱:學年第學期)考試對象:試卷類型:(1)考試時間:一、選擇題(本大題共1、 描述一個語言的文法是 。a唯一的b、不唯一的C、個數有限的2、 匯編程序是將 翻譯成;編譯程序是將 _a匯編語言程序b、機器語言程序C、高級語言程序3、設有文法Gl:It I0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有 ab0 a0c01 aaa b

39、c10可選項有a b、C、 d、4、生成非0開頭的正偶數集的文法是a Z:=ABCC:=0|2|4|6|8 B:=BA|B0| A:=1|2|3|4|5|6|7|8|9b、Z:=ABCC:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|920小題，每小題1分，共20 分)翻譯成。d匯編語言或機器語言程序5、 一個上下文無關文法G包括四個組成部分依次為：a字符串b、字母數字串C、產生式結符號h、終結符號6、 現有前綴表示的表達式文法G1:E:=-EEE:=-E E:=a|b|c則文法的句子一a-bc的所有可能語法樹有C、Z:=ABC|2|4|6|8C:=0|2|4|

40、6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9一組、一個、一組、一組?？蛇x項有：&語法分析的常用方法是自頂向下自底向上可選項有：b、 C、 d、LR (K)文法是從左到右分析，從左到右分析，從左到右分析，從左到右分析，10、素短語是指_ 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：a、 b、C、d、e、f、g11、 文

41、法的二義性和語言的二義性是兩個 概念。a、不同b、相同C、無法判斷12、 在編譯中產生語法樹是為了 。a、語法分析b、語義分析C、詞法分析13、 下述正規表達式中 與(a*+b)*(c+d)等價。可選項有：a、b、自左向右自右向左d、結束符號e、開始符號 f、文法 g、非終棵。a、9、a、b、C、d、a* (c+d)a* (c+d)a* (c+d)a、1 b、2c、3 d、47、下列文法二義文法E:=EiT|T T:=T+F|iF|F F:=E*|(O共經過 K步的一種編譯方法。 每次向前預測K步的一種編譯方法。每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。每次走 K步的一種編譯方法。

42、的短語。d、產生目標代碼+b (c+d)*+b (c+d) *+b* (c+d)(a+b) *c+ (a+b) *d(a*+b ) *c+ ( a*+b) *dc、 d、 e、f、g，這樣的語言，他們能被確定的有限自動機識別，但不能用正規表達式表示: b、不存在c無法判定是否存在17、_a、存在15、LL ( K)文法二義性的。a、都是b、都不是C、不一定都是16、 下面的文法是 。S:=aAa|aBb|bAb|bBa A:=x B:=x可選項有：a、LR (1)文法b、LALR (1)文法 c、都不是 d、a和b17、編譯過程中，比較常見的中間語言有 波蘭表示 逆波蘭表示 三元式 四元式 樹

43、形表示可選項有：a、18、-a- (b*c/ (c-d) +a、abc*cd-b-a*+/-b、c、d、(-b) *a)的逆波蘭表示是b、a-bc*cd-b-a*+/-C、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、 在編譯程序中安排中間代碼生成的目的是 便于進行存儲空間的組織 利于目標代碼優化 利于編譯程序的移植 利于目標代碼的移植 利于提高目標代碼的質量可選項有：a、b、 c d、20、代碼優化的主要目標是 如何提高目標程序的運行速度 如何減少目標程序運行所需的空間。 如何協調和 如何使生成的目標代碼盡可能簡短可選項有：a、 b、C、 d、簡答題：(每小題5分，共30分)(2)構造預測分析表并給出輸入串