编译原理第三章文法和语言

《编译原理第三章文法和语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/7/241第三章文法和语言课前思考◇高级语言有哪些一般特性？◇你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？◇学习编译程序为什么要研究语言的描述问题？2021/7/242学习目标本章目的是为语言的语法描述寻求工具◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。◇熟练使用文法定义程序设计语言的单词和语法成分◇对形式语言的理论有一个初步基础2021/7/243学习指南◇什么是文法,什么是它定义的语言？◇在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？◇什么是语法分析

2、？语法分析方法的分类？2021/7/244难重点关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。2021/7/245知识结构2021/7/246引言和预备知识高级语言程序语言是一个记号系统语法语义语法任何语言程序都可以看成是一定字符集（字母表）上的字符串语法使得这串字符形成一个形式上正确的程序语法=词法规则+语法规则例如：0.5*x1+c0.5、x1、c、*、+是语言的单词符号0.5*x1+c是语言的语

3、法单位词法单词符号语言中具有独立意义的最基本结构词法规则词法规则规定了字母表中哪些字符串是单词符号单词符号一般包括：常数、标识符、基本字、算符、界限符等我们用正规式和有限自动机理论来描述词法结构和进行词法分析语法单词符号语法单位表达式、子句、语句、函数、过程、程序语法规则规定了如何从单词符号来形成语法单位现在多数程序语言使用上下文无关文法来描述语法规则语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据例，对于一个PASCAL程序来说，一个上下文无关文法可以定义A:=B+C是合乎语法的，而A:=B+是

4、不合乎语法的。语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义离开语义，语言只是一堆符号的集合各种语言中有形式上完全相同的语法单位，含义却不尽相同对某种语言，可以定义一个程序的意义的一组规则称为语义规则目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段2021/7/24143.2符号和符号串任何一种语言都是

5、由该语言的基本符号组成的符号串的集合。基本符号集任何语言的单词符号就是定义在它的字符集上的字符串该语言的任何语句就是定义在其单词符号集上的单词串(符号串)2021/7/2415字母表：是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称符号集。例，{a，b，c，+，﹒}就是含有5个元素的一个字母表。一般用∑和V来表示符号：是语言当中最基本的不可再分的单位2021/7/2416符号串：字母表中的符号所组成的任何有穷序列。例，V={a，b，c}是一个字母表，则a，b，c，aa，ab，bc，abc等等都是V上的符号串空串：不含有任何符号的串

6、称为空串，记作句子：字母表上符合某种规则构成的串语言：字母表上句子的集合注：约定用a,b,c…表示符号；用,,…表示符号串；用A,B,C表示其集合2021/7/2418符号串的长度：如果某符号串中有m个符号，则其长度为m，记为

7、

8、=m。例，

9、abc

10、=3的长度为0符号串的连接：设和是符号串，它们的连接是把的符号写在的符号之后得到的符号串。例，若=NPU，=1108，则=NPU1108，=1108NPU符号串的方幂：设是符号串，把自身连接n次得到符号串，即=…，称为符号串的方幂，写作=

11、n。符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。2021/7/2419两个符号串集合A和B的乘积（连接）：AB={

12、A且B}注：1）串集的自身乘积称作串集的方幂2）A0={ɛ}字母表V的n次方幂是字母表V上所有长度为n的串集2021/7/24202021/7/2421字母表V的闭包V*和正闭包V+：字母表上的语言，是字母表上正闭包的子集。2021/7/24223.1文法的直观概念文法的定义∶对语言结构的描述和定义，即在形式上用来描述和规定语言结构的称为“文法”(或“语法”)。比如：“我是大学生。

13、”是汉语的一个句子汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语<句子>::=<主语><谓语><主语>::=<代词>

14、<名词><代词>: