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

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

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

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

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

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

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

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

符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù)。符號(hào)串x的長(zhǎng)度記為|x|。如|ab012|=5?？辗?hào)串：不含任何符號(hào)的符號(hào)串，記為ε。|ε|=0。符號(hào)串：符號(hào)的有窮序列稱為符號(hào)串，如compiler,string等。第6頁，共41頁，2023年，2月20日，星期四符號(hào)串的連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。

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

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

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

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

，其中AVN,

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

->表示為定義為…

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

，則可將其簡(jiǎn)寫為：A->

|

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

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

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

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

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

第11頁，共41頁，2023年，2月20日，星期四例2：無符號(hào)二進(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代表單個(gè)變量或常數(shù)；+、*、（、）是構(gòu)成算術(shù)表達(dá)式的運(yùn)算符和括號(hào)。定義由前面符號(hào)組成的單個(gè)變量或常量組成的算術(shù)表達(dá)式；若E是一個(gè)算術(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型文法：對(duì)任一產(chǎn)生式α→β，都有α(VN∪VT)+，β(VN∪VT)*

。α至少含有一個(gè)非終結(jié)符。1型文法（上下有關(guān)文法)：對(duì)任一產(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思考：符號(hào)串：aabbcc是不是上述文法定義的?第15頁，共41頁，2023年，2月20日，星期四2型文法（上下無關(guān)文法-CFG）：除有可能S→ε,對(duì)任一產(chǎn)生式A→δ，都有AVN

，δ

(VN∪VT)+。2型文法左邊是單個(gè)非終結(jié)符，右邊是由終結(jié)符和非終結(jié)符組成的符號(hào)串。上下無關(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文法的一個(gè)子集正規(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)γ=δ=ε時(shí)，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的一個(gè)推導(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的一個(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是符號(hào)串xUy中最左非終結(jié)符，則稱此直接推導(dǎo)為最左直接推導(dǎo)。若一個(gè)推導(dǎo)的每一步直接推導(dǎo)都是最左直接推導(dǎo)，那么此推導(dǎo)稱為最左推導(dǎo)。例G12[<標(biāo)識(shí)符>]：<標(biāo)識(shí)符>→<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字><字母>→a|b|c|…|x|y|z<數(shù)字>→0|1|2|3|4|5|6|7|8|9<標(biāo)識(shí)符><標(biāo)識(shí)符><數(shù)字><標(biāo)識(shí)符><數(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是符號(hào)串xUy中最右非終結(jié)符，則稱此直接推導(dǎo)為最右直接推導(dǎo)。若一個(gè)推導(dǎo)的每一步直接推導(dǎo)都是最右直接推導(dǎo)，那么此推導(dǎo)稱為最右推導(dǎo)。最右直接推導(dǎo)又稱為規(guī)范直接推導(dǎo)，最右推導(dǎo)又稱為規(guī)范推導(dǎo)。例文法如G12.<標(biāo)識(shí)符><標(biāo)識(shí)符><數(shù)字><標(biāo)識(shí)符>9<標(biāo)識(shí)符><數(shù)字>9<標(biāo)識(shí)符>69<字母>69a69第21頁，共41頁，2023年，2月20日，星期四句型、句子和語言

定義2.6

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

定義2.7

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

定義2.8

設(shè)S是文法G的開始符號(hào)，文法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｝因?yàn)镾0S100S11…0n1n重復(fù)利用規(guī)則S0S1例：證明(i*i+i)是文法G(E)：Ei|E+E|E*E|(E)的一個(gè)句子。證明：

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日，星期四文法的化簡(jiǎn)第29頁，共41頁，2023年，2月20日，星期四化簡(jiǎn)文法例：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），對(duì)于文法G的任意一個(gè)句型都存在一個(gè)相應(yīng)的語法樹：

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

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

若樹的一個(gè)結(jié)點(diǎn)至少有一個(gè)葉子結(jié)點(diǎn)，則該結(jié)點(diǎn)的標(biāo)記一定是一個(gè)非終結(jié)符；若樹的一個(gè)結(jié)點(diǎn)有多個(gè)葉結(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日，星期四問題：一個(gè)句型是否對(duì)應(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