文库文库 - 千万精品文档,你想要的都能搜到,下载即用。

编译技术总结 2019.pdf

Warm light(温暖)25 页 815.996 KB下载文档
编译技术总结 2019.pdf编译技术总结 2019.pdf编译技术总结 2019.pdf编译技术总结 2019.pdf编译技术总结 2019.pdf编译技术总结 2019.pdf
当前文档共25页 2.77
下载后继续阅读

编译技术总结 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,安全,生物,经济; 谢谢大家,有缘相识 谢 谢! 大家实现了飞跃吗?

相关文章