编译原理-1引论

1、 一. 什么叫编译程序 二. 编译过程概述 三. 编译程序的结构 四. 编译程序生成 五. 课程学习指导编译程序编译程序是系统软件系统软件中资格最老的成员之一资格最老的成员之一编译理论和技术近30年来发展十分迅速、成熟发展十分迅速、成熟1.1.编译程序历史编译程序历史现已形成一套较为系统化的系统化的编译理论和技术2.2.编译理论与其他课程关系编译理论与其他课程关系编译理论编译理论自动机和形式语言离散数学数据结构操作系统素材素材基础基础控制对象控制对象编译理论编译理论 的许多想法和技术可用于一般软件的设计一般软件的设计：3.3.编译理论的应用编译理论的应用有穷状态技术有穷状态技术模式识别模式识别

2、情报检索情报检索文本编辑程序文本编辑程序上下文无关文法上下文无关文法语法制导翻译语法制导翻译建立多种文本处理程序建立多种文本处理程序代码优化技术代码优化技术由非结构化到结构化的程序转换由非结构化到结构化的程序转换程序校验程序校验翻译程序（翻译程序（TranslatorTranslator）是一种程序，其输入输入是某种语言某种语言的一系列语句，而其输出输出则是另一种语言另一种语言的一系列语句。4.4.翻译程序翻译程序源语言程序源语言程序目标语言程序目标语言程序TranslatorTranslator输入输入输出输出编译程序（编译程序（CompilerCompiler）是一种程序。它把用高级语言写

3、的高级语言写的源程序源程序作为数据接收接收，经过翻译转换，产生面向机器的代面向机器的代码码作为输出输出。这当中代码还可能要由汇编程序汇编程序或装配程序装配程序作进一步加工，得出目标程序目标程序，交给计算机执行。5.5.编译程序编译程序高级语言源程序高级语言源程序面向机器代码面向机器代码CompilerCompiler目标程序代码目标程序代码汇编汇编 装配装配6.6.翻译与编译比较翻译与编译比较源语言程序源语言程序目标语言程序目标语言程序转变为转变为高级语言源程序高级语言源程序面向机器代码面向机器代码编译为编译为这种变换程序称为翻译程序翻译程序编译程序编译程序 有一些限制 （针对输入、输出）（针

4、对输入、输出）这种变换程序称为编译程序编译程序1.1.编译过程的组成编译过程的组成编译过程编译过程词法分析词法分析语法分析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成源程序源程序单词符号单词符号中间代码中间代码语法单位语法单位目标代码目标代码中间代码（优化后）中间代码（优化后）源程序源程序目标代码目标代码2.2.词法分析词法分析任务任务所做转换所做转换依据依据构词规则构词规则主要理论基础主要理论基础自动机理论自动机理论源程序字符串源程序字符串单词符号单词符号输入源程序；扫描、分解字符串，识别出一输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、

5、界符、个个单词（定义符、标识符、运算符、界符、常数）常数）2.2.词法分析词法分析示例示例FOR K := 1 TO 100FOR K := 1 TO 100 M := I + 10 M := I + 10 * * K K N := J + 10 N := J + 10 * * K KNEXT KNEXT KTOTONEXTNEXTFORFOR K KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +定义符定义符标识符标识符分界符分界符运算符运算符 常数常数3.3.语法分析语法分析任务任务所做转换所做转换依据依据语法规则语

6、法规则主要理论基础主要理论基础上下文无关文法上下文无关文法单词符号单词符号语法单位（语法范畴）语法单位（语法范畴）在词法分析基础上，将单词符号串转化为语在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构程序段、程序），并确定整个输入串是否构成语法上正确的程序。成语法上正确的程序。3.3.语法分析语法分析示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +变量、常数及其运算结果

7、均是表达式变量、常数及其运算结果均是表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式赋值句的形式为赋值句的形式为“变量：表达式变量：表达式”赋值句赋值句赋值句赋值句多个赋值句可构成语句块多个赋值句可构成语句块语句块语句块表达式可作为循环的初值和终值表达式可作为循环的初值和终值初值初值终值终值简单数值变量可作为循环的控制变量简单数值变量可作为循环的控制变量控制变量控制变量控制变量控制变量此时可以看出上述结果符合循环语句此时可以看出上述结果符合循环语句的语法定义，故语法分析成功完成的语法定义，故语法分析成功完成4.4.中间代码生成中间代码生成任务任务所做转换所做转换依

