编译概述

翻译和解释

编译的阶段和任务

分析阶段: 根据原语言的定义, 分析源程序 1. 词法分析 2. 语法分析 3. 语义分析

综合阶段: 根据分析结果构造目标程序 4. 中间代码生成 5. 代码优化 6. 目标代码生成

符号表的管理 错误诊断和处理

total := total + rate * 4 语法分析的分析树:

total := total + rate * 4 语义分析的语法树:

编译有关的其他概念

前端: 与源语言有关而与目标机器无关的部分 词法分析、语法分析、符号表的建立、语义分析和中间代码生成 与机器无关的代码优化工作 相应的错误处理工作和符号表操作

后端: 与目标机器有关的部分 目标代码的生成、与机器有关的代码优化 相应的错误处理和符号表操作

前后端的优点: 便于编译程序的移植和构造

“遍” 的概念: 对源程序或其中间形式从头到尾扫描一遍, 并作相关的加工处理, 生成新的中间形式或目标程序. 分遍的优点: 减少对主存容量的要求; 各遍编译程序功能独立、单纯，相互联系简单，编译程序结构清晰; 更充分的优化工作，获得高质量目标程序; 为编译程序的移植创造条件.

分遍的缺点: 增加了不少重复性的工作.

编译程序的伙伴工具

编译程序的前后处理器:

1. 预处理器
2. 汇编程序
3. 连接装配程序

预处理器

1. 宏处理
2. 文件包含
3. 语言补充

汇编程序

汇编语言用助记符表示操作码, 用标识符表示存储地址.

连接装配程序

编译原理的应用

词法分析

词法分析程序与语法分析程序的关系

词法分析作用： 扫描源程序字符流 按照源语言的词法规则识别出各类单词符号 产生用于语法分析的记号序列 词法检查 与用户接口的一些任务 - 跳过注释和空白 - 把错误和源程序联系起来 创建符号表

词法分析和语法分析关系： 词法分析作为独立的一遍 词法是语法的子程序 词法是语法的协同程序

分离词法分析程序的好处 简化设计 改进编译程序的效率 加强编译程序的可移植性

词法分析程序的输入与输出

设置缓冲区: 为了得到一个单词字符的确切性质, 需要超前扫描若干字符

记号: 某一类单词符号的类别编码

模式: 某一类单词符号的构词规则

单词: 某一类单词符号的一个特例

记号的属性

• 词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。
• 记号影响语法分析的决策，属性影响记号的翻译。
• 在词法分析阶段，对记号只能确定一种属性
  • 标识符：单词在符号表中的入口指针
  • 常数：它所表示的值
  • 关键字：（一符一种、或一类一种）
  • 运算符：（一符一种、或一类一种）
  • 分界符：（一符一种、或一类一种）

记号的描述和识别

词法：描述语言的标识符、常数、运算符和标点符号等记号的文法

语法：借助于记号来描述语言的结构的文法

文法书写约定：

• 终结符号：

  • 次序靠前的小写字母，如：a、b、c
  • 运算符号，+、-…
  • 各种标点符号
  • 数字 1、2、……9
  • 黑体字符串 id、if…

• 非终结符号

  • 次序靠前的大写字母
  • 大写字符 S 常用作文法的开始符号
  • 小写的斜体符号串 expr、term…

• 文法符号

  • 次序靠后的大写字母

• 终结符号串

  • 次序靠后的小写字母

• 文法符号串

  • 小写的希腊字母 $\alpha$、$\beta$…

词法分析程序的设计与实现

语法分析

语法分析简介

自顶向下分析

递归下降分析

从上到下，从左到右分析，最左推导，不断试探和回溯

左递归可能会导致死循环，例如: A $\rightarrow$ Ab | b, 如果识别到了 A, 就会一直执行 A $\rightarrow$ Ab

消除左递归：

递归调用预测分析

非递归预测分析

First 集合, 注意空串的条件

对于 $A \rightarrow BC$, 如果只有 $B$ 能够推出 $\varepsilon$ 元素(不一定是一步推出), 则 $B$ 和 $C$ 中的所有非 $\varepsilon$ 元素都要加入到 $First(A)$ 中; 如果 $B$ 和 $C$ 能同时推导出 $\varepsilon$ 元素, 才会有 $\varepsilon \in First(A)$

Follow 集合中一定不会有空串

注意上述规则的第三点, 若有 $A \rightarrow BC$ 且 $C \rightarrow \varepsilon \ (不一定是一步推导)$ 则有 $Follow(B) \subset Follow(A)$, 同时 $Follow(C) \subset Follow(A)$也当然满足

