高等教育编译程序概述.pptx

课程简介先行课程：高等数学、(PASCAL)、离散数学、汇编语言、数据结构编译原理课程应用领域编译原理课程应用领域编译器的设计编译器的设计一般的软件设计一般的软件设计例如：例如：例如：例如：v文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、模式识别器模式识别器模式识别器模式识别器v排版、绘图系统排版、绘图系统排版、绘图系统排版、绘图系统v程序验证器程序验证器程序验证器程序验证器编译原理编译原理编译原理编译原理吕映芝吕映芝吕映芝吕映芝清华大学出版社清华大学出版社清华大学出版社清华大学出版社 编译程序设计原理编译程序设计原理编译程序设计原理编译程序设计原理杜淑敏等杜淑敏等杜淑敏等杜淑敏等北京大学出版社北京大学出版社北京大学出版社北京大学出版社编译原理习题解答编译原理习题解答编译原理习题解答编译原理习题解答伍春香等伍春香等伍春香等伍春香等清华大学出版社清华大学出版社清华大学出版社清华大学出版社编译程序构造原理编译程序构造原理编译程序构造原理编译程序构造原理和实现技术和实现技术和实现技术和实现技术金成植金成植金成植金成植高等教育出版社高等教育出版社高等教育出版社高等教育出版社程序设计语言编译程序程序设计语言编译程序程序设计语言编译程序程序设计语言编译程序陈火旺等陈火旺等陈火旺等陈火旺等国防工业出版社国防工业出版社国防工业出版社国防工业出版社Compiler Construction Compiler Construction Compiler Construction Compiler Construction Principle and PraticePrinciple and PraticePrinciple and PraticePrinciple and Pratice编译原理及实践编译原理及实践编译原理及实践编译原理及实践Kenneth C.LoudenKenneth C.LoudenKenneth C.LoudenKenneth C.Louden机械工业出版社机械工业出版社机械工业出版社机械工业出版社参参参参考考考考书书书书籍籍籍籍参参参参考考考考书书书书籍籍籍籍作业成绩作业成绩10%+出勤出勤10%+期考成绩期考成绩80%考试成绩编译原理编译原理第一章第一章 编译程序概述编译程序概述第二章第二章 一个微小编译器一个微小编译器第三章第三章 文法和语言文法和语言第四章第四章 词法分析词法分析第五章第五章 自顶向下语法分析方法自顶向下语法分析方法第六章第六章 自底向上优先分析方法自底向上优先分析方法第七章第七章 LRLR分析方法分析方法第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成第九章第九章 符号表符号表第一第一章章 代码优化代码优化第一一章第一一章 代码生成代码生成1.1什么叫编译程序什么叫编译程序v翻译程序：翻译程序：能够将某种语言写的程序转换能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在成另一种语言的程序，而且后者与前者在逻辑上是等价的。逻辑上是等价的。v编译程序：编译程序：是一种将高级语言程序（源程是一种将高级语言程序（源程序）翻译成低级语言（目标程序）的程序序）翻译成低级语言（目标程序）的程序1.1什么叫编译程序v1.功能编译程序编译程序程序设程序设计语言计语言机器语言机器语言v2、计算机语言的层次计算机语言的层次 三个层次三个层次：高级语言、汇编语言、机器语言：高级语言、汇编语言、机器语言 语言转化：语言转化：高级语言高级语言-机器语言（编译）机器语言（编译）机器语言机器语言-高级语言（反编译）高级语言（反编译）汇编语言汇编语言-机器语言（汇编）机器语言（汇编）机器语言机器语言-汇编语言（反汇编）汇编语言（反汇编）编译的过程v3、什么是编译原理、什么是编译原理编译原理是讨论编译程序设计的基本理编译原理是讨论编译程序设计的基本理论、基本概念和基本方法的一门学科论、基本概念和基本方法的一门学科。1.2编译过程概述v1 1、六个阶段：词法分析、语法分析、语义分析与中间代、六个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成码生成、代码优化、目标代码生成2、每个阶段的任务：每个阶段的任务：词法分析：从左到右扫描源程序，识别出一个个单词词法分析：从左到右扫描源程序，识别出一个个单词保留字保留字、标识符、标识符、常数、常数、运算符、运算符、分界符、分界符例例:intsum,first,count;sum=first+count*10;a、滤掉空格、滤掉空格b、识别单词、识别单词词法分析的工作主要依据语言的词法规则，描述词法词法分析的工作主要依据语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。规则的有效工具是正规式和有限自动机。编译过程概述(续)o语法分析：在词法分析的基础上，根据语言的语法语法分析：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语规则，将单词符号串分解成各类语法短语(例：程序、例：程序、语句、表达式语句、表达式)例：例：表达式：标识符、常数是表达式；表达式的运算也是表达表达式：标识符、常数是表达式；表达式的运算也是表达式式语句：标识符表达式语句：标识符表达式while(布尔表达式布尔表达式)do语句语句if(表达式表达式)then语句语句else语句语句A：=B+C*5语法分析所依据的是语言的语法规则，语法分析所依据的是语言的语法规则，表示语法规则的工具是上下文无关文法表示语法规则的工具是上下文无关文法,用下推自动机实现。用下推自动机实现。编译过程概述(续)o语义分析和中间代码生成：对语法分析所识别出的各类语法语义分析和中间代码生成：对语法分析所识别出的各类语法单位分析其含义，进行初步的翻译单位分析其含义，进行初步的翻译(翻译成中间代码翻译成中间代码)。这一。这一阶段有两项工作：首先对每种语法范畴进行静态语义审查阶段有两项工作：首先对每种语法范畴进行静态语义审查(如如是否定义，类型是否匹配等是否定义，类型是否匹配等)，若无语义错误，进行中间代码，若无语义错误，进行中间代码的翻译。的翻译。例：例：A=A*B+C(检查、检查、C类型类型)中间代码有多种形式，如：中间代码有多种形式，如：四元式四元式:(运算符，运算对象运算符，运算对象1，运算对象，运算对象2，结果，结果)（+，A，B，T1）（+，T1，C，T2）（=，T2，-，A）语义分析依据的是语言的语义规则语义分析依据的是语言的语义规则,表示工具是属性文法。表示工具是属性文法。编译过程概述(续)o代码优化：对已产生的中间代码进行加工代码优化：对已产生的中间代码进行加工变换，使生成的目标代码更为高效变换，使生成的目标代码更为高效。优。优化包括：公共子表达式的提取、循环优化、化包括：公共子表达式的提取、循环优化、删除无用代码等。删除无用代码等。代码的优化依据的是程序的等价变换规代码的优化依据的是程序的等价变换规则。则。优化前：优化前：（+，A，B，T1）（+，T1，C，T2）（=，T2，-，A）优化后：优化后：（+，A，B，T1）（+，T1，C，A）o目标代码的生成：把中间代码目标代码的生成：把中间代码(或经优化的中或经优化的中间代码间代码)变换成变换成特定特定机器上的低级语言代码。机器上的低级语言代码。目标代码可以是：绝对指令代码、可重定位的目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码指令代码、汇编指令代码编译程序的结构编译程序的结构(续)v几个概念符号表：登记源程序中出现的名字以及名字的各种属性出错处理：遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成构造编译程序v一般生成编译程序的方法有：用一种语言写另一种语言的编译程序在一台机器上用一种语言写另一台机器上(另)一种语言的编译程序自编译方式v构造编译程序要掌握以下几方面的内容：源语言：理解其结构和含义目标语言：必须清楚硬件的系统结构和指令的格式等编译方法作业教材练习第2、4题P12