编译原理全册配套完整精品课件.ppt

1、编译原理全册配套完整精品课件编译原理全册配套完整精品课件 编译原理 3 自我介绍自我介绍 n姓名：刘善梅姓名：刘善梅 nQQQQ ： 3068353030683530 n办公室：逸夫楼办公室：逸夫楼C427C427 n 邮箱：邮箱： 4 课程介绍课程介绍 n两门独立的课程：理论（两门独立的课程：理论（4848学时）学时） 实验（实验（1616学时）学时） n考试成绩组成考试成绩组成 理论：理论：平时作业和考勤占平时作业和考勤占20%20%，期末结业，期末结业 考试占考试占80%80%； 实验：实验：根据实验报告和程序源代码评分，根据实验报告和程序源代码评分， 实验报告占实验报告占40%, 40

2、%, 程序源代码占程序源代码占60%60%。 n课程特点：课程特点：难！难！ 5 开课目的：开课目的：介绍设计与构造程序设计语言介绍设计与构造程序设计语言编译程序编译程序的的 原理与方法原理与方法 源程序源程序 编译编译 程序程序 目标程序目标程序 连接连接 可执行程序可执行程序 预备知识：预备知识：形式语言与自动机、形式语言与自动机、两门以上的高两门以上的高 级程序设计语级程序设计语 言言 汇编语言汇编语言 数据结构等数据结构等 How? 6 教学要求教学要求 通过课程的学习和实验的完成，通过课程的学习和实验的完成， 应该应该清楚的理解一个编译程序是如何工作的；清楚的理解一个编译程序是如何工

