貴州財(cái)經(jīng)大學(xué)編譯原理復(fù)習(xí)資料

1、編譯原理學(xué)習(xí)指導(dǎo)與習(xí)題解析第一章：1-1選擇、填空題(1)構(gòu)造一個(gè)編譯程序的三要素是 ， ， 。 答案：源語言、目標(biāo)語言和編譯方法、技術(shù)及工具(2)被編譯的語言為A語言，編譯的最終結(jié)果為B語言代碼，編寫編譯程序的語言為C語言。那么， 語言是源語言， 語言是宿主語言， 語言是目標(biāo)語言。 答案：A、C、B(3)下面對(duì)編譯原理的有關(guān)概念描述正確的是 。 A目標(biāo)語言只能是機(jī)器語言 B編譯程序處理的對(duì)象是源語言CLex是語法分析自動(dòng)生成器 D解釋程序?qū)儆诰幾g程序答案：c(4) 是編譯程序的組成部分。 A詞法分析程序 B代碼生成程序c設(shè)備管理程序 D語法分析程序答案：C (5)下面對(duì)編譯程序分為“遍”描述

2、正確的是 A分“遍”可以使編譯程序結(jié)構(gòu)清晰 B可以提高程序的執(zhí)行效率C可以提高機(jī)器的執(zhí)行效率 D可以增加對(duì)內(nèi)存容量的要求答案：A(6)編譯程序各階段的工作都涉及到 ， 。 A表格管理 B語法分析 C出錯(cuò)處理 D代碼優(yōu)化答案：A、C (7)編譯程序的生成方式可以是 ， ， 。 A自編譯 B高級(jí)程序設(shè)計(jì)語言編寫 C完全自動(dòng)生成 D匯編語言縮寫答案：ABD (8)設(shè)有表達(dá)式a*bc，將其中a*b識(shí)別為表達(dá)式的編譯階段是 。 A詞法分析 B語法分析 C語義分析 D代碼生成答案：B(9)設(shè)一個(gè)編譯器接收的源語言A，目標(biāo)語言為B，宿主語言為C，則該編譯器的符號(hào)表示是 。答案：CCAB(10)下面對(duì)編譯程序

3、分“遍”應(yīng)考慮的因素描述不正確的是 。 A源語言的特征和約束 B代碼優(yōu)化的因素 C編譯程序的功能 D目標(biāo)代碼的選擇答案：C I-2判斷題 (I)解釋執(zhí)行與編譯執(zhí)行的根本區(qū)別在于解釋程序?qū)υ闯绦驔]有真正進(jìn)行翻譯。 ( )答案：錯(cuò) (2)宿主語言是目標(biāo)機(jī)的目標(biāo)語言。 ( )答案：錯(cuò) (3)具有優(yōu)化功能的編譯器可以組織為一遍掃描的編譯器。 ( )答案：錯(cuò) (4)編譯程序是將用某一種程序設(shè)計(jì)語言編寫的源程序翻譯成等價(jià)的另一種語言程序(目標(biāo)程序。 ( )答案：錯(cuò) (5)編譯程序是應(yīng)用軟件。 ( )答案：錯(cuò) (6)編譯程序的基本組成中，詞法分析、語法分析和語義分析應(yīng)該是有序的。( )答案：對(duì) (7)“遍”

4、是指對(duì)源程序的從頭到尾掃描。 ( )答案：錯(cuò) (8)用高級(jí)語言書寫的源程序都必須通過翻譯，產(chǎn)生目標(biāo)代碼后才能運(yùn)行。 ( )答案：對(duì) (9)含有優(yōu)化功能的編譯程序執(zhí)行效率高。 ( ) 答案：錯(cuò) (10)解釋程序和編譯程序的不同在于，解釋程序根據(jù)語法翻譯成目標(biāo)代碼并立即執(zhí)行之，而編譯程序需產(chǎn)生中間代碼及優(yōu)化。 ( )答案：錯(cuò) 1-3簡(jiǎn)答題 (I)什么是編譯程序? 答：把用某一種程序設(shè)計(jì)語言編寫的源程序翻譯成等價(jià)的另一種語言程序(目標(biāo)程序)的程序，稱之為編譯程序。(2)源程序的編譯執(zhí)行和解釋執(zhí)行的主要區(qū)別是什么? 答：一般編譯程序從對(duì)源程序執(zhí)行途徑的角度不同，可分為解釋執(zhí)行和編譯執(zhí)行。所謂解釋執(zhí)行是

5、借助于解釋程序完成，即按源程序語句運(yùn)行時(shí)的動(dòng)態(tài)結(jié)構(gòu)，直接逐句地邊分析邊翻譯并執(zhí)行。像自然語言翻譯中的口譯，隨時(shí)進(jìn)行翻譯。所謂編譯執(zhí)行，是將源程序先翻譯成一個(gè)等價(jià)的目標(biāo)程序，然后再運(yùn)行此目標(biāo)程序，故編譯執(zhí)行分為編譯階段和運(yùn)行階段。兩種執(zhí)行方式的主要區(qū)別是：編譯執(zhí)行是由編譯程序生成一個(gè)與源程序等價(jià)的目標(biāo)程序，它可以完全取代源程序，目標(biāo)程序可運(yùn)行任意多次，不必依賴編譯程序。正像自然語言翻譯中的筆譯，一次翻譯可多次閱讀。而解釋執(zhí)行不生成目標(biāo)程序，對(duì)源程序的每次執(zhí)行都伴隨著重新翻譯的工作，而且不能擺脫翻譯程序。(3)典型的編譯程序在邏輯功能上由哪幾部分組成?各部分的功能是什么? 答：典型的編譯程序在邏輯

6、功能上由詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化及目標(biāo)代碼生成五部分組成。各部分的簡(jiǎn)要功能是： 詞法分析的任務(wù)是對(duì)輸入的符號(hào)串形式的源程序進(jìn)行最初的加工處理。它依次掃描讀入的源程序中的每個(gè)字符，根據(jù)源語言的詞法規(guī)則識(shí)別出源程序中有獨(dú)立意義的單詞，用某種特定的數(shù)據(jù)結(jié)構(gòu)對(duì)它的屬性予以表示和標(biāo)注。 語法分析的任務(wù)是：在詞法分析基礎(chǔ)上，依據(jù)源語言的語法規(guī)則，對(duì)詞法分析的結(jié)果進(jìn)行語法檢查，并識(shí)別出單詞符號(hào)串所對(duì)應(yīng)的語法范疇。語義分析與中間代碼生成的任務(wù)是：依據(jù)源語言的語義規(guī)則對(duì)語法分析所識(shí)別的語法范疇進(jìn)行語義檢查并分析其含義，翻譯成與其等價(jià)的中間代碼。 代碼優(yōu)化是為了改進(jìn)目標(biāo)代碼的質(zhì)量而在編

7、譯過程中進(jìn)行的工作。代碼優(yōu)化可以在中間代碼或目標(biāo)代碼級(jí)上進(jìn)行，其實(shí)質(zhì)是在不改變?cè)闯绦蛘Z義的基礎(chǔ)上對(duì)其進(jìn)行加工變換，以期獲得更高效的目標(biāo)代碼。而“高效”一般是指，對(duì)所產(chǎn)生的目標(biāo)程序縮短其運(yùn)行時(shí)間和節(jié)省存儲(chǔ)空間。目標(biāo)代碼生成的功能是：根據(jù)中間代碼及編譯過程中產(chǎn)生的各種表格的有關(guān)信息，最終生成所期望的目標(biāo)代碼程序。(4)編譯程序?qū)崿F(xiàn)的途徑有哪些? 答：編譯程序的實(shí)現(xiàn)途徑即實(shí)現(xiàn)方式一般可以用高、中級(jí)程序設(shè)計(jì)語言編程實(shí)現(xiàn)，可以通過移植的方式實(shí)現(xiàn)，可以通過自編譯的方式，還可以通過部分自動(dòng)生成的方式實(shí)現(xiàn)。 (5)為不同目標(biāo)機(jī)編寫相同源語言的編譯器時(shí)，其設(shè)計(jì)變化最大的是后端，為什么? 答：在編譯程序構(gòu)成的經(jīng)典

