編譯原理講義(第二章文法與語(yǔ)言)課件

1、編譯原理講義(第二章文法與語(yǔ)言)編譯原理講義編譯原理講義(第二章:文法與語(yǔ)言)南京大學(xué)計(jì)算機(jī)系趙建華編譯原理講義(第二章文法與語(yǔ)言)文法與語(yǔ)言 文法被用來(lái)精確而無(wú)歧義地描述語(yǔ)言的句子的構(gòu)成方式. 文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。編譯原理講義(第二章文法與語(yǔ)言)字母表定義：字母表是有窮非空集合。 字母表包含了語(yǔ)言中所允許出現(xiàn)的一切符號(hào)。編譯原理講義(第二章文法與語(yǔ)言)符號(hào)串 定義：符號(hào)串是由字母表中的符號(hào)所組成的有窮序列。 一個(gè)語(yǔ)言的句子總是它的字母表的符號(hào)串。這個(gè)符號(hào)串的組成必須是按照文法規(guī)則組合而成的。 語(yǔ)法分析的一個(gè)重要任務(wù)就是：判斷一個(gè)符號(hào)串的組成是否滿足某個(gè)文法的規(guī)定，并且分析出是

2、如何按照規(guī)則組成的。編譯原理講義(第二章文法與語(yǔ)言)關(guān)于符號(hào)串的概念和操作 運(yùn)算： 聯(lián)結(jié)(并置)：x=123, y=45那么xy=12345 方冪：x的n次方冪即將n個(gè)x聯(lián)結(jié)。 子符號(hào)串：v是xvy的子符號(hào)串。v非空 頭，尾：x是xy的頭，y是xy的尾。編譯原理講義(第二章文法與語(yǔ)言)符號(hào)串集合 定義：若集合A中的一切元素都是同一個(gè)同一個(gè)字母表上字母表上的集合，那么A被稱為該字母表上的符號(hào)串集合。 在本課程中，語(yǔ)言被認(rèn)為是句子的集合。（外延定義？）所以，一個(gè)語(yǔ)言就是對(duì)應(yīng)于它的字母表上的一個(gè)符號(hào)串集合。編譯原理講義(第二章文法與語(yǔ)言)符號(hào)串集合的運(yùn)算 乘積：AB = xy | xA且y B 方冪

3、：A的n次方冪就是將n個(gè)A相乘。 字母表的閉包與正閉包： 字母表A的閉包是A上的所有符號(hào)串（包括空字符串）的集合。 字母表A的正閉包是A上的所有的非空符號(hào)串的集合。編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（重寫規(guī)則） 重寫規(guī)則：一個(gè)重寫規(guī)則是一個(gè)有序?qū)?U,u)，通常寫作U := u。其中U是一個(gè)符號(hào)，稱為左部；u是一個(gè)符號(hào)串稱為右部。有時(shí)也說這個(gè)規(guī)則是U的一個(gè)規(guī)則。 重寫規(guī)則總是基于某個(gè)字匯表的。U和u中的符號(hào)必須都在這個(gè)字匯表內(nèi)。這個(gè)字匯表中有些符號(hào)不能作為左部。 存在更加復(fù)雜的規(guī)則，但是這樣的規(guī)則足夠描述程序設(shè)計(jì)語(yǔ)言的文法。編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（重寫規(guī)

4、則） 例如: 標(biāo)識(shí)符:= 字母 標(biāo)識(shí)符:= 字母|標(biāo)識(shí)符字母 第二個(gè)規(guī)則實(shí)際使用了BNF的表示方法。BNF表示方法的還包括: 花括號(hào)表示重復(fù):字母 方括號(hào)表示可選:參數(shù)編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（文法） 文法：文法GZ是一組有窮非空的重寫規(guī)則的集合。其中Z稱為識(shí)別符號(hào)。G為文法名字 文法例子：P22, 例子2.10。 所有的規(guī)則都是基于同一個(gè)符號(hào)表V。符號(hào)表又可分劃非終結(jié)符號(hào)集合VN和終結(jié)符號(hào)結(jié)合VT。編譯原理講義(第二章文法與語(yǔ)言) 句子:= := :=Peter | Berry | River := :=Swims := in := 編譯原理講義(第二章文法與語(yǔ)言)文

