《 形式语言概述》由会员分享，可在线阅读，更多相关《 形式语言概述（81页珍藏版）》请在金锄头文库上搜索。
1、第二章 形式语言概述,本章学习目标,形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言 的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是: 文法和语言的形式定义 文法的分类 句型的分析和语法树,字母表,字母表 是元素的非空有穷集合，字母表中的元素称为符号，因此字母表也称为符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。 字母表可以用表示例： =a,b，=0,1，=0,1，2，3，4，5，6，7，8，9，=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,0),符号串集合
2、的运算,字母表的闭包与正闭包的运算 闭包 设有字母表A，A的闭包定义如下：A*=A0A1 A2 An,其中，An （n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。 注：闭包可以看作由A上符号组成的所有串的集合（包括空串） 正闭包 如果不允许包含空串，则得到字母表A的正闭包。A的正闭包 A+=A1 A2 An 注：正闭包可以看作由A上符号组成的所有串的集合（不包括空串） 语言 字母表上按照某种规则形成的某个符号串的集合，所以，语言是该字母表上正闭包的子集,例：设字母表=a,b,c,依次写出长度为1、2、3的符号串，可得到 的正
3、闭包 + ：+=a,b,c,aa,ab,ac,bb,bc,aaa,aab,aac,abb,abc,baa, 在+上添入空串即得*。,2.2 文法的定义及其分类,什么是文法? 描述语言的语法结构的形式规则，严格地定义句子的结构，用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。, :=:= |:= 我|你|他:= := 是|学习:= |,我是大学生的推导过程：= 我=我=我是=我是=我是大学生,2.2.2 文法的形式定义(1),非终结符 出现在规则的左部，用括起来，表示一定语法概念的词， 用VN表示 终结符 语言中不可再分割的字符串（包括单个字符组成的串） 用VT表示
4、 V= VN U VT 开始符号 表示所定义的语法范畴的非终结符又称为识别符号 开始符号用S表示,2.2.2 文法的形式定义(2),重写规则 也叫产生式规则，或称为生成式，是形如或:=的(,)有序对,其中, 是某个字母表V+中的一个元素，是V* 中的一个元素。称为规则的左部，称为规则的右部。 例： AB读作“A定义为B”，也就是说它是一条关于A的规则（产生式）。 文法 文法G是一个四元组，G=（VN，VT，P，S），其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式的集合，SVN 为文法的识别符号或开始符号。,例： 在程序设计语言中，假设我们定义标识符的命名规则为
5、字母a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则为：abc123,我们一般用大写字母代表左边的非终结符，设N 代表，D代表，L代表，则定义标识符的文法是：G=(VN，VT，P，S) 其中，VN=N，L，D ,VT=a,b,c,1,2,3P为产生式的规则： NL， NNL ，NND ，La ，Lb ，Lc ，D1 ，D2，D3S 是开始符号, 为N 注：产生式的规则说明一点，即若A，A，A可写成A| 。“|” 读做 “或者”。 上面的产生式规则可以改写为：NL|NL|ND La|b| c D1|2|3,2.2.3 文法的分类,乔姆斯基（Chomsky）于1956年建立形式语言
6、的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。 0型文法(短语文法) 设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT )+ ，且至少含有一个非终结符，而（VNVT ）*，则称G是一个0型文法。0型文法又称短语文法，它的能力相当于一个图灵机。 例如，A 图灵机是识别0型文法的识别装置 0型文法是对产生式限制最少的文法； 对0型文法产生式的形式作某些限制，可得到其他类型文法的定义。,1型文法（上下文有关文法） 设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是1型文法或上下文有关文法。 所谓上下文有关文法即：=1A2
7、，=1B2，符号串1 和2可以认为是上下文，A只有出现在上下文之间中，才可以被符号串B替代，成为=1A2=1B2因此，1型文法又称为上下文有关文法。 能够识别上下文无关语言的自动机称为线性界限自动机。缩写为LBA 注：1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成 ，除非是开始符号产生,2型文法（上下文无关文法） 设G=(VN，VT，P，S)，若P中的每个产生式满足: 是一个非终结符, (VNVT ) *，则此文法称为2 型文法或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN 。 也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足
8、够的能力描述现今的程序设计语言。 识别上下文无关语言的自动机称为下推自动机。它是。缩写为PDA。 例: 2 型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，1，2，3，4，5，6，7，8，9P=NNDD，D0123456789注：该文法描述的符号串的集合是整数。,3型文法（右线性文法或正规文法） 对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即：Aa ,AaB 则称该文法为3型文法，又称为右线性文法或正规文法，其中A、BVN，aVT. 识别3型语言或正则语言的自动机称为有穷自动机。缩写为FA。 例:3型文法 G=（VN，VT，P，S）其中
9、，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B注：该文法产生的是二进制整数。,2.2.4 文法举例,例：1型文法G=（VN，VT，P，A）VN=S,X,Y,ZVT=x,y,z P=S xSYZxYZxYxyyYyyyZ yzZY YZzZ zz,例：2型文法G=（VN，VT，P，E） VN=E，T，F， VT=+，*，（，），i P=EE+T|T,TT*F|T,F(E)|i 注：该文法能推出具有乘和加运算的算术表达式。,例：正规文法 G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB | +A | A | .GAdB | .GBdB |
10、.H |dGdHHdH | d其中，d代表十进制数字。根据以上我们对文法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：3型语言2型语言1型语言0型语言,2.2.6 文法分类的意义,一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从文法
11、出发找不到这个推导序列，则该串就是非法的。 程序设计语言的词法分析属于正规文法，与局部语法相关的部分属于上下文无关文法，与全局语法和语义有关的部分属于上下文有关文法。,2.3 文法产生的语言和句型的语法树,推导 推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。 最左（右）推导：每次使用一个规则，以其右部取代符号串的最左（右）非终结符。 注：最左推导和最右推导称为规范推导： 归约 归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。 最左(右)归约是最右(左)推导的逆过程。 注：最左归约和最右归约称为规范归约。,文
12、法产生的语言和句型的语法树（续）,推导和规范推导 推导分为三大类：直接推导 、，长度为n(n1)的推导+和长度为n（ n0）的推导 *。 直接推导 如是文法G=(VN,VT,P,S)的规则（或说是P中的一产生式），,(VNVT)*，则称符号串为符号串应用产生式所得到的直接推导。记为。,推导长度大于0的推导 如果对于符号串v 与w存在一个直接推导序列u0 u1u2u3un (n0) 其中u0=v与un =w,则称符号串v推导出w或称w归约到v，记作v +w，称这个直接推导序列是长度为n的推导。 推导长度大于等于0的推导 如果对于符号串v和w，v=w或v=w，则记作v *w，称符号串v广义推导到符号串w，或称w广义归约到v。,
