大侠素材铺

Size: px

Start display at page:

Download "大侠素材铺"

念簧却
5 years ago
Views:

1 编译原理与技术导论计算机科学与技术学院李诚 03/09/2018

2 主要内容课程设置情况编译器的由来与挑战编译器的构造 2/45

3 课程设置时间 : 每周一 (6,7) 四 (3,4) 地点 :3B201 课程主页 ( 课件试题等 ): mpiler18/ 邮件列表 : 我们会自动将大家的邮箱加入 QQ 讨论群 : 把编译进行到底 ( 群号 : ) 3/45

4 教师李诚 ( 先进数据系统实验室, 研究方向 : 大规模实时高可靠分布式系统 ) Contact: chengli7@ustc.edu.cn Official Hours: 每周一 12:00 13:30 地点 : 东校区高性能中心 503 4/45

5 助教团队白有辉 ( 博一 ) byh0912@mail.ustc.edu.cn 王佳玮 ( 研二 ) wang.jw@yahoo.com 邵新洋 ( 研二 ) sxy799@mail.ustc.edu.cn 王一多 ( 研一 ) duo@mail.ustc.edu.cn 许冠斌 ( 研一 ) Web manager 5/45

6 参考资料教材和参考书陈意云张昱, 编译原理 ( 第 3 版 ), 高等教育出版社,2014 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd edition, Addison-Wesley, 2007 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman 著, 赵建华等译, 编译原理, 机械工业出版社,2017 其他资料 Stanford 课程主页 MIT 课程主页 : 6/45

7 考核要求 (Tentative) 考核内容包括理论学习和工程实践理论学习 (20%): 按时上课 ( 特殊情况不能来需要书面请假 ) 按时完成课后书面作业工程实践 (40%): 以组队 (<=3 人 ) 完成若干项目 (>=4) 完成一个简单的编译器每个项目要求提交代码 + 文档通过 git commit 来评估同组人员的工作量考试 (40%): 期中 (TBD, 可以是开卷 ) 期末 (TBD, 可以是开卷 ) 7/45

8 主要内容课程设置情况编译器的由来与挑战编译器的构造 8/45

9 编程语言什么是编程语言? 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, Ocaml, 脚本型 (Scripting): AWK, Perl, Python, PHP, Ruby, 9/45

10 求最大公约数 gcd 10/45

11 快速发展的编程语言 PYPL Index is created by analyzing how often language tutorials are searched on Google. 11/45

12 从无到有, 由弱到强 1954 年 IBM 研发了 704 机但是, 软件开发的成本超过了硬件所有的程序均由汇编语言开发 12/45

13 FORTRAN I John Backus (1977 图灵奖 ) 巴科斯范式 (Backus Naur Form) 基本想法 : 将高级语言翻译为低级语言开发时间减半对计算机科学影响巨大诞生了许多理论研究成果现代编译器还保留了 FORTRAN I 的大概架构 13/45

14 为什么需要编译器? 编译器使得开发者可以使用容易理解和掌握的高级语言, 而非晦涩的机器指令可移植性模块化简单化编程效率高程序开销小效率高是不可或缺的编程工具同时也是最复杂的系统软件之一 14/45

15 C 程序的编译过程 C 源程序预处理器 Preprocessor (cpp).i 连接器 Linker (ld) 目标文件.o 库代码 Library routines 输入机器代码 Machine code C 编译器 Compiler (cc) 汇编.s 汇编器 Assembler (as) 输出 15/45

16 编译器面临的挑战计算机是不断进化的体系结构的改变编译器的改变新的特征产生新的问题语言也在不断演化 C - C90, C99, C11; C , 2003, 2006, 2011, 2014 新的语言不断诞生 :Go (2009), Rust (2010), Elixir (2011), Swift (2014) 16/45

17 编译器是学科交叉的产物计算机理论有限自动机, 文法, 数据流算法树 / 图的遍历和修改, 动态规划数据结构符号表, 抽象语法树, 图系统内存空间分配与命名, 多趟系统, 编译器的构造 17/45

18 编译器是学科交叉的产物体系结构内存层次, 指令选择, 并行安全寻找漏洞和攻击防御软件工程软件开发环境, 调试人工智能启发式代码优化 18/45

19 主要内容课程设置情况编译器的由来与挑战编译器的构造 19/45

20 编译器是什么? 输入源程序编译器 Compiler 目标程序输出 20/45

21 编译器的输入标准的指令式语言 (Java, C, C++) 状态变量结构数组计算表达式 (arithmetic, logical, etc.) 赋值语句条件语句 (conditionals, loops) 函数 21/45

