编译原理 chapter1.

《编译原理 chapter1.》由会员分享，可在线阅读，更多相关《编译原理 chapter1.（61页珍藏版）》请在金锄头文库上搜索。

1、11 编译原理讲义编译原理讲义 张张 捷捷 PhonePhone：8285904182859041 QQQQ：290813268290813268 22 课程目的 n n 了解编译程序的实现原理和技术。了解编译程序的实现原理和技术。 n n 利用从本课程学习到的知识，增强编写利用从本课程学习到的知识，增强编写 和调试程序的能力。和调试程序的能力。 n n 在其它方面的应用：在其它方面的应用： uu正文查找；正文查找； uu正文处理；正文处理； uu指令识别等。指令识别等。 33 课程内容 n n 文法文法/ /语言语言/ /自动机自动机 n n 词法分析技术词法分析技术 n n 语法分析技术语

2、法分析技术 n n 语义分析技术语义分析技术 n n 代码优化和生成技术代码优化和生成技术 目 录 第一章 引论 第二章 高级语言及其语法描述 第三章 词法分析 第四章 语法分析自上而下分析 第五章 语法分析自下而上分析 第六章 属性文法和语法制导翻译 第七章 语义分析和中间代码产生 第八章 符号表 第九章 运行时存储空间组织 第十章 优化 第十一章 目标代码生成 第十二章 并行编译基础 第一章 引论 1.1 什么叫编译程序 翻译程序是指这样的程序，它能够把 某种语言的程序转换成另一种语言的程序 ，而后者与前者在逻辑上是等价的。如果 源语言是诸如FORTRAN、Pascal、C、Ada、 Sm

3、alltalk和Java这样的“高级语言”，而目 标语言是诸如汇编语言和机器语言之类的“ 低级语言”，这样的翻译程序就称为编译程 序。 6 程序设计语言 n n 程序设计语言分成两大类，一类是高级程序设计语言分成两大类，一类是高级 语言，一类是低级语言。低级语言又包语言，一类是低级语言。低级语言又包 括机器语言和汇编语言，主要是面向机括机器语言和汇编语言，主要是面向机 器的。高级语言则是面向应用的，分成器的。高级语言则是面向应用的，分成 很多种，如很多种，如FORTRANFORTRAN、PascalPascal、C C、AdaAda 、JavaJava等。等。 7 n n 机器语言本身是有由机

4、器语言本身是有由0 0和和1 1组成的，符合计组成的，符合计 算机的硬件特性，因此能够直接执行。但算机的硬件特性，因此能够直接执行。但 用机器语言编写程序很不方便且容易出错用机器语言编写程序很不方便且容易出错 ，因此就用助记符代替机器语言，产生了，因此就用助记符代替机器语言，产生了 汇编语言。汇编语言。 n n 汇编语言比机器语言在可读性方面有了进汇编语言比机器语言在可读性方面有了进 步，但是其依赖具体机器的特性无法改变步，但是其依赖具体机器的特性无法改变 ，给程序设计语言增添了难度。，给程序设计语言增添了难度。 8 n n 高级语言不能直接在机器上运行，它不是面向机高级语言不能直接在机器上运

5、行，它不是面向机 器，而是面向应用的，因此，要想让高级语言运器，而是面向应用的，因此，要想让高级语言运 行必须有编译程序。编译程序就是这样的一种程行必须有编译程序。编译程序就是这样的一种程 序，它能将高级语言编写的源程序转换成与之在序，它能将高级语言编写的源程序转换成与之在 逻辑上等价的低级语言形式的目标程序。逻辑上等价的低级语言形式的目标程序。 n n 高级语言程序的执行通常分为两个阶段，即编译高级语言程序的执行通常分为两个阶段，即编译 阶段和运行阶段，源程序的运行过程如图阶段和运行阶段，源程序的运行过程如图1-11-1所示所示 。编译阶段将源程序变换成目标程序；运行阶段。编译阶段将源程序变

