PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

训丁
6 years ago
Views:

1 引论编译原理和技术张昱中国科学技术大学计算机科学与技术学院

2 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 2

3 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 3

4 编程语言什么是编程语言 A programming language is a notation for describing computations to people and to machines. 每种编程语言有自己的计算模型过程型 (Procedural): C, C++, C#, Java 声明型 (Declarative): SQL, 逻辑型 (Logic): Prolog, 函数式 (Functional): Lisp/Scheme, Haskell, ML, 脚本型 (Scripting): AWK, Perl, Python, PHP, Ruby, 张昱 : 编译原理和技术引论 4

5 求最大公约数 gcd 张昱 : 编译原理和技术引论 5

编程语言百花齐放众多 :GitHub -- 开源项目涉及 337 种编程语言 (2017.9) http://www.99-bottles-of-beer.net/ 用 1500 种语言编写语言自身在不断发展 C - C90, C99, C11; C++ - 1998,, 2011, 2014, 2017 最流行的语言 ( 动态变化 ) Tiobe https://www.tiobe.

6 编程语言百花齐放众多 :GitHub -- 开源项目涉及 337 种编程语言 (2017.9) 用 1500 种语言编写语言自身在不断发展 C - C90, C99, C11; C ,, 2011, 2014, 2017 最流行的语言 ( 动态变化 ) Tiobe :1Java, 2C, 3C++, 4C#, 5Python, 6VB.NET 2010 年 :1Java, 2C, 3PHP, 4C++, 5VB, 6C#, 7Python 1970 年 :1Fortran, 2Lisp, 3Cobol, 4Algol60, 5APL, 6Snobol4 张昱 : 编译原理和技术引论 6

7 99 Bottles of Beer 99 bottles of beer on the wall, 99 bottles of beer. Take one down and pass it around, 98 bottles of beer on the wall. 98 bottles of beer on the wall, 98 bottles of beer. Take one down and pass it around, 97 bottles of beer on the wall bottles of beer on the wall, 2 bottles of beer. Take one down and pass it around, 1 bottle of beer on the wall. 1 bottle of beer on the wall, 1 bottle of beer. Take one down and pass it around, no more bottles of beer on the wall. No more bottles of beer on the wall, no more bottles of beer. Go to the store and buy some more, 99 bottles of beer on the wall. [Traditional] 张昱 : 编译原理和技术引论 7

8 C: 99 Bottles of Beer #define MAXBEER (99) void chug(int beers); main() { register beers; for(beers = MAXBEER; beers; chug(beers--)) puts(""); puts("\ntime to buy more beer!\n"); exit(0); } void chug(register beers) { char howmany[8], *s; s = beers!= 1? "s" : ""; printf("%d bottle%s of beer on the wall,\n", beers, s); printf("%d bottle%s of beeeeer...,\n", beers, s); printf("take one down, pass it around,\n"); if(--beers) sprintf(howmany, "%d", beers); else strcpy(howmany, "No more"); s = beers!= 1? "s" : ""; printf("%s bottle%s of beer on the wall.\n", howmany, s); } [Bill Wein] 张昱 : 编译原理和技术引论 8

9 class bottles { Java: 99 Bottles of Beer public static void main(string args[]) { String s = "s"; for (int beers=99; beers>-1;) { System.out.print(beers + " bottle" + s + " of beer on the wall, "); System.out.println(beers + " bottle" + s + " of beer, "); if (beers==0) { System.out.print("Go to the store, buy some more, "); System.out.println("99 bottles of beer on the wall.\n"); System.exit(0); } else System.out.print("Take one down, pass it around, "); s = (--beers == 1)?"":"s"; System.out.println(beers + " bottle" + s + " of beer on the wall.\n"); } } } [Sean Russell] 张昱 : 编译原理和技术引论 9

