文法和语言的基本知识

《文法和语言的基本知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章文法和语言的基本知识学习本章目的学生通过学习了解高级程序语言的一些基本概念及其分类。以及语法结构的形式描述问题。讲授6课时以板书为主本章主要讲解的内容为乔姆斯基文法及其分类，文法的二义性判断和证明，上下文无关文法的简化和语法树。重点与难点本章重点就是二义性判断和转化以及高级语言文法的内容。文法分类是难点对程序设计语言的描述是从语法、语义和语用三个因素来考虑的。所谓语法是对语言结构的定义；语义是描述了语言的含义；语用则是从使用的角度去描述语言。为了精确定义和描述程序设计语言，需采用形式化的方

2、法。所谓形式化的方法，是用一整套带有严格符号规定的符号体系来描述问题的方法。§2.1字母表和符号串的基本概念1.字母表字母表是元素的非空有穷集合。例如，∑={a，b，c}根据字母表的定义，∑是字母表，它由a，b，c三个元素组成。字母表中至少包含一个元素。字母表中的元素，可以是字母、数字或其他符号。2.1.1字母表和符号串例如，∑′={0，1}是一个字母表，由0和1两个元素组成。不同的语言有不同的字母表，如英文的字母表是26个字母、数字和标点符号的集合，C语言的字母表是由字母、数字和若干专用符号组

3、成。2.符号（字符）字母表中的元素称为符号，或称为字符。例如，前述例子中，a，b，c是字母中∑中的符号；0和1是字母表∑′中的符号。3.符号串（字）符号的有穷序列称为符号串。例如，设有字母表∑={a，b，c}，则有符号串a，b，ab，ba，cba，abc…。符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。符号串中符号的顺序很重要，如ab和ba是字母表∑上的两个不同的符号串。不包含任何符号的符号串，称为空符号串，用ε表示，即空符号串由0个符号组成，其长度{ε}=0。1.符号串

4、的连结设x和y是符号串，则串xy称为它们的连结。即xy是将y符号串写在x符号串之后得到的符号串。例如，设x=abc，y=10a，则xy=abc10a，yx=10aabc。注意：对任意一个符号串x，我们有εx=xε=x。2.1.2符号串的运算２．集合的乘积设A和Ｂ是符号的集合，则A和B的乘积定义为：AB＝｛xy｜Ｘ∈A，y∈B｝例如，设A＝｛a，b｝B={c，d}，则AB={ac，ad，bc，bd}。集合的乘积是满足于x∈A，y∈B的所有符号串xy所构成的集合。由于对任意的符号串x，总有εx=xε

5、=x，所以，对任意集合A，有：｛ε｝A=A{ε}=A特别指出的是，ε是符号串，不是集合，而｛ε｝表示由空符号串ε所组成的集合，但这样的集合不是集合φ＝｛｝。３.符号串的幂运算设x是符号串，则x的幂运算定义为x0=εX1=xx2=xx…………xn=xxxx……xx=xxn-1(n>0)例如，设x=abc，则x0=εx1=abcx2=xx=abcabc………4.集合的幂运算设A是符号串的集合，则集合A的幂运算定义为：A0={ε}A1=AA2=AA………An=AAAAA……A=AAn-1(n>0)例如

6、，设A={a，b}A0={ε}A1={a，b}A2=AA={aa，ab，ba，bb}A3=AAA=A2A={aaa，aab，aba，abb，baa，bab，bba，bbb}…………5.集合A的正闭包A+与A的闭包A*定义为A+=A1∪A2∪…An…A*=A0∪A1∪A2∪…∪An…={ε}∪A+例如，设A={a，b}，则A+={a，b，aa，ab，ba，bb，aaa，aab，…}A*={ε，a，b，aa，ab，ba，bb，aaa，aab，…}可见，集合A的正闭包表示A上元素a，b构成的所有符号串

7、的集合，集合A的闭包比集合A的正闭包多含一个空符号串ε。§2.2文法和语言的形式定义序列的集合称为形式语言。也就是说，每个形式语言都是字母表上按某种规则构成的所有符号串的集合，反之，任何一个字母表上符号串的集合均可定义为一个形式语言。形式语言不考虑语义。例如，C语言是其基本符号字母表上的符号串的集合，而每个C语言程序是基本符号的符号串。2.2.1形式语言对形式语言的描述有两种方法：⑴当语言为有穷集合时，用枚举方法来表示语言：例如：设有字母表A={a，b，c}，则L1={a，b，c}L2={a，a

8、a，ab，ac}L3={c，cc}均表示字母表A上的一个形式语言。⑵对无穷集合的语言，需要设计文法来描述：例如：用A表示∑+，用式子A→0表示符号串0∈A或A生成符号串0，符号“→”读做“生成”或“由……组成”。则集合A可表示成A→0A→1A→A0A→A1显然，由A生成的符号串属于∑+，这就是用文法描述语言。1.规则规则也称产生式，它是一个符号与一个符号串的有序对(A，β)，通常写做A→β(或A::=β)其中，A是规则左部，它是一个符号；β是规则右部，它是一个符号串；“→”和“::=”表示“定义