编译原理 第三章 文法和语言.ppt
《编译原理 第三章 文法和语言.ppt》由会员分享,可在线阅读,更多相关《编译原理 第三章 文法和语言.ppt(83页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、2022/12/211第三章第三章文法和语言文法和语言 课前思考 高级语言有哪些一般特性?你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的?学习编译程序为什么要研究语言的描述问题?2022/12/212学习目标本章目的是为语言的语法描述寻求工具 掌握对源程序给出精确无二义(严谨、简洁、易读)的语法描述手段之一文法。熟练使用文法定义程序设计语言的单词和语法成分 对形式语言的理论有一个初步基础2022/12/213学习指南 什么是文法,什么是它定义的语言?在乔姆斯基(Chomsky)的文法类型中,我们为什么关注上下文无关文法?什么是语法分析?语法分析方法的分类?2022/12/2
2、14难重点l关于文法和语言的概念是形式语言的理论基础,形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。2022/12/215知识结构2022/12/216引言和预备知识l高级语言程序语言是一个记号系统语法语义l语法任何语言程序都可以看成是一定字符集(字母表)上的字符串语法使得这串字符形成一个形式上正确的程序语法=词法规则+语法规则l例如:0.5*x1+c0.5、x1、c、*、+是语言的单词符号0.5*x1+c是语言的语法单位l词法单词符号l语言中具有独立意义的最基本结构词法规则l词法规则规定了
3、字母表中哪些字符串是单词符号l单词符号一般包括:常数、标识符、基本字、算符、界限符等我们用正规式和有限自动机理论来描述词法结构和进行词法分析l语法单词符号语法单位l表达式、子句、语句、函数、过程、程序语法规则l规定了如何从单词符号来形成语法单位l现在多数程序语言使用上下文无关文法来描述语法规则l语言的词法规则和语法规则定义了程序的形式结构,是判断输入字符串是否构成一个形式上正确的程序的依据例,对于一个PASCAL程序来说,一个上下文无关文法可以定义 A:=B+C 是合乎语法的,而A:=B+是不合乎语法的。l语义对于一个语言来说,不仅要给出它的词法、语法规则,而且要定义它的单词符号和语法单位的意
4、义离开语义,语言只是一堆符号的集合各种语言中有形式上完全相同的语法单位,含义却不尽相同对某种语言,可以定义一个程序的意义的一组规则称为语义规则目前,大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义l对于高级程序设计语言及其编译程序来说,语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题,编译原理的主要内容也可以归纳为应用形式语言理论,并将它贯穿于词法分析和语法分析两个阶段2022/12/21143.2 符号和符号串 任任何何一一种种语语言言都都是是由由该该语语言言的的基基本本符符号组成的符号串的集合。号组成的符号串的集合。l 基本符号集基本符号集l 任任何何语语言言的的单单
5、词词符符号号就就是是定定义义在在它它的的字符集上的字符串字符集上的字符串l该该语语言言的的任任何何语语句句就就是是定定义义在在其其单单词词符符号集上的单词串号集上的单词串(符号串符号串)2022/12/2115l字母表字母表:是元素的非空有穷集合,把字母表中的元素称为符号,因此字母表也称符号集。例,a,b,c,+,就是含有5个元素的一个字母表。一般用和V来表示l符号符号:是语言当中最基本的不可再分的单位2022/12/2116l符号串符号串:字母表中的符号所组成的任何有穷序列。例,V=a,b,c是一个字母表,则a,b,c,aa,ab,bc,abc等等都是V上的符号串l空串空串:不含有任何符号的
6、串称为空串,记作l句子句子:字母表上符合某种规则构成的串l语言:语言:字母表上句子的集合l注:约定用a,b,c表示符号;用,表示符号串;用A,B,C表示其集合2022/12/2118l符号串的长度符号串的长度:如果某符号串中有m个符号,则其长度为m,记为|=m。例,|abc|=3 的长度为0l符号串的连接符号串的连接:设和是符号串,它们的连接是把的符号写在的符号之后得到的符号串。例,若=NPU,=1108,则=NPU1108,=1108NPUl符号串的方幂符号串的方幂:设是符号串,把自身连接n次得到符号串,即=,称为符号串的方幂,写作=n。l符号串集合符号串集合:若集合A中的一切元素都是某字母
7、表上的符号串,则称A为字母表上的符号串集合。2022/12/2119l两个符号串集合A和B的乘积(连接):AB=|A且 B注:1)串集的自身乘积称作串集的方幂 2)A0=l字母表V的n次方幂是字母表V上所有长度为n的串集2022/12/21202022/12/2121l字母表字母表V的闭包的闭包V*和正闭包和正闭包V+:字母表上的语言,是字字母表上的语言,是字母表上正闭包的子集。母表上正闭包的子集。2022/12/21223.1 文法的直观概念 文文法法的的定定义义 对对语语言言结结构构的的描描述述和和定定义义,即即在在形形式式上上用用来来描描述述和和规规定定语语言言结结构的称为构的称为“文法
8、文法”(或或“语法语法”)。比如:“我是大学生。”是汉语的一个句子汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|2022/12/21232022/12/2124l一旦有了一组规则以后,我们可以按照如下方式用它们去推导或产生句子。我们开始去找:=左端的带有句子的规则并把它表示成:=右端的符号串l规则中的“:=”也常用“”表示,含义是使用一条规则,代替=左边的某个符号,产生右端的符号串。l 注意文法中,描述某个特定的语法成分的规则可能不只一条。2022/12/2125得到句子得到句子“我是大学生我是大学生”的全
9、部动作过程是:的全部动作过程是:我我 我我 我是我是 我是我是 我是大学生我是大学生2022/12/2126“我是大学生”的构成是符合上述规则“我大学生是”不符合上述规则这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。2022/12/21273.3 文法和语言的形式定义 前面已经对规则(或产生式)的概念进行了非形式化的说明,我们已经对其有了一个直观的了解。下面将对其进行形式化说明,并在此基础上抽象地定义文法和语言。2022/12/2128l文法文法G定义为四元组(定义为四元组(VN,VT,P,
10、S)VN:非终结符集:非终结符集VT:终结符集:终结符集P:产生式(规则)集合:产生式(规则)集合S:开始符号(或识别符号):开始符号(或识别符号)VNVT=,SVNV=VNVT,称为文法,称为文法G的文法符号集合的文法符号集合定义3.12022/12/2129l句子的语法结构,可以用一组规则来描述。l规则也称为“重写规则”、“产生式”或“生成式”,是形如或:=的(,)有序对,且V+,V*,V为某字母表。称为规则的左部(或产生式或产生式的左部的左部)称为规则的右部(或产生式或产生式的右部的右部)l这里使用的符号(:=)读作“定义为”2022/12/2130例例3.1 文法文法G=(VN,VT,
11、P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号2022/12/2131例例3.2 文法文法G=(VN,VT,P,S)VN=标识符,字母,数字标识符,字母,数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,9 S=2022/12/2132l习惯上不用将文法习惯上不用将文法G的四元组显示地表示出的四元组显示地表示出来,只将产生式写出。并有如下约定:来,只将产生式写出。并有如下约定:第一条产生式的左部是开始符号第一条产生式的左部是开始符号用尖括号括起的是非终结符,否则为终结符。或用尖括号括起的是非终结符,否则为终结符。或者大写字母表示非终结符,小写字母表示终
12、结符者大写字母表示非终结符,小写字母表示终结符G可写成可写成GS,S是开始符号是开始符号 G:S0S1 S01 GS:S0S1 S012022/12/2133l有时,为书写简洁,常把相同左部的产生式,有时,为书写简洁,常把相同左部的产生式,形如形如 A a1,Aa2 Aan 缩写缩写为:为:Aa1|a2|.|an 注意:元符号注意:元符号“|”读作读作“或或”2022/12/2134l一个文法的几种写法一个文法的几种写法例:例:G=(S,A,a,b,P,S)其中:其中:P:SaAb Aabab AaaAb A G:SaAb Aab AaAb A GS:Aabab AaaAb A SaaAb G
13、S:Aabab|a aAb|SaaAb2022/12/2135l直接推导直接推导“”定义定义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,可以给可以给出直接推导的一些例子如下:出直接推导的一些例子如下:lv=0S1,w=0011,直接推导:,直接推导:0S1 0011,使用的规则:使用的规则:S01,这里这里=0,=1。lv=
14、S,w=0S1,直接推导:直接推导:S 0S1,使用的,使用的规则:规则:S0S1,这里这里=,=lv=0S1,w=00S11,直接推导:,直接推导:0S1 00S11,使用的规则:使用的规则:S0S1,这里这里=0,=1。2022/12/2136对于例对于例3.2的文法的文法G,直接推导的例子有:,直接推导的例子有:lv=,w=,直接推导:,直接推导:,使用的规则:,使用的规则:,这里,这里=lv=,w=,直接推导:,直接推导:,使用的规则:,使用的规则:。这里这里=,。lv=abc,w=abc5,直接推导:,直接推导:abc abc5,使用的规则:使用的规则:5,这里,这里=abc,=20
15、22/12/21372022/12/2138定义定义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,也可记作,也可记作0S1 00001111对例对例3.2的文法,存在直接推导序列的文法,存在直接推导序列v=x x1=w,即
16、即 x1,也可记作,也可记作 x12022/12/21392022/12/2140文法的句型、句子的定义文法的句型、句子的定义l句型句型有文法有文法GS,若,若S x,则称,则称x是文法是文法G的句型。的句型。l句子句子有文法有文法GS,若,若S x,且,且xVT*,则称,则称x是文是文法法G的句子。的句子。例:例:G:S0S1,S01S 0S1 00S11 000S111 00001111S,0S1,000111都是文法都是文法G的句型,其中的句型,其中00001111是是G的句子。的句子。2022/12/2141定义定义3.6 由文法由文法G所产生的语言记为所产生的语言记为L(G),它是文
17、法,它是文法G的一切句子的集合的一切句子的集合:L(G)=x|S x,其中,其中S为文法的开始符号,为文法的开始符号,且且x VT*例例:G:S0S1,S01 L(G)=0n1n|n12022/12/2142l例例3.3 文法文法GS:(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEee2022/12/2143 S aSBE (SaSBE)aaSBEBE (SaSBE)aaaBEBEBE (SaBE)aaaBBBEEE (EBBE)aaabBBEEE (aBab)aaabbBEEE aaabbbEEE (bBbb)aaabbbeEE (bEbe)
18、aaabbbeeE aaabbbeee (eEee)L(G)=anbnen|n1 2022/12/2144文法的等价文法的等价l若若L(G1)=L(G2),则称文法,则称文法G1和和G2是等价的。是等价的。如文法如文法G1A:A0R 与与G2S:S0S1 等价等价 A01 S01 RA12022/12/21453.4 文法的类型文法的类型lChomsky将文法分为四种类型:将文法分为四种类型:l0型文法:型文法:G=(VN,VT,P,S)对任一产生式对任一产生式 ,都有都有(VNVT)*,且至少含有一个非终结符,且至少含有一个非终结符,(VNVT)*l0型文法(短语文法)的能力相当于图灵型文法
19、(短语文法)的能力相当于图灵机,可以表征任何递归可枚举集,而且机,可以表征任何递归可枚举集,而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的2022/12/2146 有限控制器有限控制器磁头磁头 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an l1型文法(上下文有关文法):设型文法(上下文有关文法):设G=(VN,VT,P,S)为一文法,若为一文法,若P中的每一个中的每一个产生式产生式 ,都有,都有|,仅仅仅仅 S 除外除外l1型文法也可描述为型文法也可描述为 1A 2 12,其其中中 1、2和和 都在都在V*中,中,A在在VN中。中。即只有即只有A出现在
20、出现在 1和和 2的上下文中时,才的上下文中时,才允许允许 取代取代A。2022/12/21472022/12/2148l例:例:1型(上下文有关)文法型(上下文有关)文法 文法文法GS:SaSBESaBEEBBEaBabbBbbbEbeeEeel2型文法(上下文无关文法):型文法(上下文无关文法):设设G=(VN,VT,P,S),若,若P中的每一个中的每一个产生式产生式 满足:满足:是一非终结符,是一非终结符,(VNVT)*l有时将有时将2型文法的产生式表示为形如:型文法的产生式表示为形如:A 其中其中AVN,也就是说用,也就是说用 取代非取代非终结符终结符A时,与时,与A所在的上下文无关,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 第三章 文法和语言 编译 原理 第三 文法 语言
限制150内