PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

空牝唐
4 years ago
Views:

1 Compiler Principles Overview Xiaoyuan Xie 谢晓园计算机学院 E301

2 基本情况课程类别 : 必修课程学分数 :3 课程学时数 :54 前导课程 : 高级程序设计语言离散数学数据结构计算机组成原理等考核方式 : 笔试 60% 作业和编程作业 40%

3 教师信息谢晓园, 计算机学院 E301 Tutor: 黎源

4 设置目的本课程是计算机科学与技术专业及相关专业的专业基础课, 是一门理论与实践紧密结合的课程开设本课程的目的是使学生了解并掌握编译过程中所涉及的基本理论和方法, 具备分析和实现编译器的基本能力

5 教学内容及学时分配内容学时 1. 引论 4 2. 词法分析 6 3. 上下文无关文法 4 4. 自顶向下的语法分析 4 5. 自底向上语法分析 8 6. 语法制导翻译 8 7. 中间表示 4 8. 中间代码生成 6 9. 运行阶段存储组织与管理代码生成及优化 4

6 教学内容及学时分配引论 : 编译器的作用工作过程结构构造方法等词法分析 : 正则表达式有穷自动机正则表达式到有穷自动机的转换和词法分析器生成工具 Lex 上下文无关文法 : 产生式推导语法树二义性文法设计自顶向下的语法分析 : 消除左递归与左公因子递归下降语法分析 FIRST 和 FOLLOW 集合 LL(1) 文法预测分析中的错误恢复自底向上语法分析 : 移进 - 归约技术 ; 句柄与活前缀 ;LR(0) 项与识别活前缀的自动机移进 - 归约与归约 - 归约冲突 LR(0) 文法 SLR 文法 LL(1) 项与自动机 LR(1) 文法 LALR 文法二义性的处理 LR 语法分析的错误恢复和语法分析器生成工具 Yacc

7 教学内容及学时分配语法制导翻译 : 语法制导定义 (SDD) 综合属性继承属性依赖关系图语法树遍历与属性求值的关系语法制导翻译规程 S 属性与 L 属性伴随语法分析过程的 SDD 实现中间表示 : 抽象语法树三地址码变量的作用域与符号表类型表达式与类型检查中间代码生成 : 表达式的翻译数组元素的引用控制流的翻译短路法与回填过程调用的翻译运行阶段存储组织与管理 : 程序的运行与数据区活动树与活动记录栈式运行环境嵌套过程的运行环境堆管理与垃圾回收概述参数传递方式及其实现 ; 代码生成及优化 : 目标语言指令选择寄存器分配基本快与流图基板快的优化数据流分析初步循环优化指令流水线与指令调度

8 学习资料教材编译原理原理技术与工具, 机械工业出版社,[ 美 ]Alfred V Aho, Monica S Lam,Ravi Sethi,Jeffrey D Ullman 著. 赵建华郑滔戴新译,2008 年 12 月参考书 : 编译原理, 高等教育出版社, 陈意云, 张昱,2003 编译原理及实践, 机械工业出版社,Kenneth C.Louden, 冯博琴等译, 现代编译器的 Java 实现 ( 第二版 ), 电子工业出版,Andrew W.Appel 著, 陈明译, 程序设计语言实践之路 ( 第二版 ), 电子工业出版,Michael L.Scott 著, 裘宗燕译, Parsing Techniques - A Practical Guide (Second Edition), Dick Grune and Ceriel J.H. Jacobs, Springer

9 学习资料课件每周一晚上上线 ( 主页下载 ) 同时上传上一周作业答案

10 作业作业每周 word 完成, 命名规则 :Compiler-Wi-id-Initial.docx 格式 : Deadline: 每周一上午课代表收齐, 上午 9 点半之前发给课代表, 过时不候

11 Lecture 1: Introduction Xiaoyuan Xie 谢晓园计算机学院 E301

12 How to Instruct a Computer? 最初, 我们是这样的

13 How to Instruct a Computer? 问题 :Programming bit-by-bit doesn t scale Impossible: Programmer Productivity Efficiency and Performance 我们需要 high-level 的编程语言

14 How to Instruct a Computer? Why high-level? President General Sergeant My poll ratings are low, lets invade a small nation Cross the river and take defensive positions Forward march, turn left Stop!, Shoot Foot Soldier

