《03-Complementary Ch01-Formal language 1》由会员分享，可在线阅读，更多相关《03-Complementary Ch01-Formal language 1（34页珍藏版）》请在金锄头文库上搜索。
1、College of Computer,Copyright SE Dept GPC,1,Complementary Ch01Formal language,6 Class Hours,College of Computer,Copyright SE Dept GPC,2,形式语言理论形式语言的简单数学基础语言和文法的分类（重点）语言与文法的相互求解方法（重点）编译过程中两种语法分析方法,本 章 内 容,College of Computer,Copyright SE Dept GPC,3,形 式 语 言 理 论,生成能力是语言最重要的一个特点。应从形式上、结构上考虑问题，语法应该是“一种装置（
2、device），这种装置能产生所研究对象语言的许多句子”。以类似数学那样的方法，演绎的方法，把语法分析过程公式化。,Noam Chomsky ( 1928 ),College of Computer,Copyright SE Dept GPC,4,字 母 表,定义：元素的非空有穷集合。记为。在形式语言中，字母表包含了语言中所允许出现的一切符号。例如：组成英语的字母表为=A,a,B,b 组成汉语的字母表为=,College of Computer,Copyright SE Dept GPC,5,符号串,符号串：字母表中的符号所组成的有穷序列称为符号串。一个语言的句子总是它所在字母表的符号串。这个
3、符号串的组成必须是按照 一定规则 组合而成的。语法分析的一个重要任务就是：判断一个符号串的组成是否满足已有规定。,College of Computer,Copyright SE Dept GPC,6,关于符号串的概念和操作,运算：连接/联结/并置：x=123, y=45那么xy=12345方幂：x的n次方幂即将n个x联结。子符号串：v是 xvy 的子符号串。v非空。头，尾：x是 xy 的头，y是 xy 的尾。,College of Computer,Copyright SE Dept GPC,7,符号串集合,定义：若集合A中的一切元素都是同一个字母表上的集合，那么A被称为该字母表上的符号串集
4、合。在计算机课程中，语言被认为是句子的集合。所以，一个语言就是对应于它的字母表上的一个符号串集合。,College of Computer,Copyright SE Dept GPC,8,符号串集合的运算,乘积：AB = xy | xA且y B 方幂：A 的 n 次方幂就是将 n 个 A 相乘。符号串集合的正闭包与（自反）闭包：符号串集合A的正闭包: A+ =A1A2 An 符号串集合A的（自反）闭包: A* =A0A1 An ,College of Computer,Copyright SE Dept GPC,9,文法、语言、句子的关系 文法是语言的形式化描述，可以说，确定了某一文法，则可以
5、确定一个给定的句子是否属于该文法（或者说可以由文法推导出语言的每一个句子）。 注：语言 是 句子 的集合。 字符串集合 字符串,2.2 文法及其分类,College of Computer,Copyright SE Dept GPC,10,文法、语言、句子举例,由于文法、语言、句子本质上的紧密联系，在此我们以“产生语言”的角度出发，给出文法、语言、句子的形式定义。例：以英语句子的组成为例，假定每一个句子都是由 主语短语 + 动词短语 结构组成。则有： 1. := 说明：上面1.称为该语言的 语法规则。 、称为该语言的 语法范畴。,College of Computer,Copyright SE
6、 Dept GPC,11,文法、语言、句子举例,可以看到由推导出（或说定义出）等语法范畴后，并不是我们日常语言。可进一步定义2. := the 3. :=则我们得到新的 语法范畴 、 和新的 语法规则 2. 和 3. 注：the的特殊性不可再定义,College of Computer,Copyright SE Dept GPC,12,文法、语言、句子举例,同理可以得到以下语法规则和语法范畴 4. := 5. := monkey6. := banana7. := ate 8. := has9. := the 10. := a我们可以由该语言的最大的语法范畴不断使用规则1.-10.来推导出属于该
7、文法的每一个句子。,College of Computer,Copyright SE Dept GPC,13,文法、语言、句子举例,例如： = 使用规则1 = 使用规则3 = the 使用规则2 = the 使用规则4 = the monkey 使用规则5 = the monkey ate 使用规则7 = the monkey ate a 使用规则10 = the monkey ate a banana 使用规则6同理，我们可以由推导其它的属于该语言的句子 如： a monkey ate a banana the monkey has the banana 等其余15个句子,College o
8、f Computer,Copyright SE Dept GPC,14,文法、语言、句子举例,以上十六个句子的集合，我们称之为语言。之所以该语言中可以包含十六个句子，很大部分是由于在规则1.-10.中，允许相同的左部可以生成不同的右部。 如：7. := ate 8. := has 9. := the 10. := a 也可记为： := ate | has := the | a,College of Computer,Copyright SE Dept GPC,15,文法、语言、句子举例,在上面十六个句子的集合中，或者说从我们刚刚定义的语言中，有些句子是存在语义错误的。 例如：the banan
9、a ate a monkey a banana has the monkey在一般原理性课程大部分时间内，我们一般只用考虑语法问题，而忽视语义。及承认上述十六个句子都是合法的。大部分语言的句子数目可以看成是无限的。,College of Computer,Copyright SE Dept GPC,16,文法、语言、句子总结,在上例可知：描述一种语言中，穷尽所有句子是不现实的。需要使用另一种方法描述。设计方法描述语言： 1、记录句子产生过程中所用的语法范畴。 2、记录语言中不能再继续推导最终元素。 3、规定推导所使用的所有规则。 4、语法范畴中最特殊的起始单位。,College of Comp
10、uter,Copyright SE Dept GPC,17,文法的定义,Chomsky文法的定义： G = ( VN,VT,P,S )其中：VN 非空有限的非终结符号集 VT 非空有限的终结符号集 P 产生式集 S 开始符号/识别符号，S VN 文法被用来精确而无歧义地描述语言的句子的构成方式。文法描述语言的时候不考虑语言的含义。,College of Computer,Copyright SE Dept GPC,18,终结符与非终结符-终结符：VT 组成语言的基本符号。在程序设计语言中就是以前屡次提到的单词符号。如：基本字，标识符，常数，算符，界符等。从语法分析的角度看，终结符是一个语言的不
11、可再分的基本符号。（从语法角度讲）非终结符：VN 也称语法变量，用来代表语法范畴。如“算术表达式”、“布尔表达式”、“赋值句”、“子程序”、“函数”等。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个个体记号。（从语法角度讲）,文法的定义,College of Computer,Copyright SE Dept GPC,19,文法的定义（产生式/重写规则）,产生式：一个产生式是一个有序对(,)，通常写作 或 := 。其中为左部； 为右部。对,的限制： （VNVT）+ 且至少含一 VN （VNVT）*产生式意味着能将一个符号串用另外一个符号串替换。因而又被称为重写规则。产生
12、式的简写： := , := 可以简化为： := | ,College of Computer,Copyright SE Dept GPC,20,文法举例,G（E）= ( VN,VT,P,E )其中:VN = E , T , F VT = i,+,*,(,) P= ET | E + T TF | T * F F( E )| i 请同学们写出该文法所描述语言的几个句子。,College of Computer,Copyright SE Dept GPC,21,下面我们需要思考的问题,文 法,语 言,对应问题,有何分类,有何分类,是否一致（太复杂）,College of Computer,Copyr
13、ight SE Dept GPC,22,Chomsky文法的定义：( VN,VT,P,S )Chomsky文法根据对产生式的不同限制，可分为四类：0型，1型，2型，3型。我们主要用2型和3型文法。,文法的分类,College of Computer,Copyright SE Dept GPC,23,0型文法/PSG,0型文法的产生式： := ， （VNVT）+ 且至少含一VN （VNVT）*又称短语结构文法，其能力相当于图灵机。其相对应所描述的语言称为0型语言，又称为递归可枚举集合。0型语言是不可判定的。,College of Computer,Copyright SE Dept GPC,24,1型文法/CSG,1型文法的产生式：1A2 :=12 A VN ， 1, 2（VNVT）* , （VNVT）+ 1, 2被称为上下文。1型文法也可以如下定义：所有的规则的右部都比左部长。1型文法是可判定的。但是现在没有找到有效的方法。,College of Computer,Copyright SE Dept GPC,25,2型文法/CFG,2型文法的产生式：A:= ，其中A VN , （VNVT）* ，若AS则 。2型文法又称为上下文无关文法。一般的程序设计语言的语法都使用2型文法描述。2型文法是可判定的，且有有效的判定方法2型文法的例子：S :=ab|aSb,
