编译原理第1章详解.ppt

第一章 引论 ;§1.0 课程简介;本课程在教学计划中的地位、作用和任务 计算机科学与技术专业高年级学生的专业必修课。 先修课程：程序设计方法、高级程序设计语言(PASCAL、C、…)、数据结构、离散数学等。 作用和任务 专业素质与能力的训练与培养； 从事与编译系统相关的工作； 提高软件开发的能力； 一个难度很大的系统软件的实例； 大量实用的工具和方法； 考研需要。 ;三、参考书： 1.《编译原理》（原版名：Compiler Principles, Techniques, and Tools） 阿霍（Aho, A. V.）等著，李建中等译 机械工业出版社 （龙书） 2. 《现代编译原理-C语言描述》 （原版名：Modern Compiler Implementation in C ）Andrew W. Appel等著，陈明译 电子工业出版社（虎书） 3. 《高级编译器设计与实现》 （原版名： Advanced Compiler Design and Implementation ）Steven S. Muchnick等著 机械工业出版社 （鲸书）;§1.1 什么是编译程序;§1.2 编译程序工作过程;词法分析（扫描程序） 任务：输入源程序，对构成源程序的字符串扫描和分解，识别出其中的单词 （如标识符、常数、算符、界限符等）； 输入：源程序字符串； 输出：单词串，也就是等长的内部形式（即属性字）； 依据：词法规则； 词法规则的研究和描述工具：正规式、自动机；;语法分析（识别程序） 任务：在词法分析的基础上，把单词符号串分解成各类语法单位（语法范畴），并确定整个输入串是否构成语法上正确的程序 ； 输入：单词符号串； 输出：语法单位（语法树）； 依据：语法规则； 语法规则的描述：上下文无关文法，下推自动机； 例：id1=id2+id3*10的语法树;语义分析与中间代码生成 任务：分析各类语法范畴的含义，进行静态语义检查（类型检查、控制流检查、一致性检查和相关名字检查）并进行初步翻译； 输入：语法树或中间表示 输出：中间代码 （四元式）； 依据：语义规则； 语义规则的描述：属性文法。 例：语义分析类型检查，有错误吗？ int a, *p; a=10; p=a;;中间代码 中间代码是一种独立于具体硬件的记号系统，或者与现代计算机的指令形式有某种程度的接近，或者能比较容易地变换成机器指令。 中间代码主要有三元式、间接三元式、逆波兰记号、树形表示，常用的中间代码是四元式。 例1：id1=id2+id3*50的四元式 (1) (inttoreal 50 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (= t3 - id1) ;优化 对中间代码进行加工变换，以期在最后阶段产生更高效的目标代码； 输入：优化前的中间代码； 输出：优化后的中间代码； 依据：程序的等价变换规则； 常用技术：基本块优化、循环优化等。 例：id1=id2+id3*50的四元式优化处理 (1) (inttoreal 50 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (= t3 - id1) 优化结果： (1) (* id3 60.0 t1) (2) (+ id2 t1 id1);目标代码生成 任务：把优化后的中间代码变换成特定机器上的低级语言代码 （目标代码）； 输入：中间代码； 输出：目标代码； 依据：硬件系统的结构和机器指令的含义； 目标代码种类： 绝对指令代码：目标代码可立即执行； 汇编指令代码：需汇编器汇编之后才能运行； 可重定位的指令代码：必须借助连接转配程序把各个模块连接在一起，确定变量（或常数）在内存的位置，转入内存中指定的起始地址，使之成为可运行的绝对指令代码程序； ;例：生成汇编指令代码 (1) (* id3 60.0 t1) (2) (+ id2 t1 id1) 汇编代码如下： movf id3, R2 mulf #60.0, R2 movf id2, R1 addf R2, R1 movf R1, id1;§1.3 编译程序的结构;表格与表格管理： 用各类表格登记源程序的各类信息和编译各阶段的进展情况，在编译的各阶段都涉及到构造、查找、更新有关的表格； 出错处理： 由专门的一组出错处理程序发现源程序中的错误并将错误信息报告给用户； 遍（Pass） 对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。通常每“遍”的工作从外存上获得前一遍的中间结果开始，完成所含的有关工作，直到结果纪录与外存为止；;编译前端与后