四川大學(xué)編譯原理期末試卷4套+復(fù)習(xí)資料

1、四川大學(xué)期末考試試題A (閉卷) (2012-2013學(xué)年第2學(xué)期)一簡答題 1.符號表的作用是什么？為了達到對其插入刪除等操作的復(fù)雜度為O(1)，需將其組織成什么數(shù)據(jù)結(jié)構(gòu)。2.分析樹和語法書的區(qū)別。 3.什么是正規(guī)集。 4.什么叫句子，什么叫句型。 5.二義文法一定不是LL（1）   二給定文法      SA      AA+A|B+    &

2、#160; By 1. 畫出句子y+y+的分析樹 2.給出句子y+y+的最右推導(dǎo)    三給定正則表達式（a|b）*abb 1.使用thompson構(gòu)造法構(gòu)造等價的NFA。 2.用子集法對（1）得到的NFA進行確定化和最小化，得到等價的最小DFA。 3.使用雙層多分支語句實現(xiàn)（2）得到的DFA。寫出偽代碼。四給定文法 statementif-stmt|other|e if-stmtif(exp)statement else-part else-partel

3、se statement|e exp0|1 寫出遞歸下降子程序的偽代碼。5 給定文法 SSX|a Xe|+SY|Yb Ye|-SXc 1. 對文法中的每一個非終結(jié)符構(gòu)造First集和Follow集。 2.構(gòu)造LL（1）分析表 3.基于分析表，使用LL(1)對句子a+a-ac進行自頂向下的語法分析，給出每一步的動作及分析棧和輸入串的變化情況。六給定文法 EE+T|T TT*F|F F(E)|id  1.構(gòu)造LR（0）項目的DFA： 2.構(gòu)造SLR（

4、1）的分析表 3.利用2得到的分析表對id+id*id進行自頂向下的語法分析。七 1.給出構(gòu)造Follow集合的算法描述 2.給出SLR（1）算法的描述 四川大學(xué)期末考試試題 (閉卷) (2010-2011學(xué)年第2學(xué)期) 1. 簡答題 (12分) (1) 編譯器的前端和后端分別包括哪幾個階段？前后端分開有什么好處？ (2) 解釋器和編譯器有什么本質(zhì)區(qū)別？ (3) 詞法分析和語法分析的功能分別是什么？ (4) 分析樹與抽象語法樹

5、有什么不同？2. 已知字母表 = a, b, cå，定義在上的語言L具有以下特征：(5分) (1) 若出現(xiàn)a，則其后至少緊跟兩個c； (2) 若出現(xiàn)b，則其后至少緊跟一個c。 試給出可以產(chǎn)生語言L的正規(guī)表達式。  3. 文法如下：(8分) exp exp addop term |termaddop +|- termterm mulop factor| factormulop * factor (exp)|number(1) &

6、#160;給出句子3*)58(+的最左推導(dǎo)； (2) 構(gòu)造(1)中句子的抽象語法樹。  4. 文法如下：(10分) exp exp and exp|exp or exp|not  exp|(exp)|TRUE|FALSE (1) 此文法是否為二義文法？為什么？ (2) 試將文法改寫為非二義文法，要求運算符優(yōu)先級由低到高分別是or、and、not，且and和or是左結(jié)合的，not是右結(jié)合的。  5. DFA構(gòu)造題(20

7、分) 已知正規(guī)表達式 bbca*)|( (1) 使用Thompson構(gòu)造方法構(gòu)造對應(yīng)的NFA； (2) 用子集構(gòu)造法將得到的NFA確定化為DFA； (3) 將得到的DFA最小化。6. LL(1)分析題(20分) 文法如下： A Pa  P bPa|bQb  Q Qa|a (1) 消除文法左遞歸，提左因子； (2) 為所得文法的每個非終結(jié)符構(gòu)造First集和Follow集； (3) 所得文法是LL(1)文法嗎

8、？為什么？ (4) 構(gòu)造所得文法的LL(1)分析表。7. LR(k)分析題(25分) 文法如下： declaration type list-var ®type int|float var -list id,var -list|id (1) 構(gòu)造文法的LR(0)項目的DFA； (2) 構(gòu)造SLR(1)分析表； (3) 這個文法是SLR(1)文法嗎？如果不是，請說明原因； (4) 給出對應(yīng)輸入串int x,y,z進行SLR(1)

9、分析的步驟(要求給出分析過程中每一步的詳細(xì)情況，包括：分析棧、輸出串及執(zhí)行的動作)。四川大學(xué)期末考試試題A (閉卷) (2008-2009學(xué)年第2學(xué)期)  一、簡答題 (本大題共4小題，每小題3分，共12分) 1. 按照次序?qū)懗鲆粋€完整的編譯器的各個階段以及各個階段的輸入輸出。2. 一個文法必須滿足哪些條件才是LL(1)的？3.給出上下文無關(guān)文法(Context-Free Grammar)的定義。4.寫正規(guī)表達式：所有不以0開頭的十進制偶數(shù)的集合。二、算法題 (本答題共1小題，每小題8分，共8分)

