编译原理第1章

1、第一章第一章 引论引论 课程简介、编译程序的基本概念、课程简介、编译程序的基本概念、典型的编译过程典型的编译过程1.0 课程简介1.0 课程简介课程简介一一课程基本信息课程基本信息1. 课程中文名称：编译原理课程中文名称：编译原理2. 课程英文名称：课程英文名称：Compile Principle3. 课程主要内容：编译程序的工作原理与开发设计方法课程主要内容：编译程序的工作原理与开发设计方法4. 课程类别：必修课程类别：必修5. 适用专业：信息工程学院计算机科学与技术专业适用专业：信息工程学院计算机科学与技术专业6. 总学时：总学时：48学时（其中理论学时（其中理论40学时，上机学时，上机8

2、学时）学时）7. 总学分：总学分：3 1.0 课程简介二二本课程在教学计划中的地位、作用和任务本课程在教学计划中的地位、作用和任务1.计算机科学与技术专业高年级学生的专业必修课。计算机科学与技术专业高年级学生的专业必修课。2.先修课程：程序设计方法、高级程序设计语言先修课程：程序设计方法、高级程序设计语言(PASCAL、C、)、数据结构、离散数学等。、数据结构、离散数学等。3.作用和任务作用和任务专业素质与能力的训练与培养；专业素质与能力的训练与培养；从事与编译系统相关的工作；从事与编译系统相关的工作；提高软件开发的能力；提高软件开发的能力；一个难度很大的系统软件的实例；一个难度很大的系统软件

3、的实例；大量实用的工具和方法；大量实用的工具和方法；考研需要。考研需要。1.1 什么是编译程序三、参考书：三、参考书：1.编译原理编译原理（原版名：（原版名：Compiler Principles, Techniques, and Tools） 阿霍阿霍（Aho, A. V.）等著，李建中等译）等著，李建中等译 机械工业出版社机械工业出版社 （龙书）（龙书）2. 现代编译原理现代编译原理-C语言描述语言描述 （原版名：（原版名：Modern Compiler Implementation in C ）Andrew W. Appel等著，陈明译等著，陈明译 电子工业出版社电子工业出版社（虎书）（

4、虎书）3. 高级编译器设计与高级编译器设计与实现实现 （原版名：（原版名： Advanced Compiler Design and Implementation ）Steven S. Muchnick等等著著 机械工业出版社机械工业出版社 （鲸书）（鲸书）理论理论技术技术实现实现1.2 编译程序工作过程1.1 什么是编译程序什么是编译程序一一翻译程序翻译程序：把源语言程序逻辑等价的转换成目标语言程序的：把源语言程序逻辑等价的转换成目标语言程序的程序；程序；二二编译程序编译程序：源语言是高级语言，目标程序是低级语言的翻译：源语言是高级语言，目标程序是低级语言的翻译程序；程序； 三三编译程序的分

5、类编译程序的分类 1. 诊断编译程序：用于帮助程序开发和调试；诊断编译程序：用于帮助程序开发和调试； 2. 优化编译程序：着重于提高目标代码的效率；优化编译程序：着重于提高目标代码的效率； 3. 交叉编译程序：运行编译程序的计算机为宿主机，运行编译交叉编译程序：运行编译程序的计算机为宿主机，运行编译程序所产生的目标代码的计算机为目标机，如果编译程序产程序所产生的目标代码的计算机为目标机，如果编译程序产生不同于其宿主机的机器代码，称为交叉编译程序；生不同于其宿主机的机器代码，称为交叉编译程序； 4. 可变目标编译程序：若不需重写编译程序中与机器无关部分可变目标编译程序：若不需重写编译程序中与机器