3、作的； 如果在以后遇到了任何一个程序设计语言，如果在以后遇到了任何一个程序设计语言，应该应该 知道如何实现这个语言的多数机制；知道如何实现这个语言的多数机制； 应应具有一定的使用编译构造工具开发编译程序的具有一定的使用编译构造工具开发编译程序的 经验；经验； 会会将所学的常用技术和算法应用于类似的软件的将所学的常用技术和算法应用于类似的软件的 设计和实现中。设计和实现中。 理论课内容简介：理论课内容简介： 第一章：绪论 第二章：编译基础(形式语言 、有穷自动机等） 第三章：词法分析 第四章：语法分析 第五章：语法制导翻译和中间代码生成 第七章：程序运行时的存贮分配问题 第八章：代码优化 第九章

4、：目标代码生成 第六章：符号表 实验课内容简介：实验课内容简介： 第一次课：词法分析 （4学时） 第二次课：语法分析 （4学时） 第三次课：词义分析、代码生成 （4学时） 第四次课：小型C语言编译器设计（4学时） 详细实验内容请见实验要求和实验指导书 9 教材：教材：编译原理编译原理（第（第2版），张素琴、吕映芝、蒋维杜、戴桂版），张素琴、吕映芝、蒋维杜、戴桂 兰，清华大学出版社兰，清华大学出版社 2004 参考书：参考书： 教材及主要参考书教材及主要参考书 Compilers: Principles, Technigues, and Tools Alfred V.Aho, Ravi Seth

5、i, Jeffrey D.Ullman, Addison-Wesley,1986. 译著版：机械工业出版社，译著版：机械工业出版社，2003，李建中，姜守旭译。，李建中，姜守旭译。(龙书）龙书） 中文名：编译原理技术和工具中文名：编译原理技术和工具 Modern Compiler Implementation in Java Modern Compiler Implementation in C Andrew W.Appel，人民邮电出版社影印，人民邮电出版社影印，2005 （虎书）（虎书） 中文名：现代编译原理中文名：现代编译原理 Advanced Compiler Design and I

6、mplementation Steven S. Muchnick, 1997. 机械工业出版社影印机械工业出版社影印，2003 （鲸书）（鲸书） 中文名：高级编译器设计与实现中文名：高级编译器设计与实现 内地 内地 陈火旺（国防科大版）陈火旺（国防科大版） 陈意云（中国科技大学版）陈意云（中国科技大学版） 王生原等（人民邮电版）王生原等（人民邮电版） 王生原等（清华大学第三版）王生原等（清华大学第三版） 主要参考书主要参考书 11 第一章绪论第一章绪论 n编译器就是一个编译器就是一个程序程序，它，它读入读入用某种语言用某种语言 编写的源程序，并编写的源程序，并翻译翻译成一个成一个与之等价与之等

7、价的的 另一种语言编写的源程序。另一种语言编写的源程序。 编译器编译器源程序源程序 目标程序目标程序 错误信息错误信息 Fortran、 Pascal、 Java、 C . 另一种程序另一种程序 设计语言、设计语言、 汇编语汇编语 言、机言、机 器语言器语言 1.1什么是编译程序什么是编译程序 什么是编译程序什么是编译程序 编译程序编译程序通常通常是是从较高级语言的程序翻译从较高级语言的程序翻译 至较低级语言的程序至较低级语言的程序，如，如 C 代码 汇编代码a C compiler C+ 代码 汇编代码a C+ compiler C+ 代码 C代码 another C+ compiler J

8、ava 代码 Bytecode代码 a Java compiler 13 1.2编译过程概述编译过程概述 编译程序的工作，从输入源程序开始，到输出目编译程序的工作，从输入源程序开始，到输出目 标程序结束，与自然语言之间的翻译有很多相似之处。标程序结束，与自然语言之间的翻译有很多相似之处。 一段英文翻译成中文，一段英文翻译成中文， 需经下列步骤：需经下列步骤： 识别出句子中的单词识别出句子中的单词 分析句子的语法结构分析句子的语法结构 根据句子的含义进行初步分析根据句子的含义进行初步分析 对译文进行修饰对译文进行修饰 写出最后的译文写出最后的译文 编译程序编译程序 词法分析词法分析 代码优化代码

9、优化 语法分析语法分析 语义分析及中语义分析及中 间代码生成间代码生成 目标代码生成目标代码生成 构成编译程构成编译程 序各个阶段序各个阶段 I am a teacher. 14 编译器的各个阶段：编译器的各个阶段： 编译器是分编译器是分 阶段执行的。阶段执行的。 每个阶段将源程每个阶段将源程 序从一种表示转序从一种表示转 换成另一种表示换成另一种表示 源程序源程序 词法分析器词法分析器 错错 误误 处处 理理 器器 符符 号号 管管 理理 表表 语法分析器语法分析器 语义分析器语义分析器 中间代码生成器中间代码生成器 代码优化器代码优化器 代码生成器代码生成器 编译的各编译的各 个阶段个阶段

10、 15 各分析阶段各分析阶段 随着编译器各个阶段的进展，源程序的内部表示不随着编译器各个阶段的进展，源程序的内部表示不 断地发生变化。断地发生变化。 以以a=b+c *d为例为例 1。词法分析。词法分析 读入源程序读入源程序 完成的任务：完成的任务： 识别出单词：识别出单词： a、=、b、+、c 、 *、 、 d 并用记号方式表示识别出的单词并用记号方式表示识别出的单词 关键字、标识关键字、标识 符、常数、算符、常数、算 符和界符符和界符 例：例：25表示表示a、b、c、d；36：；：；2：；：；31： ：* 记号表示逻辑记号表示逻辑 上相关的字符上相关的字符 序列，常用整序列，常用整 数来表

11、示数来表示 上述单词表示为：上述单词表示为：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*), (25,d) n程序文本程序文本If x = y then z := 1 else z := 2; 经经词法分析，变成一个个单词词法分析，变成一个个单词 nif, x, =, y, then, z, :=, 1, else, z, :=, 2, ; n语言的单词符号是由语言的单词符号是由词法规则词法规则所确定的。所确定的。词法词法 规则规则规定了字母表中哪样的字符串是一个单词规定了字母表中哪样的字符串是一个单词 符号。符号。 又又例例， ， 从左至右扫描字符流的源程

12、序从左至右扫描字符流的源程序、分解构成源、分解构成源 程序的字符串，程序的字符串，识别出识别出(拼拼)一个个的一个个的单词单词 （符号）（符号） 单词符号是语言中具有独立意义的最基本单词符号是语言中具有独立意义的最基本 结构。多数程序语言中，结构。多数程序语言中，单词单词符号一般符号一般 包括包括 各类型的各类型的常数、保留字、标识符常数、保留字、标识符 、运算符、界符、运算符、界符等等。等等。 词法分析词法分析第一步识别单词第一步识别单词 position := initial + rate * 60; 单词类型单词类型单词值单词值 标识符标识符1(id1) position 算符算符(赋值

13、赋值) := 标识符标识符2(id2) initial 算符算符(加加) + 标识符标识符3(id3) rate 算符算符(乘乘) * 整数整数 60 分号分号 ； 词法分析词法分析 19 语法分析语法分析 在词法分析的基础上，根据语言的语法规则，在词法分析的基础上，根据语言的语法规则， 把单词符号串组成各类语法单位把单词符号串组成各类语法单位. 具体的说，语法分析是在单词流的基础上建立具体的说，语法分析是在单词流的基础上建立 一个层次结构一个层次结构-建立语法树建立语法树 赋值语句赋值语句 标识符标识符 = 表达式表达式 id1表达式表达式 标识符标识符 id2 +表达式表达式 表达式表达式

14、 * 标识符标识符 id3 表达式表达式 整数整数 60 语法分析语法分析 举例举例 id1 := id2 + id3 * 60 ; （Pascal）语法规则）语法规则 :=“:=” :=“+” :=“*” :=“(”“)” := := := 赋值语句赋值语句 标识符标识符表达式表达式 表达式表达式+ 表达式表达式表达式表达式 标识符标识符整数整数 标识符标识符 := 表达式表达式 * id1:=id2+id3*60 := + 60 * id1 id2 id3 23 语义分析阶段语义分析阶段 语义分析利用语法分析阶段确定的层次结构来识别语义分析利用语法分析阶段确定的层次结构来识别 表达式和语句

15、中的操作信息及类型信息表达式和语句中的操作信息及类型信息 = + a b * c d temp1=c*d temp2=b+temp1 temp1 temp2 a=temp2 语义分析语义分析 n 句子的结构理解了，句子的结构理解了，扑捉它的扑捉它的“含义含义” 如：杰克说杰瑞把他的作业落在了家里。如：杰克说杰瑞把他的作业落在了家里。 “他的他的”是谁的？是谁的？ 又：杰克说杰克把他的作业落在了家里。又：杰克说杰克把他的作业落在了家里。 几个杰克？几个杰克？ n杰克把她的作业落在了家里。杰克把她的作业落在了家里。 （杰克是男生）（杰克是男生）“杰克杰克”和和“她的她的”不一致。不一致。 “杰克杰

16、克”和和“他的他的”才匹配才匹配 语义分析语义分析 26 中间代码生成阶段中间代码生成阶段 本阶段将产生源程序的一个显式中间表示本阶段将产生源程序的一个显式中间表示 这种中间表示可以看成是某种抽象的程这种中间表示可以看成是某种抽象的程 序，通常是与平台无关的序，通常是与平台无关的 其重要性质：其重要性质：1.易于产生易于产生 2.易于翻译成目标程序易于翻译成目标程序 下面是用下面是用三地址码三地址码（四元式）（四元式）表示的例子：表示的例子： temp1=c*d temp2=b+temp1 a=temp2 （* , c , d , tempt1) (+ , b, tempt1 , tempt2

17、) (= , tempt2 , , a) id1:= id2 + id3 * 60 (1)(inttoreal, 60, ,t1) (2)(*,id3,t1,t2) (3)(+,id2,t2,t3) (4)(:=,t3,id1) 28 代码优化阶段代码优化阶段 对代码进行变换对代码进行变换以使得编译产生的目标代码更高效以使得编译产生的目标代码更高效 （执行速度更快）（执行速度更快）。 对上面中间代码进行优化处理后，产生如对上面中间代码进行优化处理后，产生如 下的代码：下的代码： temp1=c*d a=b+temp1 temp1=c*d temp2=b+temp1 a=temp2 如下程序 语

