形式語言概論

形式語言概論第1頁，共41頁，2023年，2月20日，星期四形式語言理論：是指由數(shù)學(xué)方法研究自然語言和人工語言(程序設(shè)計語言)之語法理論，主要討論了語言和文法的數(shù)學(xué)機(jī)制以及語言和文法的分類。第2頁，共41頁，2023年，2月20日，星期四文法的直觀概念

如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在如何給出它的有窮表示的問題。雖然無法列出全部句子，但是可以給出一些規(guī)則，用這些規(guī)則來說明句子的組成結(jié)構(gòu)，然后用它們?nèi)ネ茖?dǎo)產(chǎn)生句子。文法：是闡述語法的一個工具

第3頁，共41頁，2023年，2月20日，星期四“你是大學(xué)生”對“我是教師”對“我大學(xué)生是”錯“我學(xué)習(xí)大學(xué)生”對〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉|〈名詞〉〈代詞〉∷=我|你|他〈名詞〉∷=王明|大學(xué)生|教師|英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是|學(xué)習(xí)〈直接賓語〉∷=〈代詞〉|<名詞>

〈句子〉〈主語〉〈謂語〉

〈代詞〉〈謂語〉我〈謂語〉我〈動詞〉〈直接賓語〉我是〈名詞〉我是教師推導(dǎo)：我是教師

巴科斯-瑙爾范式(EBNF)第4頁，共41頁，2023年，2月20日，星期四例如，描述標(biāo)識符的文法如下：<標(biāo)識符>::=<字母><標(biāo)識符>::=<標(biāo)識符><字母><標(biāo)識符>::=<標(biāo)識符><數(shù)字><字母>::=a|b|c|d|…|z<數(shù)字>::=0|1|2|3|4|5|6|7|8|9第5頁，共41頁，2023年，2月20日，星期四字母表和符號串

字母表：是元素的非空有窮集合，用表示。字母表中的元素稱為符號。

例如：漢語的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號等。PASCAL語言的字母表是由字母、數(shù)字、算符、保留字等組成。

符號串的長度：符號串中符號的個數(shù)。符號串x的長度記為|x|。如|ab012|=5?？辗柎翰缓魏畏柕姆柎?，記為ε。|ε|=0。符號串：符號的有窮序列稱為符號串，如compiler,string等。第6頁，共41頁，2023年，2月20日，星期四符號串的連接：設(shè)x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。

如:x=ab、y=123，則xy=ab123。顯然，εx=xε=x。符號串集合的乘積：兩個符號串集合A和B的乘積定義為：AB={xy|x∈A且y∈B}。特別地{ε}A=A{ε}=A。如:A={ab,c},B={d,efg},則AB={abd,abefg,cd,cefg}。符號串的方冪：設(shè)x為符號串，則xn=xx…x(x連接n次)。特別有x0=ε。符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。符號串集合的方冪：同一符號串集合的乘積。如:A={a,bc},則A2={aa,abc,bca,bcbc}A3=A2A=?第7頁，共41頁，2023年，2月20日，星期四符號串集合的正閉包:

符號串集合A正閉包A+=A1A2….An….即A+為集合A上所有符號串的集合。符號串集合的自反閉包:

符號串集合A正閉包A*={}A+=A+{}顯然有A+=AA*=A*A第8頁，共41頁，2023年，2月20日，星期四文法產(chǎn)生式：

設(shè)VN,VT分別是非空有限的非終結(jié)符號集和終結(jié)符號集，令V=VNVT,VNVT=，一個產(chǎn)生式是一般形式為：A->

，其中AVN,

V*，，A稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部。

->表示為定義為…

如果產(chǎn)生式集合中的產(chǎn)生式有共同的左部，如:A->，A->

，則可將其簡寫為：A->

|

。變量表符號表第9頁，共41頁，2023年，2月20日，星期四文法：文法G定義為四元組(VN,VT,P,S)。其中：

VN：非終結(jié)符號集。非終結(jié)符號代表某一類的記號，如“算術(shù)表達(dá)式”、“賦值句”等等。

VT：終結(jié)符號集。終結(jié)符號代表不可再分的基本符號，如保留字、標(biāo)識符、常數(shù)、運(yùn)算符、界符等。

VN∩VT=Φ；V=VN∪VT稱為文法G的詞匯表。

