《形式语言概论》PPT课件.ppt

《《形式语言概论》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章形式语言概论文法和语言形式化定义文法的类型语言和语法树文法和语言的几点说明分析方法简介本章小结形式语言理论：是指由数学方法研究自然语言和人工语言(程序设计语言)之语法理论，主要讨论了语言和文法的数学机制以及语言和文法的分类。文法的直观概念如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在如何给出它的有穷表示的问题。虽然无法列出全部句子，但是可以给出一些规则，用这些规则来说明句子的组成结构，然后用它们去推导产生句子。文法：是阐述语法的一个工具“你是大学生”对“我是教师”对“我大学生是”错“我学习大学生”对〈句子〉∷=

2、〈主语〉〈谓语〉〈主语〉∷=〈代词〉

3、〈名词〉〈代词〉∷=我

4、你

5、他〈名词〉∷=王明

6、大学生

7、教师

8、英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是

9、学习〈直接宾语〉∷=〈代词〉

10、<名词>〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈名词〉我是教师推导：我是教师巴科斯-瑙尔范式(EBNF)例如，描述标识符的文法如下：<标识符>::=<字母><标识符>::=<标识符><字母><标识符>::=<标识符><数字><字母>::=a

11、b

12、c

13、d

14、…

15、z<数字>::=0

16、1

17、2

18、3

19、4

20、5

21、6

22、7

23、8

24、9字母表和符号串字母表：是

25、元素的非空有穷集合，用表示。字母表中的元素称为符号。例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、算符、保留字等组成。符号串的长度：符号串中符号的个数。符号串x的长度记为

26、x

27、。如

28、ab012

29、=5。空符号串：不含任何符号的符号串，记为ε。

30、ε

31、=0。符号串：符号的有穷序列称为符号串，如compiler,string等。符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。如:x=ab、y=123，则xy=ab123。显然，εx=xε=x。符号串集合的乘积：两个符号串集合A和B的乘积定

32、义为：AB={xy

33、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=?符号串集合的正闭包:符号串集合A正闭包A+=A1A2….An….即A+为集合A上所有符号串的集合。符号串集合的自反闭包

34、:符号串集合A正闭包A*={}A+=A+{}显然有A+=AA*=A*A文法产生式：设VN,VT分别是非空有限的非终结符号集和终结符号集，令V=VNVT,VNVT=，一个产生式是一般形式为：A->，其中AVN,V*，，A称为产生式的左部，称为产生式的右部。->表示为定义为…如果产生式集合中的产生式有共同的左部，如:A->，A->，则可将其简写为：A->

35、。变量表符号表文法：文法G定义为四元组(VN,VT,P,S)。其中：VN：非终结符号集。非终结符号代表某一类的记号，如“算术表达式”、“赋值句”等等。VT：终结符号集。终结符号代表不

36、可再分的基本符号，如保留字、标识符、常数、运算符、界符等。VN∩VT=Φ；V=VN∪VT称为文法G的词汇表。S：开始符号。开始符号是一个特殊的非终结符号，表示文法G所定义的最终的语法范畴。P：产生式的集合。产生式是定义语法范畴的一种书写格式，形式如下：α→β其中，α称为产生式左部，它必须是包含非终结符；β称为产生式右部，它可以是终结符、非终结符或他们的组合。例1：文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>

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

38、Bi.BiBi→0

39、1

40、Bi0

41、Bi1}例3：设E代表“算术表达式”；i代表单个变量或常数；+、*、（、）是构成算术表达式的运算符和括号。定义由前面符号组

42、成的单个变量或常量组成的