个人理解感觉就是:

1. 直观上 $First(A)$ 中的一个元素不能对应两个不同的产生式
2. 如果 $First(A)$ 中含有 $\varepsilon$, 则必须 $First(A) \cap Follow(A) = \phi$
3. 2 的理解有些不对, 还是看图片的算法吧

自底向上分析

短语, 直接短语, 句柄: B 站例题

短语，句柄等概念

LR 分析

LL 分析需要消除左递归, LR 分析不需要消除左递归 LR(K)的含义: L: 从左到右扫描字符, R: 推导过程使用最右推导, K: 向前看 K 个字符

分析模型

LR(0)

正常构造即可

7 编译原理构造 LR(0)分析表(包含构建项目规范族）

SLR(1)

DFA 与 LR(0) 相同, 分析表中规约项目的位置要根据 FOLLOW 集合写

8 编译原理构造 SLR(1)分析表

LR(1)

LR(1) 文法的 DFA 构造: 编译原理—混子速成期末保过, 精准空降到 1:09:19

提示:

1. 别忘了每个项目都要求闭包
2. ,后面的多个字符是并列关系, 比如: $ A \rightarrow \cdot B,\ c/d $, 求 $B$ 的 lookhead字符 的时候是求 $First(c) \cup First(d) = { c, d }$

分析表中的规约项目的位置根据 lookhead字符 写

LALR(1)

把 LR(1) 中的同心集合并, 合并后只可能会产生规约-规约冲突

同心集: , 前面的分析相同, 只有 lookhead 字符 不同的式子

判断是否是上述几种文法的方式:

• LR(0)文法的DFA中不存在移进-规约冲突和规约-规约冲突 (下面简称冲突), 则为 LR(0)文法;
• LR(0)的DFA中存在冲突, 但是可以通过 Follow 集合解决冲突, 则为 SLR(1)文法;
• LR(1)的DFA不存在冲突, 或存在冲突但是可以通过展望字符解决冲突, 则为 LR(1)文法;
• LR(1)的DFA合并同心集后没有产生冲突, 则为 LALR(1)文法.

语法制导翻译

很抽象的一章, 网上也找不到什么资料, 先贴个链接, 剩下的等期末复习再补全

北邮 编译原理（下）_北邮编译原理与技术期中-CSDN 博客

语义分析

C 语言对于 struct 和 union 使用名字等价, 其他类型使用结构等价

运行环境

绘制控制栈状态:

• 控制链: 由当前函数指向调用当前函数的函数;
• 访问链: 由当前函数指向代码中当前函数的上一级函数.

参数传递机制:

display 表:

d[i]: 指向嵌套深度为 i 的最新活动的活动记录

左边第二张图应该只是中间动画, 不用管

中间代码生成

【编译原理笔记 11】中间代码生成：类型表达式，声明语句的翻译_编译原理表达式翻译-CSDN 博客

目标代码生成

指令开销：和寄存器相关操作均为 0，和立即数或内 存操作为 1，移动/加法等操作为 1

代码优化

【编译原理笔记 19】代码优化： 支配结点和回边，自然循环及其识别，删除全局公共子表达式和复制语句，代码移动，作用于归纳变量的强度削弱，归纳变量的删除_编译原理 回边-CSDN 博客

基本块优化步骤:

• 常数合并及常数传播: 将 x:=2+3 合并为 x:=5;
• 删除公共表达式: 将相同的表达式用相同的变量代替, 比如a:=b+c, d:=b+c替换为a:=b+c, d:=a;
• 复制传播: 在复制语句 f:=g后出现的f尽量用g代替;
• 削弱计算强度: 删除x:=x*1这种没有意义的计算, 将x:=y**2这种复杂的乘方计算简化成x:=y*y这种简单的乘法计算;
• 改变计算次序

其中每一步都夹杂着删除死代码

循环的优化:

• 循环展开: 少量的循环展开后可能计算量会更小;
• 代码外提/频度削弱: 将循环内计算的代码提到循环外, 避免每次都计算一遍;
• 削弱计算强度: 比如用加法代替乘法, 比如在循环中需要每次获取数组元素的地址t=i*4, 那么就可以在循环外设置变量t=0, 循环内的计算则为t=t+4;
• 删除归纳变量: 依旧是上述例子, 每次循环会有一个变量i, 称之为基本归纳变量, t则称为与i同族的归纳变量. 假定循环条件为i<10, 可以删除i, 同时将条件修改为t<40

总而言之, 就是尽量避免重复计算用更少的计算, 更少的语句达到同样的效果