5、法和語(yǔ)言的定義（推導(dǎo)） 文法的作用是描述某種語(yǔ)言的句子的構(gòu)成方式。使用文法我們可以產(chǎn)生對(duì)應(yīng)語(yǔ)言的句子。 從識(shí)別符號(hào)開始，不斷將當(dāng)前符號(hào)串中的非終結(jié)符號(hào)替換為該符號(hào)的某個(gè)規(guī)則的右部。直到當(dāng)前的符號(hào)串中所有的符號(hào)都是終結(jié)符號(hào)為止。編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（推導(dǎo)） 例子：句子=主語(yǔ)謂語(yǔ)狀語(yǔ)=名詞謂語(yǔ)狀語(yǔ)= = Peter swims in river編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（推導(dǎo)） 直接推導(dǎo)：v=xUy，w=xuy，并且U:=u是文法中的一個(gè)重寫規(guī)則，那么我們說v可以直接推導(dǎo)到w，或者w可以直接規(guī)約到v。記作 v = w。 例如：主語(yǔ)謂語(yǔ)狀語(yǔ)=名詞謂語(yǔ)

6、狀語(yǔ)編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（推導(dǎo)） 推導(dǎo)：對(duì)于符號(hào)串v和w，如果存在一個(gè)直接推導(dǎo)序列u0=u1=un，并且u0=v，un=w，那么我們說v可以推導(dǎo)到w，或者w規(guī)約到v。記作v =+ w。 這個(gè)推導(dǎo)長(zhǎng)度為n，且稱w為對(duì)應(yīng)于v的一個(gè)字。 v=* w 表示v=w或者v =+ w。編譯原理講義(第二章文法與語(yǔ)言)文法和語(yǔ)言的定義（推導(dǎo)） 推導(dǎo)的例子：P25頁(yè)例2.12。 文法： := := | := 0 | 1 | 2 | 3 | | 9 VT0,1,2,3,4,5,6,7,8,9, VN = 編譯原理講義(第二章文法與語(yǔ)言)推導(dǎo)的例子 = = = = = 23= 123編譯

7、原理講義(第二章文法與語(yǔ)言)語(yǔ)言的定義（句型,句子） 對(duì)于文法GZ，x稱為G的一個(gè)句型如果：Z =* x識(shí)別符號(hào)是最簡(jiǎn)單的句型。 GZ的一個(gè)句型x被稱為句子，如果：xVT*也就是說句子是全部由終結(jié)符號(hào)組成的句型。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言的定義（短語(yǔ)，簡(jiǎn)單短語(yǔ)） 短語(yǔ)：對(duì)于文法GZ，如果Z =* xUy，U=+ u。顯然，w=xuy是一個(gè)句型。我們稱u是句型句型w中相對(duì)于中相對(duì)于U的短語(yǔ)短語(yǔ)。 簡(jiǎn)單短語(yǔ)：在上面的定義中，如果U := u是G的一個(gè)規(guī)則，那么，u是句型句型w中相中相對(duì)于對(duì)于U的簡(jiǎn)單短語(yǔ)。 例子：P22頁(yè)例2.13。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言的定義（短語(yǔ)，句柄）

8、 注意：在尋找一個(gè)句型的短語(yǔ)（或簡(jiǎn)單短語(yǔ)）時(shí)，必須要求將這個(gè)短語(yǔ)規(guī)約為相應(yīng)的非終結(jié)符號(hào)后所得到的符號(hào)串仍然是句型。 句柄：一個(gè)句型的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄。 定義句柄的原因：在自底向上識(shí)別一個(gè)符號(hào)串時(shí)，總是規(guī)約這個(gè)句柄。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言的定義（文法的語(yǔ)言） 文法的語(yǔ)言：一個(gè)文法GZ的語(yǔ)言，用L(GZ)表示，定義如下：L(GZ) = x | Z=* x 并且 x VT+ 一個(gè)文法的語(yǔ)言就是該文法的所有的句子的集合。 文法的語(yǔ)言是所有終結(jié)符號(hào)串所組成的集合的子集，一般是真子集。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言的定義（遞歸與語(yǔ)言） 遞歸的規(guī)則：U := U 左右遞歸規(guī)則