6、换成目标程序；运行阶段 则由所生成的目标程序连同运行系统（数据空间则由所生成的目标程序连同运行系统（数据空间 分配子程序、标准函数程序等）接受程序的初始分配子程序、标准函数程序等）接受程序的初始 数据作为输入，运行后输出计算结果。如果目标数据作为输入，运行后输出计算结果。如果目标 程序是汇编语言的形式，则需要在编译阶段和运程序是汇编语言的形式，则需要在编译阶段和运 行阶段之间加一个汇编阶段。行阶段之间加一个汇编阶段。 9 10 n n 高级语言编写的程序除了可以通过编译方高级语言编写的程序除了可以通过编译方 式外，还可以通过解释程序执行。所谓解式外，还可以通过解释程序执行。所谓解 释程序是一种

7、语言翻译程序，读入一条语释程序是一种语言翻译程序，读入一条语 句，解释一条语句，执行一条语句，边读句，解释一条语句，执行一条语句，边读 入边执行。入边执行。 11 n n 程序设计语言的执行基本有两种方式：程序设计语言的执行基本有两种方式： uu解释方式：使用解释程序，对程序逐个解释方式：使用解释程序，对程序逐个 语句进行分析，根据语句的含义进行执语句进行分析，根据语句的含义进行执 行。行。 uu翻译方式：首先由翻译程序将程序翻译翻译方式：首先由翻译程序将程序翻译 成为机器语言（或者虚拟机的语言），成为机器语言（或者虚拟机的语言）， 然后执行。然后执行。 n n 比较：比较： uu翻译的方式可

8、以使得一次翻译过后，多翻译的方式可以使得一次翻译过后，多 次运行。适于花较大的精力进行优化工次运行。适于花较大的精力进行优化工 作。作。 12 编译程序 源程序 目标程序 (*.C / *.PAS) (*.OBJ / *.EXE) 13 n n 解释程序与编译程序的主要区别是：编译程序解释程序与编译程序的主要区别是：编译程序 将源程序翻译成目标程序后再执行目标程序，将源程序翻译成目标程序后再执行目标程序， 而解释程序是逐条读出源程序中的语句并执行而解释程序是逐条读出源程序中的语句并执行 ，即在解释程序的执行过程中，即在解释程序的执行过程中并不产生目标程并不产生目标程 序序。 n术语“编译”的内

9、涵是实现从源语言表示的算法 向目标语言表示的算法的等价变换。 编译程序的分类 宿主机：运行编译程序的计算机 目标机：运行编译程序产生目标代码的计算机 a 诊断编译程序：帮助程序开发和调试； b 优化编译程序：提高代码效率； c 交叉编译程序：产生不同于宿主机的机器代码； d 可变目标编译程序：不需重写与机器无关的 部分； 1. 识别出句子中的一个个 单词 2. 分析句子的语法结构 3. 初步翻译句子的含意 4. 译文修饰 5. 写出最后的译文 1. 词法分析 2. 语法分析 3. 语义分析与中间代码 生成 4. 优化 5. 目标代码生成 英译与编译的比较 1.2 1.2 编译过程概述编译过程概

10、述 掌握编译过程的五个基本阶段，是我们学习编译 原理课程的基本内容，把编译的五个基本阶段与英译 中的五个步骤相比较，有利于对编译过程的理解。 1.词法分析 任务：输入源程序，对构成源程序 的字符串进行扫描和分解，识别出一个 个单词（也称单词符号，或简称符号） 。 如基本字、标识符、常数、算符、界符。 在词法分析阶段所依循的是语言的 词法规则。描述词法规则的有效工具是 正规式和有限自动机。 17 n n 在高级语言中，所谓单词，就是指逻辑上在高级语言中，所谓单词，就是指逻辑上 紧密相连的一组字符，这些字符具有集体紧密相连的一组字符，这些字符具有集体 含义。单词是语言中最小的语义单位，如含义。单词

