編譯原理3課件

第三章文法和語言3.1文法的直觀概念3.2符號(hào)和符號(hào)串3.3文法和語言的形式定義3.4文法的類型3.5上下文無關(guān)文法及其語法樹3.6句型分析語言和文法為什么關(guān)心文法問題？

為語言的描述尋求一種工具(以確定什么樣的句子屬于該語言)。窮舉法是不合適的(原因？)。提供有限的描述語言特性的法則—文法要對(duì)程序設(shè)計(jì)語言給出精確無二義的語法描述，嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀形式化工具

“形式化”是指這樣的事實(shí)：語言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來陳述，形式化很像是數(shù)學(xué)的符號(hào)化文法的直觀概念以自然語言為例，人們羅列出所有的句子，但人們可以給出一些規(guī)則，用它們來說明或定義句子合理的組成結(jié)構(gòu)這里采用前面介紹過的EBNF來如下簡(jiǎn)單地表示自然語言中句子的構(gòu)成規(guī)則：<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=我|你|他符號(hào)和符號(hào)串語言離不開符號(hào)的使用字母表：

字母表是符號(hào)的非空有窮集合，因此，字母表也可稱為符號(hào)集不同的語言可以有不同的字母表符號(hào)串：

由字母表中的符號(hào)組成的任何有窮的符號(hào)序列稱為符號(hào)串符號(hào)串及若干相關(guān)運(yùn)算符號(hào)串的頭尾，固有頭和固有尾：

如果z=xy是一個(gè)符號(hào)串，那么稱x是z的頭，y是z的尾；如果x是非空的，那么y稱為固有尾；同樣，如果y非空，那么稱x是固有頭例，對(duì)于z=abc，那么z的頭是,a,ab,abc，除abc外，其他都是固有頭；z的尾是,c,bc,abc，z的固有尾是,c,bc求符號(hào)串長(zhǎng)度：

如果某符號(hào)串x中有m個(gè)符號(hào)，則稱其長(zhǎng)度為m，并表示為|x|=m例，|001110|=6符號(hào)串上的運(yùn)算符號(hào)串的連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y放在x之后得到的符號(hào)串顯然，x=x=x；|xy|=|x|+|y|符號(hào)串的方冪：

把x連接n次得到的符號(hào)串，如z=xx，寫作z=xn

例，x0=，x1=x等等；如果x=AB，則x2=ABAB字符串集合：

如果集合A中的元素都是某字母表上的符號(hào)串(符號(hào)串的集合)，則稱A為該字母表上的符號(hào)串集合文法定義定義：文法G為四元組(VN,VT,,P,S)其中，VN，VT和P都是非空有窮集。具體地，VN是非終結(jié)符號(hào)(或語法實(shí)體，或語法變量)集；VT終結(jié)符號(hào)集；P是規(guī)則的集合S是稱作識(shí)別符號(hào)或開始符號(hào)的一個(gè)非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪

