软件工程技术知识体系机器学习 / 神经网络 (AI) 不确定性 ( 黑盒, 概率 ) 编译技术灵活多变, 但有基因数据库技术联系组合, 摘取基础技术联线 : 直观易懂分布式系统面向对象编程计算机网络操作系统数据结构 2

Size: px

Start display at page:

Download "软件工程技术知识体系机器学习 / 神经网络 (AI) 不确定性 ( 黑盒, 概率 ) 编译技术灵活多变, 但有基因数据库技术联系组合, 摘取基础技术联线 : 直观易懂分布式系统面向对象编程计算机网络操作系统数据结构 2"

员米
5 years ago
Views:

1 编译原理 Compiler Principles 第一章引论湖南大学信息科学与工程学院软件工程系杨金民 2018

2 软件工程技术知识体系机器学习 / 神经网络 (AI) 不确定性 ( 黑盒, 概率 ) 编译技术灵活多变, 但有基因数据库技术联系组合, 摘取基础技术联线 : 直观易懂分布式系统面向对象编程计算机网络操作系统数据结构 2

3 灵活多变 : 计算器该如何编程? a + b a + b * c a + b * (c + d) (a + b * (c + d )) * (e + f) (a 0 + (a 1 + (a 2 + a 3 * x))*x)*x... 3

4 课程性质什么叫真正的编程, 我想只有从这门课才会感知 ; 大家以前做的编程, 都是就事论事, 谁都能玩的事情领会什么叫模型, 什么叫算法, 什么叫工具, 什么叫真正的编程 ; 正因为如此, 它被定为专业核心课 ; 课程特点 : 抽象深奥, 难于搞懂 ; 注意事项 : 千万别掉队, 狠下功夫 : 学习, 思考, 琢磨, 动手 ; 好处 : 拉开档次, 上台阶的机会 ; 分水岭就在于此 ; 4

5 教材和参考文献教材 : 赵建华等译. 编译原理 ( 第 2 版 ). 机械工业出版社, 2009 龙之书. 参考 : 陈火旺. 程序设计语言编译原理 ( 第 3 版 ). 国防工业出版社 QQ 群 : 软件工程系编译原理课程 5

6 课程组杨金民教授 ; 电话 : , QQ: rj_jmyang@hnu.edu.cn; 办公室 : 软件大楼 403; 6

7 学生个人素养 1) 掌握专业技能能力, 具备软件工程实施能力, 能够胜任编程测试部署维护等常规性工作 ; 2) 领悟技术本质能力, 具备软件工程中的分析, 权衡, 设计决策能力, 能够胜任项目经理之类的担纲性工作 ; 3) 自我推销能力写作与表达能力, 有技巧地渲染论题, 引发别人兴趣, 抓住别人的的眼球, 搏取别人的注意信任和欣赏 ; 4) 理解人性能力因势利导, 抓住天时, 利用地利, 顺应人和, 稳步前进, 梦想成真 7

8 课程考评规定 :3 次无故缺课, 不允许考试, 成绩记为 0 分 ; 1 课堂测试 12% 6 次,2 分 / 次 2 小班讨论 8% 4 次,2 分 / 次 3 实验 12% 4 次,3 分 / 次 4 作业 16% 8 次,2 分 / 次 5 期中考试 16% 闭卷 6 期末考试 36% 闭卷基本要求 : 课后必须花课时数的 4 倍以上来复习, 做作业 8

9 小班讨论表现自己的机会要求 : 报告自己的所思, 所想, 所做, 自己的观点和认识 ; 千万不要从网上下载, 然后照本宣科, 抄录照搬记 0 分 ; 目的 : 锻炼表演技能 : 表现自己, 打动听众, 使听众受益 ; 一个班分成 6 个小组 ; 一个组 15 分钟 : 报告 8 分钟, 讨论 7 分钟 ; 每个学生每堂讨论课后, 要写出总结 ( 电子稿 ), 提交老师 ; 老师每堂讨论课, 做记录, 作为给分的依据 ; 9

10 小班讨论的主题 GCC 编译器,grep 查找工具正则表达式及其应用有限自动机的应用乔姆斯基文法层次及其应用寄存器分配垃圾回收代码优化编译技术的应用嵌入式编译器并行编译器符号表管理

11 实验安排 16 学时,4 次,8 个实验选做其中的 4 个 ; 每人独立完成, 并通过测试 ; 提交实验报告打印稿和电子版源代码和测试样例电子版参考编译器 tiny 编译器, 源代码见课程中心

12 学习该课程的前提计算机体系结构 : 包括汇编语言 ; 高级程序语言