9、：U := U；U := U 文法的遞歸：U =+ U，稱文法遞歸于U。 文法的左右遞歸： 如果文法是非遞歸的，那么其語(yǔ)言是有窮的。編譯原理講義(第二章文法與語(yǔ)言)文法與語(yǔ)言（例子） GA：A:=bA|a； L(GA)=bia|i=0 GZ：Z:=Ab；A:= aaA A:=aa L(GZ) = a2nb|n=1編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言的分類 Chomsky文法的定義：(VN,VT,P,Z) 該定義是我們前面講的定義的一個(gè)更加形式化的表達(dá)。 在這個(gè)定義中，文法規(guī)則的左部可以是一個(gè)非空符號(hào)串。 Chomsky文法被分為四類，我們主要用2型和3型文法。編譯原理講義(第二章文法與語(yǔ)言)C

10、homsky文法類（0型文法PSG） 0型文法的規(guī)則形如：u:=v，u,v為符號(hào)串，且u非空。0型文法的相應(yīng)語(yǔ)言稱為0型語(yǔ)言，又稱為遞歸可枚舉集合。 0型語(yǔ)言是不可判定的。 例子：G：Z:=#A1#；#A:=#；A1:=11A；A# := B#；1B := B1；#B := #A L(G)=#1i#|i=2n,n=0編譯原理講義(第二章文法與語(yǔ)言)Chomsky文法類（1型文法CSG） 1型文法的規(guī)則如下：xUy:=xuy，其中U為非終結(jié)符號(hào)，x,y,u為符號(hào)串，且u非空。1型文法又稱為上下文相關(guān)文法。 1型文法也可以如下定義：所有的規(guī)則的右部都不比左部短。 1型文法是可判定的。但是現(xiàn)在沒有找

11、到有效的方法。編譯原理講義(第二章文法與語(yǔ)言)Chomsky文法類（2型文法CFG） 2型文法的規(guī)則有如下形狀：U:=u，其中U是非終結(jié)符號(hào)，u是符號(hào)串。2型文法又稱為上下文無(wú)關(guān)文法。 一般的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法都使用2型文法描述。 2型文法是可判定的，且又有效的判定方法。編譯原理講義(第二章文法與語(yǔ)言)Chomsky文法類（3型文法RG） 文法規(guī)則的形狀：U:=T或者U:=WT，其中U，W是非終結(jié)符號(hào)，T是終結(jié)符號(hào)。 3型文法又稱為正則文法，其語(yǔ)言也稱為正則語(yǔ)言。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)言類對(duì)運(yùn)算的封閉性 給定某個(gè)語(yǔ)言類中的語(yǔ)言，如果對(duì)它們進(jìn)行某種運(yùn)算之后得到的新語(yǔ)言仍舊是該類語(yǔ)言，

12、那么該語(yǔ)言類對(duì)此運(yùn)算封閉。 所有語(yǔ)言類對(duì)并，乘積，閉包運(yùn)算封閉。 CFG語(yǔ)言類對(duì)交，補(bǔ)運(yùn)算不封閉。 正則語(yǔ)言類對(duì)交并補(bǔ)運(yùn)算封閉。編譯原理講義(第二章文法與語(yǔ)言)3型語(yǔ)言與有窮自動(dòng)機(jī) 任何一個(gè)3型語(yǔ)言都可以使用一個(gè)有窮自動(dòng)機(jī)來(lái)識(shí)別。 有窮自動(dòng)機(jī)包括一個(gè)有限控制器，和一個(gè)輸入帶。機(jī)器從輸入帶從左到右逐個(gè)讀入輸入符號(hào)，最終根據(jù)有限控制器的狀態(tài)確定輸入的符號(hào)串是否是該型語(yǔ)言的句子。機(jī)器的每一個(gè)動(dòng)作根據(jù)當(dāng)前讀入的符號(hào)和當(dāng)前狀態(tài)確定。編譯原理講義(第二章文法與語(yǔ)言)有窮自動(dòng)機(jī)例子aacbbabcabcaabc編譯原理講義(第二章文法與語(yǔ)言)2型語(yǔ)言與下推自動(dòng)機(jī) 任何一個(gè)2型語(yǔ)言都可以使用一個(gè)下推自動(dòng)機(jī)來(lái)識(shí)

