编译原理第三章文法和语言.ppt
《编译原理第三章文法和语言.ppt》由会员分享,可在线阅读,更多相关《编译原理第三章文法和语言.ppt(83页珍藏版)》请在三一文库上搜索。
1、2019/3/12,1,第三章 文法和语言,课前思考, 高级语言有哪些一般特性? 你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的? 学习编译程序为什么要研究语言的描述问题?,2019/3/12,2,学习目标,本章目的是为语言的语法描述寻求工具 掌握对源程序给出精确无二义(严谨、简洁、易读)的语法描述手段之一文法。 熟练使用文法定义程序设计语言的单词和语法成分 对形式语言的理论有一个初步基础,2019/3/12,3,学习指南, 什么是文法,什么是它定义的语言? 在乔姆斯基(Chomsky)的文法类型中,我们为什么关注上下文无关文法? 什么是语法分析?语法分析方法的分类?,20
2、19/3/12,4,难重点,关于文法和语言的概念是形式语言的理论基础,形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,2019/3/12,5,知识结构,2019/3/12,6,引言和预备知识,高级语言 程序语言是一个记号系统 语法 语义,语法 任何语言程序都可以看成是一定字符集(字母表)上的字符串 语法使得这串字符形成一个形式上正确的程序 语法=词法规则+语法规则 例如:0.5*x1+c 0.5、x1、c、*、+是语言的单词符号 0.5*x1+c是语言的语法单位,词法 单词符号 语言中具有独
3、立意义的最基本结构 词法规则 词法规则规定了字母表中哪些字符串是单词符号 单词符号一般包括:常数、标识符、基本字、算符、界限符等 我们用正规式和有限自动机理论来描述词法结构和进行词法分析,语法 单词符号 语法单位 表达式、子句、语句、函数、过程、程序 语法规则 规定了如何从单词符号来形成语法单位 现在多数程序语言使用上下文无关文法来描述语法规则 语言的词法规则和语法规则定义了程序的形式结构,是判断输入字符串是否构成一个形式上正确的程序的依据,例,对于一个PASCAL程序来说,一个上下文无关文法可以定义 A:=B+C 是合乎语法的, 而A:=B+ 是不合乎语法的。,语义 对于一个语言来说,不仅要
4、给出它的词法、语法规则,而且要定义它的单词符号和语法单位的意义 离开语义,语言只是一堆符号的集合 各种语言中有形式上完全相同的语法单位,含义却不尽相同 对某种语言,可以定义一个程序的意义的一组规则称为语义规则 目前,大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义,对于高级程序设计语言及其编译程序来说,语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题,编译原理的主要内容也可以归纳为应用形式语言理论,并将它贯穿于词法分析和语法分析两个阶段,2019/3/12,14,3.2 符号和符号串,任何一种语言都是由该语言的基本符号组成的符号串的集合。 基本符号集 任何语言的单词符号就
5、是定义在它的字符集上的字符串 该语言的任何语句就是定义在其单词符号集上的单词串(符号串),2019/3/12,15,字母表:是元素的非空有穷集合,把字母表中的元素称为符号,因此字母表也称符号集。例,a,b,c,+,就是含有5个元素的一个字母表。一般用和V来表示 符号:是语言当中最基本的不可再分的单位,2019/3/12,16,符号串:字母表中的符号所组成的任何有穷序列。例,V=a,b,c是一个字母表,则a,b,c,aa,ab,bc,abc等等都是V上的符号串 空串:不含有任何符号的串称为空串,记作,句子:字母表上符合某种规则构成的串 语言:字母表上句子的集合 注:约定用a, b, c表示符号;
6、用, , 表示符号串;用A, B, C表示其集合,2019/3/12,18,符号串的长度:如果某符号串中有m个符号,则其长度为m,记为|=m。 例,|abc|=3 的长度为0 符号串的连接:设和是符号串,它们的连接是把的符号写在的符号之后得到的符号串。例,若=NPU, =1108,则=NPU1108, =1108NPU,符号串的方幂:设是符号串,把自身连接n次得到符号串,即=,称为符号串的方幂,写作=n。 符号串集合:若集合A中的一切元素都是某字母表上的符号串,则称A为字母表上的符号串集合。,2019/3/12,19,两个符号串集合A和B的乘积(连接): AB=| A且 B 注:1)串集的自身
7、乘积称作串集的方幂 2)A0= 字母表V的n次方幂是字母表V上所有长度为n的串集,2019/3/12,20,2019/3/12,21,字母表V的闭包V*和正闭包V+:,字母表上的语言,是字母表上正闭包的子集。,2019/3/12,22,3.1 文法的直观概念,文法的定义对语言结构的描述和定义,即在形式上用来描述和规定语言结构的称为“文法”(或“语法”)。,比如:“我是大学生。”是汉语的一个句子 汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语 := :=| := 我 | 你 | 他 := 王明 | 大学生 | 工人 | 英语 := := 是 | 学习 :=|,2019/3/12,2
8、3,2019/3/12,24,一旦有了一组规则以后,我们可以按照如下方式用它们去推导或产生句子。我们开始去找:=左端的带有句子的规则并把它表示成:=右端的符号串 规则中的“:=”也常用“”表示,含义是使用一条规则,代替=左边的某个符号,产生右端的符号串。 注意文法中,描述某个特定的语法成分的规则可能不只一条。,2019/3/12,25,得到句子“我是大学生”的全部动作过程是: 我 我 我是 我是 我是大学生,2019/3/12,26,“我是大学生”的构成是符合上述规则 “我大学生是”不符合上述规则 这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这
9、里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。,2019/3/12,27,3.3 文法和语言的形式定义,前面已经对规则(或产生式)的概念进行了非形式化的说明,我们已经对其有了一个直观的了解。下面将对其进行形式化说明,并在此基础上抽象地定义文法和语言。,2019/3/12,28,文法G定义为四元组(VN,VT,P,S) VN :非终结符集 VT :终结符集 P:产生式(规则)集合 S:开始符号(或识别符号) VNVT= , SVN V=VNVT,称为文法G的文法符号集合,定义3.1,2019/3/12,29,句子的语法结构,可以用一组规则来描述。 规则也称为“重写规则”、“产生式”或“生
10、成式”,是形如或:=的(,)有序对,且V+, V* ,V为某字母表。 称为规则的左部(或产生式的左部) 称为规则的右部(或产生式的右部) 这里使用的符号(:=)读作“定义为”,2019/3/12,30,例3.1 文法G=(VN,VT,P,S) VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,2019/3/12,31,例3.2 文法G=(VN,VT,P,S) VN =标识符,字母,数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,2019/3/12,32,习惯上不用将文法G的四元组显示地表示出来,只将产生式写出。并有如下约定: 第一条
11、产生式的左部是开始符号 用尖括号括起的是非终结符,否则为终结符。或者大写字母表示非终结符,小写字母表示终结符 G可写成GS,S是开始符号 G:S0S1 S01 GS: S0S1 S01,2019/3/12,33,有时,为书写简洁,常把相同左部的产生式,形如 A a1,Aa2 Aan 缩写为:Aa1|a2|.|an 注意:元符号“|”读作“或”,2019/3/12,34,一个文法的几种写法 例:G=(S,A,a,b,P,S) 其中: P:SaAb Aab AaAb A G:SaAb Aab AaAb A GS: Aab AaAb A SaAb GS:Aab |aAb | SaAb,2019/3/
12、12,35,直接推导“” 定义3.2:如是文法G=(Vn,VT,P,S)的规则(或说是P中的一产生式),若有符号串v,w满足:v=,w= ,其中V*,V* 则称v直接推导出w,记作 v w 或w直接归约到v,对于例3.1的文法G:S0S1,S01 ,可以给出直接推导的一些例子如下: v=0S1,w=0011,直接推导:0S1 0011,使用的规则:S01,这里=0,=1。 v=S,w=0S1,直接推导:S 0S1,使用的规则:S0S1,这里=,= v=0S1,w=00S11,直接推导:0S1 00S11,使用的规则:S0S1,这里=0,=1。,2019/3/12,36,对于例3.2的文法G,直
13、接推导的例子有: v=,w= ,直接推导: ,使用的规则: ,这里= v= ,w= ,直接推导: ,使用的规则: 。这里=, 。 v=abc ,w=abc5,直接推导:abc abc5, 使用的规则: 5,这里=abc,=,2019/3/12,37,2019/3/12,38,定义3.3 如果存在直接推导的序列: v w0 w1 . wn=w (n0) 则称v 推导出(产生)w(推导长度为n), 或称w归约到v。记作v w 定义3.4 若有v w,或v=w, 则记为v w,对例3.1的文法,存在直接推导序列v=0S1 00S11 000S111 00001111=w, 即0S1 00001111
14、,也可记作0S1 00001111 对例3.2的文法,存在直接推导序列v= x x1=w, 即 x1,也可记作 x1,2019/3/12,39,2019/3/12,40,文法的句型、句子的定义,句型 有文法GS,若S x,则称x是文法G的句型。 句子 有文法GS,若S x,且xVT*,则称x是文法G的句子。 例:G:S0S1, S01 S 0S1 00S11 000S111 00001111 S,0S1,000111都是文法G的句型,其中00001111是G的句子。,2019/3/12,41,定义3.6 由文法G所产生的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S x,其中
15、S为文法的开始符号,且x VT* 例:G: S0S1, S01 L(G)=0n1n|n1,2019/3/12,42,例3.3 文法GS: (1)SaSBE (2)SaBE (3)EBBE (4)aBab (5)bBbb (6)bEbe (7)eEee,2019/3/12,43,S aSBE (SaSBE) aaSBEBE (SaSBE) aaaBEBEBE (SaBE) aaaBBBEEE (EBBE) aaabBBEEE (aBab) aaabbBEEE aaabbbEEE (bBbb) aaabbbeEE (bEbe) aaabbbeeE aaabbbeee (eEee),L(G)= an
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第三 文法 语言
链接地址:https://www.31doc.com/p-2258607.html