13 第一章绪论 1. 编译的含义 ; 机器语言高级程序语言 2. 编译过程和环节 ; 3. 编译器的构造方法学 : 模型, 算法, 工具 ; 4. 编译技术的广泛应用 ; 5. 程序语言的种类 ; 6. 程序设计语言基础 ;

14 计算机 (CPU+ 存储器 ) 与机器语言 CPU 运算 : 输入, 输出数据代码存储器单元地址 MOV EAX, ptr [ ] ADD EAX, ptr [ A] CALL ; 要解决的问题 : 快!!! 天气预测 ; 雷达跟踪 ; 当你打电话时, 系统就要找到你的账户, 检查是否有余额

15 快的实现途径提高单个 CPU 做事的速度把电路做得更加细小 : 微电子技术 : 摩尔定理 ; 采用并行处理策略, 多核 CPU, 多线程技术第二种策略的发挥, 是有条件的 : 提交的计算任务有并行性如果是串行性的计算任务, 就变成了摆设因此, 分析并提取任务中的并行性, 构建并行执行的机器代码, 是编译器中要考虑的重要问题

16 计算机的特点 CPU 与存储器的不协调性 : a = a+c; b = d+a; MOV R0, a; ADD R0, c; MOV a,r0; MOV R0, d; ADD R0, a; MOV b,r0; CPU Register Cach Memory MOV R0, a; ADD R0, c; MOV a,r0; ADD R0, d; MOV b, R0; Disk 因此, 寄存器的分配, 是一个编译器要考虑的另一重要问题

17 高级程序语言 vs 机器语言高级程序语言的特点 : 用名称表达概念与概念之间的关系例如 : if shape = 梯形 then 面积 = ( 上底 + 下底 ) 高 /2; else if shape = circle then 面积 = 半径 2 ; 控制有多种形式 : if: 条件的满足 ; while,do...until: 动态, 实时循环 ; switch: 互斥的离散事件机器语言的特点操作指令 ( 地址 ), 数据 ( 地址 ); 跳转指令 ; MOV R0, a; ADD R0, c; MUL R0, d; DIV R0, 2; MOV e,r0; GOTO [ ] 近似日常表达, 易于理解, 简洁, 易于掌握, 修改 ;

18 高级程序语言 vs 机器语言高级程序语言追求的目标 : 通用 : 与计算机型号的无关性 ; 简单 : 易于理解, 简洁, 易于掌握 ; 鲁棒 : 可靠 ; 重用 : 组件化, 可装配性, 互操作能力 ; 概念多 : 变量的作用域, 变量类型 ; 结构体 : 数组, 链表, 堆, 栈机器语言概念单一 : 指令, 数据, 地址每句的含义单一 ; 代码很长 ; 多句综合就难以理解 ; 指令存储器地址很多 ; 表达式, 函数, 模块 ; 面向对象 : 类, 封装 ; 继承 ; 多态 ; 满足机器处理要求概念之间的逻辑与时序关系, 一目了然

19 编译原理的含义 : 课程目标编译 : 翻译, 然后优化 ; 策略 : 高级语言通用机器语言优化特定的机器语言优化 ; 构建编译器的方法学 : 使用模型, 算法, 工具 ; 策略 : 用程序来生成程序, 简单的表达式编译器 ;

20 2. 翻译过程把英文翻译为中文的过程如下 : 识别出句子中的一个个单词 ; 分析句子的语法结构 ; 根据句子的含义进行初步翻译 ; 对译文进行修饰 ; 写出最后的译文词法分析语法分析中间代码产生优化目标代码产生

21 英译中例子 you are suppose to wear a formal suit with a red flower over the right chest to take part in the welcome ceremony to the president. 你被假定穿上右胸前配带一朵红花的正式西装去参加欢迎总统的仪式 ; 去参加总统欢迎仪式时, 你应穿右配红花的正装

22 编译流程前端后端与源语言有关与目标机器有关词法分析器字符流语法分析器标识符流语义分析器语法树中间代码生成器语法树机器无关代码优化器通用机器代码机器代码生成器通用机器代码机器代码优化器目标机器代码目标机器代码符号表

23 词法分析词法分析 / 扫描 (lexical analysis, scanning) 高级语言程序由句子串联而成, 句子由词素 (lexeme) 串联而成 ; 词素分为两类 : 预定义符 ( 保留字, 标点符, 运算符 ) 和自定义符 ; 例如, 对句子 :position = initial + rate * 60; 根据语言的命名规则, 逐字母扫描一遍, 就知有 7 个词素 : position = initial + rate * 60 [id,1] [=,] [id,2] [+,] [id,3] [*,] [60]

