课程简介 Principles of Compiler Yinliang Zhao Xi an Jiaotong University 2012 本课程内容介绍把高级语言程序转换为低级语言程序的原理和实现技术 本课程目的是为计算机科学与技术专业的本科生系统地介绍程序分析 变换 运行管理及优化等技术 旨在培养学生解决程序构造和处理的能力, 所学知识在编译器设计实现 程序分析与验证 程序转换和优化等应用中均能发挥作用 2 任课教师情况 教学安排 Instructor: 赵银亮教授联系方式 :yinliang_zhao@163.com 办公室 : 西一楼 411 室, 电话 82667860-808 T:3 人 与编译有关的研究背景 : Lisp 机 Lisp_M1 系统 (1987-90) Common Lisp Object System 实现 (1990-95) 并行程序性能分析 (1996-98) C 语言交叉编译器 (2000-01) DSP C 编译系统 (2002-05) 推测多线程编译技术 (2008-10) 总学时 52 64 课内学时 44 56, 主要讲授大纲中的知识点上机实验 8, 将安排具体题目, 提交结果辅导答疑, 每周四下午 4-6 点西一楼 411 室综合成绩 : 平时成绩 20%, 包括上机 作业和课堂笔记上机 : 由班长去计算机系实验中心登记作业 : 指定时间提交, 过后不补课堂笔记 : 期末统一收缴后检查并评分期末考试 80% 3 4 线程级推测模型及编译优化方法 (2012-15) 1
教材及参考书 陈火旺等. 程序设计语言编译原理 ( 第 3 版 ). 国防工业出版社. Kenneth C. Louden. Compiler Construction: Principles and Practice ( 英文版 1997). 机械工业出版社, 2002 lfred V. ho, Ravi Sethi, Jeffrey D. Ullman. Compilers :principles, techniques, and tools(2001) 有翻译本 : 南大赵建华等译. 编译原理. 机械工业, 2009. 下载区与讨论区 邮件联系方式联系方式 :xjtucompiler2012@163.com 课件及资料下载 问题讨论等 : 用密码 xjtucompiler 打开上述邮箱可以下载资料有问题发邮件到上述邮箱 回答问题或讨论也可以使用这个邮箱进行 5 6 第一章, 1.1-1.5 第二章, 2.1-2.3 第三章, 3.1-3.3, 3.4 1 第四章, 4.1-4.6 第五章, 5.1, 5.2*, 5.3,5.4 1 第六章, 6.1-6.2, -* 第七章, 7.1-7.7 第八章, 8.1-8.4 第九章, 9.1-9.5, 9.6* 第十章, 10.1-10.3, 11.4* 主要教学内容 引论形式语言简介词法分析自顶向下语法分析自底向上语法分析属性文法中间代码生成符号表运行时存储空间组织代码优化 寄存器分配 注意 : 讲课内容与教材内容不是严格一致, 对于一些内容, 课件中讲得更深入细致, 另一些内容则相比教材更简略, 总体服从大纲要求 7 几点说明 先修课程 : 离散数学 数据结构 程序设计语言 形式语言与自动机学习本课程的目标 : 理解编译过程 ; 能够编写简单的编译程序 ; 有进行程序分析 变换 评价的基础 学习的途径 : 原理入手 ( 掌握知识点 ); 掌握相关理论方法和技术方法 ; 多做练习 本课程的编程实验推荐采用 C 或 Java 编程进行 8 2
第一章引论 基本概念 什么叫编译程序编译过程概述编译程序的结构及生成 编译程序是一个程序, 该程序将用某个语言写的程序 ( 称为源程序 ) 作为输入, 并翻译成为功能上等价的另一个语言程序 ( 称为目标程序 ). 源语言通常是高级语言, 如 C, Fortran 等 ; 目标语言通常是低级语言如汇编或机器语言 ; 随着翻译的进行, 编译程序也报告错误信息以帮助程序员改错, 直到翻译通过为止. 9 源语言 源程序 if(a==b) a=2; b=4;... 输入 编译器词法分析语法分析语义处理代码生成代码优化 错误及警告 实现语言 目标程序 mov a, R1 mov b, R2... 输出 目标语言 10 几个注意的问题 语言的抽象层次 1 源语言是高级语言, 目标语言是低级语言时? 源语言和目标语言任意时? 编译器 / 翻译程序 2 书写编译器的语言可以是高级语言也可以是低级语言. 用什么语言编写编译器无关紧要 3 运行编译器的机器跟运行目标程序的机器可以相同也可以不同. 编译器 / 交叉编译器 宿主机 / 目标机 11 机器语言 : 汇编语言 : 高级语言 : 能够被计算机的硬件直接执行的指令程序将硬件指令用一些助记符表示 如 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) 12 3
编译器的种类 诊断编译程序侧重于错误信息, 帮助开发调试优化编译程序侧重于提高代码效率交叉编译程序宿主机和目标机不是同一个机器可变目标编译程序 仅定制编译器中跟机器有关部分实现针对新目标机的代码生成 解释器和编译器特点 概念上的不同 ( 翻译 / 直接执行 ) 基于解释执行的程序可以动态修改自身, 而基于编译执行的程序动态性较弱 基于解释方式有利于人机交互 基于解释执行的速度较慢 解释器需要保存的信息较多, 空间开销大二者实现技术相似 13 14 1.2 编译过程概述 for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 编译过程 源程序 ( 字符流 ) 词法分析单词符号 (Token 流 ) 语法分析语法单位 ( 语法树 Parse 树 ) 语义分析中间表示代码优化优化的中间表示代码生成 15 目标代码 ( 汇编代码 ) 16 4
Step1 词法分析 依循语言的词法规则, 扫描源程序的字符串, 识别每一个单词, 并将其表示成内部表示形式, 即 TOKEN. Step1 词法分析 18..23 + val#ue 源程序字符流 : 不是数 变量名不能有 # 字符 TOKEN 流 : Num(234) mul_op lpar_op Num(11) add_op Num(-22) rpar_op 17 文法 ; 正规式 ; 有限自动机 18 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 19 源程序在文件中的表示 20 5
Step2 语法分析 ($begin ($id,z1) ($semi ($line, ($var, ($colon ($line, ($write ($id,x1) ($real ($id,z1) $Lparen ($colon ($semi ($assig ($id,z1) ($real ($line, ($id,x1) ($plus ($semi ($id,x1) ($plus ($realc,5.5) ($line, $assig ($intc, 55) $Rparen ($var, ($realc, 0.5) ($semi, ($semi, 依据语言的语法规则, 将单词的 Token 序列转化为语法单位 ( 语法范畴 )( 短语 子句 句子 程序段 程序 ), 并确定整个输入串是否构成一个语法上正确的程序 确定 Token 之间有什么关系 ($line, ($read $Lparen ($id,x1) $Rparen ($semi ($line, ($id,z1) ($assig ($id,z1) ($plus ($id,x1) ($end ($stop # 词法分析后的 TOKEN 表示 21 22 Token 流 : num * ( num + num ) 语法树 : <expr> num <expr> <op> 语法分析 <expr> 规约 ; ( * <expr> ) LL(1) 分 <expr> <op> 析法 <expr> LR 分析法 num + num 文法 ; 语法树 ; 推导 ; 23 语法分析 int * foo(i, j, k)) int j; for(i=0; i j) fi(i>j) return j; 不是保留字 不是表达式 多余的括号 缺少步长 24 6
Step3 语义分析 语义分析 对语法分析所识别出的各类语法范畴, 分析其含义, 查错, 并产生源程序所对应的中间表示 ( 中间代码 ) 确定整体结构的含义 属性文法 ; 语义函数 int * foo(i, j, k) int j; int x; x = x + j + N; return j; 类型未说明变量未说明返回结果类型不匹配使用了没有初始化的变量 25 26 for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; Step4 优化 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; Constant Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 27 28 程序等价变换 ; 控制流 数据流分析 7
Constant Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; lgebraic Simplification for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; 29 30 lgebraic Simplification for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; Copy Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; 31 32 8
Copy Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Common Subexpression Elimination for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); 33 34 Common Subexpression Elimination Dead Code Elimination int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; 35 int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; 36 9
Dead Code Elimination int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Loop Invariant Removal int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; 37 38 Loop Invariant Removal int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t; Strength Reduction int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t; 39 40 10
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; 41 Step5 代码生成 中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码 42 43 44 11
1.3 编译程序的结构及生成 源程序 表格管理 表格管理出错处理遍前端与后端 T 型图 表 格 管 理 词法分析单词符号语法分析语法单位中间代码生成中间代码代码优化 中间代码 出错处理 表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他表格操作关注方便性和时空效率 目标代码生成 目标代码 45 46 出错处理 一遍与多遍编译 语法错误不符合语法 ( 或词法 ) 规则的错误 单词拼写错误 括号不匹配等语义错误不符合语义规则的错误 说明错误 作用域错误 类型不匹配等 是对源程序或编译中间结果从头到尾扫描一次, 并做有关的加工处理, 生成新的中间结果或目标程序 注意各遍间的中间结果 ( 内部形式 外部形式 ) 全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内 47 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 48 12
编译前端与后端 前端指跟目标机无关的部分, 一般包括 : 词法 语法 语义分析 ; 后端指跟目标机有关的部分, 一般包括优化和代码生成 ; 前后端之间的接口 : 中间表示符号表 49 50 51 52 13
T 型图 用高级语言 L 构造编译程序 S I T S Source Language T Target Language I Implementation Language 由用 I 语言写的编译程序把用 S 语言写的源程序翻译成用 T 语言写的目标程序 53 P L L 将写好的语言 P 的编译程序用 L 的编译程序编译后就可得到用 机器代码实现的 P 编译程序 P 54 编译程序的移植 自编译方式 L (2) L B (2) L L B (3) L B (4) B B 先对语言的核心部分构造一个小小的编译程序 ( 可用低级语言实现 ) 再以它为工具构造能编译更多语言成分的较大编译程序如此不断扩展, 最后形成整个编译程序 ( 滚雪球 ) L L (1) 将至此再将 (2), (2) 用将 L (1) 编写能在用 机器上的 (3) 编译编译, B 得到机, L 的编即可 机译程序器上运行的产生得到已有 B 机器上运行的产生 (1) 机器上的高级移植为 B B L 代码的的语 LB 代码的的 L 言的编译程序 L (2) (3) (1) (4) (4) 55 56 14
构造工具 构造编译程序的工具称为编译程序 - 编译程序 或编译程序产生器自动产生扫描器 LEX FLEX 自动产生语法分析器 YCC BISON Java 编译器的编译器 Jastdd 编译技术的应用 高级程序设计语言的实现语言特征与编译优化动态编译针对计算机体系结构的优化并行性存储层次结构新计算机体系结构的设计 RISC 与专用体系结构程序翻译软件生产率工具 57 58 小结 理论方法 : 形式语言与自动机 属性文法 数据流分析等编译技术 : 词法 语法 语义分析方法, 代码生成与优化方法编译程序构造 : 编译器结构 典型算法 数据结构课程内容主要涉及编译器前端 本章练习 概要了解编译过程的内容和特点掌握交叉编译器 T 形图概念查阅维基百科词条, 了解概念 programming language compiler 59 60 15