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

2025/5/241第三章

文法和语言

2025/5/242课前思考高级语言有哪些一般特性？你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？学习编译程序为什么要研究语言的描述问题？

2025/5/243学习目标本章目的是为语言的语法描述寻求工具掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础

2025/5/244学习指南什么是文法,什么是它定义的语言？在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？什么是语法分析？语法分析方法的分类？

2025/5/245难重点关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。

2025/5/246知识结构

高级语言程序语言是一个记号系统语法语义引言和预备知识

12任何语言程序都可以看成是一定字符集（字母表）上的字符串语法使得这串字符形成一个形式上正确的程序语法=词法规则+语法规则语法0.5、x1、c、*、+是语言的单词符号5*x1+c是语言的语法单位例如：0.5*x1+c

我们用正规式和有限自动机理论来描述词法结构和进行词法分析单词符号一般包括：常数、标识符、基本字、算符、界限符等04单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。词法规则规定了字母表中哪些字符串是单词符号03词法规则语言中具有独立意义的最基本结构02单词符号词法01

语法单词符号语法单位表达式、子句、语句、函数、过程、程序语法规则规定了如何从单词符号来形成语法单位现在多数程序语言使用上下文无关文法来描述语法规则语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据

添加标题而A:=B+是不合乎语法的。添加标题A:=B+C是合乎语法的，添加标题例，对于一个PASCAL程序来说，一个上下文无关文法可以定义

语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义离开语义，语言只是一堆符号的集合各种语言中有形式上完全相同的语法单位，含义却不尽相同对某种语言，可以定义一个程序的意义的一组规则称为语义规则目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义

对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段

2025/5/24143.2符号和符号串任何一种语言都是由该语言的基本符号组成的符号串的集合。基本符号集任何语言的单词符号就是定义在它的字符集上的字符串该语言的任何语句就是定义在其单词符号集上的单词串(符号串)

2025/5/2415符号：是语言当中最基本的不可再分的单位字母表：是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称符号集。例，{a，b，c，+，﹒}就是含有5个元素的一个字母表。一般用∑和V来表示

2025/5/2416符号串：字母表中的符号所组成的任何有穷序列。例，V={a，b，c}是一个字母表，则a，b，c，aa，ab，bc，abc等等都是V上的符号串空串：不含有任何符号的串称为空串，记作?

句子：字母表上符合某种规则构成的串语言：字母表上句子的集合注：约定用a,b,c…表示符号；用?,?,?…表示符号串；用A,B,C表示其集合

2025/5/2418符号串的长度：如果某符号串?中有m个符号，则其长度为m，记为|?|=m。例，|abc|=3?的长度为0符号串的连接：设?和?是符号串，它们的连接??是把?的符号写在?的符号之后得到的符号串。例，若?=NPU，?=1108，则??=NPU1108，??=1108NPU

2025/5/2419符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串的方幂：设?是符号串，把?自身连接n次得到符号串?，即?=???…??，称为符号串?的方幂，写作?=?n。

2025/5/2420两个符号串集合A和B的乘积（连接）：AB={??|?A且?B}注：1）串集的自身乘积称作串集的方幂A0={?}字母表V的n次方幂是字母表V上所有长度为n的串集

2025/5/2421字母表V的闭包V*和正闭包V+：字母表上的语言，是字母表上正闭包的子集。

2025/5/24223.1文法的直观概念文法的定义∶对语