編譯原理復習(有答案)

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

2、字母表、符號串和集合的概念及運算 例：(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 ：非終結符集VT ：終結符集P：產(chǎn)生式規(guī)那么集合S：開始符號或識別符號例：給定文法，A:= bA | cc，下面哪些符號串可由其推

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

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

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

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

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

8、174;y 轉換成： A=xy A®xA½y 轉換成： A=x*y A®x, A®y 轉換成： A=x½y 例：給出下述文法所對應的正規(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 的組成例：指出哪些串是自動機可接受的 xy xyxxy yyyx xyyxyxyxxy l NFA和DFA的相互轉換例

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的相互轉換例：構造正規(guī)式1(0|1)*101相應的DFA 答：先構造NFA：用子集法將NFA確定化 .01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態(tài)，令AB為B、AC為C、ABY為D，因為D含有YNFA的終態(tài)，所以D為終態(tài)。.01X.AAABBCBCADDCBDFA的狀態(tài)圖：:第

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

11、)中 (e) 當(d)中所有Yi e, (i=1, 2, n), 那么FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)e 計算FOLLOW(A)： (a) 設S為文法中開始符號，把#參加FOLLOW(S)中(這里“#為句子括號)。 (b) 假設AaBb是一個產(chǎn)生式，那么把FIRST(b)的非空元素參加FOLLOW(B)中。 如果b e那么把FOLLOW(A)也參加FOLLOW(B)中。計算SELECT(A->a)：Aa, AVN, aV*, 假設a e,那么SELECT(Aa)=FIRST(a)假設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. 對形如U:=x1 | x2 | | xn 的規(guī)那么，要求First(xi) First(xj)=F,(ij);B. 對形如 U:=x1 | x2 | | xn 的規(guī)那么，假設xi=>*e, 那么要求First(xj) Follow(U)=F,(ij)C. a 和 bD. 都不是l 構造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 集，各非終結符的 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)生式的上下文無關文法 G 中沒有形如 A®BC的產(chǎn)生式，其中B, CVN，那么稱G 為算符文法OG。l 最左素短語的概念設有文法GS，其句型的素短語是一個短語，它至少包含一個終結符，且除自身外不再包含其他素短語。處于句型最左邊的素短語為最左素短語例：給定文法G如下：EE+T|T；TT*F|F； FPF|P；PE|i 句型P*P+i的最左素短語為 A 。 A. P*P； B. P； C. P+i； D. P*P+i 第七章 LR分析l LR(K)的含義l L 從左至右掃描輸入符號串l R 構造一個最右推導的逆過程l K 向右順序查看輸入串的K個

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