18、法分析结果 j = 2 * i + 1; if (j = n) j = 2 * i + 3; return aj; t1 = 2 * i t2 = t1 + 1 j = t2 t3 = j n if t3 goto L0 t4 = 2 * i t5 = t4 + 3 j = t5 L0: t6 = aj return t6 t1 = 2 * i t2 = t1 + 1 j = t2 t3 = j n if t3 goto L0 t4 = 2 * i t5 = t4 + 3 j = t5 L0: t6 = aj return t6 t1 = 2 * i j = t1 + 1 t3 = j n i

19、f t3 goto L0 j = t1 + 3 L0: t6 = aj return t6 代码优化代码优化 代码优化代码优化 id1:= id2 + id3 * 60 (1)(inttoreal60-t1) (2)( * id3 t1t2) (3)( +id2t2t3) (4)( :=t3-id1) 变换变换 （1） ( *id3 60.0 t1) ( 2）（）（ + id2 t1 id1) 32 代码生成阶段代码生成阶段 生成目标机机器代码或汇编代码生成目标机机器代码或汇编代码 (*,id360.0 t1) (+,id2t1id1) movf id3,R2 mulf #60.0,R2 mo

20、vf id2,R1 addf R2,R1 movf R1,id1 nExample: a in R0, i in R1, n in R2 t1 = 2 * i j = t1 + 1 t3 = j n if t3 goto L0 j = t1 + 3 L0: t6 = aj return t6 sll R1, 1, R1 add R1, 1, J cmp J,R2 blt .LL3 add R1, 3, J .LL3: ld R0+J, Rt retr 代码生成代码生成 n记录记录源程序中使用的源程序中使用的标识符标识符 n收集收集每个标识符的各种每个标识符的各种属性信息属性信息 n普通变量：普

