编译原理

概览

机器语言 ---> 汇编语言(助记符 MOV...) ---> 高级语言（不依赖于特定机器）

机器语言 --- > 汇编语言或高级语言的过程 ：

编译系统的结构

image-20210830163918375

语义分析(Semantic Analysis)

语义：中间表示，独立于表示语言

编译器的结构

image-20210830164732319

结构

词法分析器

主要任务：从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元（Token）形式

image-20210830165359571

举个例子

image-20210830165538515

😃 如何实现词法分析器？

语法分析

从词法分析器输出的token序列中识别出各类短语，并构造语法分析树(parse tree)

举个例子

image-20210830170121279

语义分析

主要任务：

1. 收集标识符的属性信息

• 种属Kind：简单变量、复合变量、过程
• 类型Type: 整型、字符型...
• 存储位置、长度
• 值
• 作用域
• 参数和返回值信息

符号表：用于存放标识符的属性信息的数据结构

2. 语义检查
   • 变量或过程未经声明就使用
   • 变量或过程名重复声明
   • 运算分量类型不匹配
   • 操作符和操作数之间的类型不匹配
     • 数组下表不是整数...
     • .....

中间代码生成和编译器后端

三地址码(Three-address Code)

​ 由类似汇编的指令序列组成，每个指令最多由三个操作数(operand)

常用的三地址指令

image-20210830171023260

三地址指令的四元式表示

image-20210830171111052

举个例子

image-20210830172102677

语法结构树/语法树（Syntax Tree）

语言及其文法

基本概念

字母表：一个有穷符号集合

乘积、n次幂、正闭包、克林闭包

串：字母表中符号的有穷序列（空串的长度为0）

连接（connection）：y附加到x后面形成的串，xy

空串是连接运算的单位元

image-20210830172522935

串s的n次幂：将n个s连接起来

文法的定义

文法的形式化定义

image-20210830172924632

Vn 非终结符：用来表示语法成分的符号（“语法变量”）

image-20210830173602635

S：开始符号，表示该文法中最大的语法成分

image-20210830174100349

符号约定

image-20210830174146387

image-20210830174157061

image-20210830174324785

语言的定义

推导Derivations和规约Reductions

image-20210901172339176

image-20210901172605747

image-20210901172850226

归约是推导的逆过程

句型和句子

image-20210901173246838

文法分类

0型文法

image-20211026164131136

0型文法生成的语言是0型语言 L(0)

1型语言

image-20211026164316687

2型文法

上下文无关文法

image-20211026164347199

3型文法

正则文法

image-20211026164600834

联系

逐级的包含关系，0型文法包含域最广

上下文无关文法的语法树

image-20211026164933836

句型的短语

分析树中每一棵自身的边缘 ： 该句型的一个短语
直接短语：子树只有父子两代节点，则子树的边缘叫这个句型的直接短语

直接短语一定是某个产生式的右部
产生式的右部不一定是给定句型的直接短语

二义性文法

一个文法可为某个句子生成多棵分析树，则这个文法是二义性的

词法分析

正则表达式

描述正则语言的更紧凑的方法，按照一定的规则递归构建

image-20211026165918119

可以用正则表达式定义的语言叫正则语言或者正则集合

代数规律

image-20211026170108127

等价性

image-20211026170141425

正则定义

image-20211026170231330

提供了类似Alias之类的东西

例子

image-20211026170424415

有穷自动机

Finite Automata

具有离散的输入输出信息和有穷数目的内部状态。根据当前的状态和面临的输入信息可以决定系统的后继行为（电梯装置）

image-20211026170802603

image-20211026170828588

如果存在一个对应于输入串x的从初始状态到某个终止状态的转换序列，称串x被该FA接受

一个有穷自动机M接受的所有串构成的集合是该FA定义的语言 L(M)

最长子串匹配

输入串的多个前缀与一个或者多个模式匹配时，总是选择最长前缀进行匹配
到达某个终止状态后，只要输入带还有符号，FA就继续前进，寻找尽可能长的匹配

分类

• 确定的FA DFA
• 非确定的FA NFA

DFA

image-20211027143046811

DFA 可以用转换图或者转换表表示

image-20211027143449774

NFA

沿着标记a 的边能达到的状态的集合（不是单一的）

image-20211027143523033

image-20211027143734974

等价性

对于任何NFA 都存在识别同一语言的DFA
对于任何NFA 都存在识别同意语言的NFA

$$\mathrm{正}\mathrm{则}\mathrm{文}\mathrm{法}⟺\mathrm{正}\mathrm{则}\mathrm{表}\mathrm{达}\mathrm{式}⟺FA$$

