編譯原理2012復(fù)習(xí)

1、復(fù)習(xí),2011.4.26,第一章要點(diǎn),編譯器的概念。其輸入和輸出。機(jī)器語(yǔ)言->匯編語(yǔ)言->高級(jí)語(yǔ)言。喬姆斯基分層結(jié)構(gòu)。0型-無(wú)限制文法1型-上下文相關(guān)文法2型-上下文無(wú)關(guān)文法3型-正則文法,第一章要點(diǎn),相關(guān)程序和概念解釋器編輯器交互式開發(fā)環(huán)境（IDE）調(diào)試程序分析和綜合前端和后端遍※編譯器的翻譯過(guò)程,第一章 2009,編譯器各處理階段的正確順序是（ ）A．詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成；

2、B．語(yǔ)法分析、詞法分析、語(yǔ)義分析、代碼生成；C．語(yǔ)義分析，語(yǔ)法分析、詞法分析，代碼生成；D．以上都不對(duì)。編譯器中語(yǔ)法分析的輸入和輸出分別是（ ）A．字符串、記號(hào)串B．記號(hào)串、注釋樹C．記號(hào)串、語(yǔ)法樹D．語(yǔ)法樹、注釋樹 什么是編譯器？請(qǐng)簡(jiǎn)述編譯器的功能及其輸入輸出。,第一章 2008,以下對(duì)編譯器(compiler)描述錯(cuò)誤的是（ ）。A 編譯器的輸入是由源語(yǔ)言編寫的源程序，輸出是由目標(biāo)語(yǔ)言編寫的目標(biāo)程序。

3、B 編譯器是一個(gè)執(zhí)行程序而不是一個(gè)轉(zhuǎn)換程序。C 編譯器和編輯器以及其它程序經(jīng)常被捆綁成一個(gè)與用戶交互的開發(fā)環(huán)境(IDE)中。D 按照編譯器掃描的遍數(shù)，可把編譯器分為一遍掃描和多遍掃描的編譯器。把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由______完成的。 A、編譯器 B、解釋器C、匯編器 D、預(yù)處理器,第

4、一章 2008,編譯器的工作可分為多個(gè)階段，詞法分析、語(yǔ)法分析、語(yǔ)義分析階段的結(jié)果分別是（）。A 分析樹、語(yǔ)法樹、語(yǔ)義樹；B 分析樹、語(yǔ)法樹、注釋樹；C 記號(hào)序列、語(yǔ)法樹、語(yǔ)義樹；D 記號(hào)序列、分析樹、注釋樹。文法根據(jù)限定條件分為四種文法：0型文法、1型文法、2型文法、3型文法。其中2型文法又叫做（）文法，3型文法又叫做（　）文法。高級(jí)程序設(shè)計(jì)語(yǔ)言源程序有兩種執(zhí)行方式，即____和____。 什么是編譯器？什么是遍。

5、什么是掃描器？掃描器的功能是什么？,第一章 2010,以下對(duì)編譯器(compiler)描述錯(cuò)誤的是（ ）。A. 編譯器是將一種語(yǔ)言翻譯成另一種語(yǔ)言的計(jì)算機(jī)部件，包括軟件部分和硬件部分；B. 輸入編譯器的源語(yǔ)言通常是高級(jí)語(yǔ)言，如C語(yǔ)言；輸出編譯器的目標(biāo)語(yǔ)言通常是低級(jí)語(yǔ)言，如01代碼；C. 詞法分析是編譯器的一個(gè)處理階段；D. 編譯器和編輯器以及其它程序經(jīng)常被捆綁成一個(gè)與用戶交互的開發(fā)環(huán)境(IDE)中。,第一章 2010,匯編

6、語(yǔ)言與機(jī)器語(yǔ)言相比，其主要優(yōu)點(diǎn)在于（ ）。A．匯編語(yǔ)言機(jī)器依賴性強(qiáng)；B．匯編程序的可執(zhí)行程序的長(zhǎng)度可以大幅下降；C．匯編語(yǔ)言的符號(hào)形式更易理解，也提高了編寫程序的準(zhǔn)確性；D．以上都不對(duì)。,第一章 2010,一般的編譯器中，語(yǔ)法分析的結(jié)果是生成源程序的（ ）。A．記號(hào)序列；B．分析樹；C．語(yǔ)法樹；D．注釋樹。編譯程序和解釋程序有哪些區(qū)別？,第一章 2011,下列程序中沒有翻譯功能的是（ ）。A匯編器

