第一章編譯概述1.1翻譯程序的三種方式1.編譯：將高級(jí)語(yǔ)言編寫的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言。2.解釋：將高級(jí)語(yǔ)言編寫的源程序翻譯一句執(zhí)行一句，不生成目標(biāo)文件，直接執(zhí)行源代碼文件。3.匯編：用匯編語(yǔ)言編寫的源程序翻譯成與之等價(jià)的機(jī)器語(yǔ)言。1.2編譯程序的五個(gè)階段1.詞法分析：對(duì)源程序的字符串進(jìn)行掃描和分解，識(shí)別出每個(gè)單詞符號(hào)。2.語(yǔ)法分析：根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)分解成各類語(yǔ)法單位。3.語(yǔ)義分析與中間代碼生成：對(duì)各種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查，若正確則進(jìn)行中間代碼翻譯。4.代碼優(yōu)化：遵循程序的等價(jià)變換規(guī)則。5.目標(biāo)代碼生成：將中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。第二章文法和語(yǔ)言2.1符號(hào)串和語(yǔ)言2.1.1字母表1.定義：字母表是有窮非空的符號(hào)集合。2.表示：通常用字母表大寫字母A，B，…Z和希臘字母Σ表示。eg：A={0,1}，Σ={a,b,c,d}3.說(shuō)明1）字母表包含了語(yǔ)言中所允許出現(xiàn)的一切符號(hào)。2）字母表中的符號(hào)也稱字符。2.1.2符號(hào)串1.定義：由字母表中的符號(hào)組成的有窮序列。2.表示：通常由t，u，v，w，x，y，z等小寫英文字母來(lái)表示。3.說(shuō)明

1）符號(hào)串由構(gòu)成的符號(hào)的種類、數(shù)量、順序共同決定。2）不包含任何符號(hào)的符號(hào)串稱為空符號(hào)串，簡(jiǎn)稱空串，用ε表示。4.對(duì)于給定的字母表Σ，符號(hào)串的遞歸定義如下：1）ε是Σ上的一個(gè)符號(hào)串。2）若x是Σ上的符號(hào)串，a是Σ的符號(hào)，則xa是Σ上的符號(hào)串。并規(guī)定εa=a，aε=a3）y是Σ上的符號(hào)串，當(dāng)且僅當(dāng)y由1）和2）導(dǎo)出。5.子符號(hào)串：一個(gè)非空符號(hào)串中若干連續(xù)符號(hào)組成的部分。6.字符串的前綴和后綴若z=abd是字母表Σ={a,b,c,d}上的符號(hào)串，則ε，a，ab，abd都是z的前綴；ε，d，bd，abd都是z的后綴。（正序逆序排序即可，前綴為正序排序的所有子串，后綴為逆序排序的所有子串）7.符號(hào)串之間的運(yùn)算1）連接：符號(hào)串x，y的連接xy就是把符號(hào)串y寫在x后面得到的字符串。eg：若x=ab，y=cd，則xy=abcd，yx=cdab。2）方冪：若x是符號(hào)串，xn表示n個(gè)按順序連接。當(dāng)n=0時(shí)，x0是空符號(hào)串ε。2.1.3語(yǔ)言1.定義：由字母表上的一些符號(hào)串組成的集合。2.說(shuō)明空集?是一個(gè)語(yǔ)言，僅含一個(gè)空符號(hào)串的集合{ε}也是一個(gè)語(yǔ)言。?和{ε}是不同的語(yǔ)言。3.符號(hào)串集合之間的運(yùn)算1）并集

設(shè)A和B是符號(hào)串的集合，則A和B的并集定義為

A∪B=

{x|x∈Aorx∈B}2）乘積（我覺(jué)得就是笛卡爾積）

設(shè)A和B是符號(hào)串的集合，則A和B的乘積定義為

