提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

编译原理

前言
一、绪论
- 1、编译系统的结构
- 2、编译程序的生成
二、CFG文法
三、词法分析
- 1、词法的输入输出
- 2、词法的正则表达式、正则文法、状态转移图表示
四、自顶向下的句法/语法分析
五、自底向上的语法分析
六、句法制导翻译
七、中间代码生成
九、运行时存储
十一、代码生成
- 指令开销

前言

这是对编译原理课程的重点总结，其中未必全

一、绪论

1、编译系统的结构

编译器

2、编译程序的生成

T形图

自展

移植

注意

：默认拥有的T形图：

B语言

~~B语言~~

A机器

B语言

~~C语言~~

A机器

例题：

二、CFG文法

1、文法的构造

example

2、文法的推导与规约->语法树

举例如下：

推导规约

最左推导对应最右规约，最右推导对应最左规约

短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语

直接/简单短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串

句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列

3、文法的二义性

CFG的二义性

一般来说，程序语言存在无二义性文法，例如条件跳转指令

三、词法分析

1、词法的输入输出

输入源程序，输出单词符号(token：种别-属性值），即：把构成源程序的字符串转换成“等价的”单词序列

根据词法规则识别及组合单词，进行词法检查

对数字常数完成数字字符串到二进制数值的转换

删去空格字符和注释

在这里插入图片描述

2、词法的正则表达式、正则文法、状态转移图表示

标识符文法

根据正则文法构造正则表达式

在这里插入图片描述

四、自顶向下的句法/语法分析

1、自顶向下分析的基本思想

从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。
从树根S开始，构造所给输入符号串的语法树

自顶向下分析面临的问题：

二义性问题：如果一个文法G是二义性的，假设wL(G)且w存在两个最左推导，则在对w进行自顶向下的句法分析时，句法分析程序将无法确定采用w的哪个最左推导——解决办法：改造文法，引入新的文法变量——>例子同 if 的二义性处理

回溯问题：如果A有多个候选式存在公共前缀，则自顶向下的句法分析程序将无法根据当前输入符号准确地选择用于推导的产生式，只能试探。当试探不成功时就需要退回到上一步推导，看A是否还有其它的候选式，这就是回溯(backtracking)——解决方法：提取左因子

左递归引起的无穷推导问题：如果存在推导A -> αAβ，则称文法G是递归的，当α=ε时称之为左递归——解决方法：转换为右递归

2、LL(1)文法

如果G的任意两个具有相同左部的产生式A→α|β满足下列条件：

1. 如果α、β均不能推导出ε，则FIRST(α)∩FIRST(β)=空；

2. α和β至多有一个能推导出ε；

3. 如果β ==> ε，且FIRST(α)∩FOLLOW(A) =空

则称G为LL(1)文法

FIRST、FOLLOW集的构造与利用

FIRST集如下

终结符的FIRST集即为本身

FOLLOW集如下

3、预测分析器（总体结构与构造）

预测分析表

即

LL(1)分析表

构造文法
改造文法：消除二义性、消除左递归、提取左因子
求每个

候选式的FIRST集

和

变量的FOLLOW集
检查是不是 LL(1) 文法

若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”
构造预测分析表
实现预测分析器

一个表构造的例子

4、递归下降分析器

对应每个变量设置一个处理子程序：

A→X1 X2 … Xk … Xn

⑴ 当遇到Xk是终极符号时直接进行匹配;

⑵ 当遇到Xk是语法变量时就调用X对应的处理子程序.
要求处理子程序是可以递归调用的
从文法构造语法图，对每个非终结符A执行如下操作：1. 创建一个开始状态和一个终止状态（返回状态）2. 对每个产生式A→X1X2　… Xn，创建一条从开始状态到终止状态的路径，边上的标记分别为X1，X2，… ，Xn

递归子程序法总体步骤：

构造文法；

改造文法：消除二义性、消除左递归、提取左因子；

求每个候选式的FIRST集和语法变量的FOLLOW集；

检查G是不是 LL(1) 文法，若G不是 LL(1)文法，说明文法G的复杂性超过了自顶向下方法的分析能力，需要附加新的“信息”；

按照LL(1)文法画语法图；

化简语法图；

按照语法图为每个语法变量设置一个子程序。

五、自底向上的语法分析

1、总体概念

思想：从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。
核心：寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法

2、算符优先分析法

优先法

解释

算符

名称起源

算符文法

：如果文法G=（ V，T，P，S）中不存在形如A→αBCβ 的产生式，则称之为算符文法(OG —Operator Grammar)，即：如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。

算符优先文法

：设G=（V，T，P，S）为OG，如果 a,b∈VT, a≡b, a≮b, a≯b 至多有一个成立，则称之为算符优先文法(OPG —Operator Precedence Grammar) ——在无ε产生式的算符文法Ｇ中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法

优先关系

定义：

假设G是一个不含ε-产生式的文法，A、B和C均是G的语法变量，G的任何一对终结符a和b之间的优先关系定义为：

a≡b，当且仅当文法G中含有形如A→…ab…或A→…aBb…的产生式；

a≮b，当且仅当文法G中含有形如A→…aB…的产生式，而且B => +b…或B =>+Cb…；

a≯b，当且仅当文法G中含有形如A→…Bb…的产生式，而且B => +…a或B => +…aC；

a与b无关系，当且仅当a与b在G的任何句型中都不相邻。

关键：优先关系表的构造

3、LR分析法

状态法

：

根据句柄的识别状态（句柄是逐步形成的）

用状态来描述不同时刻下形成的那部分句柄

因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态

例如： S→bBB可分解为如下识别状态

S→.bBB 移进b

S→bB.B 等待归约出B

S→b.BB 等待归约出B

S→bBB. 归约

采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。