10 AWK: 99 Bottles of Beer BEGIN { for(i = 99; i >= 0; i--) { print ubottle(i), "on the wall,", lbottle(i) "." print action(i), lbottle(inext(i)), "on the wall. print } } function ubottle(n) { return sprintf("%s bottle%s of beer", n? n : "No more", n - 1? "s" : "") } function lbottle(n) { return sprintf("%s bottle%s of beer", n? n : "no more", n - 1? "s" : "") } function action(n) { return sprintf("%s", n? "Take one down and pass it around," : \ "Go to the store and buy some more,") } function inext(n) { return n? n - 1 : 99 } [Osamu Aoki, 张昱 : 编译原理和技术引论 10

11 程序语言的设计为什么那么多语言? 单个语言不能适用所有应用程序员对语言的好坏如何编程有自己的观点和看法没有评价语言好坏的普遍接受的标准语言进化之驱动力应用的多样性提高软件开发生产力 (productivity) 改善软件的安全性可靠性和可维护性支持并行 (parallelism) 与并发 (concurrency) 移动和分发, 模块化, 多范型张昱 : 编译原理和技术引论 11

12 程序语言设计的计算思维计算思维 (Computational Thinking) Jeannette M. Wing Computational Thinking CACM, vol. 49, no. 3, pp , 2006 Computational thinking is a fundamental skill for everyone, not just for computer scientists. To reading, writing, and arithmetic, we should add computational thinking to every child s analytical ability. Just as the printing press facilitated the spread of the three Rs, what is appropriately incestuous about this vision is that computing and computers facilitate the spread of computational thinking. 语言设计中的计算思维 Problem Domain Mathematical Abstraction Mechanizable Model of Computation Programming Language 张昱 : 编译原理和技术引论 12

13 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 13

14 编译器是什么源程序编译器 Compiler 输入目标程序输出张昱 : 编译原理和技术引论 14

15 目标语言另一种编程语言 CISCs( 复杂指令集 ):x86 IA64 RISCs( 精简指令集 ):MIPS ARM 多核 / 众核 GPUs : CUDA OpenCL FPGAs 量子计算机 TPU,NPU 张昱 : 编译原理和技术引论 15

16 解释器源程序输入解释器 Interpreter 输出直接在输入上执行源程序张昱 : 编译原理和技术引论 16

17 Java 编译器源程序.java 翻译器 Translator (javac) 输入中间表示 Intermediate Representation.class Java 虚拟机 Virtual Machine (java) 输出张昱 : 编译原理和技术引论 17

18 编译器的其他形式交叉编译器 (Cross compiler) 在一个平台上生成另一个平台上的代码 PC arm-linux-gcc ARM 增量编译器 (Incremental compiler) 以增量地编译源程序, 只编译修改的部分, 如 Freeline 即时编译器 (Just-in-time compiler) 在运行时对 IR 中每个被调用的方法进行编译, 得到目标机器的本地代码, 如 Java VM 中的即时编译器预先编译器 (Ahead-of-time compiler ) 在程序执行之前将 IR 翻译成本地码, 如 ART 中的 AOT 张昱 : 编译原理和技术引论 18

19 Java 虚拟机类加载器 Class loader 输入垃圾收集器 Garbage collector Java 字节码.class 字节码解释器 Bytecode Interpreter 输出即时编译器 JIT Compiler 机器代码 Machine code 输出输入张昱 : 编译原理和技术引论 19

20 C 编译器 C 源程序预处理器 Preprocessor (cpp).i 连接器 Linker (ld) 目标文件.o 库代码 Library routines 输入机器代码 Machine code C 编译器 Compiler (cc) 汇编.s 汇编器 Assembler (as) 输出张昱 : 编译原理和技术引论 20

21 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 21

22 编译器的阶段 source program Front end 前端 Back end 后端 target program Lexical Analyzer 词法分析器 Token Stream 记号流 Syntax Analyzer 语法分析器 Syntax Tree 语法树 Semantic Analyzer 语义分析器 Annotated Syntax Tree 带注解的语法树 Interm. Code Gen. 中间代码生成器 Interm. Rep. 中间表示 Code Optimizer 代码优化器 Interm. Rep. 中间表示 Code Gen. 代码生成器 Symbol Table 符号表张昱 : 编译原理和技术引论 22

23 编译器的阶段 source program Front end 前端 Program input Lexical Analyzer 词法分析器 Syntax Analyzer 语法分析器 Semantic Analyzer / Interm. Code Gen. 语义分析器 / 中间代码生成器 Tree-walk routines 树遍历程序 Program output Token Stream 记号流 Syntax Tree 语法树 Abstract Syntax Tree or other Interm. Rep. 抽象语法树或其他中间表示 Symbol Table 符号表张昱 : 编译原理和技术引论 23

24 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 24

25 int main( ) { int i = getint( ), j = getint( ); A B } Parse Tree 分析树张昱 : 编译原理和技术引论 25

26 A while (i!= j) { if ( i > j ) i = i j; else j = j i; } B putint( i ); Parse Tree 分析树张昱 : 编译原理和技术引论 26

27 Abstract Syntax Tree 抽象语法树 Symbol Table 符号表张昱 : 编译原理和技术引论 27

28 int main( ) { int i = getint( ), j = getint( ); A while (i!= j) { if ( i > j ) i = i j; else B j = j i; C } D putint( i ); } 张昱 : 编译原理和技术引论 28

29 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 29

30 基础实验的考虑词法分析器记号流源代码 Parser0 Parser 是否合法? 高级中间表示 (AST) 解释器是否合法? 程序变换器优化器语义检查器低级中间表示 ( 如 LLVM IR) 低级中间代码生成器 (AST2LIR) LLVM 编译器工具链代码生成器寄存器分配器 JIT 汇编码 ( 如 x86, MIPS) 张昱 : 编译原理和技术引论 30

31 解析器的生成器生成器生成 Lexer:Flex(for windows) Jflex 生成 Parser LALR: Bison(for windows) Java CUP LL: JavaCC ANTLR LL(*) [PLDI2011] 文法对 Parser 的影响 LR Parser 的优势 : 速度快表达能力强 LL Parser 的优势 : 代码结构与文法对应, 易理解, 容易增加错误处理和错误恢复张昱 : 编译原理和技术引论 31

32 ANTLR ANTLR(ANother Tool for Language Recognition) [ Prof. Terence Parr, since 1989 支持多种代码生成目标 Java C++ C# Python Go JavaScript Swift 张昱 : 编译原理和技术引论 32

基于开展的实验开源 : 源码阅读, 消化理解生成器基于的原理各种语言实现 :31 种模式 1. 从文法到递归下降识别器 2. LL(1) 递归下降词法分析器 3. LL(1) 递归下降语法解析器 4. LL(k) 递归下降语法解析器 5. 回溯解析器 6. 记忆解析器 7. 谓词解析器 8. 解析树 ( 分析树 ) 9. 同型抽象语法树 10. 规范化异型 AST 11.

33 基于开展的实验开源 : 源码阅读, 消化理解生成器基于的原理各种语言实现 :31 种模式 1. 从文法到递归下降识别器 2. LL(1) 递归下降词法分析器 3. LL(1) 递归下降语法解析器 4. LL(k) 递归下降语法解析器 5. 回溯解析器 6. 记忆解析器 7. 谓词解析器 8. 解析树 ( 分析树 ) 9. 同型抽象语法树 10. 规范化异型 AST 11. 不规则的异型 AST 12. 内嵌遍历器 13. 外部访问者 14. 文法访问者 15. 模式匹配者 ( 子树 ) 16. 单作用域符号表 17. 嵌套作用域符号表 18. 数据聚集的符号表 19. 类的符号表型 20. 计算表达式的类型 21. 自动类型提升 22. 静态类型检查 23. 动态类型检查 24. 语法制导的解释器 25. 基于树的解释器 26. 字节码汇编器 27. 栈式解释器 28. 寄存器解释器 29. 语法制导的翻译器 30. 基于规则的翻译器张昱 : 编译原理和技术引论 31. 模型驱动的转换 33

34 我听到的会忘掉, 我看到的能记住, 我做过的才真正明白张昱 : 编译原理和技术引论 34

大侠素材铺

大侠素材铺编译原理与技术导论计算机科学与技术学院李诚 03/09/2018 主要内容课程设置情况编译器的由来与挑战编译器的构造 2/45 课程设置时间 : 每周一 (6,7) 四 (3,4) 地点 :3B201 课程主页 ( 课件试题等 ): http://staff.ustc.edu.cn/~chengli7/courses/co mpiler18/ 邮件列表 : 我们会自动将大家的邮箱加入