11、是语言中最小的语义单位，如 语言中的关键字、标识符、运算符和界限语言中的关键字、标识符、运算符和界限 符。词法分析的依据是词的构造。单词的符。词法分析的依据是词的构造。单词的 构造规则在高级语言中有明确的规定，比构造规则在高级语言中有明确的规定，比 如哪些为保留字、变量如何定义、常量如如哪些为保留字、变量如何定义、常量如 何构造、分界符有哪些等。何构造、分界符有哪些等。 18 for I:=1 to 100 do 19 表1-1词法分析程序 类型名类型名单词单词类型名类型名单词单词 保留字保留字main main 左括号左括号 ( ( 右括号右括号 ) ) 花括号花括号 保留字保留字float

12、 float 标识符标识符 x x 等号等号 = = 常量常量 2 2 逗号逗号 , , 标识符标识符 y y 等号等号 = = 常量常量 3 3 逗号逗号 , , 标识符标识符 s s 分号分号 ; ; 标识符标识符 s s 等号等号 = = 标识符标识符 x x 运算符运算符 + + 标识符标识符 y y 运算符运算符 * * 常量常量 5 5 分号分号 ; ; 花括号花括号 n n 例如，用例如，用C C 语言编语言编 写的程序段如下：写的程序段如下： n n main( )main( ) n n n n float x=2,y=3,s;float x=2,y=3,s; n n s=x+

13、y*5;s=x+y*5; n n n n 识别出的单词序列识别出的单词序列 为表为表1-11-1所示所示 2020 例：一个 C 程序的编译过程 n n 源程序：源程序： main( ) main( ) printf( printf(“ “hellohello” ”);); n n 1. 1. 词法分析词法分析 uu分析字符序列；分析字符序列； uu识别单词（种别、识别单词（种别、 属性）属性） uu查词法错误；查词法错误； uu标识符登记；标识符登记； 结果结果 IDNIDNmainmain ( ) IDNIDN printf printf ( STRSTRhellohello ) ; 2.

14、语法分析 在词法分析的基础上，根据语言的语法规 则，把单词符号串分解成各类语法单位（语法 范畴），如“短语”、“句子”、 “子句”、“程序 段”等。通过语法分析，确定整个输入串是否 构成语法上正确的“程序”。 语法规则通常用上下文无关文法描述。 2222 语法分析 n n 分析单词序列；分析单词序列； n n 识别语法结构；识别语法结构； n n 查语法错误；查语法错误； n n 构造分析树；构造分析树； 3. 语义分析与中间代码的产生 这一阶段通常包括两方面的工作首先对各种语法 范畴进行静态语义检查，如果正确则进行另一方面的 工作，即进行中间代码的翻译。 通常使用属性文法描述语义规则。 所谓

15、“中间代码”是一种含义明确，便于处理的记 号系统,它通常独立于具体的硬件系统。一般用四元 式表示中间代码。 中间代码除四元式外，还有三元式、间接三元式 、逆波兰记号、树形表示等。 算符 左操作数 右操作数 结果 2424 语义分析过程 n n 确认标识符的属性确认标识符的属性 uu类型、作用域等类型、作用域等 n n 语义检查语义检查 uu运算的合法性、取值范围等运算的合法性、取值范围等 n n 子程序的静态绑定子程序的静态绑定 uu代码存储的相对地址代码存储的相对地址 n n 变量的静态绑定变量的静态绑定 uu数据存储的相对地址数据存储的相对地址 2525 生成中间代码 n n 中间语言中间

16、语言 uu简单规范简单规范 uu机器无关机器无关 uu易于优化与转换易于优化与转换 n n 按照语法分析树生按照语法分析树生 成中间语言代码成中间语言代码 uu运算指令运算指令 uu控制指令控制指令 例（三地址代码）例（三地址代码） x := sx := s（赋值）（赋值） param xparam x（参数（参数 ） call fcall f（函数调用（函数调用 ） 注释注释: : s s 是是 hello hello 的地址的地址 f f 是函数是函数 printf printf 的地的地 址址 2626 常见的中间语言有常见的中间语言有逆波兰式逆波兰式、三元式三元式和和四元式四元式。 例如，四元式的形式为例如，四元式的形式为: : （算符，运算对象