10、0;給出基于DFA進行詞法分析的表驅(qū)動的實現(xiàn)算法。3、 分析題 (本答題共3小題，每小題分?jǐn)?shù)見題首，共10分) 文法如下：SSS+|SS*|a+® 1. (4分)給出句子aa+a*的最右推導(dǎo)； 2. (3分)構(gòu)造(1)中句子的分析樹； 3. (3分)這個文法產(chǎn)生的語言是什么？4、 文法二義性分析題 (本大題共2小題，每小題5分，共10分) 文法如下： expexp op exp |(exp)|TRUE |FALSEOp and|or® 

11、1. 此文法是否為二義文法？為什么？ 2. 試將文法改寫成非二義文法，要求運算符op是左結(jié)合的，且and的優(yōu)先級高于or的優(yōu)先級。5、 DFA構(gòu)造題 (本大題共3小題，每小題分?jǐn)?shù)見題首，共20分)6、 已知正規(guī)表達式 (a|b)*c*b1. (6分)使用Thompson構(gòu)造方法構(gòu)造對應(yīng)的NFA； 2. (8分)用子集構(gòu)造法將得到的NFA確定化為DFA； 3. (6分)將得到的DFA最小化。六、LL(1)分析題 (本大題共4小題，每小題5分，共20分) 文法如下：SS

12、LS |a®           LbbL|b® 1. 消除文法左遞歸，并提左因子； 2. 為所得文法的每個非終結(jié)符構(gòu)造First集和Follow集； 3. 構(gòu)造所得文法的LL(1)分析表； 4. 所得文法是LL(1)文法嗎？為什么？七、LR(k)分析題 (本大題共3小題，每小題分?jǐn)?shù)見題首，共20分) 文法如下： S(A)|bB® 

13、60;         A a|aB®            BA a b® 1. (10分)構(gòu)造文法的LR(0)項目的DFA； 2. (6分)構(gòu)造SLR(1)分析表； 3. (4分)這個文法是SLR(1)文法嗎？請說明是或不是的原因。四川大學(xué)期末考試試題A (閉卷) (2007

14、-2008學(xué)年第2學(xué)期) 1. (9分)簡答題 (1) 編譯器的前端和后端分別包括哪幾個階段？前后端分開有什么好處？   (2) 在建立LL(1)語法分析器的時候，提左因子和消除左遞歸的目的分別是什么？ (3) 詞法分析和語法分析的功能分別是什么？2. (5分)已知字母表=a,b,c，定義在上的語言L具有以下特征： (1) 若出現(xiàn)a，則其后至少緊跟兩個c； (2) 若出現(xiàn)b，則其后至少緊跟一個c。 試給出可以產(chǎn)生語言L的正規(guī)表達式。3.

15、 (6分)文法如下， S(L)|a  LL,S|S(1)  證明句子(a,(a,a)可以由此文法產(chǎn)生； (2) 構(gòu)造(1)中句子的分析樹。4.  (5分)構(gòu)造如下文法的遞歸下降分析程序（recursive-descent parser）SbSa|b5.  (10分)文法如下， ExpExp® Op Exp|(Exp)|number ®Op+|-|* (1) 此文法是否為二義文法？為什么？ (2) 試將文法改

16、寫為非二義文法，其中要求運算符Op是左結(jié)合的，且*的優(yōu)先級高于+、-的優(yōu)先級。6.  (20分)已知正規(guī)表達式)(a|ba)*(b|a)(1)  使用Thompson構(gòu)造方法構(gòu)造對應(yīng)的NFA； (2) 用子集構(gòu)造法將得到的NFA確定化為DFA； (3) 將得到的DFA最小化。7.  (25分)文法如下， S(L)|a  LL,S|S(1) 消除文法左遞歸； (2) 為所得文法的每個非終結(jié)符構(gòu)造First集和Follow集； (3) 所得文法是LL(1)文法