24 词法分析词法单元 (token): [token_name, attribute_value]; 例如 : [id,1] [=,] [id,2] [+,] [id,3] [*,] [60] 符号表 : row_id name type class v_class row_num 01 if 预留保留字 02 = 预留运算符 03 ; 预留标点符号 1 position 自定义全局变量 float initial 自定义局部变量 int rate 自定义局部变量 float 120 为了调试, 还应该记录哪些信息?

25 语法分析语法分析 / 解析 (syntax analysis/parsing): 根据语言的语法规则, 句子中各个词素含义来表达句义, 采用树型结构来表达, 也叫句子的语法树 (syntax tree) [id,1] [=,] [id,2] [+,] [id,3] [*,] [60] 语法分析 [id,1] = [id,2] + [id,2] * 表达出了运算过程, [60]

26 语义分析语义分析 (semantic analysis) 使用语法规则和符号表中的信息, 检查句子是否满足语言定义的语义约束例如 : 类型检查 (type checking) 例如 : 数组的下标一定要为整数 [id,1] = [id,2] + [id,2] * [60] [id,1] = [id,2] + [id,2] * intofloat 语义分析 60

27 中间代码生成根据语义分析的输出, 生成通用机器语言, 也叫中间表示, 例如三地址代码 : 每个指令最多包含三个数据 : 两个输入数, 一个输出数 [id,1] = [id,2] + [id,2] * intofloat 60 t1= intofloat(60) t2= id3 * t1 t3= id2 + t2 id1= t2 机器语言的特征是什么, 通用机器与具体机器有什么差异?

28 中间代码优化通过对中间代码的分析, 改进中间代码的质量降低资源使用 : 尽量减少存储器容量,CPU 计算量, 数据传输量实现更快机器语言特征 : 数据的存储, 数据的运输, 运算 ; 通用机器的存储单一, 无穷 ; t1= intofloat(60) t2= id3 * t1 t3= id2 + t2 id1= t2 具体机器的存储有区分, 有限 ; 减少了多少存储器容量,CPU 计算量, 数据传输? t1= id3 *60.0 id1= t1 + id2

29 目标代码生成把中间表示形式映射到目标语言 ( 特定机型 ) 寄存器的分配, 指令选择, 内存分配 t1= id3 *60.0 id1= t1 + id2 MOV EAX, id3 MULF EAX, #60.0 ADD EAX, id2 MOV id1,eax

30 目标代码的优化例如, 并行性分析与挖掘, 基于目标的优化 : 低功耗, 高效, 低存储

31 编译中优化的价值编译中的优化, 对有的应用程序, 就其运行速度而言, 优化前的运行时间, 与优化后的运行时间相比, 可以达到 10 倍 JAVA 程序在起初, 运行速度是其短板, 后来各种优化技术的应用, 大大得到了改进, 因而被普遍使用优化是编译器中至关重要的核心问题 ;

32 实例 : JAVA 语言 javac Java 源程序 (.java) Java 编译器 Java 字节码 (.class) java Java 虚拟机 ( 解释器 ) 解释执行操作系统平台

33 实例 :.net 编程工作原理各种高级语言代码各自的编译器即时编译 JIT 托管代码 (MSIL ) CLR 操作系统平台.NET

34 实例 : C++,C 语言 C/C++ 源程序 (.c/.cpp) 编译器 (compiler): 编译 obj 目标代码 ( 机器代码 ) 链接器 (linker): 组合装配 exe 可执行文件加载器 (loader): 定位 / 重定位进程

35 Release/Debug 版开发过程中, 有调试版本 / 发布版本之分, 它们有什么差异? 调试中, 可以看到函数调用栈, 各变量的值, 如何实现的? 编译如何支持调试!!! 符号表!!!

36 编译原理课程的教学内容什么叫分析, 什么叫综合, 归纳? 前端和后端分开, 会有什么好处? 前端 ( 分析部分 ) 后端 ( 综合 ) 与源语言有关与目标机器有关词法分析器字符流语法分析器标识符流语义分析器语法树中间代码生成器语法树机器无关代码优化器通用机器代码机器代码生成器通用机器代码机器代码优化器目标机器代码目标机器代码

37 3. 编译器构造方法学用就事论事方式来开发编译器, 一旦语法规则改变 ( 补充与改变 ), 就要去修改源程序, 问题 : 代价高, 时间长, 隐患多, 脆弱用编译器来生成编译器 ; 用程序来生成程序 ; 这涉及模型, 算法, 工具高层次, 高水平, 高境界的程序设计方式