6、无关部分就能改变目标机，则该编译程序为可变目标编译程序；就能改变目标机，则该编译程序为可变目标编译程序； 1.2 编译程序工作过程1.2 编译程序工作过程编译程序工作过程一一自然语言的翻译过程：自然语言的翻译过程：二二编译程序的工作过程编译程序的工作过程：1.2 编译程序工作过程1. 词法分析（扫描程序）词法分析（扫描程序） 任务：输入源程序，对构成源程序的字符串扫描和分解，任务：输入源程序，对构成源程序的字符串扫描和分解，识别出其中的单词识别出其中的单词 （如标识符、常数、算符、界限符（如标识符、常数、算符、界限符等）；等）； 输入：源程序字符串；输入：源程序字符串； 输出：单词串，也就是等

7、长的内部形式（即属性字）；输出：单词串，也就是等长的内部形式（即属性字）； 依据：词法规则；依据：词法规则； 词法规则的研究和描述工具：正规式、自动机；词法规则的研究和描述工具：正规式、自动机；例：例：C语言源程序片段语言源程序片段int a;a=a+3;词法分析后结果如右图词法分析后结果如右图 单词类型单词类型单词值单词值保留字保留字 int标识符标识符a界符界符;标识符标识符a算符算符=标识符标识符a算符算符+整数整数3界符界符; 1.1 什么是编译程序2. 语法分析（识别程序）语法分析（识别程序） 任务：在词法分析的基础上，把单词符号串分解成各类任务：在词法分析的基础上，把单词符号串分解

8、成各类语法单位（语法范畴），并确定整个输入串是否构成语语法单位（语法范畴），并确定整个输入串是否构成语法上正确的程序法上正确的程序 ； 输入：单词符号串；输入：单词符号串； 输出：语法单位（输出：语法单位（语法树语法树）；）； 依据：语法规则；依据：语法规则； 语法规则的描述：上下文无关文法，下推自动机；语法规则的描述：上下文无关文法，下推自动机；例：例：id1=id2+id3*10的语法树的语法树赋值语句赋值语句id1表达式表达式表达式表达式id2id310=+*=+*=+1.2 编译程序工作过程3. 语义分析与中间代码生成语义分析与中间代码生成 任务：分析各类语法范畴的含义，进行任务：分析

9、各类语法范畴的含义，进行静态语义检查静态语义检查（类型检查、控制流检查、一致性检查和相关名字检查）（类型检查、控制流检查、一致性检查和相关名字检查）并进行初步翻译；并进行初步翻译； 输入：语法树或中间表示输入：语法树或中间表示 输出：中间代码输出：中间代码 （四元式）；（四元式）； 依据：语义规则；依据：语义规则； 语义规则的描述：属性文法。语义规则的描述：属性文法。例：语义分析类型检查，有错误吗？例：语义分析类型检查，有错误吗？int a, *p;a=10;p=a;1.1 什么是编译程序中间代码中间代码中间代码是一种独立于具体硬件的记号系统，或者与现代计算中间代码是一种独立于具体硬件的记号系