15 How to Instruct a Computer? High-level Candidature --- 自然语言? 具有强大的抽象能力, 但是 Ambiguous Same expression describes many possible actions Programming languages 程序设计语言 high abstraction precision (avoid ambiguity) conciseness expressiveness modularity

16 Programming Language 1.1 程序设计语言

17 1.1 程序设计语言发展史史前文明 : 算盘, 齿轮计算器, Jacquard Loom 1950~: 汇编语言及汇编器 1940~: 机器语言

18 1.1 程序设计语言 1957: 算数表达式的翻译 FORTRAN; COBOL; lgol60; LISP 发展史 1960~: 算法语言的诞生 ( 递归与循环 ) 涌现了上百种程序设计语言 ( 特殊目的语言 ; 通用语言 )

19 1.1 程序设计语言 1970~: 数据结构的自动表示简化, 抽象 (PASCAL; C; ) 1990~: 网络语言 (Java), Libraries, 脚本语言 (Perl; Javascript) 发展史 1980~: 面向对象语言 (Ada; Modular; Smalltalk; C++ ) 2000~: 说明语言 (XML,UML,Z)

1.1 程序设计语言使用统计 More than 2500 PL now. every 2 weeks, a new PL is born since 1954 http://oreilly.

20 1.1 程序设计语言使用统计 More than 2500 PL now. every 2 weeks, a new PL is born since Hello World Collection 收集了 428 个不同语言写的 ``Hello World'' 程序.

21 1.1 程序设计语言分类 ( 几千种程序设计语言 ) 功能科学计算 (Fortran); 商业数据处理 (Cobol); 表处理 (Lisp); 格式处理 (Latex); 数据库语言 (SQL); 抽象级别低级 : 机器语言 & 汇编语言高级 ( 不同范例 paradigms) 划代 (ith-generation Language,iGL) 1GL: 机器语言 2GL: 汇编语言 3GL: 高级程序设计语言, 如 FORTRAN,ALGOL,BASIC,LISP 等 ; 4GL: 为特定应用设计的语言, 如数据库查询语言 SQL, 文本排版 Postscript 等 ; 5GL: 指基于逻辑和约束的语言, 如 Prolog,OPS5

22 1.1 程序设计语言高级程序语言 ( 不同范型 :paradigms) 过程式 (Procedural programming languages--imperative) 程序中指明如何完成一个计算任务 FORTRAN, PASCAL, C 函数式 (Functional programming languages--declarative) 程序中指明要进行哪些计算 LISP, HASKELL, ML, OCAML, SCALA 逻辑式 (Logical programming languages--declarative) 事实 + 推理规则 PROLOG 对象式 (Object-oriented programming languages) 支持面向对象编程 Smalltalk, Java, C++, Eiffel, Ruby 说明式语言 (Declarative programming): 与上述命令式 (Imperative language) 不同, 没有控制结构, 甚至没有赋值, 仅有问题说明, 或者说纯数学定义

23 1.1 程序设计语言高级程序语言 ( 不同转换方式 ) 编译型语言需通过编译器 (compiler) 将源代码编译成机器码, 之后才能执行的语言一般需经过编译 (compile) 链接 (linker) 这两个步骤编译是把源代码编译成机器码, 链接是把各个模块的机器码和依赖库串连起来生成可执行文件优点 : 编译器一般会有预编译的过程对代码进行优化因为编译只做一次, 运行时不需要编译, 所以编译型语言的程序执行效率高可以脱离语言环境独立运行缺点 : 编译之后如果需要修改就需要整个模块重新编译编译的时候根据对应的运行环境生成机器码, 不同的操作系统之间移植就会有问题, 需要根据运行的操作系统环境编译不同的可执行文件代表语言 :C C++ Pascal swift 解释型语言不需要编译, 相比编译型语言省了道工序, 解释性语言在运行程序的时候才逐行翻译优点 : 有良好的平台兼容性, 在任何环境中都可以运行, 前提是安装了解释器 ( 虚拟机 ) 灵活, 修改代码的时候直接修改就可以, 可以快速部署, 不用停机维护缺点 : 每次运行的时候都要解释一遍, 性能上不如编译型语言代表语言 :JavaScript Python Erlang PHP Perl Ruby 混合型语言比如 C#,C# 在编译的时候不是直接编译成机器码而是中间码,.NET 平台提供了中间语言运行库运行中间码, 中间语言运行库类似于 Java 虚拟机.net 在编译成 IL 代码后, 保存在 dll 中, 首次运行时由 JIT 在编译成机器码缓存在内存中, 下次直接执行 ( 博友回复指出 ) Java 先生成字节码再在 Java 虚拟机中解释执行