8、劃分中，詞法分析、語法分析及語義分析中間代碼生成稱為編譯程序的前端，代碼優(yōu)化及代碼生成稱為后端。涉及前端的功能僅與源語言的詞法、語法及語義相關(guān)適于自動(dòng)生成。對(duì)后端實(shí)現(xiàn)的代碼優(yōu)化和代碼生成，鑒于不同的目標(biāo)機(jī)具有不同的體系結(jié)構(gòu)和指令系統(tǒng)，代碼優(yōu)化和代碼生成需要基于特定的目標(biāo)機(jī)來設(shè)計(jì)和實(shí)現(xiàn)。(6)簡(jiǎn)述編譯程序中“出錯(cuò)處理”程序的作用。 答：“出錯(cuò)處理”作為編譯程序的一個(gè)不可或缺的公共程序，其主要作用是對(duì)在編譯過程中掃描、翻譯源程序時(shí)根據(jù)文法規(guī)則和語義規(guī)則診斷源程序中存在的錯(cuò)誤，對(duì)錯(cuò)誤進(jìn)行定性、定位和必要的容錯(cuò)處理。這樣可以協(xié)助程序員及時(shí)準(zhǔn)確地發(fā)現(xiàn)源程序中的錯(cuò)誤，以提高調(diào)試程序的效率，方便用戶修改程序

9、，并能把錯(cuò)誤限制在盡可能小的范圍里。(7)為不同目標(biāo)機(jī)編寫相同源語言的編譯器時(shí)，其設(shè)計(jì)變化最大的是后端，為什么？ 答：在編譯程序構(gòu)成的經(jīng)典劃分中，詞法分析、語法分析及語義分析中間代碼生成稱為編譯程序的前端，代碼優(yōu)化及代碼生成稱為后端。涉及前端的功能僅與源語言的詞法、語法及語義相關(guān)適于自動(dòng)生成。對(duì)后端實(shí)現(xiàn)的代碼優(yōu)化和代碼生成，鑒于不同的目標(biāo)機(jī)具有不同的體系結(jié)構(gòu)和指令系統(tǒng)，代碼優(yōu)化和代碼生成需要基于特定的目標(biāo)機(jī)來設(shè)計(jì)和實(shí)現(xiàn)。(8)簡(jiǎn)述編譯程序中“出錯(cuò)處理”程序的作用。答：“出錯(cuò)處理”作為編譯程序的一個(gè)不可或缺的公共程序，其主要作用是對(duì)在編譯過程中掃描、翻譯源程序時(shí)根據(jù)文法規(guī)則和語義規(guī)則診斷源程序中