13、別。 下推自動(dòng)機(jī)相當(dāng)與一個(gè)有窮自動(dòng)機(jī)和一個(gè)棧。自動(dòng)機(jī)的每一步動(dòng)作根據(jù)棧頂?shù)姆?hào)，當(dāng)前讀入的符號(hào)，一個(gè)有限控制器的當(dāng)前狀態(tài)來(lái)確定，可以包括讀入符號(hào)，壓棧，出棧，和確定接受。編譯原理講義(第二章文法與語(yǔ)言)形式語(yǔ)言與程序設(shè)計(jì)語(yǔ)言 雖然程序設(shè)計(jì)語(yǔ)言的語(yǔ)法都使用上下文無(wú)關(guān)文法來(lái)描述，但是通常語(yǔ)言都是上下文相關(guān)的。 使用上下文無(wú)關(guān)文法描述語(yǔ)言的原因是：存在高效處理上下文無(wú)關(guān)文法的技術(shù)。編譯原理講義(第二章文法與語(yǔ)言)關(guān)于CFG的進(jìn)一步討論 Chomsky范式：所有的上下文無(wú)關(guān)語(yǔ)言都可以用如下形式的文法產(chǎn)生：所有的規(guī)則都形如：U := VW 或者 U:=T，其中U,V,W為非終結(jié)符號(hào)，T為終結(jié)符號(hào)。 Gr

14、eibach范式：所有上下文無(wú)關(guān)語(yǔ)言都能由這樣的文法產(chǎn)生：U:=Tu，這里U為非終結(jié)符號(hào)，T為終結(jié)符號(hào)。編譯原理講義(第二章文法與語(yǔ)言)關(guān)于CFG的進(jìn)一步討論 自嵌套：一個(gè)上下文無(wú)關(guān)文法為自嵌套的，如果存在一個(gè)非終結(jié)符號(hào)U滿足:U =* xUy，且x,y非空。 定理2.6 若一個(gè)CFG GZ不是自嵌套的，那么L(G)必然是一個(gè)正則語(yǔ)言。 但是，自嵌套的上下文無(wú)關(guān)文法也可能產(chǎn)生正則語(yǔ)言。例:P35頁(yè)編譯原理講義(第二章文法與語(yǔ)言)關(guān)于推導(dǎo)的性質(zhì) 定理2.7 對(duì)于CFG，如果存在句型x=x1x2xn且x=*y，必然存在y1,y2,yn使得: xi=*yi且y= y1y2yn。 定理2.8 如果:x

15、=*y，如果x的首符號(hào)是終結(jié)符號(hào)，則y的首符號(hào)也是終結(jié)符號(hào)；反之，如果y的首符號(hào)是非終結(jié)符號(hào)，那么x的首符號(hào)也是非終結(jié)符號(hào)。編譯原理講義(第二章文法與語(yǔ)言)空規(guī)則 定理2.9 設(shè)L是由上下文無(wú)關(guān)文法G=(VN,VT,P,Z)產(chǎn)生的語(yǔ)言，P中可能包含空規(guī)則，則L能由這樣的文法產(chǎn)生，在這樣的文法中每一個(gè)規(guī)則或者是U:=u，或者Z:=空. 這個(gè)定理表示：在語(yǔ)言中增加和刪除一個(gè)空串，并不會(huì)改變語(yǔ)言的類別。編譯原理講義(第二章文法與語(yǔ)言)文法等價(jià) 定義：設(shè)G和G是兩個(gè)文法，如果L(G)等于L(G)，那么我們說G和G等價(jià)。 例子： GS S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c GS

16、S:=Sc|Bc B:=Bb|Ab A:=Aa|a 兩個(gè)CFG文法是否等價(jià)是不可判定的。編譯原理講義(第二章文法與語(yǔ)言)文法的等價(jià)變換 當(dāng)有些技術(shù)不能處理一種文法時(shí)，我們可以將它處理為另外一個(gè)等價(jià)文法來(lái)處理。這就是等價(jià)變換。 使文法和語(yǔ)言類一致。 消除二義性。 使文法適用于某種分析技術(shù)。 文法滿足某種特殊需要。編譯原理講義(第二章文法與語(yǔ)言)文法等價(jià)變換的種類 壓縮文法等價(jià)變換 增廣文法等價(jià)變換 范式文法等價(jià)變換 消去左遞歸等價(jià)變換編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換 主要作用是刪除文法中不可能被使用的規(guī)則，稱為多余規(guī)則。包括： 規(guī)則的左部不可能在句型中出現(xiàn)。 使用了此規(guī)則之后，句