24 1.1 程序设计语言不同的程序设计语言机制 ( 函数式过程式逻辑式对象式 ), 需要采用不同的技术编写编译程序过程式语言的编译是对象式语言编译的基础本课程重点关注过程式程序设计语言编译程序的构造原理和技术

25 1.1 程序设计语言动态类型语言 (Dynamically Typed Language) 编译时不知道变量类型, 运行时才决定类型错误属于运行错误, 运行时报错静态类型语言 (Statically Typed Language) 编译时候决定变量类型错误属于语法错误, 编译器报错强类型定义语言 (Explicit type conversion) 偏向于不容忍隐式类型转换弱类型定义语言 (Implicit type conversion) 偏向于容忍隐式类型转换

26 Overview of Compiler 1.2 编译器概述

27 1.2 编译器概述编译器 (Compiler) 将某种语言 ( 源语言 ) 编写的程序翻译成语义等价的另一种语言 ( 目标语言 ) 编写的程序错误源程序编译器目标程序目标程序若是可执行的机器语言程序, 则可以被用户调用, 处理输入并产生输出输入目标程序输出 ( 结果 ) 目标程序若是汇编语言的程序, 则须经汇编器汇编后方可执行编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误

28 1.2 编译器概述编译器的重要使命 :Translate a program High-level of Description Low-level of Implementation Program written in a Programming Languages Compiler Assembly Language Translation

Precisely determine what actions it require Assembly Language Translation Figure-out

29 1.2 编译器概述 High-level of Description Low-level of Implementation Program written in a Programming Languages Translation involves: Compiler Read and understand the program Precisely determine what actions it require Assembly Language Translation Figure-out how to faithfully carry-out those actions Instruct the computer to carry out those actions

30 1.2 编译器概述回顾例子 President General Sergeant My poll ratings are low, lets invade a small nation Cross the river and take defensive positions Forward march, turn left Stop!, Shoot Foot Soldier

31 1.2 编译器概述示例 Input Output Compiler

32 1.2 编译器概述输入 :Standard imperative language (C, C++) State Variables, Structures, Arrays Computation Expressions (arithmetic, logical, etc.) Assignment statements Control flow (conditionals, loops) Procedures

33 1.2 编译器概述输出 : 机器代码 State Registers Memory with Flat Address Space Machine code load/store architecture Load, store instructions Arithmetic, logical operations on registers Branch instructions

34 1.2 编译器概述编译程序的伙伴程序编辑器 (editor) 除一般的文本编辑功能外, 还可以对正在编辑的文本进行分析提示自动提供关键字匹配等功能 ; 预处理器 (preprocessor) 删除源程序中的注释执行宏替换以及包含文件的嵌入等 ; 汇编程序 (assembler) 将编译程序生成的汇编代码汇编成机器代码 ; 连接程序 (linker) 将不同的目标文件连接到一个可执行的文件中 ; 装入程序 (loader) 将程序加载到内存中以便执行 ;

35 1.2 编译器概述整体流程 Editor Absolute Machine Code Skeletal Source Program Loader/Linker Preprocessor Source Program Relocatable Machine Code Assembler Compiler Target Assembly Program

36 source file (.c.pas.java) Compiler Abstract machine code assembly file (.a.asm) libraries (.lib) Assembler Object file (.o.obj.dcu) Linker Interpreter (Java virtual Machine,.NET runtime) executable file (.exe) process Loader OS (.dll,.so)

37 Construction of Compiler 1.3 编译器的组成

38 1.3 编译器组成如何翻译考虑自然语言翻译过程 : 从中文到英文你能够通过自己的努力实现你的梦想! 翻译的一般过程 : 识别单词检查语法检查语义翻译你能够通过自己的努力实现你的梦想! You can put your dreams into reality through your efforts!

39 1.3 编译器组成自然语言翻译过程总结掌握源语言和目标语言 : 词法语法和语义翻译过程包括 : 分析源句子是否正确拼写, 包括识别单词及其属性依据源语言的语法建立语法结构检查句子是否有意义将句子翻译成目标语言翻译每个语法部分将其组合成有意义的目标语言句子 I eat sky in dog.

40 1.3 编译器组成表处理源程序词法分析语法分析语义分析中间代码生成中间代码优化目标代码生成目标程序错误处理分析合成

