




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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. 寫出給
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- A-Level經(jīng)濟(jì)學(xué)(A2)2024-2025學(xué)年模擬試卷:宏觀政策影響評(píng)估全攻略
- 廣東省實(shí)驗(yàn)中學(xué)11-12學(xué)年高一上學(xué)期期末試題(政治)
- 2025年征信考試題庫(kù):征信風(fēng)險(xiǎn)評(píng)估與防范信用風(fēng)險(xiǎn)防范技術(shù)應(yīng)用試題
- 2025年乒乓球裁判員等級(jí)考試二級(jí)模擬試卷:規(guī)則應(yīng)用與執(zhí)裁技巧提升策略
- 理論與實(shí)踐財(cái)務(wù)成本管理試題及答案
- 廣東省仲元中學(xué)2017-2018學(xué)年高二下學(xué)期期中試題文(數(shù)學(xué))
- 2025年學(xué)校食堂食品安全衛(wèi)生管理要點(diǎn)全解
- 2025年消防安全知識(shí)培訓(xùn)考試題庫(kù):消防信息化建設(shè)培訓(xùn)教材云計(jì)算教程試題
- 2025年高考數(shù)學(xué)模擬檢測(cè)卷(概率與統(tǒng)計(jì)綜合)-概率問(wèn)題與統(tǒng)計(jì)圖表結(jié)合試題
- 安全評(píng)估業(yè)務(wù)合作協(xié)議書
- 《高效面試技巧課件版》教案
- 實(shí)驗(yàn)室精密儀器全面維護(hù)保養(yǎng)服務(wù)協(xié)議
- (三模)2025年沈陽(yáng)市高中三年級(jí)教學(xué)質(zhì)量監(jiān)測(cè) (三)生物試卷(含答案)
- 拓?fù)鋬?yōu)化與異形結(jié)構(gòu)打印-洞察闡釋
- 【綏化】2025年黑龍江綏化市“市委書記進(jìn)校園”事業(yè)單位引進(jìn)人才287人筆試歷年典型考題及考點(diǎn)剖析附帶答案詳解
- 粉筆協(xié)議班電子合同
- 2025年電纜購(gòu)銷合同范本9篇
- 2025+CSCO非小細(xì)胞肺癌診療指南解讀課件
- 中學(xué)生學(xué)憲法班會(huì)課件
- 醫(yī)院后勤考試試題及答案
- -小學(xué)英語(yǔ)人稱代詞與物主代詞講解課件(共58張課件).課件
評(píng)論
0/150
提交評(píng)論