形式语言概论

形式语言概论第一页，共四十一页，2022年，8月28日形式语言理论：是指由数学方法研究自然语言和人工语言(程序设计语言)之语法理论，主要讨论了语言和文法的数学机制以及语言和文法的分类。第二页，共四十一页，2022年，8月28日文法的直观概念

如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在如何给出它的有穷表示的问题。虽然无法列出全部句子，但是可以给出一些规则，用这些规则来说明句子的组成结构，然后用它们去推导产生句子。文法：是阐述语法的一个工具

第三页，共四十一页，2022年，8月28日“你是大学生”对“我是教师”对“我大学生是”错“我学习大学生”对〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|教师|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|<名词>

〈句子〉〈主语〉〈谓语〉

〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈名词〉我是教师推导：我是教师

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

字母表：是元素的非空有穷集合，用表示。字母表中的元素称为符号。

例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、算符、保留字等组成。

符号串的长度：符号串中符号的个数。符号串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：终结符号集。终结符号代表不可再分的基本符号，如保留字、标识符、常数、运算符、界符等。

VN∩VT=Φ；V=VN∪VT称为文法G的词汇表。

S：开始符号。开始符号是一个特殊的非终结符号，表示文法G所定义的最终的语法范畴。

P：产生式的集合。产生式是定义语法范畴的一种书写格式，形式如下：α→β

其中，α称为产生式左部，它必须是非终结符；β称为产生式右部，它可以是终结符、非终结符或他们的组合。第十页，共四十一页，2022年，8月28日例1：文法G=（VN，VT，P，S）

VN={标识符，字母，数字} VT={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z<数字>→0,…,<数字>→9} S=<标识符>习惯上只将产生式写出。并有如下约定：1、第一条产生式的左部是开始符号；2、用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符；3、G可写成G[S]，其中S是开始符号；文法例子

第十一页，共四十一页，2022年，8月28日例2：无符号二进制数的描述文法

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代表单个变量或常数；+、*、（、）是构成算术表达式的运算符和括号。定义由前面符号组成的单个变量或常量组成的算术表达式；若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型正规文法文法类型逐渐增加限制第十四页，共四十一页，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出现在γ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型文法（正规文法）：除S→ε外,所有产生式α→β的形式都为

A→aB或A→a，其中AVN

，BVN

，aVT。正规文法是CFG文法的一个子集正规文法例：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（应用规则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，使用规则S→01，γ=0，δ=1）S0S1（U=S，w=0S1，使用规则S→0S1，γ=ε，δ=ε）0S100S11（U=0S1，w=00S11，使用规则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规约到v第十九页，共四十一页，2022年，8月28日最左推导定义2.9

在xUy=>xuy直接推导中，若xVT*,UVN,即U是符号串xUy中最左非终结符，则称此直接推导为最左直接推导。若一个推导的每一步直接推导都是最左直接推导，那么此推导称为最左推导。例G12[<标识符>]：<标识符>→<字母>|<标识符><字母>|<标识符><数字><字母>→a|b|c|…|x|y|z<数字>→0|1|2|3|4|5|6|7|8|9<标识符><标识符><数字><标识符><数字><数字><字母><数字><数字>a<数字><数字>a6<数字>a69

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

定义2.10

在xUy=>xuy直接推导中，若yVT*,UVN,即U是符号串xUy中最右非终结符，则称此直接推导为最右直接推导。若一个推导的每一步直接推导都是最右直接推导，那么此推导称为最右推导。最右直接推导又称为规范直接推导，最右推导又称为规范推导。例文法如G12.<标识符><标识符><数字><标识符>9<标识符><数字>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的句子。〖结论〗句子一定是句型，句型不一定是句子。区别第二十二页，共四十一页，2022年，8月28日例:文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

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

n1｝因为S0S100S11…0n1n重复利用规则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整除的整数集合的文法

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

N第二十七页，共四十一页，2022年，8月28日(1)允许0开头的偶正整数集合的文法

E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法

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型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）第三十一页，共四十一页，2022年，8月28日语法树

设文法G=（VN,VT,P,S），对于文法G的任意一个句型都存在一个相应的语法树：

树中每个结点都有一个标记，该标记是VNVT中的一个符号；

树的根结点标记是文法的识别符号S；

若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符；若树的一个结点有多个叶结点，该结点的标记为A，这些叶结点的标记从左到右分别是B1，B2，….，Bn，则AB1B2…BnP文法的句型都可依据其产生式来生成相应的语法树。第三十二页，共四十一页，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