10、存在的錯(cuò)誤，對(duì)錯(cuò)誤定性、定位和必要的容錯(cuò)處理。這樣可以協(xié)助程序員及時(shí)準(zhǔn)確地發(fā)現(xiàn)源程序中的錯(cuò)誤，以提高調(diào)試程序的效率，方便用戶修改程序，并能把錯(cuò)誤限制在盡可能小的范圍里。第二章：22 習(xí)題2-1)選擇、填空題設(shè)有字母表A=0，A= 答案：，0，00，000 用于描述另一種語言的語言稱為 答案：元語言(3)一個(gè)文法所描述的語言是一個(gè)無限集合,則該文法一定是 文法。答案：遞歸(4)下面不能用于對(duì)文法進(jìn)行描述的是 。 A源語言 B.EBNF C.BNF D.語法圖答案：A(5)設(shè)有文法G的符號(hào)集V，非終結(jié)符集VN ，終結(jié)符集VT，下列敘述中正確的是 。 AV=VT B.V=VN C.V=VTVN D.

11、 V=VTVN答案：D(6設(shè)文法G(S)為：S 0A A 1B B 0|0S則L(G(S)為 。 A.L1=(01)n0|n1 B. L2=(010)n|n1 C. L3=0(10)n|n1 D. L4=(010)n0|n0 答案：B(7)設(shè)有文法G(S)為：S (B)a B Bb|b| 下列敘述錯(cuò)誤的是 。 A.G是2型文法 B. LG=bna|n0 C. LG=(b )na|n0 D.有文法G為S （）a|(B)a B bB|b，則G=G答案：C(8)給定文法G(S)： S 0S|1A|0 A 1|1S|0B B 1A|0B下列符號(hào)串是L(G)中元素的是 。A10100010011011

12、B. 0101001110010010C1101010011110111 D. 1010011101101010答案：A(9)設(shè)有文法G(S)：S S1|S0|Sa|Sc|a|b|c ，下列符號(hào)串中不是該文法的句子的是 。A.ab0 B.a0c01 C.aaa D.bc10答案：A(10)設(shè)有文法G(S)： S Bs|Aa| A bA|Ac C bCaS|a下列符號(hào)串是L(G)中元素的是 。A.ba121b100a2 B.b1000aa C.a800b900a D.b10000 答案：D(11)設(shè)有文法G(S)： S aA|bC|a A aS|Bb B aC|bA|b C aB|bS下述不為L(zhǎng)

13、(G)的句子的是 。A. a100b100ab100 B.a1000b500aba C.a100b40aab2a D.a100b40ab10aa 答案：B(12)文法G(S)為： S aA A bB B a|aS則L(G)為 。A.L1=abna|n1 B. L2=aban|n1 C. L3=aban|n1 D. L4=aban|n0 答案：C(13)設(shè)有文法G，滿足LG=aibjcjdi|i0且j1的文法G為 。A. S aSd|T T bcT|bc B.S aSd|T T bTc|bc C. S AB|B A aAd|ad B bBc|bc D. S Abc|A A aAd|ad 答案：B

14、(14)語言LG=ambn|nm1的文法G是 。 A. S Abb A aB|a B bB|b B.S Abb A Ba|a B aBb|b C. S Ab A aAb|a D. S aAb A Ab|aAb| 答案：D (15)給出語言LG=aibjcj|i0,j1，其相應(yīng)的文法G為 和 。A. S aS|T T bcT|bc B. S aS|T T bTc|bc C. S AB|B A aA|a B bBc|bc D. S Abc|A A aA|a 答案：B、C (16)給出語言LG=aibjcj|i0,j1L(G)= ，其相應(yīng)的文法G為 。A. S aSc|B B bB|b B.S aS

15、|T T bTc|bc C. S Abc|A A aA|a D. S AB|A A aA|a B bBc|bc 答案：D (17)設(shè)有語言L(G(S)=ab ,下面描述該語言正確的文法是 。 A. S AB A Aa| B Bb|b B.S AB|AS A Aa|a B b C. S AB|AS A aA|a B Bb| D. S SA|A A aAb|a 答案：B(18)設(shè)有語言L(G)=由于相同個(gè)數(shù)(0或n)的a和b組成的句子，滿足對(duì)L(G)描述的正確的文法是 和 。 A. S abS| B. S aSbS|bSaS| C.S aSb|ab| D. S SS|aSb|bSa|答案：B、D(

16、19)設(shè)定義在字母表a,b,c,x,y,z上的正規(guī)式r=(a|b|c)(x|y|z),則L(r)中元素有 個(gè)。 A. 9 B. 6 C. 18 D. 27答案：A(20)正規(guī)集L=a|n0相應(yīng)的正規(guī)式是 。答案：a*(21)設(shè)正規(guī)式r=(a|b)(x|y),則下面錯(cuò)誤的正規(guī)集元素是 。 A. abx B. bxxx C. a D.bxyyxxy答案：A(22)下述正規(guī)式中與(a|b)(c|d)等價(jià)的是 。 A.a(c|d)|b(c|d) B.a(c|d)|b(c|d) C.a(c|d)|b(c|d) D.(a|b)c|(a|b)d 答案：C(23)有文法G(S): S Ax|By A y|Ay

17、 B x|y 下面與文法G(S)表示相同語言的正規(guī)式是 。 A. yx|xy|y B. yx|x|xy C.yyX|xy|y D. yyx|xy|xy 答案：D(24)有文法G(S)： S dA A a|aB B aB|a|b|Bc C bC|b下面與文法G(S)表示相同語言的正規(guī)式是 。 A. daabb B. daab C. daa D. daab答案：B(25)設(shè)有文法G(S)： S AB|AS A aA|a B b文法G(S)與下面正規(guī)式等價(jià)的是 。 A. aabb B. aab C. (ab) D. a(ab)b答案：B(26)設(shè)文法G(S)：S aS|Sb|a|b則文法G(S)所識(shí)

18、別語言的正規(guī)式為 。答案：a*(a|b)b* (27) 設(shè)文法G(A)： S Sab|bR R S|a G(S)的語言L(G(S)= 。答案：b*baab* (28)設(shè)文法G(A)： A B B X|BA X Xa|Xb|a|b則文法G(A)所識(shí)別語言的正規(guī)式為 。答案：(a|b)(a|b)*(a|b)(a|b)*)* (29)設(shè)文法G(V)：V aaV|bc該文法對(duì)應(yīng)的語言L(G)= 。答案：a2nbc|n0 (30)已知語言：LGS=a2m+1bm+1m0a2mbm+2|m0 則文法G(S)是 。答案：S aaSb|ab|bb (31)設(shè)有語言：LGS=anbnci|n1，i0，則文法G(

19、S)是 。答案：S Sc|A A aAb|ab (32)已知2型文法G(S)相對(duì)應(yīng)的2型語言為：LGS=ambnanbm|m0，n1，則它的文法G(S)可描述為 。答案：S aSb|A A bAa|ba (33) 不是DFA的構(gòu)成成分。 A有窮字母表 B初始狀態(tài)集合 C終止?fàn)顟B(tài)集合 D有限狀態(tài)集合 答案：B (34)有限自動(dòng)機(jī)M和N等價(jià)是指 。 AM和N的字母表相同 BM和N狀態(tài)數(shù)和有向邊數(shù)相等 CM和N狀態(tài)數(shù)或有向邊數(shù)相等 DM和N識(shí)別的字符串集合相同答案：D (35)如果一個(gè)正規(guī)式所代表的集合是無窮的，則該正規(guī)式必含有的運(yùn)算是 。 A連接運(yùn)算“.” B或運(yùn)算“|” C閉包運(yùn)算“*” D括號(hào)

20、“（）”答案：C2-2 判斷題（1）設(shè)有文法符號(hào)集V，則VTVN=V。 （ ）答案：錯(cuò)（2）一部文法G的文法符號(hào)不屬于VT。 （）答案：對(duì)（3）有文法G1=G2，則L(G1)=L(G2)。 （）答案：對(duì)（4）一個(gè)語言的文法是不唯一的。 （）答案：對(duì)（5）元語言是描述另一種語言的語言。 （）答案：對(duì)（6）BNF是一種廣泛被采用的描述文法的工具。 （）答案：對(duì)（7）文法G所描述的語言就是G的終結(jié)符號(hào)集VT的閉包VT。 （）答案：錯(cuò)（8）對(duì)于文法G（S）=（VN，VT，P,S），V=VNVT，r是文法（）的句型當(dāng)且僅當(dāng)S=r，且rV，是文法（）的句子當(dāng)且僅當(dāng)S=，且rVT（）答案：對(duì)（）文法的一個(gè)句

21、子對(duì)應(yīng)于多個(gè)推導(dǎo)，則是二義的。（）答案：錯(cuò)（）對(duì)給定的文法（），若至少有一個(gè)句型存在兩個(gè)或兩個(gè)以上不同的最左（或最右）推導(dǎo)，這是判斷是二義文法的充分非必要條件。（）答案：錯(cuò)（）對(duì)給定的文法（），若至少有一個(gè)句型存在兩棵或兩棵以上的不同的樹，是判斷是二義文法的充分必要條件。（）答案：對(duì)（）一棵分叉樹反映了其葉節(jié)點(diǎn)從左向右連接形成的句型的任意推導(dǎo)情況。（）答案：錯(cuò)（）和的區(qū)別之一是映射函數(shù)是否唯一。（）答案：對(duì)（）一個(gè)正規(guī)式只能等價(jià)于一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)。（）答案：錯(cuò)（）任意有限自動(dòng)機(jī)都鞥轉(zhuǎn)化為一等價(jià)的特殊自動(dòng)機(jī)；其狀態(tài)圖中初態(tài)無射入弧，終態(tài)無射出弧。（）答案：對(duì)（）對(duì)任何正規(guī)集，都有正規(guī)式（

22、）。（）答案：對(duì)（）設(shè)有和都是非的正規(guī)式，則有（）（）。（）答案：錯(cuò)（）使用正規(guī)式運(yùn)算能夠描述定義在字母表上的所有符號(hào)串集合。（）答案：錯(cuò)（）喬姆斯基把文法分為四種類型，即型、型、型、型。型文法也稱為正規(guī)文法，型文法是短語文法。（）答案：錯(cuò)（）正規(guī)式產(chǎn)生的語言都可以用上下文法來描述。（）答案：對(duì)（）對(duì)任何正規(guī)式，都存在一個(gè)，滿足（）（）。（）答案：對(duì)（）正規(guī)文法、正規(guī)式、和在接受語言的能力上是相互等價(jià)的。（）答案：對(duì)（）自動(dòng)機(jī)和狀態(tài)數(shù)不同，則二者必不等價(jià)。（）答案：錯(cuò)（）一個(gè)有限自動(dòng)機(jī)只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（）答案：錯(cuò)（）一個(gè)有限自動(dòng)機(jī)識(shí)別的語言是一個(gè)無限

23、集合，則該有限自動(dòng)機(jī)的狀態(tài)圖一定含有回路。（）答案：對(duì)（）如果一個(gè)有限自動(dòng)機(jī)接受空串，則他的狀態(tài)轉(zhuǎn)換圖一定含有弧。（）答案：錯(cuò)（）一個(gè)確定的有限自動(dòng)機(jī)，可以通過多條路識(shí)別一個(gè)符號(hào)串。（）答案：錯(cuò)（）的確定化算法具有消除弧的功能。（）答案：對(duì)（）正則文法一定不是二義文法。（ ）答案：錯(cuò)（）對(duì)每一個(gè)左線性文法G1，一定存在一個(gè)有線性文法G2，使得（G1）（G2）。（ ）答案：對(duì)簡(jiǎn)答題（）喬姆斯基分類法按照什么原則對(duì)文法進(jìn)行分類？分成了幾類？各有什么樣的特點(diǎn)？答：按產(chǎn)生式的不同對(duì)文法進(jìn)行分類。分為類：型：產(chǎn)生式無限制。型：產(chǎn)生式限制為形如A 型：產(chǎn)生式限制為形如A 。型：產(chǎn)生式限制為形如A B或A

24、或者(A B或A )。（）簡(jiǎn)要概述分析樹的概念及其作用。答：分析樹的根節(jié)點(diǎn)是文法的開始符號(hào)，結(jié)點(diǎn)間的父子關(guān)系為產(chǎn)生式規(guī)則，即若父節(jié)點(diǎn)標(biāo)識(shí)為，子結(jié)點(diǎn)從左到右依次標(biāo)識(shí)為a1，a2an，則在文法中存在一產(chǎn)生式a1a2an，一棵分析樹的從左到右的葉結(jié)點(diǎn)，就形成了由該分析樹表示的推導(dǎo)出的句型。分析樹的生長(zhǎng)過程是一個(gè)句子的推導(dǎo)過程，分析樹額可以直觀形象的表示經(jīng)推導(dǎo)而產(chǎn)生的句子結(jié)構(gòu)，有助于理解句子的語法結(jié)構(gòu)層次。（）如何判斷一部文法是二義文法？答：對(duì)一部文法，如果至少存在一個(gè)句子，對(duì)應(yīng)兩棵（或兩棵以上）不同的分析樹或有兩個(gè)不同的最左推導(dǎo)，則這個(gè)文法是二義性的。（）簡(jiǎn)述正則表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性的證明思路

25、，并簡(jiǎn)要說明每步要完成的基本工作或要解決的關(guān)鍵問題是什么？答：正則表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性的證明思路為正規(guī)式的合成與分解，或狀態(tài)轉(zhuǎn)換函數(shù)的合成與分解。正則表達(dá)式有限自動(dòng)機(jī)：每步的基本工作是完成正規(guī)式的分解，即分解狀態(tài)轉(zhuǎn)換函數(shù)，增加狀態(tài)圖中的狀態(tài)或弧。有限自動(dòng)機(jī)正則表達(dá)式：每步的基本工作是完成正規(guī)式的合成，即合成狀態(tài)轉(zhuǎn)換函數(shù)，減少狀態(tài)圖中的狀態(tài)或弧。（）簡(jiǎn)述和的區(qū)別。答：和的區(qū)別是：的狀態(tài)轉(zhuǎn)換函數(shù)值是一個(gè)狀態(tài)子集，反映在狀態(tài)轉(zhuǎn)換圖上即從一狀態(tài)結(jié)點(diǎn)出發(fā)可以有不止一條同一標(biāo)記的弧?？梢詭мD(zhuǎn)換（不處理任何符號(hào)，就進(jìn)行狀態(tài)轉(zhuǎn)換）。第三章：3.2 習(xí)題3-1選擇、填空題（1）詞法分析器的輸入是 。A、單

26、詞符號(hào)串 B、源程序 C、語法單位 D、目標(biāo)程序答案：B（2）設(shè)有C語句的程序如下：while(i&+j) c=2.19; j+=k; i+;則經(jīng)過詞法分析后可以識(shí)別的單詞個(gè)數(shù)是 個(gè)。A、19 B、20 C、21 D、23答案：B（3）下列選項(xiàng)中，不屬于預(yù)處理程序要完成的功能的是 。A、濾掉源程序中的注釋 B、查找源程序中無用字符C、運(yùn)行宏替換 D、實(shí)現(xiàn)文件包含的嵌入和條件編譯的嵌入答案：B（4）編譯過程中掃描器的任務(wù)包括 。1、組織源程序的輸入2、按詞法規(guī)則分隔單詞，識(shí)別出其屬性，并轉(zhuǎn)換成token串輸出3、刪除注釋4、刪除空格或無用字符5、行計(jì)數(shù)，列計(jì)數(shù)6、發(fā)現(xiàn)并定位詞法錯(cuò)誤7、建立符號(hào)表

27、A、2 3 4 7 B、2 3 4 6 7 C、1 2 3 4 6 7 D、1 2 3 4 5 6 7 答案：D（5）將識(shí)別各類單詞的有限自動(dòng)機(jī)合并后得到的有限自動(dòng)機(jī) 。A、可能是NFA 也可能是DFA B、一定是DFAC、一定是NFA D、是最小的DFA 答案：A（6）屬性字是詞法分析器對(duì)源程序中各單詞處理后的 形勢(shì)，也是單詞在編譯程序處理過程中的一種內(nèi)部表示。A、輸入 B、內(nèi)部 C、輸出 D、外部答案：C（7）算術(shù)表達(dá)式123+45.6，詞法分析后，下面的合法單詞是 和 。 A、十進(jìn)制數(shù)123 B、符號(hào)串123C、數(shù)字串123 D、十進(jìn)制數(shù)45.6答案：AD（8）C語言中的表達(dá)式a+=1，

28、詞法分析后，能識(shí)別出的單詞個(gè)數(shù)是 。、 、 、 、答案：D（）在詞法分析階段不能識(shí)別的是 。、標(biāo)示符 、運(yùn)算符 、四元式 、常數(shù)答案：C（）詞法分析程序的輸入是，輸出是。答案：源程序字符串、屬性字符流（）單詞就是語言中具有獨(dú)立意義的最小 單位。答案：語法（）屬性字的二元組的表示式為。答案：（）構(gòu)造識(shí)別單詞的有限自動(dòng)機(jī)時(shí)一般先對(duì)單詞進(jìn)行分類，構(gòu)造識(shí)別各類單詞的有限自動(dòng)機(jī)，然后各類有限自動(dòng)機(jī)，構(gòu)成一個(gè)能識(shí)別語言所有單詞的有限自動(dòng)機(jī)。答案：合并（）程序設(shè)計(jì)語言的單詞符號(hào)一般分為：關(guān)鍵字、運(yùn)算符和界符。答案：標(biāo)識(shí)符、常量（）詞法分析基于型文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。答案：3判斷題（）是典型

29、的詞法分析程序。（）答案：錯(cuò)（）詞法分析的依據(jù)是源語言的文法規(guī)則。（）答案：錯(cuò)（）源程序中的單詞是具有獨(dú)立意義的短語。（）答案：錯(cuò)（）單詞的屬性字一般應(yīng)該包括單詞類別和單詞。（）答案：錯(cuò)（）編譯的預(yù)處理程序的處理對(duì)象是源程序。（）答案：對(duì)（）在語言中的一個(gè)語句；詞法分析后識(shí)別出、和；四個(gè)單詞。（）答案：錯(cuò)（）一個(gè)字母或數(shù)字在語言中不一定是單詞，因?yàn)樗麄儾灰欢ň哂歇?dú)立的意義。（）答案：對(duì)（）構(gòu)造識(shí)別單詞的有限自動(dòng)機(jī)時(shí)，先要對(duì)程序語言的單詞按類構(gòu)造出相應(yīng)的有限自動(dòng)機(jī)。（）答案：對(duì)簡(jiǎn)答題（）詞法分析的任務(wù)是什么？答：詞法分析的任務(wù)是對(duì)輸入的字符串形勢(shì)的源程序按順序進(jìn)行掃描，在掃描的同時(shí)，根據(jù)源語言的