41 1.3 编译器组成分析部分 (Analysis) 源程序 - 语法结构 - 中间表示搜集源程序中的相关信息, 放入符号表分析定位程序中可能存在的错误信息 ( 语法语义错误 ) 又称编译器的前端 (front end), 是于机器无关的部分合成部分 (Synthesis) 根据符号表和中间表示构造目标程序又称编译器的后端 (back end), 是于机器相关的部分

42 1.3 编译器组成符号表管理记录源程序中使用的变量的名字, 收集各种属性名字的存储分配类型作用域过程名字的参数数量参数类型等等符号表可由编译器的各个步骤使用

43 1.3 编译器组成 --- 词法分析词法分析 / 扫描 (lexical analysis, scanning) 读入源程序的字符流, 输出有意义的词素 (lexeme) 基于词素, 产生词法单元 token: <token-name, attribute-value> 程序语言处理的最小单位 token-name 由语法分析步骤使用 attribute-value 指向相应的符号表条目, 由语义分析 / 代码生成步骤使用程序语言规定了单词构成的规则和单词类别.

44 1.3 编译器组成 --- 词法分析 Program (character stream): position = initial + rate * 60 Lexical Analyzer (Scanner) Token Stream: <id,1> <=, > <id, 2> <+, > <id,3> <*, > <number, 4> 报错 : val#ue Variable names cannot have # character Not a number

45 1.3 编译器组成 --- 语法分析词法分析后, 需要得到词素序列的语法结构语法分析 / 解析 (syntax analysis/parsing) sentence 是对单词的再次重组程序设计语言规定了词法单元语句的重组规则语句的类别. -

46 1.3 编译器组成 --- 语法分析语法分析 / 解析 (syntax analysis/parsing) 根据各个词法单元的第一个分量来创建树形中间表示形式通常是语法树 (syntax tree/parse tree) 指出了词法单元流的语法结构

47 1.3 编译器组成 --- 语法分析 Program (character stream) Lexical Analyzer (Scanner) num * ( num + num ) <expr> Token Stream <expr> <op> <expr> Syntax Analyzer (Parser) Parse Tree num * <expr> ( ) <expr> <op> <expr> num + num

48 1.3 编译器组成 --- 语法分析 Program (character stream) Lexical Analyzer (Scanner) Token Stream Syntax Analyzer (Parser) Parse Tree

