编译技术总结 2019.pdf

编译技术 Compiler Principles 课程总结 湖南大学信息科学与工程学院 软件工程系 杨金民 2019/06 软件工程技术知识体系 机器学习/神经网络(AI) 不确定性( 概率 ） 编译技术 灵活多变，但有基因 数据库技术 联系  组合，摘取 基础技术 联线 ：直观易懂 分布式系统 面向对象编程 计算机网络 操作系统 数据结构 2 灵活多变：计算器该如何编程实现？ la+b la+b*c l a + b * (c + d) l (a + b * (c + d )) * (e + f) l (a0 + (a1 + (a2 + a3 * x))*x)*x l ........ 3 处理的问题：可扩展的树形结构 l 词法分析是处理线性结构的内容； l 程序：可扩展的树形结构； l 其它可扩展的树形结构体：HTML文档，XML文档，JSON； l 所有交互数据——带语义，须解析的数据 ； l 解析器，编辑器，编译器；脚本引擎，浏览器，安全扫描器； l 网状：是在树状的基础上，附加属性：而且是引用属性； 4 可扩展的树形结构 l 串接性；经典的，如串联电路，序列/流程/环节： F(E) l 并列性；经典的，如并行电路，F(E) | id l 嵌套性；E  E +T ； S  while （B）S l 等级/优先级/有序性： EE+T； TT*F F(E) Fid 5 前端与后端 C++语言 C语言 编译器 Fortran语言 pascal语言 Cobol语言 X86, Windows X86, Linux Java语言 Basic语言 虚拟机 中间代码 Apple 手机, Andriod IBM Cray, Unix 6 编译型执行 vs 解释型执行 （编译，链接，加载 vs 解释执行） l 都要对程序进行语法分析和语义分析，翻译成目标代码； l 在编译型执行中，目标代码为机器指令序列；在解释性执行中， 目标代码为函数调用序列； l 编译型执行时，是对整个程序进行先翻译，后执行。因此，会 对整个程序进行中间代码优化和机器代码优化； l 解释型执行时，则是每翻译一个语句，便执行这个语句。因此 通常不做优化。对不要执行的语句块，则直接跳过，不做翻译； l 编译型执行，适合低级的特定概念层面上的计算密集型程序， 7 解释型执行适合高级的抽象概念层面上的交互密集型程序； 第三章要掌握的内容 l 模式的正则表达式表达； l 正则表达式的三种运算，以及？: 0个或1个 l 基于组合原则的正则表达式表达  NFA； l 基于子集构造法的NFA  DFA l 基于DFA的匹配与识别：输入串是否匹配正则表达式； 第四章 要掌握的内容——LL文法和LL分析 l 语法的上下文无关文法表达；正则表达式  上下文无关文法 l LL(1)语法分析：消除左递归，提取左公因子（彻底）； l 对文法的每个产生式：计算FIRST（）；对每个非终结符号： 计算FIRST（），FOLLOW（）； l 填写出文法的LL(1)预测分析表；判断文法是否是LL(1)文法； l 基于LL(1)预测分析表，基于栈，对输入串做自顶向下的推导。 完成语法分析，语义分析，中间代码的生成。得出产生式展 开序列；判断输入串是否符合文法； 第四章 要掌握的内容——LR文法和LR分析 l LR(0)项目，LR(1)项目，LALR(1)项目， l 文法  DFA（基于LR(0)项集，LR(1)项目） LR语法分析表； l 判断文法是否是LR(0)，SLR(1)，规范LR(1)，LALR(1) 文法； l 基于文法的语法分析表，基于栈（符号实例栈，状态栈），对 输入串做自底向上的推导。完成语法分析，语义分析，中间代 码的生成。得出产生式规约序列；判断输入串是否符合文法； DFA的优势——LR(0)项有物理含义 E I0 E'→E E→ E + E E→ E*E E→ (E) E→ id I1 E'→E E→ E + E E→ E*E + I4 E→ E + E E→ E + E E→ E*E E→ (E) E→ id $ Accept * id id I3 E→ id ( I7 E→ E + E E→ E + E E→ E*E E I8 E→ E * E E→ E + E E→ E*E + + + * * * id id ( I5 E→ E*E E→ E + E E→ E*E E→ (E) E→ id E I2 F→ (E) E→ E + E E→ E*E E→ (E) E→ id E ( ( I6 F→ (E ) E→ E + E E→ E*E ) I9 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 DFA的优势——LR语法分析实用的原因 I4 S→ id = E id I0 P→S S→ {S} S→ if(B) S S→ while(B) S S→ id = E S { { if I3 S→if( B ) S S→ {S} S→ if(B) S S→ while(B) S S→ id = E if I1 P→S I2 S→ {S} S→ SS S→ if(B) S S→ while(B) S S→ id = E I6 S S→if( B ) S I5 S→ {S} S→ SS S S→ if(B) S S→ while(B) S S→ id = E } S I7 S→ {S} I8 S→ SS 第五章 语法制导的翻译 目标：语义分析；中间代码生成； 给非终结符定义属性；综合属性，继承属性，L属性 给终结符只有综合属性，无继承属性； SDD表达了一个产生式中的各符号的属性之间的关系； SDT表达了在语法分析中的某个状态时刻，要执行的动作； 自然是：先SDD  SDT SDD：把每个非终结符/终结符看作一个类；SDT：把每个非终 结符/终结符看作类的实例； 13 编译过程 目标机器代码 机器代码优化器 目标机器代码 机器代码生成器 通用机器代码 中间代码优化器 通用机器代码 中间代码生成器 语法树 语义分析器 语法树 语法分析器 标识符流 词法分析器 字符流 在实现上，三者是一块儿完成的 与目标机器有关 与源语言有关 后端(综合) 前端(分析部分) 在概念上，语法分析，语义分析，中间代码生成: 三个环节/步骤； 语言特性 • 高级语言程序：明显的结构体：表达概念间的内在关系（静态)， 以及时序关系(依赖关系)。原子数据，结构体，表达式，语句， 语句块，函数。用名字表达：直观简单，通俗易懂，灵活通用， 重用鲁棒； • 中间代码的特性：数据和代码进行了分离；语句的单一性；概念 减少，如分支/循环的统一化；用概念地址表达。无直观的结构 和层次，语句短小，程序侃长，可读性很差，数据与代码分离。 • 机器语言程序：用内存地址表达；在处理上过程更加细化：因运 算/处理的约束性，存储空间的有限性，引入了数据/代码的运输； 编译技术 • 编译的含义是翻译plus优化； • 编译被拆分成7个环节； • 编译器构造方法学：模型，算法，工具的运用，使用编译器来 构造编译器； 第六章 代码生成——语义分析和中间代 码生成 l 先看文法，是LL文法，还是LR文法； l LL文法：设立继承属性，也可有综合属性； l LR文法：设立综合属性； l 基于语法分析过程的压栈/出栈特性，构思出SDT； l 在某时刻的状态值，在后面要用到时，通过设置哑非终结符来记 录，哑非终结符的实例也入栈； l 在SDD中，把每个非终结符/终结符看作一个类；在SDT中，把 每个非终结符/终结符看作类的实例； 第六章 LR文法的SDT LR文法：设立综合属性； l B.truelist, B. falselist ； S. nextlist，因为嵌套，有关系； B  B1 && B2 | B1 || B2 | (B1) | E> E | id ① S if (B) S1 else S2 ② S while(B) S1 ③ S for(S1; S2; S3) S4 l B.truelist, B. falselist的确定时刻；S. nextlist的确定时刻； SSS； S {S} 程序 l 程序由数据和代码构成，采用树形结构：程序由块构成，块可 嵌套； l 数量用变量名来标示，有存储地址。数据通过其地址来访问。 变量分为两类：数据变量和地址变量（也称作引用变量）。 第七章 运行时环境 l 局部变量的内存地址，编译时不确定。表达：BaseAddress + Offfset， BaseAddress：函数实例的；offset：常量； Ø 每个语句块(block): 都有自己的符号表。 Ø 基于block的嵌套关系，每个符号表都有一个prior, Ø 一个局部变量的offset的计算，要从它所属的符号表，一直上索 到函数的符号表； l 全局变量：有确定性，内存地址； l new 变量，引出了一个说不尽的话题：内存回收； 第八章 代码生成 l 中间代码优化： l 将中间代码划分成基本快： l 头：起始语句，标签语句，call的目标语句；goto语句随后的语 句； l 尾：call语句；goto语句；结束语句 l 基本快的优化； block之间的优化； l 活跃变量/死变量； l 间接变直接； l 多次变一次； 第八章 代码生成 l 三类机器指令：运输，运算， 跳转； l 三类寻址：变量；数组a(Rx)； 指针0(Rx)； l 寄存器的分配与指派： Ø 基本快翻译中的寄存器分配； Ø 循环体中的寄存器分配； Ø 全局级的寄存器分配； l 引用表， 寄存器描述符，变量描述符； 因为供不应求，引发了寄存器的腾空问题 概念名词 l 语法分析树； l 注释语法分析树；带上属性值的语法分析树； l 抽象语法分析树；表达引用关系 l DAG(有向无环图）：无重复的抽象语法树； 展望 l 调试和Debug： l 多处理器结构：将代码划分成可并行执行的块：数据流分析，依 赖关系分析； l 缓存结构：对即将要的数据和代码：内存  二级cache  一级cache  寄存器； l 拓展应用领域：WEB，安全，生物，经济； 谢谢大家，有缘相识 谢 谢！ 大家实现了飞跃吗？