30、詞法規(guī)則識(shí)別具有獨(dú)立意義的單詞，并產(chǎn)生與其等價(jià)的屬性字流作為輸出。（）詞法分析程序的基本功能有哪些？詞法分析的實(shí)質(zhì)是什么？答：詞法分析的基本功能是讀入字符串形勢(shì)的源程序并識(shí)別出具有獨(dú)立意義的最小語法單位-單詞，然后將單詞變換成帶有單詞性質(zhì)且定長(zhǎng)的屬性字。 詞法分析的實(shí)質(zhì)是依據(jù)詞法規(guī)則，從讀入的源程序中識(shí)別出具有獨(dú)立意義的最小語法單位。（）詞法分析中識(shí)別的單詞具有什么特征？識(shí)別的依據(jù)是什么？答：詞法分析中識(shí)別的單詞具有的特征是具有獨(dú)立意義并是最小語法單位，不滿足任何一個(gè)條件都不是單詞，識(shí)別的依據(jù)是詞法規(guī)則。（）簡(jiǎn)述構(gòu)造識(shí)別單詞的有限自動(dòng)機(jī)的方法與步驟。答：構(gòu)造識(shí)別單詞的有限自動(dòng)機(jī)的方法與步驟如下

31、：對(duì)程序語言的單詞按類構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。對(duì)各類狀態(tài)轉(zhuǎn)換圖進(jìn)行合并，構(gòu)成一個(gè)能識(shí)別語言所有單詞的狀態(tài)轉(zhuǎn)換圖，其合并方法為：將各類單詞的狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)合并為一個(gè)唯一的初態(tài)?；?jiǎn)并調(diào)整沖突的狀態(tài)編號(hào)。（）實(shí)際的詞法分析程序一般帶有預(yù)處理子程序，簡(jiǎn)述預(yù)處理子程序的主要功能。答：預(yù)處理子程序一般完成的主要功能是濾掉源程序中的注釋、刪除源程序中無用字符、進(jìn)行宏替換、實(shí)現(xiàn)文件包含的嵌入和條件編譯的嵌入登。（）何為超前搜索技術(shù)？答：在對(duì)源程序掃描過程中，比一般單詞的識(shí)別超前搜索了多個(gè)符號(hào)后才得以確認(rèn)為一單詞的搜索技術(shù)成為超前搜索技術(shù)。34有如下語言源程序段int m;m=33;printf(“ m

32、=%dn”,m);合法單詞有哪些？答：合法單詞共14個(gè)，他們是int , m , ; , m , = , 33 , ; , printf , ( , “m=%dn” , , , m ,) 和；。3-5 設(shè)計(jì)C語言全部運(yùn)算符的屬性字。答：設(shè)計(jì)屬性字的方法并不唯一，可以有多種方法。C語言全部運(yùn)算符的屬性字可簡(jiǎn)單設(shè)計(jì)如下：(0,+) (1,-) (2,*) (3,/) (4,+) (5,-) (6,+=) (7,-=) (8,&) (9,&) (10,) (12,=) (13,) (14,。則在自上而下語法分析中對(duì)A推導(dǎo)不帶回溯的條件是 。 AFIRSTFIRSTFIRST= BFIRSTFIRST

33、=與FIRSTFIRST=與FIRST FIRST= CFIRSTFIRSTFIRST= DFIRSTFIRST=或FIRSTFIRST=或FIRST FIRST=答案：B(6)下列文法中， 是LL(1)文法。（S是公理） A S aSb|ab BS ab|Sab C S As|b DS As|a答案：C(7)設(shè)有文法G(S)為：S AB|bCA |bB |aDC AD|bD aS|c則FOLLOW(A)= ，F(xiàn)IRST(S)= 。答案：FOLLOW(A)= a ，c，# ，F(xiàn)IRST(S)= a，b， (8)設(shè)有文法G(S為開始符號(hào))：S Ap|BqA a|cAB b|dBFIRST(Ap)

34、= 。Aa，c Bb，d Cp，q D其他答案答案：A4-判斷題(1)語法分析的任務(wù)是分析語句是如何構(gòu)成的。（ ）答案：錯(cuò)(2)語法分析必須在語義分析之前完成。（ ）答案：對(duì)(3)自上而下語法分析實(shí)施的是最左推導(dǎo)。（ ）答案：對(duì) (4)設(shè)有文法G：S Qq|qQ cQd|該文法是LL(1)文法。 （ ）答案：錯(cuò)(5)LL(1)分析法中的“”是指掃描源程序當(dāng)前指針P+所指的源程序串的字符。（）答案：錯(cuò)(6)自上而下分析及自下而上分析中的“下”指的是被分析的源程序串（）答案：對(duì)(7)自上而下分析及自下而上分析中的“上”指的是分析樹的根結(jié)點(diǎn)或文法的開始號(hào)。 （ ）答案：對(duì)(8)語法分析方法中的遞歸下

35、降分析法屬于自上而下分析方法。（）答案：對(duì)(9)文法若存在左遞歸，則在自上而下語法分析過程中會(huì)因?yàn)榧倨ヅ湓斐伤惴ǖ幕厮荨?（ ）答案：錯(cuò)(10)LL（1）分析器必須滿足文法不含左公因子和不含左遞歸。（）答案：對(duì)(11)LL（1）分析過程中使用的分析棧存放的是已經(jīng)掃描且分析過的源程序串。 （ ）答案：對(duì)(12)LL（1）分析過程中使用的分析棧只能存放文法的終結(jié)符。（）答案：錯(cuò)(13)LL（1）分析的主要依據(jù)是LL（1）分析表。 （ ）答案：對(duì)(14)LL（1）中的“1”通過求FIRST得到。 （ ）答案： 錯(cuò)(15)設(shè)文法中有產(chǎn)生式T ，若采用遞歸下降分析方法，則T對(duì)應(yīng)的函數(shù)是空函數(shù)。（）答案：

