編譯原理講義(第二章文法與語言).ppt

編譯原理講義 (第二章:文法與語言),南京大學(xué)計(jì)算機(jī)系 趙建華,文法與語言,文法被用來精確而無歧義地描述語言的句子的構(gòu)成方式. 文法描述語言的時候不考慮語言的含義。,字母表,定義：字母表是有窮非空集合。 字母表包含了語言中所允許出現(xiàn)的一切符號。,符號串,定義：符號串是由字母表中的符號所組成的有窮序列。 一個語言的句子總是它的字母表的符號串。這個符號串的組成必須是按照文法規(guī)則組合而成的。 語法分析的一個重要任務(wù)就是：判斷一個符號串的組成是否滿足某個文法的規(guī)定，并且分析出是如何按照規(guī)則組成的。,關(guān)于符號串的概念和操作,運(yùn)算： 聯(lián)結(jié)(并置)：x=123, y=45那么xy=12345 方冪：x的n次方冪即將n個x聯(lián)結(jié)。 子符號串：v是xvy的子符號串。v非空 頭，尾：x是xy的頭，y是xy的尾。,符號串集合,定義：若集合A中的一切元素都是同一個字母表上的集合，那么A被稱為該字母表上的符號串集合。 在本課程中，語言被認(rèn)為是句子的集合。（外延定義？）所以，一個語言就是對應(yīng)于它的字母表上的一個符號串集合。,符號串集合的運(yùn)算,乘積：AB = xy | xA且y B 方冪：A的n次方冪就是將n個A相乘。 字母表的閉包與正閉包： 字母表A的閉包是A上的所有符號串（包括空字符串）的集合。 字母表A的正閉包是A上的所有的非空符號串的集合。,文法和語言的定義（重寫規(guī)則）,重寫規(guī)則：一個重寫規(guī)則是一個有序?qū)?U,u)，通常寫作 U := u。其中U是一個符號，稱為左部；u是一個符號串稱為右部。有時也說這個規(guī)則是U的一個規(guī)則。 重寫規(guī)則總是基于某個字匯表的。U和u中的符號必須都在這個字匯表內(nèi)。這個字匯表中有些符號不能作為左部。 存在更加復(fù)雜的規(guī)則，但是這樣的規(guī)則足夠描述程序設(shè)計(jì)語言的文法。,文法和語言的定義（重寫規(guī)則）,例如: 標(biāo)識符:= 字母 標(biāo)識符:= 字母|標(biāo)識符字母 第二個規(guī)則實(shí)際使用了BNF的表示方法。BNF表示方法的還包括: 花括號表示重復(fù): 字母 方括號表示可選: 參數(shù),文法和語言的定義（文法）,文法：文法GZ是一組有窮非空的重寫規(guī)則的集合。其中Z稱為識別符號。G為文法名字 文法例子：P22, 例子2.10。 所有的規(guī)則都是基于同一個符號表V。符號表又可分劃非終結(jié)符號集合VN和終結(jié)符號結(jié)合VT。,句子:= := :=Peter | Berry | River := :=Swims := in := ,文法和語言的定義（推導(dǎo)）,文法的作用是描述某種語言的句子的構(gòu)成方式。使用文法我們可以產(chǎn)生對應(yīng)語言的句子。 從識別符號開始，不斷將當(dāng)前符號串中的非終結(jié)符號替換為該符號的某個規(guī)則的右部。直到當(dāng)前的符號串中所有的符號都是終結(jié)符號為止。,文法和語言的定義（推導(dǎo)）,例子： 句子=主語謂語狀語 =名詞謂語狀語 = = Peter swims in river,文法和語言的定義（推導(dǎo)）,直接推導(dǎo)：v=xUy，w=xuy，并且U:=u是文法中的一個重寫規(guī)則，那么我們說v可以直接推導(dǎo)到w，或者w可以直接規(guī)約到v。記作 v = w。 例如： 主語謂語狀語 =名詞謂語狀語,文法和語言的定義（推導(dǎo)）,推導(dǎo)：對于符號串v和w，如果存在一個直接推導(dǎo)序列u0=u1=un，并且u0=v，un=w，那么我們說v可以推導(dǎo)到w，或者w規(guī)約到v。記作v =+ w。 這個推導(dǎo)長度為n，且稱w為對應(yīng)于v的一個字。 v=* w 表示v=w或者v =+ w。,文法和語言的定義（推導(dǎo)）,推導(dǎo)的例子：P25頁例2.12。 文法： := := | := 0 | 1 | 2 | 3 | | 9 VT0,1,2,3,4,5,6,7,8,9, VN = ,推導(dǎo)的例子, = = = = = 23 = 123,語言的定義（句型,句子）,對于文法GZ，x稱為G的一個句型如果： Z =* x 識別符號是最簡單的句型。 GZ的一個句型x被稱為句子，如果： xVT* 也就是說句子是全部由終結(jié)符號組成的句型。,語言的定義（短語，簡單短語）,短語：對于文法GZ，如果Z =* xUy，U=+ u。顯然，w=xuy是一個句型。我們稱u是句型w中相對于U的短語。 簡單短語：在上面的定義中，如果U := u是G的一個規(guī)則，那么，u是句型w中相對于U的簡單短語。 例子：P22頁例2.13。,語言的定義（短語，句柄）,注意：在尋找一個句型的短語（或簡單短語）時，必須要求將這個短語規(guī)約為相應(yīng)的非終結(jié)符號后所得到的符號串仍然是句型。 句柄：一個句型的最左簡單短語稱為該句型的句柄。 定義句柄的原因：在自底向上識別一個符號串時，總是規(guī)約這個句柄。,語言的定義（文法的語言）,文法的語言：一個文法GZ的語言，用L(GZ)表示，定義如下： L(GZ) = x | Z=* x 并且 x VT+ 一個文法的語言就是該文法的所有的句子的集合。 文法的語言是所有終結(jié)符號串所組成的集合的子集，一般是真子集。,語言的定義（遞歸與語言）,遞歸的規(guī)則：U := U 左右遞歸規(guī)則：U := U；U := U 文法的遞歸：U =+ U，稱文法遞歸于U。 文法的左右遞歸： 如果文法是非遞歸的，那么其語言是有窮的。,文法與語言（例子）,GA：A:=bA|a； L(GA)=bia|i=0 GZ：Z:=Ab；A:= aaA A:=aa L(GZ) = a2nb|n=1,語言的分類,Chomsky文法的定義： (VN,VT,P,Z) 該定義是我們前面講的定義的一個更加形式化的表達(dá)。 在這個定義中，文法規(guī)則的左部可以是一個非空符號串。 Chomsky文法被分為四類，我們主要用2型和3型文法。,Chomsky文法類（0型文法PSG）,0型文法的規(guī)則形如：u:=v，u,v為符號串，且u非空。0型文法的相應(yīng)語言稱為0型語言，又稱為遞歸可枚舉集合。 0型語言是不可判定的。 例子：G：Z:=#A1#；#A:=#；A1:=11A；A# := B#；1B := B1；#B := #A L(G)=#1i#|i=2n,n=0,Chomsky文法類（1型文法CSG）,1型文法的規(guī)則如下：xUy:=xuy，其中U為非終結(jié)符號，x,y,u為符號串，且u非空。1型文法又稱為上下文相關(guān)文法。 1型文法也可以如下定義：所有的規(guī)則的右部都不比左部短。 1型文法是可判定的。但是現(xiàn)在沒有找到有效的方法。,Chomsky文法類（2型文法CFG）,2型文法的規(guī)則有如下形狀：U:=u，其中U是非終結(jié)符號，u是符號串。2型文法又稱為上下文無關(guān)文法。 一般的程序設(shè)計(jì)語言的語法都使用2型文法描述。 2型文法是可判定的，且又有效的判定方法。,Chomsky文法類（3型文法RG）,文法規(guī)則的形狀：U:=T或者U:=WT，其中U，W是非終結(jié)符號，T是終結(jié)符號。 3型文法又稱為正則文法，其語言也稱為正則語言。,語言類對運(yùn)算的封閉性,給定某個語言類中的語言，如果對它們進(jìn)行某種運(yùn)算之后得到的新語言仍舊是該類語言，那么該語言類對此運(yùn)算封閉。 所有語言類對并，乘積，閉包運(yùn)算封閉。 CFG語言類對交，補(bǔ)運(yùn)算不封閉。 正則語言類對交并補(bǔ)運(yùn)算封閉。,3型語言與有窮自動機(jī),任何一個3型語言都可以使用一個有窮自動機(jī)來識別。 有窮自動機(jī)包括一個有限控制器，和一個輸入帶。機(jī)器從輸入帶從左到右逐個讀入輸入符號，最終根據(jù)有限控制器的狀態(tài)確定輸入的符號串是否是該型語言的句子。機(jī)器的每一個動作根據(jù)當(dāng)前讀入的符號和當(dāng)前狀態(tài)確定。,有窮自動機(jī)例子,a,a,c,b,b,abcabcaabc,2型語言與下推自動機(jī),任何一個2型語言都可以使用一個下推自動機(jī)來識別。 下推自動機(jī)相當(dāng)與一個有窮自動機(jī)和一個棧。自動機(jī)的每一步動作根據(jù)棧頂?shù)姆?，?dāng)前讀入的符號，一個有限控制器的當(dāng)前狀態(tài)來確定，可以包括讀入符號，壓棧，出棧，和確定接受。,形式語言與程序設(shè)計(jì)語言,雖然程序設(shè)計(jì)語言的語法都使用上下文無關(guān)文法來描述，但是通常語言都是上下文相關(guān)的。 使用上下文無關(guān)文法描述語言的原因是：存在高效處理上下文無關(guān)文法的技術(shù)。,關(guān)于CFG的進(jìn)一步討論,Chomsky范式：所有的上下文無關(guān)語言都可以用如下形式的文法產(chǎn)生：所有的規(guī)則都形如：U := VW 或者 U:=T，其中U,V,W為非終結(jié)符號，T為終結(jié)符號。 Greibach范式：所有上下文無關(guān)語言都能由這樣的文法產(chǎn)生：U:=Tu，這里U為非終結(jié)符號，T為終結(jié)符號。,關(guān)于CFG的進(jìn)一步討論,自嵌套：一個上下文無關(guān)文法為自嵌套的，如果存在一個非終結(jié)符號U滿足: U =* xUy，且x,y非空。 定理2.6 若一個CFG GZ不是自嵌套的，那么L(G)必然是一個正則語言。 但是，自嵌套的上下文無關(guān)文法也可能產(chǎn)生正則語言。例:P35頁,關(guān)于推導(dǎo)的性質(zhì),定理2.7 對于CFG，如果存在句型x=x1x2xn且x=*y，必然存在y1,y2,yn使得: xi=*yi且y= y1y2yn。 定理2.8 如果:x=*y，如果x的首符號是終結(jié)符號，則y的首符號也是終結(jié)符號；反之，如果y的首符號是非終結(jié)符號，那么x的首符號也是非終結(jié)符號。,空規(guī)則,定理2.9 設(shè)L是由上下文無關(guān)文法G=(VN,VT,P,Z)產(chǎn)生的語言，P中可能包含空規(guī)則，則L能由這樣的文法產(chǎn)生，在這樣的文法中每一個規(guī)則或者是U:=u，或者Z:=空. 這個定理表示：在語言中增加和刪除一個空串，并不會改變語言的類別。,文法等價,定義：設(shè)G和G是兩個文法，如果L(G)等于L(G)，那么我們說G和G等價。 例子： GS S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c GS S:=Sc|Bc B:=Bb|Ab A:=Aa|a 兩個CFG文法是否等價是不可判定的。,文法的等價變換,當(dāng)有些技術(shù)不能處理一種文法時，我們可以將它處理為另外一個等價文法來處理。這就是等價變換。 使文法和語言類一致。 消除二義性。 使文法適用于某種分析技術(shù)。 文法滿足某種特殊需要。,文法等價變換的種類,壓縮文法等價變換 增廣文法等價變換 范式文法等價變換 消去左遞歸等價變換,壓縮文法等價變換,主要作用是刪除文法中不可能被使用的規(guī)則，稱為多余規(guī)則。包括： 規(guī)則的左部不可能在句型中出現(xiàn)。 使用了此規(guī)則之后，句型永遠(yuǎn)也不能推導(dǎo)得到句子。 一個規(guī)則U:=u不是多余的，當(dāng)且僅當(dāng)： Z=* xUy，且 （條件1） U=+t, 且t是終結(jié)符號串。 （條件2）,壓縮文法等價變換,已壓縮文法定義：沒有多余規(guī)則的文法稱為壓縮了的（或已壓縮的）文法。 壓縮算法： 算法重復(fù)執(zhí)行下面兩個部分，直到不能刪除更多的規(guī)則： 刪除不滿足條件一的規(guī)則。 （子算法1） 刪除不滿足條件二的規(guī)則。 （子算法2）,壓縮文法等價變換（子算法1）,步驟1：對規(guī)則中識別符號z加標(biāo)記； 步驟2：對左部非終結(jié)符號加有標(biāo)記的規(guī)則，將其右部中的所有非終結(jié)符號加標(biāo)記。 步驟3：檢查是否一切非終結(jié)符號都加過標(biāo)記。是，結(jié)束；否，執(zhí)行步驟4。 步驟4：如果上一次步驟2中沒有多加標(biāo)記，刪除所有左部沒有加標(biāo)記的規(guī)則，結(jié)束。否則，轉(zhuǎn)向步驟2。,壓縮文法等價變換（子算法1）,例子： Z := Be A := Ae A := e B := Ce B := Af C := Cf D := f,壓縮文法等價變換（子算法2）,步驟1：對uVT+的規(guī)則U:=u的左部非終結(jié)符號U加標(biāo)記。 步驟2：對右部僅包含終結(jié)符號和已加標(biāo)記的非終結(jié)符號的規(guī)則的左部加標(biāo)記。 步驟3：檢查是否對一切非終結(jié)符號加過標(biāo)記。是，結(jié)束；否則，執(zhí)行步驟4。 步驟4：如果上一次步驟2執(zhí)行時沒有多加任何標(biāo)記，那么刪除左部沒有加標(biāo)記的規(guī)則，否則，轉(zhuǎn)到步驟2。,壓縮文法等價變換（子算法2）,例子： Z := Be A := Ae A := e B := Ce B := Af C := Cf,增廣文法等價變換,一般來講，以識別符號為左部的規(guī)則有多個。在規(guī)約的時候使用的規(guī)則也時不唯一的。增廣文法變換使得文法只有一個以識別符號為左部的規(guī)則。 變換方法：GZ變換為GZ，且增加規(guī)則Z := Z。有時候，新的規(guī)則為Z := Z#。此時所得到的語言有所不同。 是一種變換的特例：P40頁。,消單規(guī)則等價變換,目的：提高分析算法的效率。注意：單規(guī)則有時是有用的，但是，太多的單規(guī)則會影響分析的效率。 算法的基本思想是： 首先，對于每個U，求解出所有的V，使得U=*V。 對于所有的U =* V，且V := u，增加規(guī)則 U:= u，得到的文法依舊是等價的。,消單規(guī)則等價變換（算法）,步驟1：對每個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),消單規(guī)則等價變換（例子）,G2.10E： E :=E+T E:=T T:=T*F T:=F F:=(E) F:=i NE=E,T,F E:= E+T | T*F |(E) | i .,習(xí)題,GA A:=aAb | ab,證明： L(G)=anbn 設(shè)計(jì)文法：anbmcmdn,Chomsky范式范式變換,步驟1：消單規(guī)則。 步驟2：變換成為：U:=T 或者 U:=V1V2Vm 步驟3：引入新的非終結(jié)符號。 U:=V1V2Vm修改為 U:=V1W1 ； W1:=V2W2 ； Wm-1:=Vm-1Vm；,Chomsky范式范式變換（例子）,步驟1：對于文法G2.10E，消除單規(guī)則: E:=E+T E:=T*F E:=(E) E:=i 步驟2：引入規(guī)則A:=+ M:=* 原來的規(guī)則變?yōu)? E:=EAT E:=TMF 步驟3： 原來的規(guī)則變?yōu)? E := EB B:=AT .,消規(guī)則左遞歸等價變換,改寫規(guī)則左遞歸成為右遞歸 將E := E+T | T改寫為: E := TE E := + TE | ,消規(guī)則左遞歸等價變換(例子),E := E+T|T T:= T*F|F F:=(E)|i 變換得到如下文法: E := TE E=+TE| T := FT T=*FT| F := (E)|i,消規(guī)則左遞歸等價變換(BNF),沿用擴(kuò)充BNF表示法 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,消規(guī)則左遞歸等價變換(例子2),E := T | -T | E+T | E-T 步驟1：提因子 E := (T|-T) | E(+T|-T) 步驟2： E:=(T|-T)+T|-T 或者E:=(-| )T(+|-)T,消文法左遞歸(方法),要求：文法不包含回路，無空規(guī)則 步驟1：排列非終結(jié)符號U1,U2,Un 步驟2：執(zhí)行程序（見下一頁） 步驟3：刪除無用規(guī)則。 原理：將非終結(jié)符號排序之后，消除所有形如Ui:=Ujx的規(guī)則，其中i=j。這樣，對于任何非終結(jié)符號Ui，如果Ui=+Ujx，必然有ji。不可能有文法左遞歸。,消文法左遞歸(步驟2的程序),For(i=1; I=n; I+) for(j:=1;j= i-1; j+) 將形如Ui:=Ujr的規(guī)則改寫為 Ui:=xj1r|xj2r|xjkr 消除Ui的規(guī)則左遞歸，新的規(guī)則加 入文法。 ,消文法左遞歸(步驟2的解釋),在改寫規(guī)則的時候，對于每個i, 得到的規(guī)則保證：Ui:=Ujx時，必然有ji。改寫的規(guī)則也包括新加入的規(guī)則。,消文法左遞歸（例子）,S := Sa | Tbc | Td T := Se | gh 步驟1：排序: S T 步驟2：循環(huán)： i = 1, j=1; 消除規(guī)則左遞歸。 i=2, j=1; 消除T:=Sx的情況，并消除規(guī)則左遞歸。 步驟3：,語法樹的概念,定義：語法樹是這樣的一個語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號組成。根結(jié)點(diǎn)對應(yīng)于識別符號。只有非終結(jié)符號對應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對應(yīng)于文法中的一個規(guī)則的左部和右部。 引入語法樹的意義：作為識別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對于其后的語義分析有非常重要的意義。,語法樹的相關(guān)概念,結(jié)點(diǎn)：每個樹的結(jié)點(diǎn)對應(yīng)于一個符號。結(jié)點(diǎn)的名字就是該符號。 邊：兩個結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹：語法樹的某個結(jié)點(diǎn)和它向下射出的部分。,語法樹的相關(guān)概念（續(xù)）,末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號。,語法樹的例子,語法GS: S:=AB A:=aAb | ab B:=cBd | cd,S,A,B,a,b,c,B,d,c,d,S=AB=abB=abcBd=abccdd,從推導(dǎo)構(gòu)造語法樹,步驟1：根結(jié)點(diǎn)為識別符號。 步驟2：對于每一次推導(dǎo)使用的規(guī)則U := u，找出U對應(yīng)的結(jié)點(diǎn)（此時應(yīng)該是末端結(jié)點(diǎn)），從該結(jié)點(diǎn)向下畫分支，子結(jié)點(diǎn)從左到右分別是u中從左到右的符號。 重復(fù)步驟2直到推導(dǎo)的最后一步。,語法樹中子樹的性質(zhì),定理2.12：一個子樹的末端結(jié)點(diǎn)的組成的符號串是相對于子樹的根結(jié)點(diǎn)的短語。 如果這個子樹的高度是1（兩層）的話，其末端結(jié)點(diǎn)組成的符號串是根結(jié)點(diǎn)的簡單短語。,從語法樹構(gòu)造推導(dǎo),構(gòu)造的過程是一個剪枝的過程。每剪掉一個分支，添加一步規(guī)約過程。 首先，任意找一個高度為1的子樹，確定這個子樹對應(yīng)的規(guī)則。將子樹的分支剪掉，得到一個新的語法樹。該語法樹的末端結(jié)點(diǎn)對應(yīng)的符號串就是經(jīng)過一步規(guī)約之后得到的句型。如此循環(huán)，直到語法樹只剩下一個根結(jié)點(diǎn)。,從語法樹構(gòu)造推導(dǎo)（續(xù)）,同一棵語法樹可以得到不同的推導(dǎo)，但是其實(shí)質(zhì)上是使用規(guī)則的順序不同。這些推導(dǎo)的過程實(shí)際是等價的。 例如： S=AB=AcBd=Accdd=abccdd S=AB=abB=abcBd=abccdd,文法的二義性,定義：如果對于某文法的同一個句子存在兩棵不同的語法樹，則該句子是二義性的。而該文法是二義性文法。 這里的二義性是指語法結(jié)構(gòu)上的。 如果一個句子具有二義性，那么對這個句子的結(jié)構(gòu)可能有多種正確的解釋。通常情況下，句子的語義要通過其語法結(jié)構(gòu)來定義，所以，二義性一般是有害的。,文法二義性（例子）,文法GE：E:=E+E | E*E | (E) | i 文法的句子: i+i*i，其語法樹如下：,E,E,+,E,E,*,E,二義性,一般來講，二義性是針對文法而言的，說語言二義性是無意義的。 定義2.35：如果某個語言對應(yīng)的文法都是二義性的，那么這個語言被稱為先天二義性的。 定理2.13：文法的二義性是不可判定的。 即使文法是無二義性的，其句子對應(yīng)的語義仍然必須有嚴(yán)格的定義，才可以避免語義的二義性。,句型分析（概念）,句型分析就是識別一個符號串是否是某文法的句型。它是一種推導(dǎo)或語法樹的構(gòu)造過程。對于一個給定的符號串，試圖按照文法的規(guī)則構(gòu)造其對應(yīng)的推導(dǎo)，或語法樹。,分析技術(shù)分類,自頂向下技術(shù):從文法的識別符號開始，由它推導(dǎo)出與輸入符號相同的符號串。 從語法樹的角度看,自頂向下的分析過程就是：以識別符號作為根結(jié)點(diǎn)，試圖從根結(jié)點(diǎn)