第二章文法和形式语言 《编译原理》课程组 计算机工程学院 第二章文法和形式语言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法机器语法树 2.6 句型分析 2.7 文法的实用限制 第2章文法和语言 【学习目标】 本章目的是为语言的语法描述寻求工具 ◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。 ◇对形式语言的理论有一个初步基础 ◇根据语言文法的特点指导语法分析的过程 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 第2章文法和语言 【教学重点】 概念：文法，推导，直接推导，最左(右)推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等 4种文法的定义、文法的构造和文法的推导 语法树的构造和最左（右）推导； 二义文法、二义性的证明； 句型分析； 2.1 文法的直观概念 一、语言概述 语言是由符合语法的句子组成的集合。 –汉语-- 所有符合汉语语法的句子的全体 –英语-- 所有符合英语语法的句子的全体 –程序设计语言-- 所有该语言的程序的全体
每个句子构成的规律 研究语言每个句子的含义 每个句子和使用者的关系 一、语言概述（续1） 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法Syntax 语义Semantics 语用Pragmatics 一、语言概述（续2） 语法：指语言的一组规则，用它可以形成和产生一个合适的程序。 –如何由基本字符构成一个个单词； –如何由一系列单词构成程序 语法只定义什么样的符号序列是合法的，而不表达这些符号及符号序列的含义 语义：明确程序各部分的含义 –静态语义：由一系列限定规则组成，并确定哪些合乎语法的程序是合适的； –动态语义：表明程序要做些什么，要计算什么 一、语言概述（续3） 形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性， –语言的形式 –该形式相关联的意义 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 二、文法的直观概念 表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷= 我| 你| 他 〈名词〉∷= 王明| 大学生| 工人| 英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是| 学习 〈直接宾语〉∷=〈代词〉|〈名词〉
第二章文法和语言的概念和表示 本章概述 本章中，我们将概述高级程序语言的结构和主要的共同特征，并介绍程序语言的语法描述方法。 主要学习内容：程序设计语言的定义，高级语言的一般特性，高级语言的语法描述，上下文无关文法，语法分析树和二义性，乔姆斯基文法体系。 学习目标：理解程序语言的词法、语法和语义等概念，进一步掌握高级程序设计语言的一般结构和主要共同特征，使学生具有必要的基础知识；理解文法和语言的一些基本概念，如文法的定义和构造、句型、句子、语言、推导、语法树等。 学习重点和难点：语法，语义，文法的构造。 2.1 概述 显然，用高级语言编程比用低级语言来得方便，但要解决两个问题： 1.计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。 2.用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。 任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。 “我是大学生”是汉语的一个句子。 用语法来描述： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了这一组规则以后，按照如下方式用它们导出句子： 开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成： 〈句子〉?〈主语〉〈谓语〉， 然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉?〈代词〉〈谓语〉， 重复做下去，这样句子“我是大学生”的导出的全部动作过程是： 〈句子〉?〈主语〉〈谓语〉 ?〈代词〉〈谓语〉