带有空边的NFA

image-20211027144532929

与不带空边NFA的等价性

image-20211027144650234

正则表达式 -> DFA

$$\mathrm{正}\mathrm{则}\mathrm{表}\mathrm{达}\mathrm{式}\stackrel{NFA}{\to }DFA$$

正则表达式 -> NFA

不同的正则表达式对应的NFA类型

image-20211027145312770

NFA -> DFA

image-20211027145543629

image-20211027150323489

$$\varepsilon-closure(s)$$： 能够从NFA状态s开始只通过$$\varepsilon$$转换到达NFA状态集合 ### 识别标识符的DFA  转换  整合多个DFA为一个DFA  ### 词法分析阶段的错误处理 * 单词拼写错误 int i = 0x3G * 非法字符 ~ @ 如果当前状态与当前输入符号在转换表对应项中的信息为空，则报错，调用错误处理程序 * 查找已扫描字符串中的最后一个对应于某终态的字符 * 找到了，将该字符与前面的字符识别成一个单词。输入指针退回到该字符，扫描器重新回到初始状态 * 没找到，说明出错，采用错误恢复策略 **恐慌模式** 在剩余的输入中不断删除字符，直到词法分析器能在剩余输入的开头发现一个正确的字符为止 ## 自顶至下分析 ### First和Follow集 #### 计算FIRST **First(X)**：可以从X推导出的所有**串首终结符**构成的集合，如果X能推到出e，则e∈FIRST(X)  计算方式： * 计算一个符号的FIRST  * 计算符号串的FISTR  #### 计算终结符的FOLLOW FOLLOW(A) : 可能在某个句型中紧跟在A后边的终结符a的集合，如果A是某个矩形的最右符号，则把$添加到FOLLOW(A)中  一个终结符的follow集可能依赖于另一个终结符的follow集  算法：  **注意要迭代更新哦！！！** #### 计算SELECT集合 定义  计算  #### LL(1)文法  $$SELECT(A \rightarrow \alpha) \cap SELECT(A \rightarrow \beta) = \phi $$

其中alpha 和beta不能同时 $$\xRightarrow * \varepsilon$$

注意第一条 ----> α和β的SELECT集就不会相交了

第三条意义：同一非终结符的各个产生式的可选集不相交

• L：从左向右扫描输入
• L：产生最左推导
• 1：每一步只需要向前看一个输入符号来决定语法分析动作

递归的预测分析法

在预测下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式的选择

为每一个非终结符都要编写递归的下降过程

非递归的预测分析法

根据预测分析表构造一个自动机 （表驱动的预测分析）

下推自动机PDA。DFA不能识别下面的例子

image-20211027155042904

image-20211027155343212

image-20211027155414682

image-20211027155533916

总结

image-20211027155712340

预测分析中的错误处理

• 栈顶非终结符和当前输入符号不匹配
• 栈顶非终结符与当前输入符号在一蹙额分析表对应项中的信息为空

采用恐慌模式：忽略输入中的一些符号，知道输入中出现由设计者选定的同步词法单元集合中的某个词法单元

例子

image-20211027160145284

image-20211027160429586

自底向上分析

以消除剩余输入为主

image-20211027161701527

image-20211027161927887

一有匹配就归约（以刚进来的为准）

失败情况

image-20211027162628334

< IDS >,ib 没有进行规约，错误的识别了句柄

句柄：句型的最左直接短语

LR分析法

image-20211027163000350

基本原理

image-20211027163142562

状态堆栈 + 输入符号堆栈 + 缓冲符号栈

image-20211027164920571

image-20211027164749977

LR(0)

image-20211027165127289

增广文法

image-20211027165227328

image-20211027165405765

image-20211027170026739

分析表构造

closure函数

image-20211027170944130

image-20211027171011018

goto函数

image-20211027171028416

image-20211027171047696

image-20211027170912641

image-20211027171131963

移入/归约冲突

image-20211027171227654

归约归约冲突

image-20211027171319095

不是所有的CFG上下文无关文法都能用LR0方法进行分析，CFG不总是LR0文法

SLR分析

FOLLOW集帮助判定什么时候规约，SLR（1）：向前查看一个符号

image-20211103095603535

image-20211103095819326

image-20211103095927692

LR（1）分析

SLR分析存在的问题

• 仅仅简单考察下一个输入符号是否属于规约项目的FOLLOW集，但不能确保正确的规约

image-20211103100100103

image-20211103100320722