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

Size: px

Start display at page:

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

底逮
4 years ago
Views:

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

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 处理的问题 : 可扩展的树形结构词法分析是处理线性结构的内容 ; 程序 : 可扩展的树形结构 ; 其它可扩展的树形结构体 :HTML 文档,XML 文档,JSON; 所有交互数据带语义, 须解析的数据 ; 解析器, 编辑器, 编译器 ; 脚本引擎, 浏览器, 安全扫描器 ; 网状 : 是在树状的基础上, 附加属性 : 而且是引用属性 ; 4

5 可扩展的树形结构串接性 ; 经典的, 如串联电路, 序列 / 流程 / 环节 : F (E) 并列性 ; 经典的, 如并行电路,F (E) id 嵌套性 ;E E +T ; S while (B)S 等级 / 优先级 / 有序性 : E E+T; T T*F F (E) F id 5

6 前端与后端 C++ 语言 C 语言编译器虚拟机 X86, Windows Java 语言 X86, Linux Basic 语言中间代码 Apple Fortran 语言手机, Andriod pascal 语言 IBM Cray, Unix Cobol 语言 6

7 编译型执行 vs 解释型执行 ( 编译, 链接, 加载 vs 解释执行 ) 都要对程序进行语法分析和语义分析, 翻译成目标代码 ; 在编译型执行中, 目标代码为机器指令序列 ; 在解释性执行中, 目标代码为函数调用序列 ; 编译型执行时, 是对整个程序进行先翻译, 后执行因此, 会对整个程序进行中间代码优化和机器代码优化 ; 解释型执行时, 则是每翻译一个语句, 便执行这个语句因此通常不做优化对不要执行的语句块, 则直接跳过, 不做翻译 ; 编译型执行, 适合低级的特定概念层面上的计算密集型程序, 解释型执行适合高级的抽象概念层面上的交互密集型程序 ; 7

8 第三章要掌握的内容模式的正则表达式表达 ; 正则表达式的三种运算, 以及?: 0 个或 1 个基于组合原则的正则表达式表达 NFA; 基于子集构造法的 NFA DFA 基于 DFA 的匹配与识别 : 输入串是否匹配正则表达式 ;

9 第四章要掌握的内容 LL 文法和 LL 分析语法的上下文无关文法表达 ; 正则表达式上下文无关文法 LL(1) 语法分析 : 消除左递归, 提取左公因子 ( 彻底 ); 对文法的每个产生式 : 计算 FIRST(); 对每个非终结符号 : 计算 FIRST(),FOLLOW(); 填写出文法的 LL(1) 预测分析表 ; 判断文法是否是 LL(1) 文法 ; 基于 LL(1) 预测分析表, 基于栈, 对输入串做自顶向下的推导完成语法分析, 语义分析, 中间代码的生成得出产生式展开序列 ; 判断输入串是否符合文法 ;

10 第四章要掌握的内容 LR 文法和 LR 分析 LR(0) 项目,LR(1) 项目,LALR(1) 项目, 文法 DFA( 基于 LR(0) 项集,LR(1) 项目 ) LR 语法分析表 ; 判断文法是否是 LR(0),SLR(1), 规范 LR(1),LALR(1) 文法 ; 基于文法的语法分析表, 基于栈 ( 符号实例栈, 状态栈 ), 对输入串做自底向上的推导完成语法分析, 语义分析, 中间代码的生成得出产生式规约序列 ; 判断输入串是否符合文法 ;

