编译原理 - 陈火旺版 - 第一章

编译方法中国人民大学信息学院陈文萍教学目的&要求•教学目的–介绍程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术方法和一些自动构造工具•教学要求–掌握编译器的基本结构–掌握编译器的工作机制–能独立完成小型编译程序–能将所学的技术和算法应用于类似软件的设计和实现中•联系信息：–E-mail：[e-mail]教学安排讲授内容课时1.概述22.高级语言及其语法描述2-43.词法分析6-84.自上而下语法分析4-65.自下而上语法分析10-12评分标准•平时成绩：10%•实验成绩：20%（两个实验）•期末成绩：70%（笔试闭卷）1.概述•1.1什么是编译程序•1.2编译过程•1.3编译程序的结构•1.4与编译程序相关的程序•1.5编译程序的生成1.1什么是编译程序•编译程序：把高级程序设计语言翻译成等价的低级语言程序，最终生成可执行代码。–功能：翻译程序，语言转换系统–编译型语言：C，C++等•翻译程序：把一种程序语言翻译成另一种程序语言的程序，两者逻辑上等价。如：编译，汇编，反汇编等。编译程序高级语言程序低级语言程序源语言程序目标语言程序翻译程序1.1什么是编译程序•解释程序：以源程序作为输入，不产生目标程序，而是按照语言的定义，边解释边执行。–许多用于编译程序的构造技术同样也适用于解释程序。–解释型语言：如Basic•Java：先编译为中间代码，再解释执行。1.2编译过程•引例：翻译（编译）程序的工作过程：譬如：“Iwishyousuccess.”翻译成汉语。1）单词进行词法分析：“I”“wish”“you”“success”（代）（动）（代）（名）我希望你成功2）语法分析：（主语）（谓语）（间宾）（直宾）结论：是一个合乎英语语法的句子。3）语义分析：我希望你成功。4）汉语句子进行修饰（优化）：祝你成功。1.2编译过程•编译器的工作过程–词法分析–语法分析–语义分析及中间代码生成–代码优化–目标代码生成1.2编译过程——词法分析•扫描源程序的字符串，识别单词（基本字、标识符、常数、算符、界符）–例：position:=initial+rate*60;单词类型单词值标识符1(id1)position算符(赋值):=标识符2(id2)initial算符(加)+标识符3(id3)rate算符(乘)*整常数60界符；1.2编译过程——词法分析又如一个C源程序片断：inta;a=a+2;词法分析后可能返回:单词类型单词值基本字int标识符(变量名)a界符;标识符(变量名)a算符(赋值)=标识符(变量名)a算符(加)+整数2界符；1.2编译过程——语法分析•依据语法规则，把源程序的单词符号串组成语法单位（短语、子句，语句）•层次分析•例：position:=initial+rate*60;规则：赋值语句::=标识符“:=”表达式表达式::=表达式“+”表达式表达式::=表达式“*”表达式表达式::=标识符表达式::=整数表达式::=实数1.2编译过程——语法分析表达式赋值语句标识符表达式表达式+表达式标识符常数标识符:=表达式*1.2编译过程——语法分析:=+N60*Id1PositionId2initialId3rate分析结果：id1:=id2+id3*N1.2编译过程——语法分析规则赋值语句::=标识符“:=”表达式表达式::=表达式“+”表达式表达式::=表达式“*”表达式表达式::=标识符表达式::=整数表达式::=实数position+initial:=rate*60----语法错！1.2编译过程——语义分析•语义审查(静态语义)–上下文相关性–类型匹配–类型转换例:Programp();Varrate:real;procedureinitial;…position:=initial+rate*60/*error*//*error*//*warning*/;Programp();Varrate:real;Varinitial:real;Varposition:real;…position:=initial+rate*60…1.2编译过程——语义分析1.2编译过程——语义分析:=+inttoreal60*Id1PositionrealId2initialrealId3ratereal1.2编译过程——中间代码生成•独立于具体的硬件•与机器指令接近，易变换成机器指令•四元式：（算符、左操作数、右操作数、结果）–对左右操作数进行某种运算，所得值保存在结果中–按语义规则，生成四元式序列1.2编译过程——中间代码生成id1:=id2+id3*60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)1.2编译过程——代码优化•功能：对中间代码加工变换，生成更高效的目标代码•手段：公共子表达式的提取，循环优化，删除无用代码等•原则：等价变换1.2编译过程——代码优化例：id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换（1）(*id360.0t1)(2）（+id2t1id1)1.2编译过程——目标代码生成•中间代码——特定机器上的低级语言代码•目标代码的形式：–绝对指令代码–可重定位的指令代码–汇编指令代码(*,id3，60.0，t1)(+,id2，t1，id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id11.3编译程序结构•编译程序框架出错处理程序语法分析器语义分析与中间代码生成器目标代码生成器词法分析器代码优化器表格管理程序源程序单词符号语法单位中间代码中间代码目标代码1.3编译程序结构——表格管理•符号表：–记录源程序中使用的名字–收集每个名字的各种属性信息•类型、作用域、分配的存储单元信息1.3编译程序结构——出错处理•功能：检查错误、报告出错信息、排错、恢复编译工作•错误分类–语法错误：非法字符，括号不匹配–语义错误：说明错误，作用域错误，类型不一致1.3编译程序结构——编译阶段的组合•遍（Pass）对源程序或源程序的中间结果从头到尾扫描一遍•编译的前端（frontend）：与源语言有关，与目标机无关–词法分析，语法分析，语义分析，中间代码生成•编译的后端（backend）：与目标机有关，依赖于中间语言–代码优化，目标代码生成1.4与编译程序相关的程序•解释程序（interpreter）•汇编程序（assembler）•连接程序（linker）•装载程序（loader）•编辑器（editor）•调试程序（debugger）•预处理器（preprocessor）•描述器（profiler）•项目管理器（projectmanager）1.5编译程序的生成•实现编译程序的语言：机器语言，汇编语言或高级语言•T型图：–S：源语言；T：目标语言；I：编译器实现语言STI1.5编译程序的生成•T型图的组合•交叉编译AHBBKKAHKABHBCHACHAHBBHHAHH1.5编译程序的生成•自编译（自举）AHAAHAAHHAHH反复此过程以将要编译的语言编写一个编译器AHAAHHAHH核心的小编译器较优的编译器编译器的最终版本1.5编译程序的生成•移植一个用自身源代码编写的编译器AKAAHHAKHAKAAKHAKK交叉编译器原始编译器目标重定位为K的编译器目标重定位后的编译器