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ì)用戶程序的差錯(cuò)能力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.acbbcB.abbcacC.abcD.acc例： (a|b)a +(ba) * 和后面的那些串匹配?（ ADE）A.baB.bbaC.ababaD.aaE.baa文法的定義（四元組表示）文法 G 定義為四元組（VN，VT， P，S）VN ：非終結(jié)符集VT ：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開(kāi)始符號(hào)（或識(shí)別符號(hào)）例：給定文法，A:= bA | cc ，下面哪

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

4、 L(r)中元素為9個(gè)。例：文法G 產(chǎn)生式為 SAB，AaAb|，B cBd|cd ，則B L(G)。A. ababcd； B. ccdd； C. ab；D.aabb等價(jià)文法例：如果兩個(gè)文法描述了同一個(gè)語(yǔ)言，則這兩個(gè)文法是等價(jià)文法。文法的類型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：A ，AaB ，BAb，Ba是幾型文法？ 2 型例：文法Sa|bC ，

5、 Cd 是幾型文法？ 3型最左（右）推導(dǎo)規(guī)范推導(dǎo)：最右推導(dǎo)被稱為規(guī)范推導(dǎo)規(guī)范句型 ：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型規(guī)范歸約 :左歸約為規(guī)范歸約二義性例：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(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)造兩

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

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

8、xB, By轉(zhuǎn)換成：A=xyAxA y轉(zhuǎn)換成：A=x yAx, Ay轉(zhuǎn)換成：A=x y例：給出下述文法所對(duì)應(yīng)的正規(guī)式：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 的組成例：指出哪些串是自動(dòng)機(jī)可接受的（ ） xy xyxxy yyyxxyyxyxyxxyNFA和 DFA的相互轉(zhuǎn)換例：將下圖確定化：答：用子集法將NFA 確定化：.01S VQ QU VQ VZ QUQUV

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

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

11、FIRST(Yi)都包含在 FIRST(X)中為(e)當(dāng) (d)中所有 Yi, (i=1,2, n),. 產(chǎn)SELECT FOLLOW則FIRST(X)=FIRST(Y1) FIRST(Y2)生集集 FIRST(Yn) 式計(jì)算 FOLLOW(A)：S(a) 設(shè) S 為文法中開(kāi)始符號(hào)，把#加入q#PS'FOLLOW(S)中(這里 “ #為”句子括號(hào) )。S'(b) 若 A B 是一個(gè)產(chǎn)生式，則把a(bǔ)#aPS'FIRST( )的非空元素加入FOLLOW(B)中。ffS'如果則把 FOLLOW(A)也加入#FOLLOW(B)中。P計(jì)算 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.對(duì)形如 U:=x1 | x2 |的xn規(guī)則，要求 First(xi) First(xj)=,(i j);B.對(duì)形如U:=x1 | x2 | 的xn規(guī)則，若 xi=>* ,

13、 則 要 求 First(xj) Follow(U)=,(i j)C. a 和 bD. 都不是構(gòu)造 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第六章自底向上優(yōu)先分析算符文法的定義如果不含空產(chǎn)生式的上下文無(wú)關(guān)文法G中沒(méi)有形如ABC 的產(chǎn)生式，其中 B, C VN，則稱 G 為算符文法（ OG）。最左素短語(yǔ)的概念設(shè)有文法 GS，其句型的素短語(yǔ)是一個(gè)短

14、語(yǔ)，它至少包含一個(gè)終結(jié)符，且除自身外不再包含其他素短語(yǔ)。處于句型最左邊的素短語(yǔ)為最左素短語(yǔ)例：給定文法G 如下：EE+T|T；TT*F|F ；F P F|P； P（E） |i句型 P*P+i 的最左素短語(yǔ)為（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從左至右掃描輸入符號(hào)串各候選式的 FIRST 集，各非終結(jié)符的FOLLOW 集R構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程K 向右順序查看輸入串的 K 個(gè)符號(hào)LR 分析器的邏輯結(jié)構(gòu)及活前綴等概念LR 分析

15、對(duì)文法的要求構(gòu)造 LR(0)分析表、 SLR(1)分析表用 SLR分析法分析非二義性的文法和二義性的文法。例：已知文法A aAd|aAb|判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b# 給出分析過(guò)程。答：文法：AaAd|aAb| 拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序?yàn)椋?S' A1A aAd2A aAb3A 由產(chǎn)生式知：First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = #Follow(A ) = d,b,#G的 LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示：在 I0中：A .aAd和 A .aAb為移進(jìn)項(xiàng)目， A .為歸約項(xiàng)目，存在移進(jìn) -歸約沖突，因此所給文法不是 LR(0)文法。在 I0、 I2 中：Follow(A) a=，db，# a=所以在 I 0、I2 中的移進(jìn) -歸約沖突可以由Follow 集解決，所以 G 是