华中科技大版 编译原理课件

华中科技大学出版社出版,编译原理课件,主编何炎祥

第二章 形式语言概论本章主要介绍形式语言理论中的一些最 基本的概念和基础知识，它是学习以后 各章节的基石。

华中科技大学出版社出版,编译原理课件,主编何炎祥

内容回顾(1)翻译程序作用

翻译程序

编译方法解释方法

编译程序概述编译的组成和流程 编译程序结构

编译各部分的功能 编译的实施和逻辑结构

华中科技大学出版社出版,编译原理课件,主编何炎祥

内容回顾(2)信息表管理程序

源 程 序

词 法 分 析 程 序

语 法 分 析 程 序

语 义 分 析 程 序

中 间 代 码 生 成

代 码 优 化 程 序

目 标 代 码 生 成

目 标 代 码

错误检查和处理程序编译程序结构

华中科技大学出版社出版,编译原理课件,主编何炎祥

内容概要符号的有穷集合

一个语言的成分包括字母表(Alphabet),文法 (Grammar)以及它的语义。 结构规则的

形式语言理论

操作规则的 有穷集合

有穷集合

Chomsky于1956年提出 讨论语言和文法的数学机制以及语言和文法的分类

是编译程序的重要理论基础

本章将主要讨论字母表、符号串、产生式文法系 统以及句子分析等方面的内容。

华中科技大学出版社出版,编译原理课件,主编何炎祥

2.1 字母表与符号串字母表：元素的非空有穷集合。记作∑。

符号：字母表中的元素。符号串：符号的有穷序列。

空符号串：什么符号也不包括的符号串，记作ε。

符号串的运算

② 符号串的长度。 ③ 符号串的连接。 ④ 符号串集合的乘积。 ⑤ 符号串的方幂。 ⑥ 符号串集合的方幂。 ⑦ 符号串集合的正闭包。 ⑧ 符号串集合的自反闭包。

华中科技大学出版社出版,编译原理课件,主编何炎祥

符号串的长度符号串所包含符号的个数，称为符号串的长度。设x是一符 号串，它的长度记为|x|,|ε| = 0

符号串的连接设x,y是两个符号串，则xy称为x与y的连接。

符号串集合的乘积设A、B是两个符号串集合，AB表示A与B的乘积，则定义

AB={xy | x A, y B}Example

设A={ ab, c }, B= { d, efg },则 AB={abd, abefg, cd, cefg}

华中科技大学出版社出版,编译原理课件,主编何炎祥

符号串的方幂同一符号串的连接可写成方幂形式。设x是一符号串，则定 义 x0 = ε, x1 = x, x2 = xx, x3 = xxx,…

符号串集合的方幂A0 = {ε}, A1 = A, A2 = AA, A3 = AAA,…

符号串集合的正闭包和自反闭包设符号串集合A,A的正闭包记为A+,自反闭包记为A*,则

A+=A1∪A2∪… ∪ An∪… A*={ε}∪A+ = A+∪ {ε}

华中科技大学出版社出版,编译原理课件,主编何炎祥

、{}、 { }的区别

特别指出的是：

是空符号串, 不是集合

{ }表示由空符号串 所组成的集合Φ={} , 表示空集

Φ,即空符号串不等于空集

华中科技大学出版社出版,编译原理课件,主编何炎祥

2.2 文法及其分类

文法: 定义或描述语言的语法结构的一组形式规则。

He gave me a book.<句子> <主语><谓语><间接宾语><直接宾语> <主语> <代词> <谓语> <动词> <间接宾语> <代词> <直接宾语> <冠词> <名词> <代词> He <代词> me <名词> book <冠词> a

<动词> gave

华中科技大学出版社出版,编译原理课件,主编何炎祥

2.2.1 产生式的定义

定义2.1 设VN、 VT分别是非空有限的非终结符号集 和终结符号集，V= VT ∪ VN ,VT VN= 。一个产 生式是一个序偶对(α ,β ),其中,α V+, β V* ,通常表示为 α →β 或 α ::=β

如果产生式集合中的产生式有共同的左部，如 α →β ,α →γ ,则可简写为 α →β |γ

华中科技大学出版社出版,编译原理课件,主编何炎祥

文法的定义

定义2.2 文法G是一个四元组， G=(VT,VN,S,P) ,其中， VN、 VT分别是非空有限的非终结符号集 和终结符号集， VT VN= ,P是产生式集，S VN 称为文法的识别符号或开始符号。

例2.1 文法

G1=(VT,VN,S,P) VN={S,B,C,D} VT={a,b,c} P={S→aSBC, S→abc, CB→CD, CD→BD, BD→BC, bB→bb, bC→bc, cC→cc}

华中科技大学出版社出版,编译原理课件,主编何炎祥

2.2.2 文法分类0型文法又称为短语结构文法 ，它的能力相当于图灵机。 若对0型文法的产生式作某些 限制，则可给出其它三种类型 Chomsky将文法分为四种类型：0型、1型、2型和3 的文法。

型。

0型文法(无限制的文法)

其产生式具有以下形式： 0型文法 → G1=(VT,VN,S,P) VN={S,B,C,D} 其中， (VN∪VT)+, (VN∪VT)* VT={a,b,c} P={S→aSBC, S→abc, CB→CD, CD→BD, BD→BC, bB→bb, bC→bc, cC→cc}

华中科技大学出版社出版,编译原理课件,主编何炎祥

文法分类

符号串 1和 2可以认 为是上下文，其间的 A可以被符号串 替代 ，因此1型文法又称为 上下文有关文法。

1型文法(上下文有关文法) 其产生式具有以下形式：

→ 1型文法 其中 = 1A 2 ; = 1 2 ; 1 , 2 (VN∪VT)* ;A VN ; G6=(VN,VT,P,S) (VN={S,X,Y,Z} ∪VT)+。 其中， VN

VT={x,y,z} P={S→xSYZ xYZ, xY→xy,yY→yy, yZ→yz zZ→zz}

华中科技大学出版社出版,编译原理课件,主编何炎祥

文法分类

2型文法产生式的左部是单个非终结符 ，右部是由终结符和非终结符组成的 符号串。2型文法又称为上下文无关文 法。很适合描述现今的程序设计语言 ，是我们学习的重点。

2型文法(上下文无关文法) 在1型文法的产生式中，上下文 1和 2用空符号串 代替，则有以下形式的产生式，称为2型文法： A→ 2型文法

G3=(VN,VT,P,E)

其中，

其中，A VN, (VN∪VT)+。VN={E,T,F}VT={+,*,(,),i } P={E→E+T T,T→T F F,F→(E) i }

华中科技大学出版社出版,编译原理课件,主编何炎祥

文法分类

3型文法(右线性文法和正规文法) 如果P中的产生式只含有下面的两种形式：

A→a ,

A→aB

3型文法 则称该文法为3型文法，又称为右线性文法或正规 G4=(VN,VT,P,S) 文法。其中，A,B VN,a VT*。 其中， V ={S,A,B}N

VT={0, 1 } P={S→0 1 1A 0B,A→1A 0B,B→0 1 0B }

华中科技大学出版社出版,编译原理课件,主编何炎祥

四种类型描述能力比较

0型

1型 2型3型