7、B 解釋器C 編譯器D 編輯器判斷：如果編譯器的源語(yǔ)言發(fā)生了改變，那么其前端操作無(wú)需修改。（ ）什么是語(yǔ)義分析程序？請(qǐng)解釋其功能及其輸入和輸出。,第二章要點(diǎn),掃描程序的功能及其輸入輸出。正則表達(dá)式什么是由r生成的語(yǔ)言，字母表，元符號(hào)三種基本操作有限自動(dòng)機(jī)定義DFA NFA,第二章要點(diǎn),※正則表達(dá)式=>NFA=>DFA=>程序RE =>NFA Thompson’s cons

8、tructionNFA=>DFA 子集構(gòu)造法DFA的化簡(jiǎn)DFA=>程序 三種方式+Lex,第二章 2011,以下對(duì)掃描器（scanner）描述正確的是（ ）。A 掃描器是編譯器的一個(gè)功能模塊，其功能是進(jìn)行語(yǔ)義分析；B 掃描器的輸入是語(yǔ)法樹，輸出是注釋樹；C 掃描器需要分析哪些字符組成了“詞”；D 掃描器無(wú)需提示任何錯(cuò)誤，而是由其它編譯器模塊來(lái)完成。,第二章 2011,下面不屬于正則表達(dá)式（re

9、gular expression）的基本操作的是（ ）。A 遞歸B 并置C 選擇D 閉包,第二章 2011,下面的NFA中，對(duì)狀態(tài)或狀態(tài)集合的ε-閉包描述正確的是（ ）。A 狀態(tài)1的ε-閉包是{2、4}；B 狀態(tài){2、3}的ε-閉包是{2、3、4}；C 狀態(tài)3的ε-閉包是{2、4}；D 狀態(tài)4的ε-閉包是空集。,第二章 2011,7.正則表達(dá)式(a|b)+生成的語(yǔ)言，以下描述正確的是（ ）。A

10、L((a|b)+)={由a和b組成的任意字符串}B L((a|b)+)={由a組成的字符串或由b組成的字符串}C L((a|b)+)={由a組成的字符串和由b組成的字符串}D 以上都不對(duì),第二章 2011,請(qǐng)解釋下面各正則表達(dá)式的含義，并分別列出其生成語(yǔ)言的實(shí)例。a．[a-zA-Z]([0-9]|[a-zA-Z])*b．AA?*\n|?*AA\nc．(+|-)?[0-9]+(“?”[0-9]+)?d．(b*a

11、b*ab*)+,第二章 2011,（15分）已知正則表達(dá)式(aa|b)*a(a|b|ε)1. 利用Thompson構(gòu)造法(Thompson’s construction)將該正規(guī)表達(dá)式(regular expression)轉(zhuǎn)化為NFA；2. 將1中得到的NFA轉(zhuǎn)化為DFA；3. 將2中得到的DFA進(jìn)行化簡(jiǎn)，以得到狀態(tài)數(shù)最少的DFA。,下面的DFA中，（ ）可以合并。A．狀態(tài)1和狀態(tài)2；B．狀態(tài)2和狀態(tài)3；C．狀態(tài)1和狀態(tài)

12、3；D．以上都不對(duì)。,第二章 2010,,第二章 2010,請(qǐng)寫出下面各個(gè)字符串的正規(guī)表達(dá)式(regular expression)a．十六進(jìn)制的數(shù)字串；b．含有偶數(shù)個(gè)2的數(shù)字串；c．不以AA開頭的大寫字母串。,第二章 2010,（15分）已知正則表達(dá)式(a|b)*a(b|ε)1. 利用Thompson構(gòu)造法(Thompson’s construction)將該正規(guī)表達(dá)式(regular expression)轉(zhuǎn)化為NFA；

13、2. 將1中得到的NFA轉(zhuǎn)化為DFA；3. 將2中得到的DFA進(jìn)行化簡(jiǎn)，以得到狀態(tài)數(shù)最少的DFA。,第二章 2009,表示“由a或b組成的含有偶數(shù)個(gè)b的字符串”的正則表達(dá)式是（ ）A．a(chǎn)*ba*ba*B. (a*ba*ba*)*C．(abab)*D. 以上都不對(duì)請(qǐng)寫出下面各個(gè)字符串的正則表達(dá)式所有整數(shù)的數(shù)字串（包括負(fù)數(shù)）字符串中至多含有一個(gè)A的大寫字母串請(qǐng)簡(jiǎn)述有限自動(dòng)機(jī)的組成元素并解釋DFA和NFA的區(qū)別。,

