編譯原理知識點

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

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

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

A∪B=

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

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

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

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

設(shè)A是符號串的集合，則集合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文法和語言的形式化定義2.2.1文法的形式化定義1.產(chǎn)生式規(guī)則1）定義：一個產(chǎn)生式規(guī)則是一個有序?qū)?A，α)。通常寫作A→α或A::=α。

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

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

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