第2章 文法和语言.ppt
《第2章 文法和语言.ppt》由会员分享,可在线阅读,更多相关《第2章 文法和语言.ppt(63页珍藏版)》请在三一文库上搜索。
1、1,第2章 文法和语言,2,构造编译程序,需针对特定的程序语言,故需对被编译的程序语言本身做精确地描述。 为语言的语法(文法)描述寻求工具。工具要对程序设计语言给出精确无二义的语法描述。(严谨、简洁、易读)。,本章目的,对于程序设计者而言,文法给出了语言的精确的语法规范说明。,3,程序设计语言描述,语法Syntax:对语言结构的定义。 语义Semantics:描述语言的含义。 语用Pragmatics:从使用者角度描述语言。,如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言。,4,形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以符号串能
2、出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,5,2.1 字母表和符号串 2.2 文法和语言的形式定义 2.3 语法树和文法的二义性 2.4 文法的类型,6,2.1 字母表和符号串,7,每个程序设计语言都是一个“基本符号”串,设有一基本符号集,那么程序设计语言可看成是在这个基本符号集上定义的,按一定规则构成的一切基本符号串组成的集合。 为了给出语言的形式定义,首先学习一些基本概念和术语。,8,(1)空符号串:没有符号的符号串 。 例如: =a,b ,a,b,aa,ab,aabba都是上的符号串,1. 字母表:符号(元素)的非空有
3、穷集合。,字符(符号):可以相互区别的记号(元素)。,2. 符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。,9,(2)符号串s的头(前缀):移走符号串s尾部的零个或多于零个符号得到的符号串。 如:b是符号串banana的一个前缀。 符号串s的尾(后缀):删去符号串s头部的零个或多于零个符号得到的符号串。 如:nana是符号串banana的一个后缀。,(3)符号串s的子串:从s中删去一个前缀和一个后缀得到的符号串。 如:ana是符号串banana的一个子串。,10,对于每个符号串s, s和两者都是符号串s的前缀,后缀和子串。 (4)符号串s的真前缀,真后缀,真子串 3.符号串
4、的运算 (1)符号串的长度:符号串中符号的个数.符号串s的长度记为|s|。 的长度为0。 (2)连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy。 如 x=ab,y=cd 则 xy=abcd 有a = a= a (3)方幂:符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a, a2=aa则a0=,11,(4)符号串集合:若集合A中所有元素都是某字母表上的符号串,则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积定义为: AB =xy|xA且yB 若 集合A=ab,cde B = 0,1,则 AB=ab1,ab0,cde0,cde1 4.闭包:
5、使用 *表示上的一切符号串(包括)组成的集合。*称为的闭包。 上的除外的所有符号串组成的集合记为+ 。 +称为的正闭包。,12,例:=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,13,文法的直观概念,14,当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。 以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明(或者定义)句子的组成结构。 比如汉语句子可以是由主语后随谓语而成,构
6、成谓语的是动词和直接宾语,以下是该句的构成规则:,15,“我是大学生。”是一个汉语句子,句子=主语谓语 主语=代词名词 代词= 我你他 名词= 王明大学生工人英语 谓语=动词直接宾语 动词= 是学习 直接宾语=代词名词,16,有了一组规则以后,按照如下方式用它们导出句子:开始去找=左端的带有句子的规则并把它由=右端的符号串代替,这个动作表示成: 句子 主语谓语, 然后在得到的串主语谓语中,选取主语或谓语,再用相应规则的=右端代替之。 重复做下去,句子:“我是大学生”的全部动作过程是:,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,符号 的含义:使用一条规
7、则,代替左边的某个符号,产生右端的符号串。,17,“我是大学生”的构成符合上述规则,而“我大学生是”不符合上述规则,那么它就不是句子。这些规则成为我们判别句子结构合法与否的依据。 换句话说,这些规则看成是一种元语言,用它描述汉语结构。这种描述语言的语法结构的形式规则称为文法。,18,王明是大学生。 他学习英语。 你是工人。,使用文法作为工具,不仅能严格定义句子结构,也能用有限的规则把语言的全部句子描述出来。 所以,文法是以有穷集合刻划无穷集合的工具。,19,上例中的局限性,对“我是大学生”作扩充“我是计算机专业的大学生。” 该句子中多了定语,相应的对前面的7条规则做相应修改。,因此,用文法描述
8、的一组规则只能描述一类句子,不同类的句子应使用不同的规则。,同理,程序设计语言也不能只用一组规则就把程序都描述完整。,20,2.2 文法和语言的形式定义,21,一、文法 二、推导 1. 直接推导(一步推导) 2. 推导序列(多步推导) 三、句型,句子 四、语言 1. 语言等价 2. 文法与语言的关系,22,如何来描述一种语言?,如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示。 如果语言是无穷的,找出语言的有穷表示。语言的有穷表示有两个途经:,生成方式 (文法):语言中的每个句子可以用严格定义的规则来构造。,识别方式(自动机):是一个过程,当输入的一任意串属于语言时,该过程经有
9、限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远继续下去。),23,文法是生成方式描述语言的:语言中的每个句子可以用严格定义的规则来构造。 下面给出文法的四个组成部分,初步对文法的形式定义有一个初步了解。,24,1. 终结符:语言中不可再分的基本符号,通常是一个语言的字母表。如程序设计语言中的基本字、常数、运算符、分界符等。,2. 非终结符:它不像终结符代表了语法的最小元素,是一种个体记号,它是一个类、一个集合。一个非终结符代表了一定的语法概念。程序设计语言中常见的语法单位有“过程”、“赋值语句”、“表达式”等。,3. 开始符号:是一个特殊的非终结符。,4. 产生
10、式:构造某个语法时应满足的规则。,25,文法G定义为四元组(VN,VT,P,S )其中: VN为非终结符号(或语法实体,或变量)集; VT为终结符号集; S为开始符号,它是一个非终结符,至少要在一条产生式中作为左部出现。 P为产生式(也称规则)的集合;,VN,VT和P是非空有穷集。 VN和VT不含公共的元素,即VN VT = 用V表示VN VT ,称为文法G的字母表。,26,文法的举例,例: 文法G=(VN,VT,P,S) VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,27,定义中的注意事项,1. 产生式形如 , “”读作“是”或“定义为”。 其中是字母表V的正
11、闭包V+中的一个符号, 是V*中的一个符号。 称为规则的左部,称作规则的右部。,2. 若 1, 2 n ,可简写为: 1 | 2 | | n,习惯表示 小写字母:终结符 大写字母:非终结符,28,例: 文法G=(VN,VT,P,S) VN =标识符,字母,数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,29,文法的几种等价写法,GS: Aab | aAb | SaAb,G:SaAb Aab AaAb A,GS: Aab AaAb A SaAb,30,直接推导“”,是文法G的产生式,若有v,w满足:v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第2章 文法和语言 文法 语言
链接地址:https://www.31doc.com/p-3423283.html