VT，稱為文法G的字母表或字匯表規(guī)則，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如→或::=的(,)有序?qū)?，其中是字母表V的正閉包V+中的一個(gè)符號(hào)且至少含一個(gè)非終結(jié)符，是V*中的一個(gè)符號(hào)。稱為規(guī)則的左部，稱作規(guī)則的右部文法定義例，文法G=(VN,VT,P,S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號(hào)文法的寫法

元符號(hào):→::=|<>

習(xí)慣:大寫字母表示非終結(jié)符,小寫字母表示終結(jié)符(1)G:S→aAbA→abA→aAbA→(2)G[S]:A→abA→aAbA→

S→aSb(3)G[S]:A→ab|aAb|εS→aSb推導(dǎo)例，有下面的推導(dǎo)，括號(hào)里是相應(yīng)的文法：<程序><分程序>.(<程序><分程序>.)<分程序>.<變量說明部分><語句>.(<分程序><變量說明部分><語句>)VAR<標(biāo)識(shí)符>;BEGINREAD(<標(biāo)識(shí)符>)END.VARA;BEGINREAD(<標(biāo)識(shí)符>)END.(<標(biāo)識(shí)符>A)VARA;BEGINREAD(<標(biāo)識(shí)符>)END.VARA;BEGINREAD(A)END.(<標(biāo)識(shí)符>A)推導(dǎo)若存在v=w0w1...wn=w,(n>0)，則記為v=>+w，稱作v推導(dǎo)出w，或w歸約到v若有v=>+w或v=w，則記為v=>*w例，有文法G：S→0S1，S→01，則可確定存在下面一些推導(dǎo)0S100S1100S11000S111000S11100001111S0S100S11000S11100001111于是，S

+00001111S*S00S11*00S11句子和句型例，設(shè)有文法G[E]：E→E+T|T

T→T*F|F

F→(E)|a

有推導(dǎo)EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a，等等通過觀察可以知道，上述文法定義的句子是用符號(hào)a，+，*，(以及)構(gòu)成的算術(shù)表達(dá)式語言、文法和句子例，由文法G生成的語言記為L(zhǎng)(G),它是文法G的一切句子的集合:L(G)={x|S*x，其中S為文法的開始符號(hào)，且x∈VT*}

例：G：S→0S1，S→01L(G)={0n1n|n≥1}集合表示形式文法、語言和句子例文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee

L(G)={anbnen|n≥1}G生成的每個(gè)串都在L(G)中L(G)中的每個(gè)串確實(shí)能被G生成文法的類型通過對(duì)產(chǎn)生式施加不同的限制，學(xué)者Chomsky將文法分為四種類型：0型文法：對(duì)任一產(chǎn)生式→，都有

(VN∪VT)+，(VN∪VT)*1型文法：對(duì)任一產(chǎn)生式→，都有||≥||，僅僅S→除外2型文法：對(duì)任一產(chǎn)生式→，都有VN

3型文法：任一產(chǎn)生式→的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT*文法的類型例，下面是1型(上下文有關(guān))文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→a BD→bD D→b Aa→bD文法與類型例，下面是2型(上下文無關(guān))文法

文法G[S]： S→AB A→BS|0 B→SA|1不同類型文法之間的關(guān)系四類文法之間存在逐級(jí)包含的關(guān)系2型文法1型文法3型文法0型文法文法和語言文法和它所產(chǎn)生的語言之間存在對(duì)應(yīng)關(guān)系0型文法產(chǎn)生的語言稱為0型語言1型文法或上下文有關(guān)文法(CSG)產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言(CSL)2型文法或上下文無關(guān)文法(CFG)產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言(CFL)3型文法或正則(正規(guī))文法(RG)產(chǎn)生的語言稱為3型語言正則(正規(guī))語言(RL)幾個(gè)理論共識(shí)結(jié)論3：任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述帶a0a1a2a3a4a5a6a7a8…an-1an…有限控制器磁頭幾個(gè)理論共識(shí)結(jié)論4：2型文法產(chǎn)生式的形式為A→，取代A時(shí)與A的上下文無關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)結(jié)論5：3型文法(正規(guī)文法RG)產(chǎn)生的語言是有窮自動(dòng)機(jī)(FA)所接受的集合3型文法與有窮自動(dòng)機(jī)定理：設(shè)G=(VN,VT,P,S)是3型文法，則存在一個(gè)有窮自動(dòng)機(jī)M=(K,,f,A,Z)，使得L(M)=L(G)可以從文法直接構(gòu)造相應(yīng)的自動(dòng)機(jī)：=VT

Z={N}，N是新增加的一個(gè)狀態(tài)A=SK={VN}{N}f的設(shè)置需視情況來定

a,對(duì)G中的形如D→tB的產(chǎn)生式,t為終結(jié)符或，有f(D,t)=Bb,對(duì)G中形如D→t的產(chǎn)生式，t為終結(jié)符或ε,有f(D,t)=Nc,對(duì)VT中的每一個(gè)a,有f(N,a)=φ從3型文法到有窮自動(dòng)機(jī)從3型文法按前述方法可直接構(gòu)造相應(yīng)的有窮自動(dòng)機(jī)G[S]：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bASaabbba,bZababBD從有窮自動(dòng)機(jī)到3型文法定理：已知一有窮自動(dòng)機(jī)M=(K,,f,A,Z)，那么存在一個(gè)3型文法G=(VN,VT,P,S)，使得L(G)=L(M)3型文法的構(gòu)造方法：VT=VN=KS=A對(duì)轉(zhuǎn)換函數(shù)

a,若f(D,t)=B，則D→tB在P中

b,若f(D,t)=B，且B在Z中，則D→t在P中從有窮自動(dòng)機(jī)到3型文法下面的例子是從有窮自動(dòng)機(jī)到3型文法的直接轉(zhuǎn)換G[S]：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bDBASaaabba,bb正規(guī)式與3型文法定理：對(duì)上的正規(guī)式r，存在一個(gè)RG=(VN,VT,P,S)使得L(G)=L(r)成立轉(zhuǎn)換方法：初始時(shí)，VT=

，SVN，生成正規(guī)產(chǎn)生式Sra,對(duì)形如Ar1r2的正規(guī)式得到產(chǎn)生式：Ar1B Br2將B加入VNb,對(duì)形如Arr1的正規(guī)式得到產(chǎn)生式：ArB，將B加入VNAr1

BrBBr1c,對(duì)形如Ar1r2的正規(guī)式得到產(chǎn)生式：Ar1Ar2

不斷應(yīng)用(R.x)做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè)VN從正規(guī)式到正規(guī)文法轉(zhuǎn)換實(shí)例對(duì)正規(guī)式r=a(ad)*，有下面的轉(zhuǎn)換過程(1)Sa(ad)*(2)SaAA(ad)*