14、第二章 2009,以下不是有限自動(dòng)機(jī)的組成元素的是（）A．開始狀態(tài)B．結(jié)束狀態(tài)C．正則表達(dá)式D．狀態(tài)轉(zhuǎn)換函數(shù)已知正則表達(dá)式(ab)*(a|b)1．構(gòu)造該正則表達(dá)式所對(duì)應(yīng)的NFA；2．由NFA構(gòu)造DFA；3．對(duì)DFA進(jìn)行最小化。,第二章 2008,以下對(duì)有窮自動(dòng)機(jī)的圖形表示描述錯(cuò)誤的是（）。用帶箭頭的線表示一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換；用圓圈表示狀態(tài)；用雙線邊界的圓圈表示接受狀態(tài)。一個(gè)有窮自動(dòng)機(jī)里只能有唯一的一個(gè)

15、接受狀態(tài)；對(duì)于給定的一個(gè)非確定性有限自動(dòng)機(jī)（NFA），以下正確的是（）。不存在與之等價(jià)的DFA。存在一個(gè)唯一等價(jià)的DFA。存在一個(gè)唯一的具有最少狀態(tài)數(shù)的等價(jià)DFA。存在等價(jià)DFA，但具有最少狀態(tài)數(shù)的DFA不唯一。,第二章 2008,請(qǐng)寫出下面各個(gè)字符串的正則表達(dá)式：以a開頭或者以b結(jié)尾的小寫字母串；以字母開頭，后面是數(shù)字或字母的符號(hào)串；（即標(biāo)識(shí)符）已知正則表達(dá)式a(ba)*（1）構(gòu)造該正則表達(dá)式所對(duì)應(yīng)的NFA；（2

16、）由NFA構(gòu)造DFA；（3）對(duì)DFA進(jìn)行最小化。,第三章 要點(diǎn),分析程序的功能及其輸入輸出。常見的高級(jí)語(yǔ)言的文法（上下文無(wú)關(guān)文法）、表示方式（BNF）以及其特點(diǎn)（包含遞歸）。推導(dǎo)分析給定文法的：終結(jié)符、非終結(jié)符、生成的語(yǔ)言、對(duì)某個(gè)串的推導(dǎo)。二義性文法概念及消除二義性的方法（1、2）常見產(chǎn)生原因及消除的方法,第三章 2011,在一般的編譯器中，語(yǔ)法分析基于（ ）文法進(jìn)行，即識(shí)別的單詞串是該類文法的句子。分析器

17、（parser）的主要功能是進(jìn)行（ ）。,第三章 2011,以下對(duì)于文法二義性的描述正確的是（ ）。A LL(1)文法是無(wú)二義性文法；B 二義性文法會(huì)對(duì)所有的符號(hào)串產(chǎn)生多個(gè)語(yǔ)法樹；C 通過(guò)相應(yīng)算法可以判斷文法的二義性；D 在語(yǔ)法分析中，二義性文法是不被允許的，必須通過(guò)修改文法來(lái)消除。,第三章 2011,判斷：一個(gè)文法所描述的語(yǔ)言是唯一的；描述一個(gè)語(yǔ)言的文法是不唯一的。（ ）考慮下列文法G[D]：D?

18、T VT?int|floatV?id，V|id 請(qǐng)給出int id，id，id進(jìn)行的最右推導(dǎo)過(guò)程，并畫出其分析樹或語(yǔ)法樹,第三章 2010,判斷：一個(gè)文法所描述的語(yǔ)言是不唯一的；描述一個(gè)語(yǔ)言的文法是唯一的。（ ）分析器(parser)的主要功能是進(jìn)行__________，分析器的輸入是________，輸出是________。,第三章 2010,請(qǐng)寫出下面文法對(duì)于表達(dá)式（（））（）進(jìn)行的最左推導(dǎo)過(guò)程，并畫出其分

19、析樹或語(yǔ)法樹。A →（A）A | ε試描述由下列文法所產(chǎn)生的語(yǔ)言。S → aSS | a,第三章 2009,在文法中可能引起二義性的原因有：（ ）A．運(yùn)算的優(yōu)先級(jí)B. 運(yùn)算的結(jié)合性C．else的懸掛問(wèn)題D. 以上都有可能,第三章 2008,以下對(duì)于語(yǔ)法二義性的描述正確的是（）。A如果文法G的某個(gè)句子存在兩棵或者兩棵以上的語(yǔ)法樹（或分析樹），則稱該文法是存在二義性的；B如果文法G的某個(gè)文法存在兩個(gè)

20、或者兩個(gè)以上的句子符合該文法規(guī)則，則稱該文法是存在二義性的；C消除文法二義性只能對(duì)文法進(jìn)行修改，別無(wú)他法；D能夠通過(guò)算法判別文法是否存在二義性 。編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是_______。①分析單詞是怎樣構(gòu)成的②分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的③分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的④分析程序的結(jié)構(gòu)A、②和③B、④ C、②③④ D、①②③④,第三章　2008,已知文法G[S]： S::=a |

