第二章 形式語言理論

第二章形式語言概論語言成分語言和文法文法的分類語言和語法文法和語言的一些特性分析方法簡介2.1語言成分

對程序設(shè)計語言的描述是從語法、語義和語用三個因素來考慮。語法：是對語言結(jié)構(gòu)的定義。語義：是描述了語言的含義。語用：則是從使用的角度去描述語言。例1：寫出賦值語句s＝2*3.1416*r*(r+h)的非形式化的描述。語法：賦值語句由一個變量，后隨一個賦值號“＝”，其后面再跟一個表達(dá)式構(gòu)成；語義：首先計算語句右部表達(dá)式的值，然后把所得結(jié)果送給左部變量中；語用：賦值語句可用來計算和保存表達(dá)式的值。

用一組數(shù)學(xué)符號和規(guī)則來描述語言的方式稱為形式描述，而把所用的數(shù)學(xué)符號和規(guī)則稱為形式語言。形式語言：只是從語法上研究語言。它是抽象的數(shù)學(xué)系統(tǒng)，用于模擬程序設(shè)計語言的語法，或者是并不很成功地模擬自然語言（如英語的語法）。形式語言理論是編譯理論的重要基礎(chǔ)，它主要研究組成符號語言的符號串的集合及它們的表示法、結(jié)構(gòu)與特性。形式語言字母表和符號字母表:元素的非空有窮集合，記為∑。

例如：∑={0?1}∑1={a?b,c}字母表中至少包含一個元素。字母表中的元素，可以是字母、數(shù)字或其他符號。不同的語言有不同的字母表。符號:字母表中的元素稱為符號或字符。

由字母表中的符號組成的任何有窮序列。

例如：0,00,10是字母表∑={0?1}上的符號串

a,ab,aaca是∑1={a?b,c}上的符號串符號串中的符號是有序的，順序不同,意義不同。例如:ab和ba不同不含任何符號的符號串稱為空串，用ε表示。符號串長度:符號串中含有符號的個數(shù)。

例如:|abc|=3 |ε|=0符號串及其運算1.符號串的連接設(shè)x、y是符號串,它們的連接是把y的符號寫在x的符號之后得到的符號串xy。

例如：x=ST，y=abu

，則xy=STabu

顯然εx=xε=x2.符號串的方冪把符號串a(chǎn)自身連接n次得到的符號串a(chǎn)n=

aa…aa。例如：a1=aa2=aa

