任课教师情况 编译原理 Principles of Compiler 赵银亮教授联系方式 :zyl9910@mail.xjtu.edu.cn 辅导老师 : 李聪 王旭昊 张长军 韦远科 赵银亮 2008 年秋 与编译有关的研究背景 : isp 机 isp_m1 系统 (1987-90) Common isp Object System 实现 (1990-95) 并行程序性能分析 (1996-98) C 语言交叉编译器 (2000-01) DSP C 编译系统 (2002-05) SpMT 编译技术 (2006-) 教学安排 教材及参考书 总学时 64 课内学时 56, 主要讲授大纲中的知识点上机实验 8, 将安排具体题目, 提交结果辅导答疑, 每周五下午 3-5 点西一楼 411 室 综合成绩 : 上机 10% ( 由各班长于计算机系实验中心登记上机时间 ) 作业 10% 指定时间提交, 过后不补考试 80% 陈火旺等. 程序设计语言编译原理 ( 第 3 版 ). 国防工业出版社. Kenneth C. ouden. Compiler Construction: Principles and Practice ( 英文版 1997). 机械工业出版社, 2002 lfred V. ho, Ravi Sethi, Jeffrey D. Ullman. Compilers :principles, techniques, and tools(2001) 课件及参考资料下载地址 : ftp 202.117.15.193 用户名和密码均为 parallel 主要教学内容 几点说明 第一章,1.1-1.5 第二章,2.1-2.3 第三章,3.1-3.3 3.4* 第四章,4.1-4.6 第五章, 5.1-5.2 5.3* 第六章,6.1-6.2 第七章, 7.1-7.7 第八章, 8.1-8.4 第九章, 9.1-9.5 第十章, 10.1-10.3 引论 形式语言简介 词法分析 自顶向下语法分析 自底向上语法分析 属性文法 中间代码生成 符号表 运行时存储空间组织 代码优化 先修课程 : 离散数学 数据结构 程序设计语言 学习本课程的目标 : 理解编译过程 ; 能够编写编译程序 ; 有进行程序分析 变换 评价的基础 学习的途径 : 原理入手 ( 掌握知识点 ); 掌握相关理论方法和技术方法 ; 多做练习 本课程的编程实验推荐采用 C 或 Java 编程 Yinliang Zhao 1
第一章引论 基本概念 什么叫编译程序 编译过程概述 编译程序的结构及生成 编译程序是一个程序, 该程序将用某个语言写的程序 ( 称为源程序 ) 作为输入, 并翻译成为功能上等价的另一个语言程序 ( 称为目标程序 ). 源语言通常是高级语言, 如 C, Fortran 等 ; 目标语言通常是低级语言如汇编或机器语言 ; 随着翻译的进行, 编译程序也报告错误或其他警告信息以帮助程序员改错, 直到翻译通过为止. 源语言 源程序 if(a==b) a=2; b=4;... 输入 词法分析语法分析语义处理代码生成代码优化 编译器 错误及警告 实现语言 目标程序 mov a, R1 mov b, R2... 输出 目标语言 1 源语言是高级语言, 目标语言是低级语言时? 源语言和目标语言任意时? 编译器 / 翻译程序 2 书写编译器的语言可以是高级语言也可以是低级语言. 3 运行编译器的机器跟运行目标程序的机器可以相同也可以不同. 用什么语言编写编译器无关紧要 编译器 / 交叉编译器 宿主机 / 目标机 语言的抽象层次 机器语言 : 能够被计算机的硬件系统直接执行的指令程序 汇编语言 : 将硬件指令用一些助记符表示 如 DD 表示加法操作, SUB 表示减法操作等等 高级语言 : 相对于前二者而言且更接近于自然语言的程序设计语言 Properties: need to be precise need to be concise need to be expressive need to be at a high-level (lot of abstractions) 编译器的种类 诊断编译程序侧重于错误信息, 帮助开发调试 优化编译程序侧重于提高代码效率 交叉编译程序宿主机和目标机不是同一个机器 可变目标编译程序仅定制编译器中跟机器有关部分实现针对新目标机的代码生成 解释器和编译器特点 概念上的不同 基于解释执行的程序可以动态修改自身, 而基于编译执行的程序动态性较弱 基于解释方式有利于人机交互 基于解释执行的速度较慢 解释器需要保存的信息较多, 空间开销大 二者实现技术相似 Yinliang Zhao 2
1.2 编译过程概述 int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 源程序 ( 字符流 ) 词法分析单词符号 (Token 流 ) 语法分析语法单位 ( 语法树 Parse 树 ) 语义分析中间表示代码优化优化的中间表示编译过程代码生成目标代码 ( 汇编代码 ) Step1 词法分析 依循语言的词法规则, 扫描源程序的字符串, 识别每一个单词, 并将其表示成所谓的机内表示 TOKEN 形式 Step1 词法分析 18..23 + val#ue 源程序字符流 : 不是数 变量名不能有 # 字符 TOKEN 流 : Num(234) mul_op lpar_op Num(11) add_op Num(-22) rpar_op 文法 ; 正规式 ; 有限自动机 Token 例子 标识符 ( 用户定义的名字 ); identifier 保留字 ( 关键字 / 基本字 ); reserved words 常数 ( 整数, 双精度数, 浮点数 );constant 界符 ( 分隔符 ); delimiters 运算符 ( 操作符 ); operators ( 种属, 值 ) 例 b e g i n v a r x 1 : r e a ; v a r z 1 : r e a l ; x : = 0. 5 ; z 1 : = x 1 + 5 5 w r i t e ( z 1 + 5. 5 ) ; e a d ( V 1 ) ; z 1 : = z 1 + 1 e n d. # l 1 ; r x 源程序在文件中的表示 Yinliang Zhao 3
Step2 语法分析 ($begin ($semi ($var, -) ($colon ($real ($colon ($semi ($assig ($real ($semi ($plus $assig ($intc, 55) ($var, -) ($realc, 0.5) ($semi, -) 依据语言的语法规则, 将单词的 Token 序列转化为语法单位 ( 语法范畴 )( 短语 子句 句子 程序段 程序 ), 并确定整个输入串是否构成一个语法上正确的程序 ($write $paren ($plus ($realc,5.5) $Rparen ($semi, -) ($read $paren $Rparen ($semi ($assig ($plus ($end ($stop # 词法分析后的 TOKEN 表示 num * ( num + num ) <expr> <expr> num 语法分析 <op> * <expr> ( <expr> ) <expr> <op> <expr> 文法 ; 语法树 ; 推导 ; 规约 ; (1) 分析法 R 分析法 语法分析 int * foo(i, j, k)) int j; for(i=0; i j) fi(i>j) return j; 多余的括号 缺少步长 num + num 不是保留字 不是一个表达式 Step3 语义分析 语义分析 对语法分析所识别出的各类语法范畴, 分析其含义, 查错, 并产生源程序所对应的中间表示 ( 中间代码 ) 属性文法 ; 语义函数 int * foo(i, j, k) int j; int x; x = x + j + N; return j; 类型未说明变量未说明返回结果类型不匹配使用了没有初始化的变量 Yinliang Zhao 4
Step4 优化 int x, y; int x, t, u, v; u = (a<<2/b); for(i = 0; i <= N; i++) v = 0; x = x + (4*a/b)*i + for(i = 0; i <= N; i++) (i+1)*(i+1); x = x + b*y; x = x + v + t*t; v = v + u; 程序等价变换 ; 控制流 数据流分析 Constant Propagation int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; lgebraic Simplification lgebraic Simplification int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; Copy Propagation int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Copy Propagation Common Subexpression Elimination Common Subexpression Elimination int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Dead Code Elimination int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Dead Code Elimination oop Invariant Removal Yinliang Zhao 5
oop Invariant Removal int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t; Strength Reduction Strength Reduction int x, t, u, v; u = (a<<2/b); v = 0; for(i = 0; i <= N; i++) x = x + v + t*t; v = v + u; Step5 代码生成 中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码 指令系统 1.3 编译程序的结构及生成 表格管理 出错处理 遍 前端与后端 T 型图 表格管理 源程序词法分析单词符号语法分析语法单位中间代码生成中间代码代码优化中间代码 出错处理 目标代码生成 目标代码 Yinliang Zhao 6
表格管理 表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他 表格操作关注方便性和时空效率 出错处理 语法错误 不符合语法 ( 或词法 ) 规则的错误 单词 拼写错误 括号不匹配等 语义错误 不符合语义规则的错误 说明错误 作用 域错误 类型不匹配等 全 最大限度发现错误 准 准确指出错误的性质和发生地点 局部化 将错误的影响限制在尽可能小的范围内 一遍与多遍编译 是对源程序或源程序的中间结果从头到尾扫描一次, 并作有关的加工处理, 生成新的中间结果或目标程序 注意各遍间的中间结果 ( 内部形式 外部形式 ) One-pass compiler: Type of software compiler that passes through the source code only once. One-pass compilers are faster, but may not generate an as efficient program. In addition, one-pass compilers cannot compile all types of source codes. http://www.computerhope.com/jargon/o/onepassc.htm 编译前端与后端 前端指跟目标机无关的部分, 一般包括 : 词法 语法 语义分析 ; 后端指跟目标机有关的部分, 一般包括优化和代码生成 ; 前后端之间的接口 : 中间表示符号表 Yinliang Zhao 7
T 型图 S I T S Source anguage T Target anguage I Implementation anguage 由用 I 语言写的编译程序把用 S 语言写的源程序翻译成用 T 语言写的目标程序 用高级语言 构造编译程序 编译程序的移植 P 将写好的语言 P 的编译程序用 的编译程序编译后就可得到用 机器代码实现的 P 编译程序 P (2) B (2) (1) (4) B B (3) B B 将至此再将 (2), (2) 用将 (1) 编写能在用 机器上的 (3) 编译编译, B 得到机, 的编即可 机译程序器上运行的产生得到已有 B 机器上运行的产生 (1) 机器上的高级移植为 B B 代码的的 B 代码的的语言 的编译程序 (2) (3) (4) (1) (4) 自编译方式 先对语言的核心部分构造一个小小的编译程序 ( 可用低级语言实现 ) 再以它为工具构造能编译更多语言成分的较大编译程序 如此不断扩展, 最后形成整个编译程序 ( 滚雪球 ) 构造工具 构造编译程序的工具称为编译程序 - 编译程序 编译程序产生器或翻译程序书写系统 自动产生扫描器 EX FEX 自动产生语法分析器 YCC BISON Yinliang Zhao 8
本章小结 编译过程 :5 个阶段 编译理论是基础 : 形式语言 属性文法 数据流方程等 编译技术是关键 : 各部分的构造 编译中的数据结构等 课程学习指导 具备一定的程序设计语言背景 本课程目标机器采用假想指令, 算法描述使用类 PSC 伪码 因为编译程序比较复杂, 故讨论中将其分解成各个部分, 学习中应注意前后联系, 多做练习 本章练习 概要了解编译过程的内容和特点 Yinliang Zhao 9