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