10、统，或者与现代计算机的指令形式有某种程度的接近，或者能比较容易地变换成机的指令形式有某种程度的接近，或者能比较容易地变换成机器指令。机器指令。中间代码主要有三元式、间接三元式、逆波兰记号、树形表示，中间代码主要有三元式、间接三元式、逆波兰记号、树形表示，常用的中间代码是四元式。常用的中间代码是四元式。例例1：id1=id2+id3*50的四元式的四元式(1)(inttoreal 50-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(=t3-id1)1.1 什么是编译程序4. 优化优化 对中间代码进行加工变换，以期在最后阶段产生更对中间代码进行加工变换，以期在最后阶段产生更高效

11、高效的目标代码；的目标代码； 输入：优化前的中间代码；输入：优化前的中间代码； 输出：优化后的中间代码；输出：优化后的中间代码； 依据：程序的等价变换规则；依据：程序的等价变换规则； 常用技术：基本块优化、循环优化等。常用技术：基本块优化、循环优化等。例：例：id1=id2+id3*50的四元式优化处理的四元式优化处理(1) (inttoreal 50-t1)(2) (*id3t1t2)(3) (+id2t2t3)(4) (=t3-id1)优化结果：优化结果：(1) (*id360.0t1)(2) (+id2t1id1)1.2 编译程序工作过程5. 目标代码生成目标代码生成 任务：把优化后的中

12、间代码变换成特定机器上的低级语任务：把优化后的中间代码变换成特定机器上的低级语言代码言代码 （目标代码）；（目标代码）； 输入：中间代码；输入：中间代码； 输出：目标代码；输出：目标代码； 依据：硬件系统的结构和机器指令的含义；依据：硬件系统的结构和机器指令的含义； 目标代码种类目标代码种类： 绝对指令代码绝对指令代码：目标代码可立即执行；：目标代码可立即执行； 汇编指令代码汇编指令代码：需汇编器汇编之后才能运行；：需汇编器汇编之后才能运行； 可重定位的指令代码可重定位的指令代码：必须借助连接转配程序把各个：必须借助连接转配程序把各个模块连接在一起，确定变量（或常数）在内存的位置，模块连接在一

13、起，确定变量（或常数）在内存的位置，转入内存中指定的起始地址，使之成为可运行的绝对转入内存中指定的起始地址，使之成为可运行的绝对指令代码程序；指令代码程序； 1.1 什么是编译程序例：生成汇编指令代码例：生成汇编指令代码(1)(*id360.0t1)(2)(+id2t1id1)汇编代码如下：汇编代码如下：movf id3, R2mulf #60.0, R2movf id2, R1addf R2, R1movf R1, id11.3 编译程序的结构1.3 编译程序的结构编译程序的结构一一编译程序总框编译程序总框 符号表符号表1.3 编译程序的结构二二表格与表格管理：表格与表格管理： 用各类表格登

14、记源程序的各类信息和编译各阶段的进展情况，用各类表格登记源程序的各类信息和编译各阶段的进展情况，在编译的各阶段都涉及到构造、查找、更新有关的表格；在编译的各阶段都涉及到构造、查找、更新有关的表格； 三三出错处理：出错处理：由专门的一组出错处理程序发现源程序中的错误并将错误信由专门的一组出错处理程序发现源程序中的错误并将错误信息报告给用户；息报告给用户； 四四遍（遍（Pass） 对源程序或源程序的中间结果从头到尾扫描一次，并作有关对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。通常每的加工处理，生成新的中间结果或目标程序。通常每“遍遍”的工作从外存上获

15、得前一遍的中间结果开始，完成所含的有的工作从外存上获得前一遍的中间结果开始，完成所含的有关工作，直到结果纪录与外存为止；关工作，直到结果纪录与外存为止；1.3 编译程序的结构五五编译前端与后端编译前端与后端 编译过程中与源语言有关与目标机无关的部分称为编译前端，编译过程中与源语言有关与目标机无关的部分称为编译前端，通常包括词法分析、语法分析、语义分析与中间代码生成，通常包括词法分析、语法分析、语义分析与中间代码生成，有的代码优化工作也可包括在前端。后端包括编译程序中与有的代码优化工作也可包括在前端。后端包括编译程序中与目标机有关的部分，如与目标机有关的代码优化和目标代码目标机有关的部分，如与目

16、标机有关的代码优化和目标代码生成；生成；1.4 编译程序与程序设计环境 1.4 编译程序与程序设计环境编译程序与程序设计环境 一一程序设计环境程序设计环境 编译程序、编辑程序、连接程序、调试工具等支持程序设计编译程序、编辑程序、连接程序、调试工具等支持程序设计人员进行程序开发的工具；人员进行程序开发的工具； 二二IDE将相互独立的程序设计工具集成起来，形成程序的集成开发将相互独立的程序设计工具集成起来，形成程序的集成开发环境。如：环境。如：Turbo Pascal、Turbo C、Visual Basic、 Visual C+、Delphi 1.5 编译程序的生成 1.5 编译程序的生成编译程

17、序的生成 一一T形图形图 ：表示源语言（表示源语言（S）、目标语言（）、目标语言（T）、编译程序实现语言（）、编译程序实现语言（I）之间的关系；之间的关系； 1.1 什么是编译程序1 1）交叉编译）交叉编译( (Cross Compiling)/)/移植移植n问题一：问题一：A A机上有一个机上有一个C C语言编译器，是否可利用此编译器实现语言编译器，是否可利用此编译器实现B B机上机上的的C C语言编译器？语言编译器？q条件：条件： 机有机有 语言的编译程序语言的编译程序q目的：实现目的：实现 机的机的 语言的编译语言的编译1.1. ( (人人) )用语言编制用语言编制B B机的编译程序机的

18、编译程序P0(CP0(C2.2. ( (机的机的C C编译编译P1)P1)编译编译P0P0，得到在，得到在A A机上可运行的机上可运行的P2(CP2(C语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器1.1 什么是编译程序3. (3. (机的机的P2)P2)编译编译P0P0，得到在，得到在B B机上可运机上可运行的行的P3(CP3(C语言语言机器机器机器机器语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器语言语言机器机器机器机器语言语言语言语言机器机器1.1 什么是编译程序2) 2) 本机编译器利用本机编译器利用n问题二：问题二： A

19、 A机上有一个机上有一个C C语言编译器，现要实现一个新语言语言编译器，现要实现一个新语言NEWNEW的编译器？的编译器？能利用交叉编译技术么？能利用交叉编译技术么？n用用C C编写编写NEWNEW的编译，并用的编译，并用C C编译器编译它编译器编译它NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW语言语言A机器机器A机器机器NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW语言语言A机器机器A机器机器NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW语言语言A机器机器A机器机器NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW

20、语言语言A机器机器A机器机器NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW语言语言A机器机器A机器机器1.1 什么是编译程序n问题三：直接在一个机上实现问题三：直接在一个机上实现C C语言编译器，还有别的技术么？语言编译器，还有别的技术么？n解决：解决：q用汇编语言实现一个子集的编译程序用汇编语言实现一个子集的编译程序(P0(P0人人) )q用汇编程序处理该程序用汇编程序处理该程序, ,得到得到P2(P2:P2(P2:可直接运行可直接运行) )q用用 子集编制语言的编译程序子集编制语言的编译程序(P3(P3人人) )q用用P2P2编译编译P3P3，得到，得到P4P43) 3

21、) 编译程序的自展技术编译程序的自展技术1.1 什么是编译程序4. 用用P2P2编译编译P3P3，得到，得到P4P4语言语言机器语言机器语言机器语言机器语言子集子集汇编语言汇编语言机器语言机器语言1. 用汇编语言实现一个用汇编语言实现一个 子集的编译程序子集的编译程序(P0(P0人人) )汇编语言汇编语言机器语言机器语言机器语言机器语言子集子集机器语言机器语言机器语言机器语言2. 用汇编程序用汇编程序(P1)(P1)处理该程序处理该程序, ,得到得到P2(P2:P2(P2:可直接运行可直接运行) )子集子集机器语言机器语言机器语言机器语言语言语言子集子集机器语言机器语言3. 用子集编制用子集编制 语言的编译程序语言的编译程序(P3(P3人人) )1.1 什么是编译程序二、二、利用编译程序自动生成器利用编译程序自动生成器词法分析器的自动生成程序词法分析器的自动生成程序词法规则说明词法规则说明词法分析程序词法分析程序(C(C程序程序) )输入：输入：词法（正规表达式）词法（正规表达式）识别动作（程序段）识别动作（程序段）输出：输出：yylexyylex( ) ( ) 函数函数LEX1.1 什么是编译程序语法分析器的自动生成程序语法分析器的自动生成程序语法规则说明语法规则说明语法分析程序语法分析程序(C(C程序程序) )输入：输入：