AB={xy|x∈Aandy∈B}。eg：若A={a,b}，B={b,c}，則AB={ab,ac,bb,bc}。對(duì)任意符號(hào)串集合A，有{ε}A=A{ε}=A。3）冪運(yùn)算

設(shè)A是符號(hào)串的集合，則A的冪運(yùn)算定義為A0={ε}A1=AAn=AAn-1（n>0）eg：若A={0,1}，則A0={ε}，A1={0,1}，A2={00,01,10,11}。4）正閉包與閉包

設(shè)A是符號(hào)串的集合，則集合A的正閉包A+和閉包A*定義為A+=A1∪A2∪…∪An∪…A*=A0∪A1∪…∪An∪…eg：若A={0,1}，則A+={0,1,00,01,10,11,000,001,…}，A*={ε,0,1,00,01,10,11,000,001,…}。2.2文法和語(yǔ)言的形式化定義2.2.1文法的形式化定義1.產(chǎn)生式規(guī)則1）定義：一個(gè)產(chǎn)生式規(guī)則是一個(gè)有序?qū)?A，α)。通常寫作A→α或A::=α。

”→"或”::=”表示“定義為”、“由…組成”、“生成”。2）含義：A→α表示左部符號(hào)A生成右部符號(hào)串α。3）若A→α；A→β，則可以寫成A→α|β?！眧”表示“或”。4）非終結(jié)符號(hào)：產(chǎn)生式規(guī)則左部出現(xiàn)的符號(hào)。5）終結(jié)符號(hào)：不是非終結(jié)符號(hào)的符號(hào)。6）非終結(jié)符號(hào)既可以出現(xiàn)在產(chǎn)生式規(guī)則的左部，也可以出現(xiàn)在產(chǎn)生式規(guī)則的右部。終結(jié)符號(hào)不能出現(xiàn)在產(chǎn)生式規(guī)則的左部。7）非終結(jié)符號(hào)通常用大寫字母或尖括號(hào)括起來(lái)的部分表示。2.文法1）定義：產(chǎn)生式規(guī)則的非空有窮集合。由四元組G=(VN，VT，P，Z)組成。2）VN：是一個(gè)非空有窮集合。它的每個(gè)元素稱為非終結(jié)符號(hào)。且VN∩VT=?。3）VT：是一個(gè)非空有窮集合。它的每個(gè)元素稱為終結(jié)符號(hào)。4）P：是文法規(guī)則(產(chǎn)生式規(guī)則)的非空有窮集合，每個(gè)產(chǎn)生式規(guī)則的形式是A→α或A::=α，其中A∈VN，α∈(VN∪VT)*。5）Z：是一個(gè)非終結(jié)符號(hào)。稱為開(kāi)始符號(hào)或識(shí)別符號(hào)。它至少要在一條產(chǎn)生式規(guī)則的左部出現(xiàn)。有它開(kāi)始識(shí)別定義的語(yǔ)言。6）通常不必將文法的四元組顯式地表示出來(lái)，而僅需給出文法的產(chǎn)生式規(guī)則集。7）對(duì)于兩個(gè)不同的文法G[Z]和G’[E]，若這兩個(gè)文法生成的語(yǔ)言相同，則稱這兩個(gè)文法是等價(jià)的。2.2.2語(yǔ)言的形式化定義1.直接推導(dǎo)與推導(dǎo)1)直接推導(dǎo)：令G=(VN，VT，P，Z)，若A→γ∈P，且α,β∈(VN∪VT)*，則稱αAβ直接推導(dǎo)出αγβ，表示成αA?βαγβ。2）推導(dǎo)：若存在一個(gè)直接推導(dǎo)序列：α0?α1?α2?…?αn，則稱這個(gè)序列是一個(gè)從α0至αn的長(zhǎng)度為n的推導(dǎo)。

當(dāng)n>0時(shí)，α0至αn的推導(dǎo)記為α0?+αn，表示從α0出發(fā)，經(jīng)過(guò)1步或者若干步可推導(dǎo)出αn。