(3)A(a|d)BAB(a|d)BB從而得到下面轉(zhuǎn)換后的文法：G[s]：SaAA AaBAdBBaBBdB BVT={a,d}VN={S,A,B}從正規(guī)文法到正規(guī)式定理：已知G=(VN,VT,P,S)，那么存在一個(gè)=VT上的正規(guī)式r，使得L(r)=L(G)成立轉(zhuǎn)換方法：對(duì)AxB，By，得到正規(guī)式A=xy對(duì)AxA|y，得到正規(guī)式A=x*y對(duì)Ax|y，得到正規(guī)式A=x|y從正規(guī)文法到正規(guī)式的實(shí)例對(duì)于文法G[s]:SaA|aAaA|a|dA|d有下面的轉(zhuǎn)換過程：A(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a((ad)(ad))=a((ad))從而得到：

R=a(ad)上下文無關(guān)文法結(jié)論：

上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)以語法樹的形式給出句型推導(dǎo)直觀表示文法、推導(dǎo)、句型和句子設(shè)有文法G[E]：E→E+T|T

T→T*F|F

F→(E)|a

有下面的推導(dǎo)成立

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*a

EE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a規(guī)范推導(dǎo)與規(guī)范句型最左推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左非終結(jié)符進(jìn)行替換最右推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最右非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型語法樹及其形式表示定義：設(shè)G=(VN,VT,P,S)為一上下文無關(guān)文法，若一棵樹滿足下列4個(gè)條件，則此樹稱作G的語法樹(也稱推導(dǎo)樹或派生樹)：1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2.根的標(biāo)記是S3.若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定AVN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式語法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之上下文無關(guān)文法的語法樹句型aabbaa可能的推導(dǎo)序列和語法樹例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa推導(dǎo)的唯一問題一棵語法樹表示了一個(gè)句型一種可能的推導(dǎo)過程，但存在下面問題值得考慮對(duì)任何一個(gè)句型，是否其推導(dǎo)過程只對(duì)應(yīng)唯一的一棵語法樹呢?對(duì)任一句型，它是否只有唯一的一個(gè)最左或最右推導(dǎo)呢?兩個(gè)不同推導(dǎo)對(duì)下面的文法，存在兩棵不同的語法樹顯然，對(duì)句型i*i+i有兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i

推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii二義文法定義1：

若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左或最右推導(dǎo)，則稱這個(gè)文法是二義的定義2：

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的文法二義性與語言二義性文法二義性和語言二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G，其中G是二義文法，但是卻有L(G)=L(G)，也就是說，這兩個(gè)文法所產(chǎn)生的語言是相同的如果一個(gè)上下無關(guān)語言，能產(chǎn)生它的每一個(gè)文法都是二義的，則說此語言是先天二義的顯然，對(duì)于一個(gè)程序設(shè)計(jì)語言來說，常常希望它的文法是無二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語句的分析是唯一的二義文法到無二義文法可以將二義文法改造為無二義文法例：將左邊的文法改造為右邊的文法，便可消除二義原因分析：通過規(guī)定運(yùn)算符的優(yōu)先性和結(jié)合性來消除二義G[E]：E→iE→E+EE→E*EE→(E)G[E]：E→T|E+TT→T|T*FF→(E)|i上下文無關(guān)文法的句型分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束句型分析方法分類主要有下面兩類：自上而下分析法它從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)自下而上分析法從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)兩種方法反映了兩種語法樹的構(gòu)造過程自上而下方法從文法符號(hào)開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果(通過從左往右遍歷語法樹而得到)正好是輸入符號(hào)串自下而上方法則是從輸入符號(hào)串開始，以它做為語法樹的結(jié)果，自底向上的構(gòu)造語法樹自上而下的語法分析例，文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子 S S S

c A d

c A d

a

b推導(dǎo)過程：S

cAd

cAd

cabd自下而上的語法分析例，文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否該文法的句子 S

A

A

cabd

ca

bd

ca

b

d

規(guī)約過程構(gòu)造的推導(dǎo)：cAd

cabdScAd自上而下的語法分析前述的方法會(huì)否碰到問題？對(duì)文法G:(1)S→cAd(2)A→ab(3)A→a

識(shí)別輸入串w=cad是否為該文法的句子從S出發(fā)得到S→cAd，下面對(duì)A有兩條規(guī)則能用，用那條？這里使用第二條A→ab，那么S→cabd，得不到所要識(shí)別的句子，此時(shí)能否宣告分析失?。涸摼渥訜o法識(shí)別？不能，因?yàn)閾Q作第三條便可問題的解決對(duì)于前面的問題，可按右面的方法解決ScAdab這時(shí)應(yīng)該回朔，把A為根的子樹剪掉，掃描過的輸入串中的a吐出來,再試探用產(chǎn)生式(3)自下而上的文法分析對(duì)前面文法(1)S→cAd(2)A→ab(3)A→a

采用自下而