17、型永遠(yuǎn)也不能推導(dǎo)得到句子。 一個(gè)規(guī)則U:=u不是多余的，當(dāng)且僅當(dāng)： Z=* xUy，且（條件1） U=+t, 且t是終結(jié)符號(hào)串。（條件2）編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換 已壓縮文法定義：沒有多余規(guī)則的文法稱為壓縮了的（或已壓縮的）文法。 壓縮算法： 算法重復(fù)執(zhí)行重復(fù)執(zhí)行下面兩個(gè)部分，直到不能刪除更多的規(guī)則： 刪除不滿足條件一的規(guī)則。（子算法1） 刪除不滿足條件二的規(guī)則。（子算法2）編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換（子算法1） 步驟1：對(duì)規(guī)則中識(shí)別符號(hào)z加標(biāo)記； 步驟2：對(duì)左部非終結(jié)符號(hào)加有標(biāo)記的規(guī)則，將其右部中的所有非終結(jié)符號(hào)加標(biāo)記。 步驟3：檢查是否一切非終

18、結(jié)符號(hào)都加過標(biāo)記。是，結(jié)束；否，執(zhí)行步驟4。 步驟4：如果上一次步驟2中沒有多加標(biāo)記，刪除所有左部沒有加標(biāo)記的規(guī)則，結(jié)束。否則，轉(zhuǎn)向步驟2。編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換（子算法1） 例子：Z := Be A := AeA := eB := Ce B := AfC := CfD := f編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換（子算法2） 步驟1：對(duì)uVT+的規(guī)則U:=u的左部非終結(jié)符號(hào)U加標(biāo)記。 步驟2：對(duì)右部?jī)H包含終結(jié)符號(hào)和已加標(biāo)記的非終結(jié)符號(hào)的規(guī)則的左部加標(biāo)記。 步驟3：檢查是否對(duì)一切非終結(jié)符號(hào)加過標(biāo)記。是，結(jié)束；否則，執(zhí)行步驟4。 步驟4：如果上一次步驟2執(zhí)行

19、時(shí)沒有多加任何標(biāo)記，那么刪除左部沒有加標(biāo)記的規(guī)則，否則，轉(zhuǎn)到步驟2。編譯原理講義(第二章文法與語(yǔ)言)壓縮文法等價(jià)變換（子算法2） 例子：Z := BeA := AeA := eB := CeB := AfC := Cf編譯原理講義(第二章文法與語(yǔ)言)增廣文法等價(jià)變換 一般來(lái)講，以識(shí)別符號(hào)為左部的規(guī)則有多個(gè)。在規(guī)約的時(shí)候使用的規(guī)則也時(shí)不唯一的。增廣文法變換使得文法只有一個(gè)以識(shí)別符號(hào)為左部的規(guī)則。 變換方法：GZ變換為GZ，且增加規(guī)則Z := Z。有時(shí)候，新的規(guī)則為Z := Z#。此時(shí)所得到的語(yǔ)言有所不同。 是一種變換的特例：P40頁(yè)。編譯原理講義(第二章文法與語(yǔ)言)消單規(guī)則等價(jià)變換 目的：提高分

20、析算法的效率。注意：?jiǎn)我?guī)則有時(shí)是有用的，但是，太多的單規(guī)則會(huì)影響分析的效率。 算法的基本思想是： 首先，對(duì)于每個(gè)U，求解出所有的V，使得U=*V。 對(duì)于所有的U =* V，且V := u，增加規(guī)則 U:= u，得到的文法依舊是等價(jià)的。編譯原理講義(第二章文法與語(yǔ)言)消單規(guī)則等價(jià)變換（算法） 步驟1：對(duì)每個(gè)UVN，構(gòu)造NU=V|U=*V，V VN 步驟2：構(gòu)造P=Ui:=u | V:=u P,V NU,|u|1或uVN 步驟3：新的不含單規(guī)則的文法為：（VN,VT,P,Z)編譯原理講義(第二章文法與語(yǔ)言)消單規(guī)則等價(jià)變換（例子） G2.10E：E :=E+TE:=TT:=T*FT:=FF:=(E

21、)F:=i NE=E,T,F E:= E+T | T*F |(E) | i .編譯原理講義(第二章文法與語(yǔ)言)習(xí)題 GA A:=aAb | ab,證明： L(G)=anbn 設(shè)計(jì)文法：anbmcmdn編譯原理講義(第二章文法與語(yǔ)言)Chomsky范式范式變換 步驟1：消單規(guī)則。 步驟2：變換成為：U:=T 或者 U:=V1V2Vm 步驟3：引入新的非終結(jié)符號(hào)。 U:=V1V2Vm修改為 U:=V1W1 ； W1:=V2W2 ； Wm-1:=Vm-1Vm；編譯原理講義(第二章文法與語(yǔ)言)Chomsky范式范式變換（例子） 步驟1：對(duì)于文法G2.10E，消除單規(guī)則:E:=E+T E:=T*F E:

22、=(E) E:=i 步驟2：引入規(guī)則A:=+ M:=* 原來(lái)的規(guī)則變?yōu)? E:=EAT E:=TMF 步驟3： 原來(lái)的規(guī)則變?yōu)? E := EB B:=AT .編譯原理講義(第二章文法與語(yǔ)言)消規(guī)則左遞歸等價(jià)變換 改寫規(guī)則左遞歸成為右遞歸將E := E+T | T改寫為:E := TEE := + TE | 編譯原理講義(第二章文法與語(yǔ)言)消規(guī)則左遞歸等價(jià)變換(例子) E := E+T|TT:= T*F|FF:=(E)|i 變換得到如下文法:E := TEE=+TE|T := FTT=*FT|F := (E)|i編譯原理講義(第二章文法與語(yǔ)言)消規(guī)則左遞歸等價(jià)變換(BNF) 沿用擴(kuò)充BNF表示

23、法 E := E+T | T 改寫為E := T+T 步驟1：提取左因子： U := ux|uy|uz = U:= u(x|y|z) 步驟2：假定U:=x|y|z|Uu；替換為 U := (x|y|z)u編譯原理講義(第二章文法與語(yǔ)言)消規(guī)則左遞歸等價(jià)變換(例子2) E := T | -T | E+T | E-T 步驟1：提因子 E := (T|-T) | E(+T|-T) 步驟2： E:=(T|-T)+T|-T 或者E:=(-| )T(+|-)T編譯原理講義(第二章文法與語(yǔ)言)消文法左遞歸(方法) 要求：文法不包含回路，無(wú)空規(guī)則 步驟1：排列非終結(jié)符號(hào)U1,U2,Un 步驟2：執(zhí)行程序（見下

24、一頁(yè)） 步驟3：刪除無(wú)用規(guī)則。 原理：將非終結(jié)符號(hào)排序之后，消除所有形如Ui:=Ujx的規(guī)則，其中i=j。這樣，對(duì)于任何非終結(jié)符號(hào)Ui，如果Ui=+Ujx，必然有ji。不可能有文法左遞歸。編譯原理講義(第二章文法與語(yǔ)言)消文法左遞歸(步驟2的程序) For(i=1; I=n; I+) for(j:=1;ji。改寫的規(guī)則也包括新加入的規(guī)則。編譯原理講義(第二章文法與語(yǔ)言)消文法左遞歸（例子） S := Sa | Tbc | TdT := Se | gh 步驟1：排序:ST 步驟2：循環(huán)： i = 1, j=1;消除規(guī)則左遞歸。 i=2, j=1;消除T:=Sx的情況，并消除規(guī)則左遞歸。 步驟3：

25、編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)法樹的概念 定義：語(yǔ)法樹是這樣的一個(gè)語(yǔ)法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號(hào)組成。根結(jié)點(diǎn)對(duì)應(yīng)于識(shí)別符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。 引入語(yǔ)法樹的意義：作為識(shí)別句子的輔助工具，語(yǔ)法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)法樹的相關(guān)概念 結(jié)點(diǎn)：每個(gè)樹的結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。 邊：兩個(gè)結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹：語(yǔ)法樹的某個(gè)結(jié)點(diǎn)和它向下射出的