17、嗎？為什么？ (4) 構(gòu)造所得文法的LL(1)分析表； (5) 寫出對輸入串)(,(aa進行LL(1)分析的過程。8. (20分)文法如下， declaration type list-var ®type int|float var -list id,var -list|id(1) 構(gòu)造文法的LR(0)項目的DFA；(10分) (2) 構(gòu)造SLR(1)分析表；(6分) (3) 這個文法是SLR(1)文法嗎？如果不是，請說明原因；(4分) 1.&#

18、160;編譯的各個階段 掃描程序(scanner) 在這個階段編譯器實際閱讀源程序（通常以字符流的形式表示）。掃描程序執(zhí)行詞法分析（Lexical analysis）：它將字符序列收集到稱作記號(t o k e n）的有意義單元中，記號同自然語言，如英語中的字詞相似。  語法分析程序(parser) 語法分析程序從掃描程序中獲取記號形式的源代碼，并完成定義程序結(jié)構(gòu)的語法分析（syntax analysis），這與自然語言中句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將

19、語法分析的結(jié)果表示為分析樹（ parse tree）或語法樹（syntax tree）。  語義分析程序（semantic analyzer） 分析程序的靜態(tài)語義，包括包括聲明和類型檢查。  源代碼優(yōu)化程序（source code optimizer），代碼生成器（code generator），目標(biāo)代碼優(yōu)化程序（target code optimizer）2. 編譯器的前端（front end），后端（back end），遍

20、（passes） 掃描程序、分析程序和語義分析程序是前端，代碼生成器是后端。 編譯器發(fā)現(xiàn)，在生成代碼之前多次處理整個源程序很方便。這些重復(fù)就是遍（p a s s）  3. 編譯器，匯編器和解釋器之間的區(qū)別     解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執(zhí)行源 程序而不是生成在翻譯完成之后才執(zhí)行的目標(biāo)代碼。 匯編程序是用于特定計算機上的匯編語言的翻譯程序。有時，編譯器會生成匯編語言以作為其目標(biāo)語言，然后再由一個匯編

21、程序?qū)⑺g成目標(biāo)代碼。  4. 掃描，分析（語法，詞法）的任務(wù) 掃描的任務(wù)是將源程序讀作字符文件并將其分為若干個記號     掃描程序的任務(wù)是從源代碼中讀取字符并形成由編譯器的以后部分（通常是分析程序）處理的邏輯單元。 由掃描程序生成的邏輯單元稱作記號（ t o k e n） 分析的任務(wù)是確定程序的語法，或稱作結(jié)構(gòu) 分析程序的任務(wù)是從由掃描程序產(chǎn)生的記號中確定程序的語法結(jié)構(gòu)，以及或隱式或顯式地構(gòu)造出表示該結(jié)構(gòu)的分析樹或語法樹

22、 5. 上下文無關(guān)文法，最左推導(dǎo)，BNF，EBNF，喬姆斯基文法層次     上下文無關(guān)文法說明程序設(shè)計語言的語法結(jié)構(gòu)，利用了與正則表達式中極為類似的命名慣例和運算。二者的主要區(qū)別在于上下文無關(guān)文法的規(guī)則是遞歸的（recursive） 最左推導(dǎo)（ leftmost derivation）是指它的每一步中最左的非終結(jié)符都要被替換的推導(dǎo) 最右推導(dǎo)（ rightmost derivation）則是指它的每一步中最右的非終結(jié)符都要被替換的推導(dǎo)。最左推導(dǎo)和與其相關(guān)的分析樹的內(nèi)

23、部節(jié)點的前序編號相對應(yīng)；而最右推導(dǎo)則和后序編號相對應(yīng)  最左推導(dǎo)的一個例子：書p73相關(guān)題目：3.3  EBNF中注意重復(fù)和可選的表示方法，語法圖 6. 句子，句型，文法所定義的語言，分析樹，抽象語法樹  7. 自頂向下，自底向上語法分析    自頂向下（t o p - d o w n）的分析算法通過在最左推導(dǎo)中描述出各個步驟來分析記號串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號是一

24、個前序編號，而且其順序是由根到葉。分為兩類：回溯分析程序（ backtracking parser）和預(yù)測分析程序（ predictive parser）    自底向上的分析程序有兩種可能的動作(除“接受”之外)： 1) 將終結(jié)符從輸入的開頭移進到棧的頂部。 2) 假設(shè)有B N F選擇Aa，將棧頂部的串a(chǎn)歸約為非終結(jié)符A。  8. 為什么要解決公因子，左遞歸 當(dāng)有公因子存在時，不能立即區(qū)分出文法規(guī)則右邊的選擇

25、60;當(dāng)有左遞歸時，將導(dǎo)致一個無限循環(huán)。  9. 寫正則表達式，構(gòu)造NFA，DFA，最小化（按照算法做） 構(gòu)造NFA（使用Thompson結(jié)構(gòu)）: 書P45-47將NFA轉(zhuǎn)換成DFA（最小子集法）： - 閉包（ - c l o s u r e）是可由轉(zhuǎn)換從某狀態(tài)或某些狀態(tài)達到的所有狀態(tài)集合，它總是包含狀態(tài)本身  子集構(gòu)造：參見Chapter_two(2).ppt 相關(guān)題目：2.1，2.12，2.16 10. 寫最左推導(dǎo)，最右推導(dǎo)，畫分析樹和抽象語法樹 相關(guān)題目：3.3  11. 寫出給