形式語言概論第一頁，共四十一頁，2022年，8月28日形式語言理論：是指由數(shù)學方法研究自然語言和人工語言(程序設計語言)之語法理論，主要討論了語言和文法的數(shù)學機制以及語言和文法的分類。第二頁，共四十一頁，2022年，8月28日文法的直觀概念

如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在如何給出它的有窮表示的問題。雖然無法列出全部句子，但是可以給出一些規(guī)則，用這些規(guī)則來說明句子的組成結構，然后用它們去推導產生句子。文法：是闡述語法的一個工具

第三頁，共四十一頁，2022年，8月28日“你是大學生”對“我是教師”對“我大學生是”錯“我學習大學生”對〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉|〈名詞〉〈代詞〉∷=我|你|他〈名詞〉∷=王明|大學生|教師|英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是|學習〈直接賓語〉∷=〈代詞〉|<名詞>

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

〈代詞〉〈謂語〉我〈謂語〉我〈動詞〉〈直接賓語〉我是〈名詞〉我是教師推導：我是教師

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

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

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

符號串的長度：符號串中符號的個數(shù)。符號串x的長度記為|x|。如|ab012|=5。空符號串：不含任何符號的符號串，記為ε。|ε|=0。符號串：符號的有窮序列稱為符號串，如compiler,string等。第六頁，共四十一頁，2022年，8月28日符號串的連接：設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}。符號串的方冪：設x為符號串，則xn=xx…x(x連接n次)。特別有x0=ε。符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。符號串集合的方冪：同一符號串集合的乘積。如:A={a,bc},則A2={aa,abc,bca,bcbc}A3=A2A=?第七頁，共四十一頁，2022年，8月28日符號串集合的正閉包:

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

符號串集合A正閉包A*={}A+=A+{}顯然有A+=AA*=A*A第八頁，共四十一頁，2022年，8月28日文法產生式：

設VN,VT分別是非空有限的非終結符號集和終結符號集，令V=VNVT,VNVT=，一個產生式是一般形式為：A->

，其中AVN,

V*，，A稱為產生式的左部，稱為產生式的右部。

->表示為定義為…

如果產生式集合中的產生式有共同的左部，如:A->，A->

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

|

。變量表符號表第九頁，共四十一頁，2022年，8月28日文法：文法G定義為四元組(VN,VT,P,S)。其中：

VN：非終結符號集。非終結符號代表某一類的記號，如“算術表達式”、“賦值句”等等。

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

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

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

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

其中，α稱為產生式左部，它必須是非終結符；β稱為產生式右部，它可以是終結符、非終結符或他們的組合。第十頁，共四十一頁，2022年，8月28日例1：文法G=（VN，VT，P，S）

VN={標識符，字母，數(shù)字} VT={a,b,c,…x,y,z,0,1,…,9} P={<標識符>→<字母> <標識符>→<標識符><字母> <標識符>→<標識符><數(shù)字> <字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9} S=<標識符>習慣上只將產生式寫出。并有如下約定：1、第一條產生式的左部是開始符號；2、用尖括號括起的是非終結符，否則為終結符。或者大寫字母表示非終結符，小寫字母表示終結符；3、G可寫成G[S]，其中S是開始符號；文法例子

第十一頁，共四十一頁，2022年，8月28日例2：無符號二進制數(shù)的描述文法

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

B→Bi|Bi

.Bi

Bi→0|1|Bi

0|Bi

1 }第十二頁，共四十一頁，2022年，8月28日例3：設E代表“算術表達式”；i代表單個變量或常數(shù)；+、*、（、）是構成算術表達式的運算符和括號。定義由前面符號組成的單個變量或常量組成的算術表達式；若E是一個算術表達式，則E+E,E*E,(E)也是算術表達式，寫成文法形式：

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

P={E→i,

E→E+E,E→E*E,E→(E)}思考：(i+i)是不是該文法定義的表達式？第十三頁，共四十一頁，2022年，8月28日文法的類型：語言學家喬姆斯基(Chomsky)把文法分成以下四種類型：0型短語文法1型上下文有關文法2型上下文無關文法3型正規(guī)文法文法類型逐漸增加限制第十四頁，共四十一頁，2022年，8月28日0型文法：對任一產生式α→β，都有α(VN∪VT)+，β(VN∪VT)*

