編譯原理復(fù)習(xí)(有答案)

1、第一章 引論1. 編譯過(guò)程的階段由詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六個(gè)階段2. 編譯程序的概念3. 編譯程序的結(jié)構(gòu)例： B 不是編譯程序的組成局部。A. 詞法分析器； B. 設(shè)備管理程序C. 語(yǔ)法分析程序； D. 代碼生成程序4. 遍的概念對(duì)源程序(或其中間形式)從頭至尾掃描一次并進(jìn)行有關(guān)加工處理，生成新的中間形式或最終目標(biāo)程序，稱為一遍。5. 編譯程序與解釋程序的區(qū)別例：解釋程序和編譯程序是兩類程序語(yǔ)言處理程序，它們的主要區(qū)別在于 D 。A. 單用戶與多用戶的差異 B. 對(duì)用戶程序的過(guò)失能力C. 機(jī)器執(zhí)行效率 D. 是否生成目標(biāo)代碼第三章文法和語(yǔ)言文法的概念

2、字母表、符號(hào)串和集合的概念及運(yùn)算 例：(ab|b)*c 與下面的那些串匹配？ ACD A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 與后面的那些串匹配？ BC A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)* 與后面的那些串匹配? ADE A.ba B.bba C.ababa D.aa E.baa 文法的定義四元組表示文法G定義為四元組VN，VT，P，SVN ：非終結(jié)符集VT ：終結(jié)符集P：產(chǎn)生式規(guī)那么集合S：開始符號(hào)或識(shí)別符號(hào)例：給定文法，A:= bA | cc，下面哪些符號(hào)串可由其推

3、導(dǎo)出 。 cc b*cc b*cbcc bccbcc bbbcc 什么是推導(dǎo) 例：文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 試給出下述表達(dá)式的推導(dǎo)：i*i+i推導(dǎo)過(guò)程：E->E+T->T+T->T*F+T->F*F+T->i*F+T->i*i+T->i*i+F->i*i+il 句型、句子的概念例：假設(shè)G一個(gè)文法，S是文法的開始符號(hào)，如果S=>*x，那么稱x是 句型 。例：對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為 句子 。l 語(yǔ)言的形式定義例：設(shè)r=(a|b|c)(x|y|z)，那么L(r)中

4、元素為 9 個(gè)。例：文法G產(chǎn)生式為SAB，AaAb|e，BcBd|cd，那么 B L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb l 等價(jià)文法例：如果兩個(gè)文法描述了同一個(gè)語(yǔ)言，那么這兩個(gè)文法是 等價(jià)文法 。l 文法的類型0型：左邊至少有一個(gè)非終結(jié)符1型：右邊長(zhǎng)度>=左邊長(zhǎng)度2型：左邊有且僅有一個(gè)非終結(jié)符3型：形如：A->aB,A->a各類型文法都是逐級(jí)包含關(guān)系，例：文法SabC|c，bCd是幾型文法？0型例：文法SabC，bCad是幾型文法？1型例：文法GA：Ae，AaB，BAb，Ba是幾型文法？2型例：文法Sa|bC，Cd是幾型文法？3型l

5、 最左右推導(dǎo)標(biāo)準(zhǔn)推導(dǎo) ：最右推導(dǎo)被稱為標(biāo)準(zhǔn)推導(dǎo)標(biāo)準(zhǔn)句型 ：由標(biāo)準(zhǔn)推導(dǎo)所得的句型稱為標(biāo)準(zhǔn)句型標(biāo)準(zhǔn)歸約:左歸約為標(biāo)準(zhǔn)歸約l 二義性例：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，那么稱這個(gè)文法是 二義的 。例：文法G1：P->PaP|PbP|cP|Pe|f，G1是 A 。 A 二義文法；B 無(wú)二義的例：證明下述文法G<表達(dá)式>是二義的。 <表達(dá)式>a|(<表達(dá)式>)|<表達(dá)式><運(yùn)算符><表達(dá)式> <運(yùn)算符>+|-|*|/答：可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo):最右推導(dǎo)1 表達(dá)式表達(dá)式運(yùn)算符表達(dá)式表達(dá)

6、式運(yùn)算符a 表達(dá)式* a 表達(dá)式運(yùn)算符表達(dá)式* a 表達(dá)式運(yùn)算符a * a 表達(dá)式+ a * a a + a * a最右推導(dǎo)2 表達(dá)式表達(dá)式運(yùn)算符表達(dá)式表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符表達(dá)式表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符 a 表達(dá)式運(yùn)算符表達(dá)式 * a 表達(dá)式運(yùn)算符a * a 表達(dá)式+ a * a a + a * al 短語(yǔ)、句柄、直接短語(yǔ)例：令文法GE為: E->E+T|E-T T->T*F|T/F|F F->(E)|i 證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。例：文法GS SaB|bA Aa|aS|bAA BaBB|bS|b 句型aabbAb的句柄是 D

7、A.a B.ab C.b D.bA 第四章 詞法分析l 詞法輸出的token表示法 l 詞法記號(hào)、模式、詞法單元的概念 l 詞法輸出的token表示 ：二元式表示單詞種別，單詞自身的值例：掃描器的任務(wù)是從 源程序 中識(shí)別出一個(gè)個(gè) 單詞 。l 正規(guī)式的概念及其代數(shù)性質(zhì)詞法分析中的單詞符號(hào)的描述工具正規(guī)式代表的集合例：請(qǐng)描述下面正規(guī)式定義的串，字母表S = 0, 1。1(0|1)*0答：必須以1開頭0結(jié)尾的串例：為下邊所描述的串寫正規(guī)式，字母表是 0, 1。以01 結(jié)尾的所有串答：(0|1)*01l 正規(guī)文法和正規(guī)式相互轉(zhuǎn)換正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)那么：正規(guī)文法 正規(guī)式A®xB, B&#