21、(T) T::=T，S | S給出句子（a，（a，a））的最左推導(dǎo)并畫出語(yǔ)法樹。,第四章 要點(diǎn),語(yǔ)法分析的分類：自頂向下，自底向上自頂向下分析方法：遞歸下降，LL(1)分析LL(1)基本方法，三種動(dòng)作（生成、匹配、接受）判斷文法是否是LL(1)文法First集和Follow集左遞歸和左因子的消除構(gòu)造分析表,第四章 2011,對(duì)下面文法中非終結(jié)符First集合描述正確的是（ ）。E?

22、(L)|a|εL?EL+|EA First(E)={ ( a + }B First(L)={ ( a + }C First(E)={ ( a + ε}D First(L)={ ( a + ε},第四章 2011,考慮下列文法G[S]：S?PSk|PP?a|*S*|ε S為開始符號(hào)，請(qǐng)計(jì)算S和P的First集合和Follow集合，判斷文法G[S]是否是LL(1)文法并說(shuō)明

23、理由。,第四章 2011,（20分）已知文法G[S]為S ? S A T | T A ? + | -T? (S) | k1．通過(guò)消除左遞歸和提取左因子（回溯），給出與G[S]等價(jià)的文法G’[S]；2．計(jì)算文法G’[S]非終結(jié)符的First集合和Follow集合；3．判斷文法G’[S]是否為L(zhǎng)L(1)文法；4．如果文法G’[S]是LL(1)文法，構(gòu)造G’[A]的分析表；5．給出輸入串k-(k+k)的分析過(guò)

24、程。,第四章 2010,對(duì)于文法G[S]： S → Q * S | Q | S Q → a | (S) | ε S為開始符號(hào)，請(qǐng)計(jì)算S和Q的First集合和Follow集合。,第四章 2010,已知文法G[A]為 A→ a | B→ b | εP→ P*A | Ak通過(guò)消除左遞歸和提取左因子（回溯），給出與G[A]等價(jià)的文法G’[A]；計(jì)算文法G’[A]非終結(jié)符的First集合和Follo

25、w集合；判斷文法G’[A]是否為L(zhǎng)L(1)文法；如果文法G’[A]是LL(1)文法，構(gòu)造G’[A]的分析表；給出輸入串的分析過(guò)程。,第四章 2009,設(shè)有文法G[S]：S→ X S | εX→ a S b | { S } | c計(jì)算文法G[S]非終結(jié)符的First集合和Follow集合；若采用自頂向下分析方法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中能否避免二義性？為什么？分析符號(hào)串a(chǎn)ababb是否為此文法的句子。,第四章

26、 2009,已知文法G[A]為A→ (L)A | (x)L→ L,s | k 通過(guò)消除左遞歸和提取左因子（回溯），給出與G[A]等價(jià)的文法G’[A]；計(jì)算文法G’[A]非終結(jié)符的First集合和Follow集合；判斷文法G’[A]是否為L(zhǎng)L(1)文法；如果文法G’[A]是LL(1)文法，構(gòu)造G’[A]的分析表；給出輸入串(k,s,s)(x)的分析過(guò)程。,第四章 2008,高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中

27、，遞歸下降分析法屬于______分析方法。A、自左至右 B．自頂向下 C、自底向上 D．自右向左LL(1)分析方法是這樣得名的：第一個(gè)“L”指的是___，第二個(gè)“L”指的是___，括號(hào)中的數(shù)字1指的是___。,第四章 2008,（10分）設(shè)有文法G[Z]：Z::=(A)A::=a│bBB::=A

28、ab(1) 若采用自頂向下分析方法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中能否避免二義性？為什么？(2) 分析符號(hào)串（bbaabab）是否為此文法的句子。（20分）已知文法G[A]為 A::=aABe | a B::=Bb | d(1) 通過(guò)消除左遞歸和提取左因子（回溯），給出與G[A]等價(jià)的文法G’[A]；(2) 計(jì)算

29、文法G’[A]非終結(jié)符的FIRST集合和FOLLOW集合；(3) 判斷文法G’[A]是否為L(zhǎng)L(1)文法；(4) 如果文法G’[A]是LL(1)文法，構(gòu)造G’[A]的分析表；(5) 給出輸入串a(chǎn)ade的分析過(guò)程。,第五章 要點(diǎn),什么是自底向上的分析方法基本操作：移入、歸約方法及能力：LR(0)<SLR(1)<SLR(k) LR(0)<SLR(1)<LR(

30、1)<LR(K)LR(0)項(xiàng)構(gòu)造DFA移入歸約沖突、歸約歸約沖突分析過(guò)程,第五章 2006,LR(0)分析中的分析動(dòng)作包括__________和__________。,第五章 2006,對(duì)于文法：E -> (L) | qL -> E L | Ea．為這個(gè)文法構(gòu)造LR(0)項(xiàng)目的DFAb．構(gòu)造SLR(1)分析表c．對(duì)輸入串(q q)進(jìn)行分析（15分）,第六章 要點(diǎn),屬性文法概念：聯(lián)編聯(lián)編時(shí)間靜態(tài)語(yǔ)

31、義和動(dòng)態(tài)語(yǔ)義常見的靜態(tài)語(yǔ)義符號(hào)表的作用、內(nèi)容符號(hào)表存儲(chǔ)的屬性,第六章 2008-2011,下面不屬于語(yǔ)義屬性的是（）A. 變量的數(shù)據(jù)類型 B. 表達(dá)式的值 C. 變量對(duì)應(yīng)的內(nèi)存地址 D. 源程序文件名判斷：為了提高查找及存取速度，符號(hào)表都采用有序表的形式。（ ）,第七章 要點(diǎn),概念運(yùn)行時(shí)環(huán)境過(guò)程活動(dòng)記錄調(diào)用序列和返回序列幾種運(yùn)行時(shí)環(huán)境及其特點(diǎn)，舉例。完全靜態(tài)的運(yùn)行時(shí)環(huán)境基于棧的運(yùn)行時(shí)環(huán)境,第七章20

32、08-2011,在編譯方法中，動(dòng)態(tài)存儲(chǔ)分配的含義是__。A、在運(yùn)行階段對(duì)源程序中的量進(jìn)行分配B、在編譯階段對(duì)源程序中的量進(jìn)行分配C、在編譯階段對(duì)源程序中的量進(jìn)行分配，在運(yùn)行時(shí)這些量的地址可以根據(jù)需要改變D、以上都不正確對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用____策略。下列對(duì)完全靜態(tài)存儲(chǔ)分配的含義描述錯(cuò)誤的是( )。A．每個(gè)過(guò)程只有一個(gè)活動(dòng)記錄；B．每個(gè)變量都有一個(gè)固定的存儲(chǔ)地址；C．沒有指針和動(dòng)態(tài)

33、分配；D．允許遞歸調(diào)用。,第七章2008-2011,過(guò)程信息表（過(guò)程活動(dòng)記錄）中至少應(yīng)該包括有____________。 ①過(guò)程名 ②過(guò)程的靜態(tài)層次 ③過(guò)程的入口地址 ④過(guò)程首部在源程序中的行號(hào) ⑤有關(guān)過(guò)程參數(shù)的信息A. ①②③ B. ①③④C. ①③⑤ D. ①②③④⑤,第七章2008-2011,關(guān)于基于棧的運(yùn)行時(shí)環(huán)境(runtime environment)，以下描述正確的是（）A. 不支持遞歸函

34、數(shù)調(diào)用；B. 支持遞歸函數(shù)調(diào)用；C. 局部變量可用靜態(tài)地址訪問(wèn)；D.一個(gè)函數(shù)對(duì)應(yīng)唯一一個(gè)過(guò)程活動(dòng)記錄。判斷：基于棧的運(yùn)行時(shí)環(huán)境中，允許程序的遞歸調(diào)用，一個(gè)程序可能同時(shí)存在多個(gè)活動(dòng)記錄。（ ）,第8-10章 要點(diǎn),中間代碼的種類后綴表示及其特點(diǎn)三元碼和四元碼代碼生成的概念（要考慮機(jī)器的物理特性）代碼優(yōu)化的分類源代碼優(yōu)化的具體實(shí)例,第8-10章 2008-2011,后綴表示的特點(diǎn)是：（）A．操作數(shù)的順序與原來(lái)相同；

35、B．操作符的順序就是計(jì)算發(fā)生的順序；C．后綴表示中無(wú)需括號(hào)；D．以上都是。,第8-10章 2008-2011,請(qǐng)寫出A:=3+(5-A/B)的后綴表示和三元組表示。請(qǐng)寫出a/b-c*(d+e)的后綴表示和四元組表示。請(qǐng)舉出中間代碼(Intermediate code)的兩種主要形式：________、_________。請(qǐng)寫出k:=i+k-3*4的后綴表示和四元組表示。請(qǐng)寫出i:=2+(4+3*5)的后綴表示和三元組表示