36、對(duì)簡(jiǎn)答題（1） 語法分析程序的功能及語法分析中要解決的基本問題是什么？答：語法分析的任務(wù)是，按照語法的語法規(guī)則，對(duì)單詞串形式的源程序進(jìn)行語法檢查，并識(shí)別出相應(yīng)的語法成分。按照詞法分析程序模型，語法分析程序處理的對(duì)象是此法分析器的輸出，即屬性字流形式的源程序，它的處理依據(jù)是語言的語法，其分析結(jié)果是識(shí)別出的無語法錯(cuò)誤的語法成分（可以用分析樹的形式來表示）。語法分析程序要解決的問題是：對(duì)給定的文法G和輸入串(VT*)，判定L(G)?即判定是否是文法G所能產(chǎn)生的句子，同時(shí)處理語法錯(cuò)誤。（2）什么是自上而下分析？什么是自下而上分析？答：自上而下分析是從文法的開始符號(hào)出發(fā)，通過反復(fù)使用文法的產(chǎn)生式，逐步推

37、導(dǎo)得到輸入串$，則可以確認(rèn)輸入串$是文法G的句子。自下而上分析的過程是：從給定的輸入串$開始，逐步進(jìn)行“歸納”，直至歸約到文法的開始符號(hào)（3）構(gòu)造一個(gè)不帶回溯的自上而下語法分析器對(duì)文法有何要求？為什么？答：文法不含左遞歸，不含左公因子。因?yàn)槲姆ê筮f歸會(huì)導(dǎo)致在自上而下分析中的最左推導(dǎo)無止境進(jìn)行，使得分析算法陷入死循環(huán)；而文法含左公因子會(huì)導(dǎo)致分析過程要窮盡所有可能的推導(dǎo)，分析過程有回溯，使得分析器開銷大，效率低。（4）什么是LL（k）分析？答：LL（k）分析是一種自上而下的分析方法。所謂LL（k）是指語法分析是按自左（第一個(gè)“L”）至右的順序掃描輸入字符串，并在分析過程中產(chǎn)生句子的最左推導(dǎo)（第二