22 编译器的输出状态寄存器内存单元机器码 load/store architecture Load, store instructions 寄存器操作 Arithmetic, logical operations 分支指令 Branch instructions 22/45

23 编译器的构造 / 阶段 Lexical 词法分析器 Source code 源程序 Token Stream 记号流 Symbol Table 符号表 23/45

24 编译器的构造 / 阶段 Lexical 词法分析器语法分析器 Source code 源程序 Token Stream 记号流 Tree 语法树 Symbol Table 符号表 24/45

25 编译器的构造 / 阶段 Lexical 词法分析器语法分析器 Semantic 语义分析器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Symbol Table 符号表 25/45

26 编译器的构造 / 阶段 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Symbol Table 符号表 26/45

27 编译器的构造 / 阶段 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Symbol Table 符号表 27/45

28 编译器的构造 / 阶段 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 28/45

29 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 29/45

30 词法分析人类在理解自然语言时, 首先要识文断字 This line is a longer Sentence article noun verb article adjective noun 30/45

31 词法分析将程序字符流分解为记号 (Token) 序列形式 :<token_name, attribute_value> position = initial + rate 60 词法分析器字符流符号表 position initial rate id, 1 = id, 2 + id, 3 60 记号流 31/45

32 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 32/45

33 语法分析人类在理解自然语言时, 其次要理解句子结构 This line is a longer Sentence article noun verb article adjective noun subject object sentence 33/45

34 语法分析也称为解析 (Parsing), 在词法记号的基础上, 创建语法结构 id, 1 = id, 2 + id, 3 60 记号流语法分析器 = id, 1 + id, 2 id, 3 60 语法树符号表 position... initial... rate... 34/

35 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 35/45

36 语义分析人类在理解自然语言时, 最后要理解句子的含义 Jack said Jerry left his assignment at home. What does his refer to? Jack or Jerry? 36/45

语义分析编译器会检查程序中的不一致如 : 类型检查 (type checking) = + 语法树 id, 1 id, 2 id, 3 60 1 2 3 符号表

37 语义分析编译器会检查程序中的不一致如 : 类型检查 (type checking) = + 语法树 id, 1 id, 2 id, 符号表 position... initial... rate... 语义分析器 = id, 1 + 语法树 id, 2 id, 3 inttofloat 60 37/45

38 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 38/45

中间代码生成是源语言与目标语言之间的桥梁 1 2 3 符号表 position... initial... rate.

39 中间代码生成是源语言与目标语言之间的桥梁符号表 position... initial... rate... = + 语法树 id, 1 id, 2 id, 3 inttofloat 中间代码生成器 60 t1 = inttofloat(60) t2 = id3 t1 t3 = id2 + t2 中间代码 id1 = t3 39/45

40 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 40/45

41 代码优化机器无关的代码优化便于生成执行时间更快更短或能耗更低的目标代码符号表 position... initial... rate... t1 = inttofloat(60) t2 = id3 t1 t3 = id2 + t2 id1 = t3 中间代码代码优化器 t1 = id3 * 60.0 id1 = id2 + t1 中间代码 41/45

42 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 42/45

代码生成如果目标语言是机器代码, 必须为变量选择寄存器或内存位置 1 2 3 符号表 position... initial... rate... t1 = id3 * 60.

43 代码生成如果目标语言是机器代码, 必须为变量选择寄存器或内存位置符号表 position... initial... rate... t1 = id3 * 60.0 id1 = id2 + t1 中间代码代码生成器 LDF R2, id3 MULF R2, R2, #60.0 LDF R1, id2 汇编代码 ADDF R1, R1, R2 STF id1, R1 43/45

44 编译器的构造 / 阶段 Front end 前端 Back end 后端 Lexical 词法分析器语法分析器 Semantic 语义分析器 Code Gen. 中间代码生成器 Code Optimizer 代码优化器 Code Gen. 代码生成器 Source code 源程序 Token Stream 记号流 Tree 语法树 Annotated Tree 带注解的语法树 Rep. 中间表示 Rep. 中间表示 Target code 目标程序 Symbol Table 符号表 44/45

45 编译原理与技术导论笋因落箨方成竹, 鱼为奔波始化龙曾记少年骑竹马, 看看又是白头翁出自增广贤文

PowerPoint Presentation

PowerPoint Presentation 引论编译原理和技术张昱 0551-63603804,yuzhang@ustc.edu.cn 中国科学技术大学计算机科学与技术学院主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 : 编译原理和技术引论 2 主要内容 1 2 编程语言及设计编译器及形式 3 编译器的阶段 4 示例 : 程序的表示 5 基础实验的考虑张昱 :