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

2、字母表、符號串和集合的概念及運算例： (ab|b) *c 和下面的那些串匹配？（ACD ）A. ababbc； B. abab；C. c；D. babc； E. aaabc例： ab* c* (a|b)c 和后面的那些串匹配？（BC）A.acbbcB.abbcacC.abcD.acc例： (a|b)a +(ba) * 和后面的那些串匹配?（ ADE）A.baB.bbaC.ababaD.aaE.baa文法的定義（四元組表示）文法 G 定義為四元組（VN，VT， P，S）VN ：非終結符集VT ：終結符集P：產生式（規則）集合S：開始符號（或識別符號）例：給定文法，A:= bA | cc ，下面哪

3、些符號串可由其推導出（ ）。 ccb*ccb*cbcc bccbcc bbbcc什么是推導例：已知文法G：E->E+T|E-T|TT->T*F|T/F|FF->(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+i句型、句子的概念例：假設 G 一個文法， S 是文法的開始符號，如果 S=>*x，則稱 x 是 句型 。例：對于文法 G，僅含終結符號的句型稱為句子。語言的形式定義例：設r=(a|b|c)(x|y|z)，則

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

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

6、個不同的最右推導:最右推導 1 表達式表達式運算符表達式表達式運算符 a表達式 * a表達式運算符表達式 * a表達式運算符 a * a表達式 + a * aa + a * a最右推導 2 表達式表達式運算符表達式表達式運算符表達式運算符表達式表達式運算符表達式運算符a表達式運算符表達式* a表達式運算符 a * a表達式 + a * aa + a * a短語、句柄、直接短語例：令文法GE為:E->E+T|E-TT->T*F|T/F|FF->(E)|i證明 E+T*F 是它的一個句型 ,指出這個句型的所有短語、直接短語和句柄。例：已知文法GSS aB|bAA a|aS|bAA

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

8、xB, By轉換成：A=xyAxA y轉換成：A=x yAx, Ay轉換成：A=x y例：給出下述文法所對應的正規式：S0A|1BA1S|1B0S|0答：S->0A | 1B->01S | 01 | 10S | 10->(01|10)S | (01|10)-> (01|10)(01|10)*即： r=(01|10) (01|10)*NFA和 DFANFA和 DFA 的組成例：指出哪些串是自動機可接受的（ ） xy xyxxy yyyxxyyxyxyxxyNFA和 DFA的相互轉換例：將下圖確定化：答：用子集法將NFA 確定化：.01S VQ QU VQ VZ QUQUV

9、QUZVZZZVZ.QUZ VZ QUZZZZ重新命名狀態子集， 令 VQ 為 A 、QU 為 B、VZ 為C、V 為 D、QUZ 為 E、Z 為 F。.01SABACBBDECFFDF.ECEFFFDFA 的狀態圖：正規式和 NFA 的相互轉換例：構造正規式 1(0|1)*101 相應的 DFA答：先構造NFA ：用子集法將NFA 確定化.01X.AA A AB AB AC AB AC A ABYABY ACAB除 X ，A 外，重新命名其他狀態，令AB 為 B、AC為 C 、ABY 為 D ，因為 D 含有 Y（NFA 的終態），所以 D 為終態。.01X.AAABBCBCADDCBDFA

10、 的狀態圖： :第五章自頂向下語法分析方法語法分析常用的方法是_B_。 自頂向下自底向上自左向右 自右向左A. B. C. D. 會求 FIRST、 FOLLOW集計算 FIRST(X)：(a) 若 XVT, 則 FIRST(X) X(b) 若 XVN, 且有產生式 X a , aVT, 則 a FIRST(X)(c) 若 X VN, X , 則 FIRST(X)(d) 若 XVN, Y1, Y2, , Yi VN, 且有產生式XYY Y; 當 Y Y Y 都12n12i-1時 ,( 其 中1i n), 則FIRST(Y1) 、FIRST(Y2)、 、 FIRST(Yi-1)的所有非 元素和

11、FIRST(Yi)都包含在 FIRST(X)中為(e)當 (d)中所有 Yi, (i=1,2, n),. 產SELECT FOLLOW則FIRST(X)=FIRST(Y1) FIRST(Y2)生集集 FIRST(Yn) 式計算 FOLLOW(A)：S(a) 設 S 為文法中開始符號，把#加入q#PS'FOLLOW(S)中(這里 “ #為”句子括號 )。S'(b) 若 A B 是一個產生式，則把a#aPS'FIRST( )的非空元素加入FOLLOW(B)中。ffS'如果則把 FOLLOW(A)也加入#FOLLOW(B)中。P計算 SELECT(A->)：qa

12、,f,#qP'A , AVN, V*,P'若,則 SELECT(A )=FIRST( )ba,f,#bP若，則 SELECT(A )=(FIRST( )- ) FOLLOW(A)例：文法：SiCtS|iCtSeS|a ，Cb中 first(S)為（A ）， follow(S)為（B ）。A. i,a；B. e,#；C. i,e,#；D. e,bLL(1)文法的條件例： LL(1)文法的條件是 _C_。A.對形如 U:=x1 | x2 |的xn規則，要求 First(xi) First(xj)=,(i j);B.對形如U:=x1 | x2 | 的xn規則，若 xi=>* ,

13、 則 要 求 First(xj) Follow(U)=,(i j)C. a 和 bD. 都不是構造 LL(1)分析表例：已給文法GS ：S SaP | Sf | P P qbP | q將 GS 改造成 LL(1)文法，并給出 LL(1)分析表。答：改造后的文法： a,f,#LL(1) 分析表為abfq#SPS'S'aPS'fS'PqP'P'bP第六章自底向上優先分析算符文法的定義如果不含空產生式的上下文無關文法G中沒有形如ABC 的產生式，其中 B, C VN，則稱 G 為算符文法（ OG）。最左素短語的概念設有文法 GS，其句型的素短語是一個短

14、語，它至少包含一個終結符，且除自身外不再包含其他素短語。處于句型最左邊的素短語為最左素短語例：給定文法G 如下：EE+T|T；TT*F|F ；F P F|P； P（E） |i句型 P*P+i 的最左素短語為（A ）。A.P*P ；B.P；S PS'C. P+i；D. P*P+iS' aPS'| fS' |第七章 LR 分析P qP'LR(K)的含義P' bP |L從左至右掃描輸入符號串各候選式的 FIRST 集，各非終結符的FOLLOW 集R構造一個最右推導的逆過程K 向右順序查看輸入串的 K 個符號LR 分析器的邏輯結構及活前綴等概念LR 分析

15、對文法的要求構造 LR(0)分析表、 SLR(1)分析表用 SLR分析法分析非二義性的文法和二義性的文法。例：已知文法A aAd|aAb|判斷該文法是否是SLR(1)文法，若是構造相應分析表，并對輸入串ab# 給出分析過程。答：文法：AaAd|aAb| 拓廣文法為G，增加產生式SA若產生式排序為：0S' A1A aAd2A aAb3A 由產生式知：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=，db，# a=所以在 I 0、I2 中的移進 -歸約沖突可以由Follow 集解決，所以 G 是