38、個(gè)“L”）。k則表示在分析過程中，每一步推導(dǎo)，最多只要向前查看（向右掃描）k個(gè)輸入字符，既能確定當(dāng)前推導(dǎo)所應(yīng)選用的文法規(guī)則。（6）LL（1）中的“1”的含義是什么？答：LL（1）中的“1”表示在分析過程中，每一步推導(dǎo)，最多只要向前查看一個(gè)字符，既能確定當(dāng)前推導(dǎo)所應(yīng)選用的文法規(guī)則。設(shè)有文法產(chǎn)生式：A ，當(dāng)時(shí)，LL(1)中的：“1”通過求FIRST()得到；當(dāng)=時(shí)，LL(1)中的“1”通過求FOLLOW(A)得到。（7）遞歸下降分析方法的實(shí)現(xiàn)思想。答：遞歸下降分析器的 基本構(gòu)造方法是，對(duì)文法的每個(gè)非終結(jié)符號(hào)，都根據(jù)其產(chǎn)生的各個(gè)候選式的結(jié)構(gòu)，為其編寫一個(gè)對(duì)應(yīng)的子程序（或函數(shù)），該子程序完成相應(yīng)的非終

39、結(jié)符對(duì)應(yīng)的語法成分的識(shí)別和分析任務(wù)。因此，遞歸下井分析器的語法分析子程序的功能是，對(duì)某個(gè)非終結(jié)符，用規(guī)則的右部符號(hào)串去匹配輸入串。分析過程是文法規(guī)則自上而下一級(jí)一級(jí)地調(diào)用有關(guān)子程序來完成的。（8）自上而下分析和自下而上分析的異同是什么？答：自上而下分析和自下而上分析的掃描模式是一樣的，都是對(duì)源程序?qū)嵤淖笙蛴业膾呙琛２煌氖欠治瞿Ｊ剑鹤陨隙路治鍪峭茖?dǎo)過程，二自下而上分析是歸約的過程。44 設(shè)有文法G和該文法的某個(gè)句子$，如何判定$是文法G的合法語句？ 解答：從文法G的開始符號(hào)，運(yùn)用文法的產(chǎn)生式規(guī)則逐步推導(dǎo)出$,則可以判定$是合法語句?；驈木渥?開始不斷運(yùn)用文法的產(chǎn)生式規(guī)則進(jìn)行歸約，直至歸約到

