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

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

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

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

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

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

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

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

例如：x=ST，y=abu

，則xy=STabu

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

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.符號串集合的方冪

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

例如：X={abc}X0

＝{

}，X1

＝{abc}，X2

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

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

+

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

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

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

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

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

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

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

求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.文法的定義是定義或描述語言的語法結構的一組形式規則。文法G（Grammar）定義為四元組（VN，VT，P，S）

VN(Nonternimal)：非終結符集。

VT(Terminal)：終結符集。

P(Production)：產生式（規則）集合。

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

其中A∈VN且至少含一個非終結符，α,β∈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.推導和直接推導

α→β是文法G的產生式，若有v，w滿足：

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

或+

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

則稱v

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

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

+

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

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

0型語言或短語結構語言。1型文法（CSG）：1型語言或上下文有關語言。2型文法（CFG）：2型語言或上下文無關語言。3型文法（RG）：3型語言或正則（正規）語言。

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

α→β

其中α∈V+，β∈V*，則該文法G為0型文法。相應的語言稱為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型文法(上下文有關)

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

αAβαμβ

其中AVN,α,β(VN∪VT)*,μ(VN∪VT)+，則該文法G為1型文法。相應的語言稱為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型文法(上下文無關)

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

Aβ

其中AVN,β(VN∪VT)*,則該文法G為2型文法。相應的語言稱為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的個數相同}4.3型文法(右線性文法和正規文法)

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

Aa或

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

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

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

或

A→a，A,B∈VN

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

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

2型文法：規則左部是單個非終結符；

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

，且α∈V*，則稱α是文法G的句型。若α僅由終結符組成,即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生成的每個終結符號串都在L(G)中，L(G)中的每個串確實能被G生成。文法一旦確定，語言也就唯一，語言可由不同的文法表示。2.語法樹

例如：TheyarestudentsandteachersofthePhysicsDepartment.

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

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

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

A→ab,B→cd符號串abccdd的推導過程如下：SABAcBdAccddabccddSBBdbaAcdcS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）SABAcBdAccddabccdd例4：已知文法G：E→E+T|T，T→T×F|F，F→（E）|i

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

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

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

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

2型文法允許以下產生式

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

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

（2） B→Af

（3）A→Ae

（4）A→e

（5）C→Cf

（6）D→f

多余規則為：（5）不可終止（6）不可到達最左推導、最右推導和規范推導

最左推導：是指對于一個推導序列中的每一步直接推導α=>β，都對α中的最左非終結符進行替換。

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

求句子101001的最右、最左推導。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

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

如果一個文法存在某個句子對應兩棵或者兩棵以上不同的語法樹，則說這個文法是二義的。二義性文法存在某個句子,它有兩個不同的最左（右）推導。二義性的文法將給編譯程序的執行帶來問題。當編譯程序對二義性文法生成的句子結構進行語法分析時，就會產生兩種甚至更多種不同的理解。語法結構上的不確定性，必將導致語義處