38 编译器构造工具词法分析程序生成器根据语言语法的正则表达式自动生成词法分析器, 如 :LEX 语法分析程序生成器根据语言的语法描述自动生成语法分析器, 如 : YACC 语法制导翻译引擎可生成一组用于遍历分析树并生成中间代码的例程 ; 代码生成器的生成器根据中间语言与目标机语言的规则, 生成一个代码生成器数据流分析引擎数据流分析是代码优化的支撑 ;

39 4. 编译技术的广泛应用技术的应用 : 编译原理中的模型, 算法, 工具,, 在安全领域, 网路领域, 自然语言处理, 查重检测领域等都有广泛的应用例如, 正则表达式和状态机安全领域特征匹配, 网路领域得 IP 查找, 自然语言处理中的分词与语义识别 ; 方法学的应用 : 借用编译器来生成编译器的思想, 通过模型, 算法, 工具来实现用程序来生成程序 ; 例如, 电路设计 ;

40 5. 语言范型强制式语言程序说明怎么做, 如 : C,C++,Java,C# 等声明式语言程序说明做什么, 如 : SQL,Prolog 等面向对象语言支持面向对象编程, 如 : C++,Java,C#, 脚本语言具有高层次运算符的解释型语言 ; 常用于把多个计算过程 ( 脚本 ) 粘合在一起如 :Javascript,PHP,Python,VBscript 等 ; 特点 : 短

41 程序设计语言的发展历程历程第一代 : 机器语言第二代 : 汇编语言 ( 宏命令 ) 第三代 :Fortran,Cobol,Lisp,C,C++, 第四代 : 特定应用语言 :SQL, Postscript 第五代 : 基于逻辑和约束的语言,Prolog 强制式语言 / 声明式语言前者指明如何完成, 后者指明要完成哪些计算冯. 诺依曼语言 / 面向对象的语言 / 脚本语言