S：開始符號。開始符號是一個特殊的非終結(jié)符號，表示文法G所定義的最終的語法范疇。

P：產(chǎn)生式的集合。產(chǎn)生式是定義語法范疇的一種書寫格式，形式如下：α→β

其中，α稱為產(chǎn)生式左部，它必須是非終結(jié)符；β稱為產(chǎn)生式右部，它可以是終結(jié)符、非終結(jié)符或他們的組合。第10頁，共41頁，2023年，2月20日，星期四例1：文法G=（VN，VT，P，S）

VN={標(biāo)識符，字母，數(shù)字} VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識符>→<字母> <標(biāo)識符>→<標(biāo)識符><字母> <標(biāo)識符>→<標(biāo)識符><數(shù)字> <字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9} S=<標(biāo)識符>習(xí)慣上只將產(chǎn)生式寫出。并有如下約定：1、第一條產(chǎn)生式的左部是開始符號；2、用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符；3、G可寫成G[S]，其中S是開始符號；文法例子

第11頁，共41頁，2023年，2月20日，星期四例2：無符號二進(jìn)制數(shù)的描述文法

G=(VN,VT,P,B) VN={B，Bi} VT={0,1,.} P={

B→Bi|Bi

.Bi

Bi→0|1|Bi

0|Bi

1 }第12頁，共41頁，2023年，2月20日，星期四例3：設(shè)E代表“算術(shù)表達(dá)式”；i代表單個變量或常數(shù)；+、*、（、）是構(gòu)成算術(shù)表達(dá)式的運(yùn)算符和括號。定義由前面符號組成的單個變量或常量組成的算術(shù)表達(dá)式；若E是一個算術(shù)表達(dá)式，則E+E,E*E,(E)也是算術(shù)表達(dá)式，寫成文法形式：

G=(VN,VT,P,S) VN={E}VT={i,+,*,(,)}

P={E→i,

E→E+E,E→E*E,E→(E)}思考：(i+i)是不是該文法定義的表達(dá)式？第13頁，共41頁，2023年，2月20日，星期四文法的類型：語言學(xué)家喬姆斯基(Chomsky)把文法分成以下四種類型：0型短語文法1型上下文有關(guān)文法2型上下文無關(guān)文法3型正規(guī)文法文法類型逐漸增加限制第14頁，共41頁，2023年，2月20日，星期四0型文法：對任一產(chǎn)生式α→β，都有α(VN∪VT)+，β(VN∪VT)*

。α至少含有一個非終結(jié)符。1型文法（上下有關(guān)文法)：對任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外。1型文法又稱為上下文有關(guān)文法，(CSGcontextsensitivegrammar)它具有如下形式:α→β，除有可能S→ε外，均有

α=γ1Aγ2β=γ1δγ2,其中γ1,γ2

(VN∪VT)*,AVN,,δ(VN∪VT)+,只有A出現(xiàn)在γ1,γ2的上下文中，才允許用δ取代A(即A→δ)。1型文法中,1<=|α|<=|β|1型文法例：G=（VN,VT，P，S），其中VN={S,B,C}，VT={a,b,c}，P={S→aSBC,S→abC,CB→BC,bB→bb,bC→bc,cC→cc}

S=>aabCBC=>aabBCC=>aabbCC=>aabbcC=>aabbccCB→CACA→BABA→BC思考：符號串：aabbcc是不是上述文法定義的?第15頁，共41頁，2023年，2月20日，星期四2型文法（上下無關(guān)文法-CFG）：除有可能S→ε,對任一產(chǎn)生式A→δ，都有AVN

，δ

(VN∪VT)+。2型文法左邊是單個非終結(jié)符，右邊是由終結(jié)符和非終結(jié)符組成的符號串。上下無關(guān)文法也稱CFG文法(ContextFreeGrammar)2型文法例1：G=（VN，VT，P，S），其中VN={S，T}，VT={a，b，c,d}，P={S→aTd,T→bT|cT|b|c}2型文法例2：G=（VN，VT，P，S），其中VN={S}，VT={0，1}，P={S→0S1,S→01}第16頁，共41頁，2023年，2月20日，星期四3型文法（正規(guī)文法）：除S→ε外,所有產(chǎn)生式α→β的形式都為