49 1.3 编译器组成 --- 语法分析 Program (character stream) Extra parentheses Lexical Analyzer (Scanner) Token Stream Syntax Analyzer (Parser) Parse Tree int * foo(i, j, k)) int i; int j; { for(i=0; i j) { fi(i>j) return j; } Not a keyword Missing increment Not an expression

50 1.3 编译器组成 --- 语义分析得到语义 (meaning), 对于编译器来说比较难语义分析 (semantic analysis) semantic: the meaning of the language. 使用语法树和符号表中的信息, 检查源程序是否满足语言定义的语义约束同时收集类型信息, 用于代码生成类型检查, 类型转换

51 1.3 编译器组成 --- 语义分析 Program (character stream) Lexical Analyzer (Scanner) Token Stream Syntax Analyzer (Parser) Parse Tree Semantic Analyzer Intermediate Representation Type not declared int * foo(i, j, k) int i; int j; { int x; x = x + j + N; return j; } Mismatched return typ Uninitialized variable used Undeclared variable

52 1.3 编译器组成 --- 中间代码生成根据语义分析的输出, 生成类机器语言的中间表示三地址代码 : 每个指令最多包含三个运算分量

53 1.3 编译器组成 --- 代码优化通过对中间代码的分析, 改进中间代码, 得到更好的目标代码快短能耗低优化有具体的设计目标

54 1.3 编译器组成 --- 中间代码生成 Program (character stream) Lexical Analyzer (Scanner) Token Stream Syntax Analyzer (Parser) Parse Tree Semantic Analyzer Intermediate Representation Code Optimizer Optimized Intermediate Representation

55 1.3 编译器组成 --- 代码生成把中间表示形式映射到目标语言寄存器的分配指令选择内存分配

56 1.3 编译器组成 --- 代码生成 Lexical Analyzer (Scanner) Program (character stream) Token Stream Syntax Analyzer (Parser) Parse Tree Semantic Analyzer Intermediate Representation Code Optimizer Optimized Intermediate Representation Code Generator Assembly code int sumcalc(int a, int b, int N) { int i; int x, t, u, v; x = 0; u = ((a<<2)/b); v = 0; for(i = 0; i <= N; i++) { sumcalc: t = i+1; xorl %r8d, %r8d x = x + v + t*t; xorl %ecx, %ecx v = v + u; movl %edx, %r9d } cmpl %edx, %r8d return x; jg.l7 } sall $2, %edi.l5: movl %edi, %eax cltd idivl %esi leal movl imull movl imull leal movl addl cmpl jle.l5.l7: movl %r8d, %eax ret 1(%rcx), %edx %eax, %r10d %ecx, %r10d %edx, %ecx %edx, %ecx (%r10,%rcx), %eax %edx, %ecx %eax, %r8d %r9d, %edx

57 1.3 编译器组成 --- 编译器的趟 (Pass) 趟 : 以文件为输入输出单位的编译过程的个数, 每趟可由一个或若干个步骤构成步骤是逻辑组织方式趟和具体的实现相关

58 1.3 编译器组成解释器 (Interpreter): 解释器直接利用用户提供的输入执行源程序中指定的操作程序输入解释器输出 ( 结果 ) 解释过程中若发现错误, 则返回修改源程序, 修改后重新解释执行

59 1.3 编译器组成编译器和解释器的比较

60 1.3 编译器组成编译器和解释器的比较相同点使用相同的实现技术区别实现机制 : 翻译 ( 程序 to 程序 )vs. 解释 ( 指令 to 指令序列 ) 解释器相对于编译器的优势可移植性好支持交互式程序设计边解释, 边执行, 错误诊断效果好编译器的优势在于 : 效率高, 一次编译, 多次运行, 存储代价小目标程序的执行速度比解释器快很多最大区别 / 根本区别 : 目标程序

61 1.3 编译器组成 Java 结合了两者 : javac 前端编译器 : 先编译成字节码 (bytecode,.class 文件 ) 由 JVM 解释执行, 可移植性好 JIT 即时编译器 (just-in-time compiling) 为了提高热点代码的执行效率, 在运行时虚拟机将会把这些代码编译成与本地平台相关的机器码, 并进行各层次的优化基于采样的热点探测基于计数器的热点探测 HotSpot VM: Oracle Java SE

62 1.3 编译器组成 Make 代码变成可执行文件, 叫做编译 (compile) 安排编译的顺序, 叫做构建 (build) Make 是最常用的构建工具, 诞生于 1977 年, 主要用于 C 语言的项目实际上任何只要某个文件有变化, 就要重新构建的项目, 都可以用 Make 构建构建规则都写在 Makefile, make [ 选项 ][ 参数 ] Apache Ant --- 基于 Java 的构建 (Build) 工具

63 Implementation of Compiler 1.4 编译器的实现

64 1.4 编译器实现 Efficient execution General Sergeant Foot Soldier Cross the river and take defensive positions Where to cross the river? Use the bridge upstream or surprise the enemy by crossing downstream? How do I minimize the casualties??

65 1.4 编译器实现 Efficient execution President General My poll ratings are low, lets invade a small nation Russia or Bermuda? Or just stall for his poll numbers to go up?

66 1.4 编译器实现编译程序要求 Correct The actions requested by the program has to be faithfully executed Efficient Intelligently and efficiently use the available resources to carry out the requests (the word optimization is used loosely in the compiler community Optimizing compilers are never optimal)

67 1.4 编译器实现实现方法编译器的开发代价是非常昂贵的, 在可能的情况下, 可以将一种语言的程序转换成另一种语言的程序, 利用另一种语言的编译器进行编译前提条件 : 两种语言在语法和语义上很近似, 或者一种语言是另一种语言的扩展实例 :C++ C L 源程序转换器 L 源程序 L 编译器目标程序

68 1.4 编译器实现构造工具扫描器生成器语法分析器生成器语法制导的翻译引擎代码生成器的生成器数据流分析引擎编译器构造工具集

69 本章小结程序设计语言 1 编译器概述 2 编译器组成 3 4 编译器实现

70 课后作业教材 Page 2: 1.1.3, 列举一些知名的编译器构造工具, 并说明他们分别的作用

71 Thank you!

2/80 2

2/80 2 2/80 2 3/80 3 DSP2400 is a high performance Digital Signal Processor (DSP) designed and developed by author s laboratory. It is designed for multimedia and wireless application. To develop application