8、据依据语义规则语义规则主要理论基础主要理论基础属性文法属性文法语法范畴语法范畴中间代码中间代码对语法分析所识别出的各类语法范畴，分析对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。其含义，并进行初步翻译（产生中间代码）。4.4.中间代码生成中间代码生成示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +(1) ( :=, 1, , K )(1) ( :=, 1, , K )(2) ( j,100, K, )(2) ( j,100, K, )(3)

9、 ( (3) ( * *, 10, K, T, 10, K, T1 1 ) )(8) ( j, , , (2)(8) ( j, , , (2)(7) ( +, K, 1, K )(7) ( +, K, 1, K )(4) ( +, I, T(4) ( +, I, T1 1, M ), M )(9) ( )(9) ( )(9)(9)(5) ( (5) ( * *, 10, K, T, 10, K, T2 2 ) )(6) ( +, J, T(6) ( +, J, T2 2, N ), N )T T1 1T T2 2(1) K := 1(1) K := 1(2) if 100K goto (9)(

10、2) if 100K goto (9)(3) T(3) T1 1 := 10 := 10 * * K K(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(4) M := I + T(4) M := I + T1 1(9)(9)(5) T(5) T2 2 := 10 := 10 * * K K(6) N := J + T(6) N := J + T2 2循环语句循环语句出口语句出口语句循环块循环块STEP 1STEP 1生成四元式生成四元式将四元式重写为另一种形式的中间代码将四元式重写为另一种形式的中间代码(1) ( :=, 1, , K

11、)(1) ( :=, 1, , K )(2) ( j,100, K, (9)(2) ( j,100, K, (9)(3) ( (3) ( * *, 10, K, T, 10, K, T1 1 ) )(8) ( j, , , (2)(8) ( j, , , (2)(7) ( +, K, 1, K )(7) ( +, K, 1, K )(4) ( +, I, T(4) ( +, I, T1 1, M ), M )(9) ( )(9) ( )(5) ( (5) ( * *, 10, K, T, 10, K, T2 2 ) )(6) ( +, J, T(6) ( +, J, T2 2, N ), N

12、)循环语句和循环语句和出口语句出口语句 彼此相连地彼此相连地被定义被定义包括循环语包括循环语句开始到有句开始到有同一控制变同一控制变量的第一个量的第一个出口语句的出口语句的那些语句的那些语句的自然序列称自然序列称为一循环块为一循环块块嵌套不可交叉，块嵌套不可交叉，嵌套块控制变量嵌套块控制变量不可同名不可同名不正确不正确正确嵌套正确嵌套缺省的缺省的 STEP STEP = = STEP 1STEP 15.5.代码优化代码优化任务任务所做转换所做转换依据依据程序等价变换规则程序等价变换规则主要理论基础主要理论基础数据流方程数据流方程中间代码中间代码中间代码（优化后）中间代码（优化后）对于代码（主要

13、是中间代码）进行加工变换，对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的以期能够产生更为高效（省时间和空间）的目标代码。目标代码。5.5.代码优化代码优化示例示例(1) K := 1(1) K := 1(2) if 100K goto (9)(2) if 100K goto (9)(3) T(3) T1 1 := 10 := 10 * * K K(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(4) M := I + T(4) M := I + T1 1(9)(9)(5) T(5) T2 2 := 10 :

14、= 10 * * K K(6) N := J + T(6) N := J + T2 2(3) K := 1(3) K := 1(4) if 100K goto (9)(4) if 100K goto (9)(8) goto (4)(8) goto (4)(7) K := K + 1(7) K := K + 1(9)(9)(3) T(3) T1 1 := 10 := 10 * * K K(4) M := I + T(4) M := I + T1 1(1) M := I(1) M := I(5) M := M + 10 (5) M := M + 10 (5) T(5) T2 2 := 10 :=

15、10 * * K K(6) N := J + T(6) N := J + T2 2(2) N := J(2) N := J(6) N := N + 10(6) N := N + 10(1) K := 1(1) K := 1(2) if 100K goto (9)(2) if 100K goto (9)(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(9)(9)6.6.目标代码生成目标代码生成任务任务所做转换所做转换依据依据硬件体系结构、指令系统硬件体系结构、指令系统中间代码中间代码目标代码目标代码将中间代码变换成特定机器上的低级语言代码将

16、中间代码变换成特定机器上的低级语言代码目标代码形式目标代码形式绝对指令、可重定位指令、汇编指令绝对指令、可重定位指令、汇编指令6.6.目标代码生成目标代码生成LD RLD R1 1, I, IL L2 2: ST R: ST R1 1, M, MLD RLD R2 2, J, JST RST R2 2, N, NLD RLD R0 0, 1, 1L L1 1: CMP 100, R: CMP 100, R0 0J LJ L2 2ADD RADD R1 1, 10, 10ADD RADD R2 2, 10, 10ADD RADD R0 0, 1, 1J LJ L1 1示例示例(8) goto (

17、4)(8) goto (4)(7) K := K + 1(7) K := K + 1(1) M := I(1) M := I(9)(9)(6) N := N + 10(6) N := N + 10(3) K := 1(3) K := 1(2) N := J(2) N := J(5) M := M + 10 (5) M := M + 10 (4) if 100K goto (9)(4) if 100K goto (9)(9)(9)(8) goto (4)(8) goto (4)(7) K := K + 1(7) K := K + 1(1) M := I(1) M := I(6) N := N +

18、 10(6) N := N + 10(3) K := 1(3) K := 1(2) N := J(2) N := J(4) if 100K goto (9)(4) if 100K goto (9)(5) M := M + 10 (5) M := M + 10 1.1.编译程序总框编译程序总框表表格格管管理理词法分析词法分析语法分析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成源程序源程序单词符号单词符号中间代码中间代码语法单位语法单位目标代码目标代码中间代码中间代码出出错错处处理理2.2.表格与表格管理表格与表格管理编译各阶段均须维持表格维持表格并进行表格管理表格管理

19、建表的技术支持技术支持是数据结构数据结构表格的分类、结构、处理方法分类、结构、处理方法决定于语言语言及机器机器，还有优化措施优化措施2.2.表格与表格管理表格与表格管理编译程序涉及的表格有：符号名表符号名表常量名、变量名、数组名、过程名、 性质、 引用、定义常数表常数表标号表标号表入口名表入口名表过程引用表过程引用表各种类型常数的值标号的定义和引用情况过程的入口名和入口位置外部过程的名字、引用位置循环表循环表等价名表等价名表公用链表公用链表格式表格式表中间代码表中间代码表3.3.出错处理出错处理一个好的编译程序应该：全全 最大限度发现错误准准 准确指出错误的性质和发生地点局部化局部化 将错误的

20、影响限制在尽可能小的范围内若能自动校正错误自动校正错误则更好，但其代价非常高代价非常高3.3.出错处理出错处理源程序中的错误通常分为 ：语法错误语法错误 不符合语法（或词法）规则的错误语义错误语义错误 不符合语义规则的错误单词拼写错误、括号不匹配 .说明错误、作用域错误、类型不匹配 .4.4.遍遍 遍遍 是对源程序或源程序的中间结果从头到尾从头到尾扫描一次扫描一次，并作有关的加工处理加工处理，生成新的中生成新的中间结果或目标程序间结果或目标程序。词法分析词法分析语法分析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成一遍一遍语法分析器语法分析器处于核心地位处于核心地位一

21、遍一遍 局部优化局部优化一遍一遍一遍一遍 全局优化全局优化5.5.编译前端与后端编译前端与后端 词法分析词法分析语法分析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成编译前端编译前端主要由与源语言有关与源语言有关但与目标机无关与目标机无关的那些部分组成编译后端编译后端包括编译程序中与目标机有关与目标机有关的那些部分以往以往 编译程序的构造大多采用机器语言机器语言或汇编语言汇编语言现在现在 编译程序的构造越来越多采用高级语言高级语言1.1.编译程序的构造工具编译程序的构造工具有时为了充分发挥效率充分发挥效率或满足不同需求满足不同需求，仍然采用 机器语言机器语言或汇编语言

22、汇编语言构造编译程序（或其核心部分）2. T2. T型图型图S SI IT TS S表示源语言表示源语言T T表示目标语言表示目标语言I I表示编译程序的实现语言表示编译程序的实现语言3. 3. 用高级语言用高级语言L L1 1构造编译程序构造编译程序L L1 1A AA AL L2 2L L1 1A AL L2 2A AA A已有用A机器代码实现的高级语言L1的编译程序可用高级语言L1编写另一个高级语言L2的编译程序将写好的语言L2的编译程序用L1的编译程序编译后就可得到用A机器代码实现的L2编译程序4. 4. 编译程序的移植编译程序的移植L LA AA A(1)(1)L LL LB B(2)(2)L LA AB B(3)(3)已有A机器上的高级 语言L编译程序（1）L LB BB B(4)(4)用L编写能在B机器上运行的L的编译程序（2）将(2)用(1)编译，得到A机器上运行的产生B代码的L的编译程序（3）L LL LB B(2)(2)再将(2)用(3)编译，即可得到B机器上运行的产生B代码的L的编译程序（4）至此，将A机器上的L的编译程序(1)移植为B机器上的L的编译程序（4）5. 5. 自编译方式自编译方式先对语言的核心部分构造一个小小的编译程序（可用低级语言实现）（可用