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

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

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

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

由字母表中的符號組成的任何有窮的符號序列稱為符號串符號串及若干相關運算符號串的頭尾，固有頭和固有尾：

如果z=xy是一個符號串，那么稱x是z的頭，y是z的尾；如果x是非空的，那么y稱為固有尾；同樣，如果y非空，那么稱x是固有頭例，對于z=abc，那么z的頭是,a,ab,abc，除abc外，其他都是固有頭；z的尾是,c,bc,abc，z的固有尾是,c,bc求符號串長度：

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

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

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

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

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

元符號:→::=|<>

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

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

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

T→T*F|F

F→(E)|a

有推導EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a，等等通過觀察可以知道，上述文法定義的句子是用符號a，+，*，(以及)構成的算術表達式語言、文法和句子例，由文法G生成的語言記為L(G),它是文法G的一切句子的集合:L(G)={x|S*x，其中S為文法的開始符號，且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生成的每個串都在L(G)中L(G)中的每個串確實能被G生成文法的類型通過對產生式施加不同的限制，學者Chomsky將文法分為四種類型：0型文法：對任一產生式→，都有

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

3型文法：任一產生式→的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT*文法的類型例，下面是1型(上下文有關)文法文法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型(上下文無關)文法

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

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

a,對G中的形如D→tB的產生式,t為終結符或，有f(D,t)=Bb,對G中形如D→t的產生式，t為終結符或ε,有f(D,t)=Nc,對VT中的每一個a,有f(N,a)=φ從3型文法到有窮自動機從3型文法按前述方法可直接構造相應的有窮自動機G[S]：S→aA|bB

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

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

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

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

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

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

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

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

R=a(ad)上下文無關文法結論：

上下文無關文法有足夠的能力描述程序設計語言的語法結構以語法樹的形式給出句型推導直觀表示文法、推導、句型和句子設有文法G[E]：E→E+T|T

T→T*F|F

F→(E)|a

有下面的推導成立

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

aASSbAa

a

b

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

推導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：

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

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

A→ab

A→a

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

c A d

c A d

a

b推導過程：S

cAd

cAd

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

A→ab

A→a

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

A

A

cabd

ca

bd

ca

b

d

規(guī)約過程構造的推導：cAd

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

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

采用自下而