8、174;y 轉(zhuǎn)換成： A=xy A®xA½y 轉(zhuǎn)換成： A=x*y A®x, A®y 轉(zhuǎn)換成： A=x½y 例：給出下述文法所對(duì)應(yīng)的正規(guī)式： S0A|1B A1S|1 B0S|0答： S->0A | 1B->01S | 01 | 10S | 10->(01|10)S | (01|10)-> (01|10) (01|10)* 即：r= (01|10) (01|10)*l NFA和DFA l NFA和DFA 的組成例：指出哪些串是自動(dòng)機(jī)可接受的 xy xyxxy yyyx xyyxyxyxxy l NFA和DFA的相互轉(zhuǎn)換例

9、：將下列圖確定化：答：用子集法將NFA確定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。.01SABACBBDECFFDF.ECEFFFDFA的狀態(tài)圖：l 正規(guī)式與NFA的相互轉(zhuǎn)換例：構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的DFA 答：先構(gòu)造NFA：用子集法將NFA確定化 .01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D，因?yàn)镈含有YNFA的終態(tài)，所以D為終態(tài)。.01X.AAABBCBCADDCBDFA的狀態(tài)圖：:第

10、五章 自頂向下語(yǔ)法分析方法語(yǔ)法分析常用的方法是_B_。 自頂向下 自底向上 自左向右 自右向左A. B. C. D. l 會(huì)求FIRST、FOLLOW集計(jì)算FIRST(X)： (a) 假設(shè)XVT, 那么FIRST(X)X (b) 假設(shè)XVN, 且有產(chǎn)生式Xa, aVT, 那么 aFIRST(X) (c) 假設(shè)XVN, Xe, 那么eFIRST(X) (d) 假設(shè)XVN, Y1, Y2, , YiVN, 且有產(chǎn)生式XY1Y2Yn; 當(dāng)Y1Y2Yi-1都e時(shí),(其中1in), 那么FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非e元素和FIRST(Yi)都包含在FIRST(X

11、)中 (e) 當(dāng)(d)中所有Yi e, (i=1, 2, n), 那么FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)e 計(jì)算FOLLOW(A)： (a) 設(shè)S為文法中開始符號(hào)，把#參加FOLLOW(S)中(這里“#為句子括號(hào))。 (b) 假設(shè)AaBb是一個(gè)產(chǎn)生式，那么把FIRST(b)的非空元素參加FOLLOW(B)中。 如果b e那么把FOLLOW(A)也參加FOLLOW(B)中。計(jì)算SELECT(A->a)：Aa, AVN, aV*, 假設(shè)a e,那么SELECT(Aa)=FIRST(a)假設(shè)ae ，那么SELECT(Aa)=(FIRST(a)-e)FOLL

12、OW(A)例：文法：SiCtS|iCtSeS|a，Cb中first(S)為 A ，follow(S)為 B 。 A. i,a； B. e,#； C. i,e,#； D. e,b l LL(1)文法的條件例：LL(1)文法的條件是_C_。A. 對(duì)形如U:=x1 | x2 | | xn 的規(guī)那么，要求First(xi) First(xj)=F,(ij);B. 對(duì)形如 U:=x1 | x2 | | xn 的規(guī)那么，假設(shè)xi=>*e, 那么要求First(xj) Follow(U)=F,(ij)C. a 和 bD. 都不是l 構(gòu)造LL(1)分析表例：已給文法 GS ： S SaP | Sf |

13、P P qbP | q 將 GS 改造成 LL(1)文法，并給出 LL(1)分析表。 答：改造后的文法：S PS'S' aPS'| fS' | eP qP'P' bP | e各候選式的 FIRST 集，各非終結(jié)符的 FOLLOW 集為.產(chǎn)生式SELECT集FOLLOW集SPS'q#S'aPS'a#fS'fe#PqP'qa,f,#P'bPba,f,#e a,f,#LL(1) 分析表為abfq#SPS'S'aPS'fS'ePqP'P'ebPee第六章 自底

14、向上優(yōu)先分析l 算符文法的定義如果不含空產(chǎn)生式的上下文無(wú)關(guān)文法 G 中沒(méi)有形如 A®BC的產(chǎn)生式，其中B, CVN，那么稱G 為算符文法OG。l 最左素短語(yǔ)的概念設(shè)有文法GS，其句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除自身外不再包含其他素短語(yǔ)。處于句型最左邊的素短語(yǔ)為最左素短語(yǔ)例：給定文法G如下：EE+T|T；TT*F|F； FPF|P；PE|i 句型P*P+i的最左素短語(yǔ)為 A 。 A. P*P； B. P； C. P+i； D. P*P+i 第七章 LR分析l LR(K)的含義l L 從左至右掃描輸入符號(hào)串l R 構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程l K 向右順序查看輸入串的K個(gè)

15、符號(hào)l LR分析器的邏輯結(jié)構(gòu)及活前綴等概念l LR分析對(duì)文法的要求l 構(gòu)造LR(0)分析表、SLR(1)分析表l 用SLR分析法分析非二義性的文法和二義性的文法。例：文法AaAd|aAb|e 判斷該文法是否是SLR(1)文法，假設(shè)是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。答：文法： AaAd|aAb| 拓廣文法為G，增加產(chǎn)生式SA假設(shè)產(chǎn)生式排序?yàn)椋? S' A 1 A aAd2 A aAb3 A 由產(chǎn)生式知： First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = # Follow(A ) = d,b,#G的LR(0)工程集族及識(shí)別活前綴的DFA如下列圖所示： 在I0中：A .aAd和A .aAb為移進(jìn)工程，A .為歸約工程，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移進(jìn)-歸約沖突可以由Foll