A→aB或A→a，其中AVN

，BVN

，aVT。正規(guī)文法是CFG文法的一個子集正規(guī)文法例：G=（VN，VT，P，A），其中VN={A,B,C,D}，VT={x,y,z}，P={A→xB|yC,B→zB|y|yC,C→xD,D→yD|x}若則稱右線型文法第17頁，共41頁，2023年，2月20日，星期四直接推導(dǎo)(定義2.3)

：

設(shè)文法G=（VN,VT,P,S），A→α是文法G的產(chǎn)生式，若有γ,δ∈V*，使得U=γAδ,w=γαδ,則說：U（應(yīng)用規(guī)則A→α）直接產(chǎn)生w或說：w是U的直接推導(dǎo)

或說：w直接歸約到U

記作

Uw。特別地，當(dāng)γ=δ=ε時，A

α例4：

文法G[S]：S→0S1，S→01，其中VN=S,VT={0,1}直接推導(dǎo)：0S10011（U=0S1，w=0011，使用規(guī)則S→01，γ=0，δ=1）S0S1（U=S，w=0S1，使用規(guī)則S→0S1，γ=ε，δ=ε）0S100S11（U=0S1，w=00S11，使用規(guī)則S→0S1，γ=0，δ=1）第18頁，共41頁，2023年，2月20日，星期四推導(dǎo)(定義2.4)

：

存在v=0=>1=>…=>n=w,(n>0)

則稱w為v的一個推導(dǎo)，記為vu。

另使用(定義2.5)

vu表示v

u或

v=u前面例子G=(VN,VT,P,S)VN={E}VT={i,+,*,(,)} P={E→i,

E→E+E,E→E*E,E→(E)}由E→(E)，E=>(E)再由E→E+E，(E)=>(E+E)再使用E→(E)，(E+E)=>(i+E)=>(i+i)證明(i+i)是文法G的一個算術(shù)表達(dá)式(由終結(jié)符組成)。v推導(dǎo)出ww規(guī)約到v第19頁，共41頁，2023年，2月20日，星期四最左推導(dǎo)定義2.9

在xUy=>xuy直接推導(dǎo)中，若xVT*,UVN,即U是符號串xUy中最左非終結(jié)符，則稱此直接推導(dǎo)為最左直接推導(dǎo)。若一個推導(dǎo)的每一步直接推導(dǎo)都是最左直接推導(dǎo)，那么此推導(dǎo)稱為最左推導(dǎo)。例G12[<標(biāo)識符>]：<標(biāo)識符>→<字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><字母>→a|b|c|…|x|y|z<數(shù)字>→0|1|2|3|4|5|6|7|8|9<標(biāo)識符><標(biāo)識符><數(shù)字><標(biāo)識符><數(shù)字><數(shù)字><字母><數(shù)字><數(shù)字>a<數(shù)字><數(shù)字>a6<數(shù)字>a69

第20頁，共41頁，2023年，2月20日，星期四最右推導(dǎo)

定義2.10

在xUy=>xuy直接推導(dǎo)中，若yVT*,UVN,即U是符號串xUy中最右非終結(jié)符，則稱此直接推導(dǎo)為最右直接推導(dǎo)。若一個推導(dǎo)的每一步直接推導(dǎo)都是最右直接推導(dǎo)，那么此推導(dǎo)稱為最右推導(dǎo)。最右直接推導(dǎo)又稱為規(guī)范直接推導(dǎo)，最右推導(dǎo)又稱為規(guī)范推導(dǎo)。例文法如G12.<標(biāo)識符><標(biāo)識符><數(shù)字><標(biāo)識符>9<標(biāo)識符><數(shù)字>9<標(biāo)識符>69<字母>69a69第21頁，共41頁，2023年，2月20日，星期四句型、句子和語言

定義2.6

如果符號串x是從識別符號推導(dǎo)出來的，即Sx，則稱x是文法G[S]的句型。開始符號S也是文法G的句型。

定義2.7

如果符號串x是終結(jié)符號構(gòu)成，即Sx，xVT*，則稱x是文法G[S]的句子。

定義2.8

設(shè)S是文法G的開始符號，文法G的語言L(G)={u|S+u,uVT*}，即文法的語言是文法的所有句子構(gòu)成的集合。

例4中文法：