當(dāng)n≥0時(shí)，α0至αn的推導(dǎo)記為α0?*αn，表示從α0出發(fā)，經(jīng)過(guò)0步或者若干步可推導(dǎo)出αn。2.句型和句子設(shè)有文法G[Z]，Z是文法G的開(kāi)始符號(hào)。1）句型：若Z?*x，x∈(VN∪VT)*，則稱符號(hào)串x為文法G[Z]的句型。2）句子：若Z?*x，x∈VT*，則稱符號(hào)串x為文法G[Z]的句子。(非終結(jié)符元素）3）句子一定是句型，句型不一定是句子。（看x的范圍就知道了）3.語(yǔ)言1）定義：文法G[Z]產(chǎn)生的所有句子的集合稱為文法G所定義的語(yǔ)言，記為L(zhǎng)(G[Z])，簡(jiǎn)寫為L(zhǎng)(G)。L(G)={x|Z?+x且x∈VT*}。2）語(yǔ)言L(G)是VT*的子集。3）L(G)中的每一個(gè)符號(hào)串均由終結(jié)符號(hào)組成，且該符號(hào)串能由開(kāi)始符號(hào)Z推導(dǎo)出來(lái)。4.遞歸規(guī)則(直接遞歸)1）定義：一個(gè)產(chǎn)生式規(guī)則中，出現(xiàn)在左部的非終結(jié)符也出現(xiàn)在其右部。2）種類：左遞歸、右遞歸、遞歸。（由非終結(jié)符出現(xiàn)的位置命名）3）左遞歸：A→A…4）右遞歸：A→…A5）遞歸：A→…A…5.文法遞歸1）定義：對(duì)于文法中的任一非終結(jié)符，若能建立一個(gè)推導(dǎo)過(guò)程，在推導(dǎo)所得的符號(hào)串中又出現(xiàn)該終結(jié)符本身，則稱文法是遞歸的。2）種類：左遞歸、右遞歸、遞歸。3）左遞歸：A?+A…4）右遞歸：A?+…A5）遞歸：A?+…A…2.2.3短語(yǔ)、直接短語(yǔ)、句柄設(shè)G[Z]是一個(gè)文法，假定αβδ是文法G的一個(gè)句型。1）短語(yǔ)：若存在Z?+αAδ且A?+β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。2）直接短語(yǔ)：若存在Z?+αAδ且A?β，則稱β是句型αβδ相對(duì)于產(chǎn)生式規(guī)則A→β的直接短語(yǔ)。3）句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。2.2.4規(guī)范推導(dǎo)和規(guī)范歸約1.最左推導(dǎo)：對(duì)一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)α?β，都是對(duì)α中的最左非終結(jié)符進(jìn)行替換。2.最右推導(dǎo)(規(guī)范推導(dǎo))：對(duì)一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)α?β，都是對(duì)α中的最右非終結(jié)符進(jìn)行替換。3.規(guī)范句型：由規(guī)范推導(dǎo)得到的句型。4.最左歸約(規(guī)范歸約)：規(guī)范推導(dǎo)的逆過(guò)程。2.3語(yǔ)法分析樹(shù)與文法的二義性2.3.1語(yǔ)法分析樹(shù)1.語(yǔ)法分析樹(shù)：一個(gè)句型推導(dǎo)過(guò)程的樹(shù)形表示稱為語(yǔ)法分析樹(shù)，簡(jiǎn)稱語(yǔ)法樹(shù)。2.滿足條件：設(shè)G=(VN，VT，P，Z)是一個(gè)上下文無(wú)關(guān)文法。1）根節(jié)點(diǎn)的標(biāo)記為Z。2）根節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)也有一個(gè)標(biāo)記，它是VN∪VT∪{ε}中的符號(hào)。3）每一個(gè)內(nèi)部節(jié)點(diǎn)的標(biāo)記A必在VN中。4）若某個(gè)內(nèi)部節(jié)點(diǎn)標(biāo)記為A，其