42 6. 程序语言基础 } include my_head.h int g_num, p=1; int main( int argc, char *argv[ ] ) { char szbuf [128]; char *psz = "Hello"; int p = 2; g_num = 189; MyFunction( p ); if (p > 0) { int p =3 ; p = strcpy(szbuf, psz); } return 0; 程序结构 : 程序由变量和函数组成 ; 程序由文件构成 ; 文件由句子构成 ; 句子分 : 定义语句 ; 操作语句 ; 连续的同级句子构成一个块 ; 块可以嵌套 ; 树形结构 ; 先定义后使用 ; 作用域 : 单向大盖小, 冲突时, 就近优先 ;

43 6. 程序语言的嵌套特性树状结构 } include my_head.h int g_num; int main( int argc, char *argv[ ] ) { char szbuf [128]; char *psz = "Hello"; int p = 2; g_num = 189; MyFunction( p ); if (p > 0) { int p; p = strcpy(szbuf, psz); } return 0; 函数块 1 main root 块函数块 2 MyFun if 块 1 while 块 2 if 块 1 if 块 2 while 块 3 函数块 3 strcpy

44 6.2 数据与存储地址程序中包含有 : 常量, 变量 ; 变量包括数据变量, 和函数变量 ( 即地址变量 ); 变量有值, 和存储地址两个概念 ; 变量的值存放在存储器中, 有一个存储地址 ; 一个变量的值, 可以是地址 ; 访问变量的值有两条途径 : 变量名, 存储地址 ; 间接访问机制 : 即间接寻址 : 通过一个数据去访问另外一个数据 ; 为高级语言开辟了广阔的想象和发挥空间 ;

45 间接寻址的应用跨模块间的函数调用编译器在编译模块 A 时, 为加载器设定 SinA 变量 ; 并把 sin 函数的地址 1024 赋给 sina; 编译器在编译模块 B 时, 为加载器设定了 sinb 变量 ; sinb = 1024 CALL ptr [128] sina = 1024 B 加载器在加载 B 到内存后, 通过检查 sinb 变量, 发现 B 中要调用 A 中的函数 sin, 于是加载模块 A, 设置 sinb = sina; 1024 函数 sin A

46 别名变量 A 的地址, 被多个其它变量 ( 假设 B,C,D) 存储, 128 sinb = 124 B 那么 A 的值, 即可通过 A 来访问, 也可通过 B,C,D 中的任何一个来访问, 于是 A,B, C,D 互称为别名在这里 sin,sina,sinb 互为别名 CALL ptr [128] sina = 1024 函数 sin A 函数调用, 如果传递参数是地址, 那么别名就还扩展到了被调函数中

47 结构体对象的访问策略 class AB { int a[10]; bool b; int getnum(); } int AB::getnum( ) { int num = 0; for (i=0; i<10; i++) if ( a[i]>18) num++; return num; } AB *p= new AB( ); p->getnum( ); class AB { int a[10]; bool b; int getnum(); } int AB::getnum(AB* this) { int num = 0; for (i=0; i<10; i++) if ( this->a[i]>18) num++; return num; } AB *p= new AB( ); getnum(p );

48 名字标识符和变量标识符字符串, 常由字母开头, 后跟若干个字母,_, 或数字 ; 用于指称一个实体, 如 : 数据对象过程类等 ; 名字助记符, 如 : 运算符 (+), 保留字, 标点符 ; 用来指称变量常量函数类型等 ; 所有标识符都是名字, 而名字不一定是标识符, 它还可以是一个表达式, 如 :x.y 是名字, 但不是标识符!

49 函数调用中的参数传递通常只有简单数据类型的参数传递, 传递的是值对于数组, 结构体对象, 类对象, 传递的是地址 ; 其原因是这些类型的数据, 空间量大, 拷贝这些类别的数据, 存储资源耗费大, 时间开销也大

50 宏扩展和预处理的含义例 1: #define ARRAYSIZE 100 那么在程序中有一个句子 :ARRAYSIZE = 10; 这个句子是否正确? 为什么? 例 2:#define a (x+1) int x =2; void b( ) {int x =1; printf( %d\n, a);} void c( ) {printf( %d\n, a);} int main() (b(); c(); return 1;} 宏扩展, 其含义就是在预处理环节, 进行文本替换预处理是在编译之前执行

51 小结 1: 编译过程前端 ( 分析部分 ) 后端 ( 综合 ) 与源语言有关与目标机器有关词法分析器字符流语法分析器标识符流语义分析器语法树中间代码生成器语法树机器无关代码优化器通用机器代码机器代码生成器通用机器代码机器代码优化器目标机器代码目标机器代码

52 小结 2 高级程序语言要解决的问题 : 通用, 简单, 重用, 鲁棒 ; 机器语言的特点是一个操作指令对应一个操作, 程序繁细很长, 可读性很差编译的含义是翻译 plus 优化 ; 编译包括词法分析, 语法分析等 7 个环节 ; 编译器构造方法学 : 模型, 算法, 工具的运用, 使用编译器来构造编译器 ; 编译技术和编译器构造方法学都有广泛的应用 ;

53 小结 3 程序语言可分为 : 强制式语言, 声明式语言, 面向对象语言, 脚本语言高级程序可编译后执行, 也可解释执行 ; 程序由数据和代码构成, 采用树形结构 : 程序由块构成, 块可嵌套 ; 数量用变量名来表示, 有存储地址数据也可通过其地址来访问变量分为两类 : 数据变量和地址变量 ( 也称作引用变量 )

54 随堂测试编译过程分为前端和后端, 前端包括哪五个环节? 后端包括哪两个环节? 画出编译的流程, 标出每个环节的输入和输出分成前端与后端的好处在哪儿? 每种高级语言都需要一个自己的前端, 还是共用一个前端? 每种机型都需要一个自己的后端, 还是共用一个后端?

55 谢谢谢谢!

编译技术 Compiler Principles 课程总结湖南大学信息科学与工程学院软件工程系杨金民 2019/06

编译技术 Compiler Principles 课程总结湖南大学信息科学与工程学院软件工程系杨金民 2019/06 编译技术 Compiler Principles 课程总结湖南大学信息科学与工程学院软件工程系杨金民 2019/06 软件工程技术知识体系机器学习 / 神经网络 (AI) 不确定性 ( 概率 ) 编译技术灵活多变, 但有基因数据库技术基础技术联线 : 直观易懂联系组合, 摘取分布式系统面向对象编程计算机网络操作系统数据结构 2 灵活多变 : 计算器该如何编程实现? a + b a +

软件工程技术知识体系 机器学习 / 神经网络 (AI) 不确定性 ( 黑盒, 概率 ) 编译技术 灵活多变, 但有基因 数据库技术 联系 组合, 摘取 基础技术 联线 : 直观易懂 分布式系统面向对象编程计算机网络操作系统数据结构 2

软件工程技术知识体系机器学习 / 神经网络 (AI) 不确定性 ( 黑盒, 概率 ) 编译技术灵活多变, 但有基因数据库技术联系组合, 摘取基础技术联线 : 直观易懂分布式系统面向对象编程计算机网络操作系统数据结构 2