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

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

2、#160; By 1. 畫出句子y+y+的分析樹 2.給出句子y+y+的最右推導(dǎo)    三給定正則表達(dá)式（a|b）*abb 1.使用thompson構(gòu)造法構(gòu)造等價(jià)的NFA。 2.用子集法對(duì)（1）得到的NFA進(jìn)行確定化和最小化，得到等價(jià)的最小DFA。 3.使用雙層多分支語(yǔ)句實(shí)現(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. 對(duì)文法中的每一個(gè)非終結(jié)符構(gòu)造First集和Follow集。 2.構(gòu)造LL（1）分析表 3.基于分析表，使用LL(1)對(duì)句子a+a-ac進(jìn)行自頂向下的語(yǔ)法分析，給出每一步的動(dòng)作及分析棧和輸入串的變化情況。六給定文法 EE+T|T TT*F|F F(E)|id  1.構(gòu)造LR（0）項(xiàng)目的DFA： 2.構(gòu)造SLR（

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

5、有什么不同？2. 已知字母表 = a, b, cå，定義在上的語(yǔ)言L具有以下特征：(5分) (1) 若出現(xiàn)a，則其后至少緊跟兩個(gè)c； (2) 若出現(xiàn)b，則其后至少緊跟一個(gè)c。 試給出可以產(chǎn)生語(yǔ)言L的正規(guī)表達(dá)式。  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)中句子的抽象語(yǔ)法樹。  4. 文法如下：(10分) exp exp and exp|exp or exp|not  exp|(exp)|TRUE|FALSE (1) 此文法是否為二義文法？為什么？ (2) 試將文法改寫為非二義文法，要求運(yùn)算符優(yōu)先級(jí)由低到高分別是or、and、not，且and和or是左結(jié)合的，not是右結(jié)合的。  5. DFA構(gòu)造題(20

7、分) 已知正規(guī)表達(dá)式 bbca*)|( (1) 使用Thompson構(gòu)造方法構(gòu)造對(duì)應(yīng)的NFA； (2) 用子集構(gòu)造法將得到的NFA確定化為DFA； (3) 將得到的DFA最小化。6. LL(1)分析題(20分) 文法如下： A Pa  P bPa|bQb  Q Qa|a (1) 消除文法左遞歸，提左因子； (2) 為所得文法的每個(gè)非終結(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)項(xiàng)目的DFA； (2) 構(gòu)造SLR(1)分析表； (3) 這個(gè)文法是SLR(1)文法嗎？如果不是，請(qǐng)說(shuō)明原因； (4) 給出對(duì)應(yīng)輸入串int x,y,z進(jìn)行SLR(1)

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

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

11、1. 此文法是否為二義文法？為什么？ 2. 試將文法改寫成非二義文法，要求運(yùn)算符op是左結(jié)合的，且and的優(yōu)先級(jí)高于or的優(yōu)先級(jí)。5、 DFA構(gòu)造題 (本大題共3小題，每小題分?jǐn)?shù)見題首，共20分)6、 已知正規(guī)表達(dá)式 (a|b)*c*b1. (6分)使用Thompson構(gòu)造方法構(gòu)造對(duì)應(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. 為所得文法的每個(gè)非終結(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)項(xiàng)目的DFA； 2. (6分)構(gòu)造SLR(1)分析表； 3. (4分)這個(gè)文法是SLR(1)文法嗎？請(qǐng)說(shuō)明是或不是的原因。四川大學(xué)期末考試試題A (閉卷) (2007

14、-2008學(xué)年第2學(xué)期) 1. (9分)簡(jiǎn)答題 (1) 編譯器的前端和后端分別包括哪幾個(gè)階段？前后端分開有什么好處？   (2) 在建立LL(1)語(yǔ)法分析器的時(shí)候，提左因子和消除左遞歸的目的分別是什么？ (3) 詞法分析和語(yǔ)法分析的功能分別是什么？2. (5分)已知字母表=a,b,c，定義在上的語(yǔ)言L具有以下特征： (1) 若出現(xiàn)a，則其后至少緊跟兩個(gè)c； (2) 若出現(xiàn)b，則其后至少緊跟一個(gè)c。 試給出可以產(chǎn)生語(yǔ)言L的正規(guī)表達(dá)式。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、寫為非二義文法，其中要求運(yùn)算符Op是左結(jié)合的，且*的優(yōu)先級(jí)高于+、-的優(yōu)先級(jí)。6.  (20分)已知正規(guī)表達(dá)式)(a|ba)*(b|a)(1)  使用Thompson構(gòu)造方法構(gòu)造對(duì)應(yīng)的NFA； (2) 用子集構(gòu)造法將得到的NFA確定化為DFA； (3) 將得到的DFA最小化。7.  (25分)文法如下， S(L)|a  LL,S|S(1) 消除文法左遞歸； (2) 為所得文法的每個(gè)非終結(jié)符構(gòu)造First集和Follow集； (3) 所得文法是LL(1)文法

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

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

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

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

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

22、 5. 上下文無(wú)關(guān)文法，最左推導(dǎo)，BNF，EBNF，喬姆斯基文法層次     上下文無(wú)關(guān)文法說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)，利用了與正則表達(dá)式中極為類似的命名慣例和運(yùn)算。二者的主要區(qū)別在于上下文無(wú)關(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é)點(diǎn)的前序編號(hào)相對(duì)應(yīng)；而最右推導(dǎo)則和后序編號(hào)相對(duì)應(yīng)  最左推導(dǎo)的一個(gè)例子：書p73相關(guān)題目：3.3  EBNF中注意重復(fù)和可選的表示方法，語(yǔ)法圖 6. 句子，句型，文法所定義的語(yǔ)言，分析樹，抽象語(yǔ)法樹  7. 自頂向下，自底向上語(yǔ)法分析    自頂向下（t o p - d o w n）的分析算法通過(guò)在最左推導(dǎo)中描述出各個(gè)步驟來(lái)分析記號(hào)串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號(hào)是一

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

25、60;當(dāng)有左遞歸時(shí)，將導(dǎo)致一個(gè)無(wú)限循環(huán)。  9. 寫正則表達(dá)式，構(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)達(dá)到的所有狀態(tài)集合，它總是包含狀態(tài)本身  子集構(gòu)造：參見Chapter_two(2).ppt 相關(guān)題目：2.1，2.12，2.16 10. 寫最左推導(dǎo)，最右推導(dǎo)，畫分析樹和抽象語(yǔ)法樹 相關(guān)題目：3.3  11. 寫出給