21、通变量：类型、作用域、分配存储信息类型、作用域、分配存储信息 n函数或过程：函数或过程：参数个数、类型、传递方法参数个数、类型、传递方法 返回值类型返回值类型 符号表管理符号表管理(登录，查找）登录，查找） 1.3 符号表 符号表 35 符号表管理符号表管理 int a,b; float e,f char ch1,ch2; 为什么要先说明为什么要先说明? 定义了变量的类型，也就规定了变量 定义了变量的类型，也就规定了变量 在内存中的存放形式，在其上所能进行的在内存中的存放形式，在其上所能进行的 运算运算 解决符号地址到存贮地址上的映射解决符号地址到存贮地址上的映射 36 编译器的一个基本功能是

22、编译器的一个基本功能是记录源程序中使用记录源程序中使用 的标识符的标识符 并将它们并将它们记载到符号表中记载到符号表中。 符号表是一个数据结构。符号表是一个数据结构。 每个标识符在符号表中都有每个标识符在符号表中都有 一条记录一条记录 名字名字 记号记号 类型类型种属种属 addr id1(25) id2(25) b a 例：例：int a,b; int简变简变 0 4 并并收集与每个标识符相关的各种属收集与每个标识符相关的各种属 性信息，性信息， int 简变简变 37 在编译的各个阶段都会发现源程序中的错误，在编译的各个阶段都会发现源程序中的错误， 1.4错误检测与报告错误检测与报告 为了

23、使编译器能继续运行，以检测出源程序中为了使编译器能继续运行，以检测出源程序中 更多的错误，在检测到错误后，必须以合适的方式更多的错误，在检测到错误后，必须以合适的方式 进行错误处理。进行错误处理。 error 38 小结：小结： 编译器编译器 的各个的各个 阶段阶段 源程序源程序 词法分析器词法分析器 错错 误误 处处 理理 器器 符符 号号 管管 理理 表表 语法分析器语法分析器 语义分析器语义分析器 中间代码生成器中间代码生成器 代码优化器代码优化器 代码生成器代码生成器 39 编译的前端和后端编译的前端和后端 前端包括词法分析、语法分析、语前端包括词法分析、语法分析、语 义分析，以及相关

24、的错误处理和符号表义分析，以及相关的错误处理和符号表 的建立的建立 前端依赖于源程序并在很大程度上前端依赖于源程序并在很大程度上 独立于目标机器。独立于目标机器。 40 后端主要包括代码优化、代码生成和相后端主要包括代码优化、代码生成和相 关错误处理。关错误处理。 后端依赖于目标机器。后端依赖于目标机器。 后端处理对象是由前端产生的结果，即中后端处理对象是由前端产生的结果，即中 间代码间代码 前端生成与平台无关的字节码前端生成与平台无关的字节码 后端是由与平台有关的解释器对所生成后端是由与平台有关的解释器对所生成 的字节码文件进行解释执行的字节码文件进行解释执行 Java语言的编译采用的是前端

25、后端方式。语言的编译采用的是前端后端方式。 编译程序的组织编译程序的组织 编译程序的遍编译程序的遍（Passes / Phases） - 对一种代码形式从头到尾扫描一遍对一种代码形式从头到尾扫描一遍 - 将一个代码空间变换到另一个代码空间将一个代码空间变换到另一个代码空间 - 代码空间代码空间 = 代码代码 + 符号表符号表 + 其他有用信息其他有用信息 编译程序的组织取决于各遍的组织编译程序的组织取决于各遍的组织 - 单遍单遍编译程序，编译程序，多遍多遍编译程序 编译程序 - 多个遍之间有逻辑上的先后关系多个遍之间有逻辑上的先后关系 - 多个遍的实现可采用顺序结构或并发结构多个遍的实现可采用

26、顺序结构或并发结构 （后者不常用）（后者不常用） 编译程序的组织编译程序的组织 例：一个以语法、语义分析程序为中心的例：一个以语法、语义分析程序为中心的 单遍编译程序单遍编译程序组织组织 source program target program 语法、语义语法、语义 分析程序分析程序 词法分词法分 析程序析程序 代码生代码生 成程序成程序 编译程序的伙伴程序编译程序的伙伴程序 解释程序解释程序（Interpreter） - 不产生目标程序文件不产生目标程序文件 - 不区别翻译阶段和执行阶段不区别翻译阶段和执行阶段 - 翻译源程序的每条语句后直接执行翻译源程序的每条语句后直接执行 - 程序执行

27、期间一直有解释程序守候程序执行期间一直有解释程序守候 - 常用于实现虚拟机常用于实现虚拟机 比较比较编译程序和解释程序编译程序和解释程序 源程序源程序 编译程序编译程序 目标程序目标程序 输入输入 目标程序目标程序 输出输出 解释程序解释程序 输出输出 输入输入 源程序源程序 预处理程序预处理程序（Preprocessor） - 支持宏定义支持宏定义（Macro definition） 如C源程序中 #define 行的处理 - 支持文件包含支持文件包含（File inclusion） 如C源程序中 #include 行的处理 - 支持其他更复杂的源程序扩展信息支持其他更复杂的源程序扩展信息

28、预处理程序和编译程序的关系预处理程序和编译程序的关系 预处理程序预处理程序 不含扩展信不含扩展信 息的源语言息的源语言 程序程序 编译程序编译程序 目标程序目标程序 含扩展信息含扩展信息 的源语言程的源语言程 序序 编译程序的伙伴程序编译程序的伙伴程序 汇编程序汇编程序（Assembler） - 翻译翻译汇编语言程序至可重定位的汇编语言程序至可重定位的（Relocatable） 机器语言程序机器语言程序 装入和连接程序装入和连接程序（Loader and Link-editor） - 装入程序对可重定位机器语言程序进行修改装入程序对可重定位机器语言程序进行修改 将相对地址变换为机器绝对地址 -

29、 连接程序合并多个可重定位机器语言程序文件连接程序合并多个可重定位机器语言程序文件 到同一个程序到同一个程序 - 装入和连接程序产生最终可执行的机器语言程序装入和连接程序产生最终可执行的机器语言程序 编译程序的伙伴程序编译程序的伙伴程序 编译程序、汇编程序及装入和连接程序编译程序、汇编程序及装入和连接程序 之间的典型关系之间的典型关系 编译程序编译程序 可重定位可重定位 的机器语的机器语 言程序言程序 装入和连接程序装入和连接程序 源程序源程序 汇编程序汇编程序 汇编语言程序汇编语言程序 可执行的可执行的 机器语言机器语言 程序程序 编译程序的伙伴程序编译程序的伙伴程序 运行时库运行时库 和分

30、开编和分开编 译的例程译的例程 调试程序调试程序（Debugger） - 反馈目标程序运行时信息反馈目标程序运行时信息 - 将目标程序运行时信息与源程序关联将目标程序运行时信息与源程序关联 - 断点管理、单步跟踪、读断点管理、单步跟踪、读/写目标机状态等功能写目标机状态等功能 调试程序和编译程序的关系调试程序和编译程序的关系 编译程序编译程序 调试信息调试信息 调试程序调试程序运行时信息运行时信息 源程序源程序 装入和连接程序装入和连接程序可执行程序可执行程序 编译程序的伙伴程序编译程序的伙伴程序 Thank You Thats all for today. 第二章 编译基础-形式语言 本讲内

31、容本讲内容 n字母表、串、语言字母表、串、语言 n文法的引例文法的引例 n文法的形式定义（定义、分类）文法的形式定义（定义、分类） n正规文法与有穷自动机正规文法与有穷自动机 n上下文无关文法上下文无关文法 第一节第一节 字母表、串、语言字母表、串、语言 1 字母表字母表：有穷非空字符集：有穷非空字符集 语言允许使用的语言允许使用的字符集字符集可识别符号可识别符号 例： 例： =a-z,A-Z,0-9,+,_,*,/,/(,),=. 2 字符串：字符串：字母表中符号组成的任何有穷字母表中符号组成的任何有穷 序列序列单词单词 例：例：scanf,int,3.1415,x1,100,ascanf,

32、int,3.1415,x1,100,a 3 字符串运算：字符串运算： A、B为字符串集合为字符串集合 x，y为字符串为字符串 连接：连接： xy 称为称为x和和y的连接的连接 例：例：int x x=100 积：积：AB=xy/x A,而 而y B 闭包：闭包：A*=A0 A1 A2. . An 其中：其中： A0= = ， Ai= = Ai-1 A A+= = A*- - A+中的每一个元素即为一个中的每一个元素即为一个语句语句 例：例： x=3.14159x=3.14159* *r r* *r r 形式语言形式语言是一个字母表上按某种规则构成的是一个字母表上按某种规则构成的 所有串的所有串

33、的集合集合。在语言中这些串称为。在语言中这些串称为句子句子。 对于一个句子，存在两个过程：对于一个句子，存在两个过程： 读读-识别过程识别过程-编译的过程编译的过程 写写-推导过程推导过程-书写源程序书写源程序 第二节第二节 文法的引例文法的引例 句子：句子：I am a teach. I am a teacher am a teacher i 第三节第三节 文法的形式定义文法的形式定义 一、几个概念一、几个概念 1、非终结符、非终结符语法变量语法变量 2、终结符、终结符单词单词 3、产生式、产生式规则规则 二、文法的定义二、文法的定义 文法是一个四元组，表示为：文法是一个四元组，表示为： G

34、=（ （V N， ，V T， ，P，S） 其中：其中： VN -非终结符集合非终结符集合 VT -终结符集合终结符集合 P-产生式集合产生式集合 S-开始符号开始符号 P： ： VV+ + ， ， V V* * V=VN VT 例：描述系表结构的文法，其形式描述为例：描述系表结构的文法，其形式描述为 G=（ （V N， ，V T， ，P，S） VN = VT =I，am ,a ,teacher S= am a teacher P= i 再给出一个描述算术表达式的文法例子再给出一个描述算术表达式的文法例子 p=EE+T|T p=EE+T|T TT TT* *F|FF|F F(E)|a F(E)|

35、a 文法文法G G（E E）：）：G=（ （V N， ，V T， ，P，S） VN =E，T，F VT =+，*，（，），（，），a S= E * 句型：句型：S= , , V V* * 为句型为句型 例：例： I am I am * 句子句子：S= w, ww, w V VT T* * w w为句子为句子 例：例：Iam a teacherIam a teacher * 语言语言：L=w/w w w V VT T* * , , 且 且S=w 例：例：I am a teacher 推导的定义推导的定义 若存在若存在v v ww0 0 ww1 1 . . wwn n=w(n0)=w(n0) 则记

36、为则记为v v =+ w w，v v推导出推导出ww，或，或ww归归 约到约到v v 若有若有v =+ wv =+ w，或，或v=wv=w， 则记为则记为v =v =* * w w 例：例：GEGE： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a E E E+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+F a+F* *F F a+a a+a* *F F a+aa+a* *a a 句子：用符号句子：用符号a a，+ +，* *，( (和和) )构成的算术构成的算术 表达式表达式 E E + T T F a T *

37、 F F a a E E E+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+F a+F* *F F a+a a+a* *F F a+aa+a* *a a 通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将文法分为将文法分为 四种类型：四种类型： 0 0型文法：对任一产生式型文法：对任一产生式，都有，都有 (V(VN NV VT T) )+ +， (V(VN NV VT T) )* * 1 1型文法：对任一产生式型文法：对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外 2 2型文法：对任一产生式型文法：对任一产生

38、式AA，都有，都有AVAVN N ， ， (V(VN NV VT T) )* * 3 3型文法：任一产生式型文法：任一产生式AA的形式都为的形式都为AaBAaB或或 AaAa，其中，其中AVAVN N ， ，BVBVN N ， ，aVaVT T 文法分类：文法分类： 文法的类型文法的类型 自然语言属于上下文有关文法自然语言属于上下文有关文法 例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCACaCABaaBBaaB CbCBCbCBBbbBBbbB ADaDADaD C C BDbDBDbD D D AabDAabD 文法的类型文

39、法的类型 是语法分析的基础是语法分析的基础 例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GSGS：SAB AB ABS|0BS|0 BSA|1SA|1 3 3型文法型文法 GS： S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|0 GI：I lT lT I l l T lT lT T dT dT T l l T d d 是词法分析的基础是词法分析的基础 文法的类型文法的类型 四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系 0 0型文法型文法 1 1型文法型文法 2 2型文法型文法 3 3型文法型文法 文法和语言文法和语言

40、 n0 0型文法产生的语言称为 型文法产生的语言称为0 0型语言型语言 1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG CSG ）产生的语言）产生的语言 称为称为1 1型语言或上下文有关语言（型语言或上下文有关语言（CSLCSL） 2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG CFG ）产生的语言）产生的语言 称为称为2 2型语言或上下文无关语言（型语言或上下文无关语言（ CF L CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG RG ）产生的语言）产生的语言 称为称为3 3型语言正则（正规）语言（型语言正则（正规）语言（ RL

41、 RL ） 根据形式语言理论根据形式语言理论, ,文法和识别系统文法和识别系统 间有这样的关系间有这样的关系 0 0型文法（短语结构文法）的型文法（短语结构文法）的能力相当于图能力相当于图 灵机，灵机，可以表征任何递归可枚举集，而且可以表征任何递归可枚举集，而且 任何任何0 0型语言都是递归可枚举的型语言都是递归可枚举的 1 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形 式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在 1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。 其其识别系统是线性界限自动机。识别系统是线性界限自

42、动机。 2 2型文法（上下文无关文法型文法（上下文无关文法CFGCFG）：产生）：产生 式的形式为式的形式为AA，取代取代A A时与时与A A的的 上下文无关。上下文无关。其识别系统是不确定的其识别系统是不确定的 下推自动机。下推自动机。 3 3型文法（正规文法型文法（正规文法RGRG）：产生的语言）：产生的语言 是是有穷自动机有穷自动机（FAFA）所接受的集合）所接受的集合 第四节第四节 正规文法与有穷自动机正规文法与有穷自动机 一、正规文法一、正规文法 1. 正规文法正规文法 能能 产生语言产生语言L(G) 2. 写出产生语言写出产生语言L(G)的正规文法的正规文法 第四节第四节 正规文法

43、与有穷自动机正规文法与有穷自动机 1、正规文法、正规文法 产生的语言的推导产生的语言的推导 例：文法例：文法 G=（ （V N， ，V T， ，P，S） 其中：其中： VN=A，B，C VT=a,b,c S=A P:A aB A aA aB A aA B bB B bC B bB B bC C cC C c C cC C c L(G)=aL(G)=am mb bn nc cp p/m,n,p /m,n,p 1 1 A=aA=aaA=A=aA=aaA=.=aa.=aaaBaB =aa =aaabB=aaabB=aaabbabbbCbC =aa =aaabbabbbcC= aabcC= aaabb

44、abbbccCbccC = aa = aaabbabbbccbccc c 最小句子：最小句子：abcabc P:A aB A aA aB A aA B bB B bC B bB B bC C cC C c C cC C c 例例1 1：写出产生语言：写出产生语言L(G)=aL(G)=am mbc bcn n/m,n/m,n 0 0的的 正规文法正规文法 解：文法解：文法 G=（ （V N， ，V T， ，P，S） 其中：其中： VN=A，C VT=a,b S=A P: 最小语言：最小语言：b b A aAaA A bA b A bCA bC C cCC cCCcCc 2. 写出产生语言写出产生

45、语言L(G)的正规文法的正规文法 例例2 2：C C语言标识符的文法描述语言标识符的文法描述 L L（G G）=w/w=w/w为字母或为字母或- -打头的字母数字串打头的字母数字串 解：解：P: IaB I -BaB I -B B aB B dB Ba B d B aB B dB Ba B d I aI a I BT T a - a,d 其其 它它 2. 写出产生语言写出产生语言L(G)的正规文法的正规文法 二、有穷自动机二、有穷自动机 正规文法产生的正规语言用有穷自动机来识正规文法产生的正规语言用有穷自动机来识 别别 根据文法根据文法-写程序写程序 -编译时用有穷自动机识别编译时用有穷自动机

46、识别 二、有穷自动机二、有穷自动机 1 1、特点：接收离散输入，状态有穷，只需考、特点：接收离散输入，状态有穷，只需考 虑当前输入和当前内部状态虑当前输入和当前内部状态 2 2、原理：、原理：有穷自动机控制器有穷自动机控制器读头自左向右读头自左向右 逐个扫描并读入逐个扫描并读入输入符号输入符号，并且根据控制器，并且根据控制器 的的当前状态当前状态和和当前输入符号当前输入符号控制转入控制转入下一个下一个 状态状态 、模型、模型Main ( ) int I , j , k ; 有穷控制器有穷控制器 、表示、表示状态图状态图 I BT T a - a,d 其其 它它 例：例：C C语言的标识符语言的

47、标识符 、形式定义、形式定义 确定的有穷自动机是一个五元组确定的有穷自动机是一个五元组 M=M=（QQ， ， ，q q0 0，Z Z） 其中：其中：QQ是一有穷状态集是一有穷状态集 是有穷输入字母表是有穷输入字母表 是是Qx QQx Q的映射函数的映射函数 其含义：其含义： （ q q1 1,a)= q,a)= q2 2 q q0 0 Q,Q,唯一的初态唯一的初态 Z Z是的子集，是终态集是的子集，是终态集 例：奇偶测试器例：奇偶测试器 q0 0 q1 1 q1 0 1 自动机：（自动机：（QQ， ， ，q q0 0，Z Z） QQ q q0 0, q, q1 1 =0,1 =0,1 q q0