26、部分。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)法樹的相關(guān)概念（續(xù)） 末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)。編譯原理講義(第二章文法與語(yǔ)言)語(yǔ)法樹的例子語(yǔ)法GS:S:=ABA:=aAb | abB:=cBd | cdSABabcBdcdS=AB=abB=abcBd=abccdd編譯原理講義(第二章文法與語(yǔ)言)從推導(dǎo)構(gòu)造語(yǔ)法樹 步驟1：根結(jié)點(diǎn)為識(shí)別符號(hào)。 步驟2：對(duì)于每一次推導(dǎo)使用的規(guī)則U := u，找出U對(duì)應(yīng)的結(jié)點(diǎn)（此時(shí)應(yīng)該是末端結(jié)點(diǎn)），從該結(jié)點(diǎn)向下畫分支，子結(jié)點(diǎn)從左到右分別是u中從左到右的符號(hào)。 重復(fù)步驟2直到推導(dǎo)的最后一步。編譯原理講義(第

27、二章文法與語(yǔ)言)語(yǔ)法樹中子樹的性質(zhì) 定理2.12：一個(gè)子樹的末端結(jié)點(diǎn)的組成的符號(hào)串是相對(duì)于子樹的根結(jié)點(diǎn)的短語(yǔ)。 如果這個(gè)子樹的高度是1（兩層）的話，其末端結(jié)點(diǎn)組成的符號(hào)串是根結(jié)點(diǎn)的簡(jiǎn)單短語(yǔ)。編譯原理講義(第二章文法與語(yǔ)言)從語(yǔ)法樹構(gòu)造推導(dǎo) 構(gòu)造的過程是一個(gè)剪枝的過程。每剪掉一個(gè)分支，添加一步規(guī)約過程。 首先，任意找一個(gè)高度為1的子樹，確定這個(gè)子樹對(duì)應(yīng)的規(guī)則。將子樹的分支剪掉，得到一個(gè)新的語(yǔ)法樹。該語(yǔ)法樹的末端結(jié)點(diǎn)對(duì)應(yīng)的符號(hào)串就是經(jīng)過一步規(guī)約之后得到的句型。如此循環(huán)，直到語(yǔ)法樹只剩下一個(gè)根結(jié)點(diǎn)。編譯原理講義(第二章文法與語(yǔ)言)從語(yǔ)法樹構(gòu)造推導(dǎo)（續(xù)） 同一棵語(yǔ)法樹可以得到不同的推導(dǎo)，但是其實(shí)質(zhì)上是

28、使用規(guī)則的順序不同。這些推導(dǎo)的過程實(shí)際是等價(jià)的。 例如： S=AB=AcBd=Accdd=abccdd S=AB=abB=abcBd=abccdd編譯原理講義(第二章文法與語(yǔ)言)文法的二義性 定義：如果對(duì)于某文法的同一個(gè)句子存在兩棵不同的語(yǔ)法樹，則該句子是二義性的。而該文法是二義性文法。 這里的二義性是指語(yǔ)法結(jié)構(gòu)上的。 如果一個(gè)句子具有二義性，那么對(duì)這個(gè)句子的結(jié)構(gòu)可能有多種正確的解釋。通常情況下，句子的語(yǔ)義要通過其語(yǔ)法結(jié)構(gòu)來(lái)定義，所以，二義性一般是有害的。編譯原理講義(第二章文法與語(yǔ)言)文法二義性（例子）文法GE：E:=E+E | E*E | (E) | i文法的句子: i+i*i，其語(yǔ)法樹如

29、下：EE+EE*EEE+EE*E編譯原理講義(第二章文法與語(yǔ)言)二義性 一般來(lái)講，二義性是針對(duì)文法而言的，說語(yǔ)言二義性是無(wú)意義的。 定義2.35：如果某個(gè)語(yǔ)言對(duì)應(yīng)的文法都是二義性的，那么這個(gè)語(yǔ)言被稱為先天二義性的。 定理2.13：文法的二義性是不可判定的。 即使文法是無(wú)二義性的，其句子對(duì)應(yīng)的語(yǔ)義仍然必須有嚴(yán)格的定義，才可以避免語(yǔ)義的二義性。編譯原理講義(第二章文法與語(yǔ)言)句型分析（概念） 句型分析就是識(shí)別一個(gè)符號(hào)串是否是某文法的句型。它是一種推導(dǎo)或語(yǔ)法樹的構(gòu)造過程。對(duì)于一個(gè)給定的符號(hào)串，試圖按照文法的規(guī)則構(gòu)造其對(duì)應(yīng)的推導(dǎo)，或語(yǔ)法樹。編譯原理講義(第二章文法與語(yǔ)言)分析技術(shù)分類 自頂向下技術(shù):從文法的識(shí)別符號(hào)開始，由它推導(dǎo)出與輸入符號(hào)相同的符號(hào)串。 從語(yǔ)法樹的角度看,自頂向下的分析過程就是