11 I 0 E' E E E + E E E*E E (E) E id id ( DFA 的优势 LR(0) 项有物理含义 E I 1 + I 4 E E' E E E + E E E + E E E + E + E E *E E E*E + E (E) $ + E id ( Accept I 3 E id id I 2 F ( E) E E + E E E*E E (E) E id * * I 5 E E* E E E E + E E E*E * E (E) * id E id id E ( ( I 7 E E + E E E + E E E *E I 8 E E * E E E + E E E *E I 6 F (E ) E E + E E E *E ) I 9 E (E) E TE' E' +TE' ε T FT ' T ' * F T ' ε F (E) id E E + T T T T * F F F (E) id E E + E E E * E E (E) id

12 DFA 的优势 LR 语法分析实用的原因 I 4 S id = E I 0 P S S {S} S if(b) S S while(b) S S id = E if id S { { I 1 P S I 2 S { S} S SS S if(b) S S while(b) S S id = E S I 5 S {S } S S S S if(b) S S while(b) S S id = E } S I 7 S {S} I 8 S SS I 3 S if( B ) S S {S} S if(b) S S while(b) S if S id = E I S 6 S if( B ) S

13 第五章语法制导的翻译目标 : 语义分析 ; 中间代码生成 ; 给非终结符定义属性 ; 综合属性, 继承属性,L 属性给终结符只有综合属性, 无继承属性 ; SDD 表达了一个产生式中的各符号的属性之间的关系 ; SDT 表达了在语法分析中的某个状态时刻, 要执行的动作 ; 自然是 : 先 SDD SDT SDD: 把每个非终结符 / 终结符看作一个类 ;SDT: 把每个非终结符 / 终结符看作类的实例 ; 13

14 编译过程前端 ( 分析部分 ) 后端 ( 综合 ) 与源语言有关与目标机器有关词法分析器字符流语法分析器标识符流语义分析器语法树中间代码生成器语法树中间代码优化器通用机器代码机器代码生成器通用机器代码机器代码优化器目标机器代码目标机器代码在概念上, 语法分析, 语义分析, 中间代码生成 : 三个环节 / 步骤 ; 在实现上, 三者是一块儿完成的

15 语言特性高级语言程序 : 明显的结构体 : 表达概念间的内在关系 ( 静态 ), 以及时序关系 ( 依赖关系 ) 原子数据, 结构体, 表达式, 语句, 语句块, 函数用名字表达 : 直观简单, 通俗易懂, 灵活通用, 重用鲁棒 ; 中间代码的特性 : 数据和代码进行了分离 ; 语句的单一性 ; 概念减少, 如分支 / 循环的统一化 ; 用概念地址表达无直观的结构和层次, 语句短小, 程序侃长, 可读性很差, 数据与代码分离机器语言程序 : 用内存地址表达 ; 在处理上过程更加细化 : 因运算 / 处理的约束性, 存储空间的有限性, 引入了数据 / 代码的运输 ;

16 编译技术编译的含义是翻译 plus 优化 ; 编译被拆分成 7 个环节 ; 编译器构造方法学 : 模型, 算法, 工具的运用, 使用编译器来构造编译器 ;

17 第六章代码生成语义分析和中间代码生成先看文法, 是 LL 文法, 还是 LR 文法 ; LL 文法 : 设立继承属性, 也可有综合属性 ; LR 文法 : 设立综合属性 ; 基于语法分析过程的压栈 / 出栈特性, 构思出 SDT; 在某时刻的状态值, 在后面要用到时, 通过设置哑非终结符来记录, 哑非终结符的实例也入栈 ; 在 SDD 中, 把每个非终结符 / 终结符看作一个类 ; 在 SDT 中, 把每个非终结符 / 终结符看作类的实例 ;

18 第六章 LR 文法的 SDT LR 文法 : 设立综合属性 ; B.truelist, B. falselist ; S. nextlist, 因为嵌套, 有关系 ; B B 1 && B 2 B 1 B 2 (B 1 ) E> E id 1 S if (B) S 1 else S 2 2 S while(b) S 1 3 S for(s 1 ; S 2 ; S 3 ) S 4 B.truelist, B. falselist 的确定时刻 ;S. nextlist 的确定时刻 ; S SS; S {S}

19 程序程序由数据和代码构成, 采用树形结构 : 程序由块构成, 块可嵌套 ; 数量用变量名来标示, 有存储地址数据通过其地址来访问变量分为两类 : 数据变量和地址变量 ( 也称作引用变量 )

20 第七章运行时环境局部变量的内存地址, 编译时不确定表达 :BaseAddress + Offfset, BaseAddress: 函数实例的 ;offset: 常量 ; 每个语句块 (block): 都有自己的符号表基于 block 的嵌套关系, 每个符号表都有一个 prior, 一个局部变量的 offset 的计算, 要从它所属的符号表, 一直上索到函数的符号表 ; 全局变量 : 有确定性, 内存地址 ; new 变量, 引出了一个说不尽的话题 : 内存回收 ;

21 第八章代码生成中间代码优化 : 将中间代码划分成基本快 : 头 : 起始语句, 标签语句,call 的目标语句 ;goto 语句随后的语句 ; 尾 :call 语句 ;goto 语句 ; 结束语句基本快的优化 ; block 之间的优化 ; 活跃变量 / 死变量 ; 间接变直接 ; 多次变一次 ;

22 第八章代码生成三类机器指令 : 运输, 运算, 跳转 ; 三类寻址 : 变量 ; 数组 a(r x ); 指针 0(R x ); 寄存器的分配与指派 : 基本快翻译中的寄存器分配 ; 循环体中的寄存器分配 ; 全局级的寄存器分配 ; 引用表, 寄存器描述符, 变量描述符 ; 因为供不应求, 引发了寄存器的腾空问题

23 概念名词语法分析树 ; 注释语法分析树 ; 带上属性值的语法分析树 ; 抽象语法分析树 ; 表达引用关系 DAG( 有向无环图 ): 无重复的抽象语法树 ;

24 展望调试和 Debug: 多处理器结构 : 将代码划分成可并行执行的块 : 数据流分析, 依赖关系分析 ; 缓存结构 : 对即将要的数据和代码 : 内存二级 cache 一级 cache 寄存器 ; 拓展应用领域 :WEB, 安全, 生物, 经济 ;

25 谢谢大家, 有缘相识谢谢! 大家实现了飞跃吗?

大侠素材铺

大侠素材铺编译原理与技术语法制导翻译 Ⅱ 计算机科学与技术学院李诚 22/10/2018 Announcement Tutorial on Thursday (25/10/2018) 3B201, Class time Assignment review Q & A Cheng @ Compiler Fall 2018, USTC 2 主要内容源程序词法分析器 token 语法分析器分析树语义分析

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

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