a0=ε3.符號串集合的乘積若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。符號串集合A和B的乘積定義為:AB={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y連接而成的串xy組成的集合。

例如：集合A=ab,cdeB=0,1

則AB=ab0,ab1,cde0,cde1

顯然{ε}A=A{ε}=A注意:{ε}并不等于空集合{}4.符號串集合的方冪

設(shè)A是符號串的集合，則稱An為符號串集A的方冪，其中n是非負(fù)整數(shù)。A0={ε}A1=AA2=AAAn=AA......A(n個)

例如：X={abc}X0

＝{

}，X1

＝{abc}，X2

＝{abcabc}5.符號串集合的正閉包

Σ+=Σ1∪Σ2∪Σ3∪…稱為Σ的正閉包。

+

表示上的除ε外的所有有窮長串的集合。例如：設(shè)A={a,b}，則：

A+={a,b,aa,ab,ba,bb,aaa,aab,…}6.符號串集合的自反閉包

Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…稱為Σ的自反閉包。

Σ*表示Σ上所有有窮長的串的集合。

例如：設(shè)有字母表Σ={0，1}，則

Σ*={ε,0,1,00,01,10,11,000,…}自反閉包與正閉包的關(guān)系

Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ例2：已知：字母表={a，b，c，d}，符號串x=ad，y=ac，集合A={ad，c}，B=gi51vnj

求xy，AB，x0，y3，A2，B0，A+，A*xy=adacAB={add，cd}x0=εy3=yyy=acacacA2=AA={adad，adc，cad，cc}B0={ε}A+=A1∪A2∪A3∪…..A*=A0∪

A1∪A2∪A3∪…..2.2文法和語言1.文法的定義是定義或描述語言的語法結(jié)構(gòu)的一組形式規(guī)則。文法G（Grammar）定義為四元組（VN，VT，P，S）

VN(Nonternimal)：非終結(jié)符集。

VT(Terminal)：終結(jié)符集。

P(Production)：產(chǎn)生式（規(guī)則）集合。

S：開始符號或識別符號。是出現(xiàn)在規(guī)則左部能派生出符號或符號串的那些符號，即每個非終結(jié)符號表示一定符號串的集合，用大寫字母表示或用尖括號把非終結(jié)符號括起來。是組成語言的基本符號，是一個語言的不可再分的基本符號，通常用小寫字母表示。是一個非終結(jié)符，且至少要在一條產(chǎn)生式的左部出現(xiàn)。P中產(chǎn)生式（重寫規(guī)則）形如：A→α|β

其中A∈VN且至少含一個非終結(jié)符，α,β∈V*。VN,VT和P是非空有窮集。VN∩VT=φ。V=VN∪VT，V稱為文法G的字母表。例如：文法G=(VN，VT，P，S)VN={A}VT={0，1}P:A→0|1|A0|A1S=A2.推導(dǎo)和直接推導(dǎo)

α→β是文法G的產(chǎn)生式，若有v，w滿足：

v=γαδ,w=γβδ,其中γ,δ∈V*則稱v直接推導(dǎo)出w，或w直接歸約到v，記作vw。直接推導(dǎo)：用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程。直接歸約：用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程。直接推導(dǎo)序列：

或+

若存在v=u0u1...un=w,(n>0)

則稱v

w，v推導(dǎo)出w，或w歸約到v（至少有1步推導(dǎo)），這個直接推導(dǎo)序列的長度為n。廣義推導(dǎo)：或*

若有vw或v=w，則記為vw，v廣義推導(dǎo)出w，w廣義規(guī)約到v（可以包含0步推導(dǎo)）。+*

+

+*三種推導(dǎo)的比較直接推導(dǎo)（）的長度為1。直接推導(dǎo)序列（+）的長度n≥1。廣義推導(dǎo)（*）的長度≥0。推導(dǎo)和規(guī)則的區(qū)別形式上的區(qū)別：推導(dǎo)用“”，規(guī)則用“”。對文法G中任何規(guī)則A，我們有A，即推導(dǎo)的依據(jù)是規(guī)則。2.3文法的分類

對文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法（PSG）：

0型語言或短語結(jié)構(gòu)語言。1型文法（CSG）：1型語言或上下文有關(guān)語言。2型文法（CFG）：2型語言或上下文無關(guān)語言。3型文法（RG）：3型語言或正則（正規(guī)）語言。

如果對于文法G，P中每個規(guī)則具有下列形式：

α→β

其中α∈V+，β∈V*，則該文法G為0型文法。相應(yīng)的語言稱為0型語言。例如：文法G=(VN,VT,P,S)，其中VN={A,B,S}VT={0,1}P={S→0AB，1B→0，B→SA|01，A1→SB1，A0→S0B}

描述的0型語言為L0(G[S])={}1.0型文法2.1型文法(上下文有關(guān))

若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為：

αAβαμβ

其中AVN,α,β(VN∪VT)*,μ(VN∪VT)+，則該文法G為1型文法。相應(yīng)的語言稱為1型語言。例如：文法G=(VN,VT,P,S)，其中VN={B,S}VT={a,b,c}

P={

S→abc|aSBc,bB→bb,cB→Bc }

描述的1型語言為L1(G[S])={anbncn|n1}3.2型文法(上下文無關(guān))

若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為：

Aβ

其中AVN,β(VN∪VT)*,則該文法G為2型文法。相應(yīng)的語言稱為2型語言。例如：文法G=(VN,VT,P,S)，其中VN={A,B,S}VT={a,b}

P={S→aB|bA,A→a|aS|bAA，B→b|bS|aBB}

描述的2型語言為L2(G[S])={x|x{a,b}+

且x中a和b的個數(shù)相同}4.3型文法(右線性文法和正規(guī)文法)

若文法G=(VN,VT,P,S)中的每一條規(guī)則的形式為：

Aa或

AaB其中A，BVN,aVT*,則該文法G為3型文法。相應(yīng)的語言稱為3型語言。例如：定義標(biāo)識符，用I代表標(biāo)識符;l代表任意一個字母;d代表任意一個數(shù)字;則定義標(biāo)識符的文法為：

P:I→l|lI|dI文法類別產(chǎn)生式形式產(chǎn)生的語言說明0型文法(短語文法)α→βα∈V+,且至少含一個非終結(jié)符，β∈V*0型語言對產(chǎn)生式基本無限制1型文法(上下文有關(guān)文法)α→β，|β|≥|α|α=r1Ar2，β=r1br2A∈VN,α,β∈V*b∈V+1型語言（上下文有關(guān)語言）將A替換成b時，必須考慮A的上下文2型文法(上下文無關(guān)文法)A→β，A∈VN

，β∈V*2型語言（上下文無關(guān)語言）無需考慮A在上下文中的出現(xiàn)情況3型文法(右線性文法)A→aB

或

A→a，A,B∈VN

，a∈VT*3型語言產(chǎn)生式全部是規(guī)定形式4種文法的比較a∈VT，正規(guī)文法例3：試分析書中P22的例2.6、2.7、2.8、2.9、2.10的文法。如何判斷4種文法

1型文法：|β|≥|α|≥1，規(guī)則左部至少有一個非終結(jié)符；

2型文法：規(guī)則左部是單個非終結(jié)符；

3型文法：看格式。練習(xí)：設(shè)有文法G[A]:A→yB，B→xB|x，寫出該文法的完整形式及推導(dǎo)。設(shè)有文法G[A1]:S→AB，A→aA|a，B→bB|b，寫出該文法的完整形式及推導(dǎo)。2.4．語言和語法1.句型、句子和語言設(shè)有文法G[S]，若符號串α是從開始符推導(dǎo)出來的,即S=>*α

，且α∈V*，則稱α是文法G的句型。若α僅由終結(jié)符組成,即S=>*α

，且α∈VT*，則稱α是文法G的句子。

所有的句子一定是句型，句型不一定是句子。例如：文法G[S]：S→0S1，S→01S0S100S11000S11100001111

句型：S，0S1，00S11，000S111，00001111

句子：00001111語言：由文法G生成的語言記為L(G),它是文法G的一切句子的集合,即 L(G)={x|S

=>+x，且x∈VT*}例如：文法G：S→0S1，S→01S0S100S1103S13

…0n-1S1n-1

0n1nL(G)={0n1n|n≥1}

文法G生成的每個終結(jié)符號串都在L(G)中，L(G)中的每個串確實能被G生成。文法一旦確定，語言也就唯一，語言可由不同的文法表示。2.語法樹

例如：TheyarestudentsandteachersofthePhysicsDepartment.

它的結(jié)點由符號組成。根結(jié)點對應(yīng)于開始符號。只有非終結(jié)符號對應(yīng)的結(jié)點有子結(jié)點。并且，一個結(jié)點和它的子結(jié)點分別對應(yīng)于文法中的一個產(chǎn)生式的左部和右部。作為識別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。語法樹的相關(guān)概念

結(jié)點：每個樹的結(jié)點對應(yīng)于一個符號。結(jié)點的名字就是該符號。邊：兩個結(jié)點之間的連線。根結(jié)點：沒有邊進(jìn)入的結(jié)點。分支：某個結(jié)點向下射出的邊和其結(jié)點稱為分支。末端結(jié)點：沒有向下射出的邊的結(jié)點成為末端結(jié)點。在相對于句型的語法樹中，末端結(jié)點可能是非終結(jié)符號。語法樹的特征

給定文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：根結(jié)點的標(biāo)記是開始符號S；每個結(jié)點的標(biāo)記都是V中的一個符號；若一棵子樹的根結(jié)點為A，且其所有直接子孫的標(biāo)記從左向右的排列次序為A1A2…AR，那么A→A1A2..AR一定是P中的一條規(guī)則；若一標(biāo)記為A的結(jié)點至少有一個除它以外的子孫，則A∈VN。構(gòu)造語法樹方法：把開始符號做為根結(jié)點，對每一步直接推導(dǎo)畫一個分支，分支的名字是所用產(chǎn)生式右部的符號（按左右順序依次出現(xiàn)），分支的個數(shù)是產(chǎn)生式右部符號串的長度。以此往下，直到再無分支可畫結(jié)束。例如：文法G[S]:S→AB,B→cBd,

A→ab,B→cd符號串a(chǎn)bccdd的推導(dǎo)過程如下：SABAcBdAccddabccddSBBdbaAcdcS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）SABAcBdAccddabccdd例4：已知文法G：E→E+T|T，T→T×F|F，F(xiàn)→（E）|i

求句型T+T×F的推導(dǎo)過程與語法樹。EET+TFT×E=>E+T

=>T+T=>T+T×FEET+TFT×E=>E+T=>E+T×F=>T+T×F從語法樹中看不出句型中的符號被替代的順序。2.5文法和語言的一些特性

無用非終結(jié)符：某個非終結(jié)符不出現(xiàn)在文法的任何一個句型中，并且不能從它推出終結(jié)符號串。含有該非終結(jié)符的規(guī)則即不可終止。不可達(dá)文法符號：如果一個非終結(jié)符（開始符號除外）不出現(xiàn)在該文法的任何其他的產(chǎn)生式的右部。該非終結(jié)符為不可達(dá)文法符號，含有該非終結(jié)符的規(guī)則即不可達(dá)規(guī)則。

有害規(guī)則：U→U，無用且引起文法的二義。可空非終結(jié)符：

2型文法允許以下產(chǎn)生式

S→ε，該產(chǎn)生式稱為空產(chǎn)生式，S稱為可空非終結(jié)符。在消除左遞歸方法中用到空產(chǎn)生式。

例如：文法G[S]：（1）S→Be

（2） B→Af

（3）A→Ae

（4）A→e

（5）C→Cf

（6）D→f

多余規(guī)則為：（5）不可終止（6）不可到達(dá)最左推導(dǎo)、最右推導(dǎo)和規(guī)范推導(dǎo)

最左推導(dǎo)：是指對于一個推導(dǎo)序列中的每一步直接推導(dǎo)α=>β，都對α中的最左非終結(jié)符進(jìn)行替換。

最右推導(dǎo)：是指對于一個推導(dǎo)序列中的每一步直接推導(dǎo)α=>β，都對α中的最右非終結(jié)符進(jìn)行替換。最右推導(dǎo)也稱為規(guī)范推導(dǎo)，用規(guī)范推導(dǎo)推導(dǎo)出的句型稱為規(guī)范句型。例5：已知文法G[S]：S→AB，A→A0|1B，B→0|S1

求句子101001的最右、最左推導(dǎo)。S右=>AB=>AS1=>AAB1=>AA01=>A1B01=>A1001=>1B1001=>101001S左=>AB=>1BB=>10B=>10S1=>10AB1=>101BB1=>1010B1=>101001例如：文法G：E→E+E|E×E|（E）|i

句子i×i+i

對應(yīng)的語法樹最左推導(dǎo)1：EE+EE×E+Ei×E+Ei×i+Ei×i+i最左推導(dǎo)2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii文法的二義性(Ambiguity)

如果一個文法存在某個句子對應(yīng)兩棵或者兩棵以上不同的語法樹，則說這個文法是二義的。二義性文法存在某個句子,它有兩個不同的最左（右）推導(dǎo)。二義性的文法將給編譯程序的執(zhí)行帶來問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處