48、 0=q=q0 0 Z=q Z=q1 1 映射函数：映射函数： （ q q , , )= q)= q （ q q , , )= q)= q （ q q1 1, ,)= q)= q （ q q1 1, ,)= q)= q 例：例： q0 0 q1 1 q1 0 1 三、正规表达式与有穷自动机三、正规表达式与有穷自动机 关系：等价、交换关系：等价、交换 文法文法 G=（ （V N， ，V T， ，P，S）和）和 自动机自动机 M=M=（QQ， ， ，q q0 0，Z Z） 可转换为：可转换为： VN为终态为终态 q q0 0 VT ，S若若 映射函数：映射函数： 、：、： a a2 2 , , 则

49、则（ ,a)= A,a)= A2 2 2 2、：、： a, a, 则则（ ,a)= T,a)= T 3 3、（ ,a)= ,a)= 空动作空动作 例：已知正规文法例：已知正规文法 （A,B,C,A,B,C,a,b,c,P,S a,b,c,P,S 其中：其中： P:A aA A aB B bB aA A aB B bB B bC C cC Cc B bC C cC Cc 试写出与其等价的试写出与其等价的 解：解：(A,B,C,a,b,c, ,S,T)(A,B,C,a,b,c, ,S,T) ABC T a a b b c c 映射函数：映射函数： （ A,a)= AA,a)= A （ A,a)= BA,a)= B （B,b)= BB,b)= B （B,b)= CB,b)= C （C,c)= CC,c)= C （C,c)= TC,c)= T 练习：练习：w/ww/w是和的个数都为偶是和的个数都为偶 数的、串数的、串 试写出能识别该语言的自动机和描述该语试写出能识别该语言的自动机和描述该语 言的文法言的文法 第五节上下文无关文法语法基础第五节上下文无关文法语法基础 一、上下文无关文法一、上下文无关文法 文法文法 G=（ （V N， ，V T， ，P，S） ） ： A （ （ VN VT) 例：例：anbn/n 1 P: S aSbaSb S ab ab 二、自嵌套性二、自嵌套性 如果上下