S，0S1，000111都是文法G的句型，000111是G的句子?！冀Y(jié)論〗句子一定是句型，句型不一定是句子。區(qū)別第22頁，共41頁，2023年，2月20日，星期四例:文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

P={S→0S1，S→01}表示什么語言？答案：L(G)＝｛0n1n

n1｝因為S0S100S11…0n1n重復(fù)利用規(guī)則S0S1例：證明(i*i+i)是文法G(E)：Ei|E+E|E*E|(E)的一個句子。證明：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，…，(i*i+i)是句型。第23頁，共41頁，2023年，2月20日，星期四表示語言表示語言有文法推出語言

文法G[N]為：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？表示語言G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9}G[N]的語言是G(N)={(0|1|2|3|4|5|6|7|8|9)n|n>=1}√第24頁，共41頁，2023年，2月20日，星期四有語言推出文法文法為SABCA

aA|aB

bB|bC

cC|c文法為文法為SaS|aAA

bA|bBB

cB|c

習(xí)題二2.2(4)若i,j,k>=0文法變成？第25頁，共41頁，2023年，2月20日，星期四文法為更巧妙文法為第26頁，共41頁，2023年，2月20日，星期四習(xí)題二2.2(6)能被5整除的整數(shù)集合的文法

E→N0|N5N→ε|DD→0|2|3|4|5|6|7|8|9

N第27頁，共41頁，2023年，2月20日，星期四(1)允許0開頭的偶正整數(shù)集合的文法

E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允許0開頭的偶正整數(shù)集合的文法

E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第28頁，共41頁，2023年，2月20日，星期四文法的化簡第29頁，共41頁，2023年，2月20日，星期四化簡文法例：G[S] 1)S→Be 2)B→Ce 3)B→Af4)A→Ae 5)A→e 6)C→Cf 7)D→fS→BeB→AfA→AeA→e第30頁，共41頁，2023年，2月20日，星期四文法和語言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）第31頁，共41頁，2023年，2月20日，星期四語法樹

設(shè)文法G=（VN,VT,P,S），對于文法G的任意一個句型都存在一個相應(yīng)的語法樹：

樹中每個結(jié)點(diǎn)都有一個標(biāo)記，該標(biāo)記是VNVT中的一個符號；

樹的根結(jié)點(diǎn)標(biāo)記是文法的識別符號S；

若樹的一個結(jié)點(diǎn)至少有一個葉子結(jié)點(diǎn)，則該結(jié)點(diǎn)的標(biāo)記一定是一個非終結(jié)符；若樹的一個結(jié)點(diǎn)有多個葉結(jié)點(diǎn)，該結(jié)點(diǎn)的標(biāo)記為A，這些葉結(jié)點(diǎn)的標(biāo)記從左到右分別是B1，B2，….，Bn，則AB1B2…BnP文法的句型都可依據(jù)其產(chǎn)生式來生成相應(yīng)的語法樹。第32頁，共41頁，2023年，2月20日，星期四問題：一個句型是否對應(yīng)唯一的一棵語法樹？例：G[Z]:

Z→aZb Z→Z Z→abZaZbab

ZaZbZab句型aabb的語法樹第33頁，共41頁，2023年，2月20日，星期四句型(i*i+i)的語法樹E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)文法G(E)：Ei|E+E|E*E|(E)第34頁，共41頁，2023年，2月20日，星期四ET

F

(E)

(E+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)

(i*i+F)

(i*i+i))EEEFFTTTTi+*(EFii

改寫為無二義文法:G(E)：EE+EE

E*EE

(E)EiG[E]: E→E+T|T T→T*F|F F→(E)|i第35頁，共41頁，2023年，2月20日，星期四上下文無關(guān)文法的語法樹

例:G[S]: E→E+T|T T→T*F|F F→(E)|iEE+TT*F(E)iE+T句型E+(E+T)*i的語法樹葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹的葉子標(biāo)記，所得的句型為推導(dǎo)樹的結(jié)果。也把該推導(dǎo)樹稱為該句型的語法樹。第36頁，共41頁，2023年，2月20日，星期四產(chǎn)生式樹

例:G[S]:E→E+T|T,T→T*F|F,F→(E)|iE+ETE+ET*TFE+ET*TFiE+ET*TFiFE+ET*TFiFE()E