第二章 形式語(yǔ)言理論

第二章形式語(yǔ)言概論語(yǔ)言成分語(yǔ)言和文法文法的分類語(yǔ)言和語(yǔ)法文法和語(yǔ)言的一些特性分析方法簡(jiǎn)介2.1語(yǔ)言成分

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

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

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

由字母表中的符號(hào)組成的任何有窮序列。

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

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

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

例如：x=ST，y=abu

，則xy=STabu

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

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

a0=ε3.符號(hào)串集合的乘積若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。符號(hào)串集合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.符號(hào)串集合的方冪

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

例如：X={abc}X0

＝{

}，X1

＝{abc}，X2

＝{abcabc}5.符號(hào)串集合的正閉包

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

+

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

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

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

Σ*表示Σ上所有有窮長(zhǎng)的串的集合。

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

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

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

求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文法和語(yǔ)言1.文法的定義是定義或描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的一組形式規(guī)則。文法G（Grammar）定義為四元組（VN，VT，P，S）

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

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

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

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

其中A∈VN且至少含一個(gè)非終結(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)生式的左部的過(guò)程。直接歸約：用產(chǎn)生式的左部替換產(chǎn)生式的右部的過(guò)程。直接推導(dǎo)序列：

或+

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

則稱v

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

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

+

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

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

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

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

α→β

其中α∈V+，β∈V*，則該文法G為0型文法。相應(yīng)的語(yǔ)言稱為0型語(yǔ)言。例如：文法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型語(yǔ)言為L(zhǎng)0(G[S])={}1.0型文法2.1型文法(上下文有關(guān))

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

αAβαμβ

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

P={

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

描述的1型語(yǔ)言為L(zhǎng)1(G[S])={anbncn|n1}3.2型文法(上下文無(wú)關(guān))

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

Aβ

其中AVN,β(VN∪VT)*,則該文法G為2型文法。相應(yīng)的語(yǔ)言稱為2型語(yǔ)言。例如：文法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型語(yǔ)言為L(zhǎng)2(G[S])={x|x{a,b}+

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

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

Aa或

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

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

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

或

A→a，A,B∈VN

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

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

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

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

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

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

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

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

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

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

…0n-1S1n-1

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

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

例如：TheyarestudentsandteachersofthePhysicsDepartment.

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

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

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

A→ab,B→cd符號(hào)串a(chǎn)bccdd的推導(dǎo)過(guò)程如下：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)過(guò)程與語(yǔ)法樹(shù)。EET+TFT×E=>E+T

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

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

有害規(guī)則：U→U，無(wú)用且引起文法的二義?？煽辗墙K結(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)：是指對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)α=>β，都對(duì)α中的最左非終結(jié)符進(jìn)行替換。

最右推導(dǎo)：是指對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)α=>β，都對(duì)α中的最右非終結(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

對(duì)應(yīng)的語(yǔ)法樹(shù)最左推導(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)

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