40、文法的開始符號(hào)，則可以判定$是合法語句。45 設(shè)有文法G(T)：T Qc|cQ Rb|bR Ta|a 說明文法G(T)是否為遞歸文法，為什么？解答：根據(jù)文法G(T)，存在推導(dǎo)序列：T=Qc=Rbc=Tabc呈現(xiàn)出文法是左遞歸文法。46 將下面的左遞歸文法G(S)改為非左遞歸的S SaP|Sf|PP QbP|QQ cSd|e解答：改寫后的文法：S PSS aPS|fS|eP QbP|QQ cSd|e47 設(shè)有文法G(A)： A BaC|CbB B Ac|c C Bb|b 試消除G(A)的左遞歸。解答：令文法G(A)的非終結(jié)符為A，B，C。 對(duì)于A，不存在直接左遞歸，將A帶入B，代換后的B的規(guī)則變

41、為：B BaCc|CbBc|cB存在直接左遞歸，消除B的直接左遞歸有：B CbBcB|cB B aCcB|將B代入C，代換后的C的規(guī)則變?yōu)椋?C CbBcBb|cBb|b C存在直接左遞歸，消除C的直接左遞歸有; C cBbC|bC C bBcBbC| 消除G(A)的左遞歸后的文法為： A BaC|CbB B CbBcB|cB B aCcB| C cBbC|bC C bBcBbC| 48 設(shè)有文法G(A)： A Aab|a B Bb|d (1)證明文法G(A)是否為L(zhǎng)L(1)文法？說明為什么？ (2)試改寫文法為L(zhǎng)L(1)文法。解答：(1)文法G(A)不是LL(1)文法。因?yàn)镚(A)含有左遞歸

42、，含有左公因子。 (2)改寫后的文法： A aA A AB| B dB B bB| 驗(yàn)證：對(duì)A有FIRST(AB)=aFOLLOW(A)=#= 對(duì)B有FIRST(bB)=bFOLLOW(B)=#= 改寫后的文法是LL(1) 文法。第五章：5.2 習(xí)題5-1 選擇、填空題（1）自下而上語法分析的主要分析動(dòng)作是_。A、 移進(jìn)-歸約 B、推導(dǎo) C、歸約 D、匹配答案：A（2）在“移進(jìn)-歸約”分析過程的每一步驟（出去到達(dá)接受狀態(tài)），棧中的文法符號(hào)加上剩余輸入符號(hào)恰好構(gòu)成一個(gè)_。答案：規(guī)范句型（3）在算符優(yōu)先分析過程中，終結(jié)符a 和b存在優(yōu)先關(guān)系ab，則表示符號(hào)a位置在棧頂，符號(hào)b的位置是_。答案：當(dāng)前輸入指針指向的符號(hào)或輸入串的當(dāng)前符號(hào)（4）下例文法中，_是算符優(yōu)先文法。 A.G1: S Aa A bB B a B. G2: S Aa A Bb