。α至少含有一個非終結符。1型文法（上下有關文法)：對任一產生式α→β，都有|β|≥|α|，僅僅S→ε除外。1型文法又稱為上下文有關文法，(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是不是上述文法定義的?第十五頁，共四十一頁，2022年，8月28日2型文法（上下無關文法-CFG）：除有可能S→ε,對任一產生式A→δ，都有AVN

，δ

(VN∪VT)+。2型文法左邊是單個非終結符，右邊是由終結符和非終結符組成的符號串。上下無關文法也稱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}第十六頁，共四十一頁，2022年，8月28日3型文法（正規(guī)文法）：除S→ε外,所有產生式α→β的形式都為

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}若則稱右線型文法第十七頁，共四十一頁，2022年，8月28日直接推導(定義2.3)

：

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

或說：w直接歸約到U

記作

Uw。特別地，當γ=δ=ε時，A

α例4：

文法G[S]：S→0S1，S→01，其中VN=S,VT={0,1}直接推導：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）第十八頁，共四十一頁，2022年，8月28日推導(定義2.4)

：

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

則稱w為v的一個推導，記為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的一個算術表達式(由終結符組成)。v推導出ww規(guī)約到v第十九頁，共四十一頁，2022年，8月28日最左推導定義2.9

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

第二十頁，共四十一頁，2022年，8月28日最右推導

定義2.10

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

定義2.6

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

定義2.7

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

定義2.8

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

例4中文法：

S，0S1，000111都是文法G的句型，000111是G的句子。〖結論〗句子一定是句型，句型不一定是句子。區(qū)別第二十二頁，共四十一頁，2022年，8月28日例:文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

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

n1｝因為S0S100S11…0n1n重復利用規(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)是句型。第二十三頁，共四十一頁，2022年，8月28日表示語言表示語言有文法推出語言

文法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}√第二十四頁，共四十一頁，2022年，8月28日有語言推出文法文法為SABCA

aA|aB

bB|bC

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

bA|bBB

cB|c

習題二2.2(4)若i,j,k>=0文法變成？第二十五頁，共四十一頁，2022年，8月28日文法為更巧妙文法為第二十六頁，共四十一頁，2022年，8月28日習題二2.2(6)能被5整除的整數(shù)集合的文法

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

N第二十七頁，共四十一頁，2022年，8月28日(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第二十八頁，共四十一頁，2022年，8月28日文法的化簡第二十九頁，共四十一頁，2022年，8月28日化簡文法例：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第三十頁，共四十一頁，2022年，8月28日文法和語言0型文法產生的語言稱為0型語言1型文法或上下文有關文法（CSG

）產生的語言稱為1型語言或上下文有關語言（CSL）2型文法或上下文無關文法（CFG

）產生的語言稱為2型語言或上下文無關語言（CFL）

3型文法或正則（正規(guī)）文法（RG）產生的語言稱為3型語言正則（正規(guī)）語言（RL）第三十一頁，共四十一頁，2022年，8月28日語法樹

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

樹中每個結點都有一個標記，該標記是VNVT中的一個符號；

樹的根結點標記是文法的識別符號S；

若樹的一個結點至少有一個葉子結點，則該結點的標記一定是一個非終結符；若樹的一個結點有多個葉結點，該結點的標記為A，這些葉結點的標記從左到右分別是B1，B2，….，Bn，則AB1B2…BnP文法的句型都可依據(jù)其產生式來生成相應的語法樹。第三十二頁，共四十一頁，2022年，8月28日問題：一個句型是否對應唯一的一棵語法樹？例：G[Z]:

Z→aZb Z→Z Z→abZaZbab

ZaZbZab句型aabb的語法樹第三十三頁，共四十一頁，2022年，8月28日句型(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)第三十四頁，共四十一頁，2022年，8月28日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第三十五頁，共四十一頁，2022年，8月28日上下文無關文法的語法樹

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

從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結果。也把該推導樹稱為該句型的語法樹。第三十六頁，共四十一頁，2022年，8月28日產生式樹

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