成为网站建设人员措施,潍坊网站制作保定公司,家用宽带怎么做网站 访问,微信app下载安装官方版第一章 编译器简介
1. 编译器的核心功能
把源代码翻译成目标代码 2. 编译器设计两个原则#xff1a;
语义相同#xff1b;以某种可察觉的方式改进输入程序 3. 编译器内部结构
前端#xff1a;依赖于源语言#xff0c;与目标机器无关。将输入的代码映射到 IR。包括分析部…第一章 编译器简介
1. 编译器的核心功能
把源代码翻译成目标代码 2. 编译器设计两个原则
语义相同以某种可察觉的方式改进输入程序 3. 编译器内部结构
前端依赖于源语言与目标机器无关。将输入的代码映射到 IR。包括分析部分(词法、语法、语义分析)、中间代码生成与优化以及这部分的符号表管理错误处理。后端依赖于目标机器与源语言无关将 IR 映射到目标机的指令集和有限资源上处理前端生成的 IR。包括目标代码生成、与目标机有关的优化以及这部分的符号表管理和错误处理工作。4. 编译器的什么性质最重要
编译的效率即编译一个程序的速度和代价编译生成代码的效率即编译器生成的可执行程序的运行效率编译生成代码的质量即和源代码语义等价性5. 编译程序的主要构成成分有
词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序、出错处理程序。 6. 编译程序与解释程序区别
前者生成目标代码而后者不生成前者产生的目标代码的执行速度比解释程序的执行速度要快后者人机交互好适于初学者使用。 7. 图灵机
一种抽象的计算模型即将人们使用纸笔进行数学运算的过程进行抽象由一个虚拟的机器替代人类进行数学运算。它有一条无限长的纸带纸带分成了一个一个的小方格每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态还有一些固定的程序。在每个时刻机器头都要从当前纸带上读入一个方格信息然后结合自己的内部状态查找程序表根据程序输出信息到纸带方格上并转换自己的内部状态然后进行移动。第二章 文法
1. 文法
语言结构的定义和描述是有穷非空的产生式集合由终结符、非终结符、产生式、开始符号四部分组成。 2. 终结符和非终结符
终结符是文法所定义的语言的基本符号可称为单词、token
非终结符是用来表示语法成分的符号称为语法变量 3. 0型文法、1型文法、2型文法、3型文法区别
0型文法 包含 1型文法 包含 2型文法 包含 3型文法
10型文法对于推导式 α→βα属于非终结符和终结符并集的正闭包且α至少含有一个非终结符并且 β 属于非终结符和终结符的闭包。它可由图灵机识别。
21型文法上下文有关文法。它可由线性线界自动机识别。
左式可以有多个字符但是必须有一个非终结符右式可以有多个字符可以是终结符或非终结符但是必须是有限个字符左式长度必须不大于右式除了右式为空。
32型文法上下文无关文法。它可由下推自动机识别。2型文法(即上下文无关文法)是描述程序设计语言语法的形式化工具
左式只能有一个字符而且必须是非终结符右式可以有多个字符可以是终结符或非终结符但是必须是有限个字符
43型文法正规文法包括左线性文法和右线性文法。它可由有限自动机识别。3型文法是是描述程序设计语言词法的形式化工具
左式只能有一个字符且必须是非终结符右式至多有两个字符如果有两个字符则必须是一个终结符和一个非终结符如果有一个字符则必须是终结符。右式如果是终结符非终结符则为右线性文法如果是非终结符终结符则为左线性文法。4. 二义性文法
二义性文法一个文法存在某个句子对应两棵不同的语法树。或者说一个文法存在某个句子有不同的最左最右推导。 二义性文法存在问题同一个程序有不同的含义程序运行的结果不是唯一的。
二义性文法解决方案文法的重写 5. 最左推导
在推导的任何一步 α → β都是对 α 中的最左非终结符进行替换。 第三章 词法分析
词法分析是编译的第一个阶段它的主要任务是从左至右逐个字符地对源程序进行扫描产生一个个单词序列用于语法分析。执行词法分析的程序称为词法分析程序或扫描程序。
词法分析器实现方法手工编码实现法、根据正则表达式画DNF 正则表达式
正则表达式与正规文法等价对任意一个正规文法存在一个定义同一个语言的正则表达式对每个正则表达式存在一个生成同一个语言的正规文法两者可相互转化。正规式和有限自动机之间可以相互转换它们之间存在着等价性。状态自动机
1DNF
有限状态自动机字母表状态集、初始状态、终结状态集、转移函数非确定的有限状态自动机NFA状态转移函数是不确定的即对于任意字符有多于一个状态可以转移确定的有限状态自动机DFA每次接受字符走到的状态是确定的即对于任意字符最多有一个状态可以转移NFA和DFA在表达力上是等价的任何DFA是某个NFA的一个特例任何NFA可以通过一个DFA模拟
2RE转化为NFAThompson算法
3NFA转为DFA子集构造算法
4DFA转化为词法分析器代码Hopcroft最小化算法 第四章 语法分析
需要掌握的LL(1)LR(0)SLRLR(1)LALR
1. 语法分析
概念在词法分析的基础上将单词序列分解成各类语法短语如“程序”、“语句”、“表达式”等。这种语法短语也成为语法单位可以表示成语法树。步骤 对程序设计语言的语法规则进行形式化描述用2型文法根据语言的语法描述形式定义各种基本语法结构的抽象语法树选择一种合适的语法分析算法并在分析程序中插入动作2. 自顶向下和自底向上
1自顶向下的分析方法LL
概念也称面向目标的分析方法也就是从文法的开始符号出发企图推导出与输入的单词符号相匹配的句子若输入串是给定文法的句子则必能推出反之必然出错。
2自底向上的分析算法LR
从输入串开始逐步进行“归约”直至归约到文法的 开始符号或者说从语法树的末端开始步步向上“归约”直到根节点。应用面广能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构能有效实现是无回溯的移进—归约方法容易查错LR分析器能够及时发现语法错误和准确指出错误位置3. 分析树
推导可以表达成树状结构和推导所用的顺序无关最左、最右、其他树中的每个内部节点代表非终结符每个叶子节点代表终结符每一步推导代表如何从双亲节点生成它的孩子节点
4. 递归下降分析
递归下降分析方法是一种自上而下的语法分析方法该方法执行一组递归函数判断输入的单词序列是否符合语法规则。为每个非终结符构造一个分析函数 用前看符号指导产生式规则的选择 5. 各种语法分析算法
1LL(1) 分析算法
其中的第一个 L 代表从左向右扫描输入第二个 L 表示产生最左推导1 代表在决定分析器的每步动作时向前看一个输入符号。LL(1)分析算法优点算法运行高效有现成的工具可用缺点 能分析的文法类型受限 往往需要文法的改写2LR(0) 分析算法
从左至右扫描和自底向上的语法分析且在分析的每一步只须根据分析栈当前已移进和归约出的全部文法符号并至多再向前查看 0 个输入符号L是指自左(Left)向右分析输入单词序列R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)括号中的 0 是指在决定当前分析动作时向右看的单词个数。LR(0) 分析算法优点容易实现缺点能分析的文法有限LR(0) 分析表可能包含冲突。
3SLR 分析算法
与 LR(0) 分析算法基本步骤相同仅区别于对规约的处理。优点有可能减少需要规约的情况有可能去除需要移进-规约冲突。缺点仍然有冲突出现的可能。
4LR(1)
缺点同心集的分裂使状态数目剧烈增长导致存储容量的急剧增加。同心集如果除前看符号外两个LR(1)项目集是相同的则称这两个项目集是同心的。
5LALR(1) 文法
LALR: lookahead-LR对 LR(1) 的同心集进行合并分析能力介于SLR和LR(1)二者之间SLR LALR(1) LR(1)6. 二义性文法在LR分析中的应用
任何一个二义性文法不是LR类文法也不是LL(k)文法任何一个二义性文法不存在与其相应的确定的语法分析器但对某些二义性文法可以人为给出优先级和结合性的规定构造出比相应的非二义性文法更优越的LR分析器第五章 语义分析
1. 语法制导翻译
基于属性文法的处理过程对单词符号串进行语法分析构造语法分析树然后根据需要构造属性依赖图遍历语法树并在语法树的各结点处按语义规则进行计算。属性文法是在短语结构文法的基础上加入每个短语和整个句子语义信息所构成的文法综合属性用于“自下而上”传递信息。在语法树中一个结点的综合属性的值由其子结点的属性值确定。只包含综合属性的属性文法称为S-属性文法。继承属性用于“自上而下”传递信息。 在语法树中一个结点的继承属性由此结点的父结点和/或兄弟结点的。既包含综合属性又包含继承属性的是L-属性文法。
2. 语义分析的概念
审查源程序有无语义错误为代码生成阶段收集类型信息。其任务是检查程序结构控制结构和数据结构的一致性或完整性。比如控制流检查唯一性检查名字的上下文相关性检查类型检查等。 第六章 中间表示
1. 中间表示的概念
进行了语法分析和语义分析阶段的工作后将源程序变成一种内部表示形式这种内部表示形式叫做中间语言或中间代码。 2. 中间表示的结构
图IR语法分析树、抽象语法树、有向无环图、控制流图、依赖关系图、调用图
线性IR堆栈机代码、三地址代码 第七章 代码优化
1. 代码优化概念
对被优化的程序进行的一种语义保持的变换语义保持就是程序的可观察行为不能改变 2. 代码优化的目的和意义
代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行 一种等价变换在保证变换前后代码执行结果相同的前提下尽量使目 标程序运行时所需要的时间短同时所占用的存储空间少。 3. 分类前端优化、中间表示上的优化、窥孔优化、局部优化、循环优化、全局优化 第八章 目标代码生成
1. 目标代码生成概念
把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。其任务是给源程序的数据分配计算资源、给源程序的代码选择指令。
