编译原理笔记

https://www.cnblogs.com/MRJ1/p/11599465.html

高级语言一般特性

字母表

字母表是符号的非空有穷集合；符号是一个抽象实体。任 何程序语言都有自己的字母表。 计算机语言：由符号“0”和“1”组成的字母表: ∑={0，1}，即01码 C语言字母表： ∑={A~Z, a~z, 0~9, +, -, *, /, <, =,>,_,&,^,~ ,,:,‘,”,;，.，?, (, ),{,}, [, ],空格,!,#,% } ※通常用符号Σ表示字母表。

符号串

由字母表中的符号所组成的的任何有穷序列 被称之为该字母表上的符号串,也称作“字”或“句子”。 (1)ε是∑上的一个符号串 (2)若x是∑上的符号串，而a是∑的元素,则xa 是∑上的符号串 (3)w是∑上的符号串,当且仅当它由(1)和(2) 导出 设s是符号串，

前 缀：移走s的尾部的零个或多于零个符号所得字串

后 缀：删去s的头部的零个或多于零个符号所得字串

子 串: 从s中删去一个前缀和一个后缀所得字串 真前缀、真后缀和真子串：不是s和ε的前缀、后缀和子串

子序列: 从s中删去零个或多于零个符号(不要求是连续)

逆 转：将S中的符号按相反次序写出而得到的符号串。

长 度：是符号串中符号的数目。例如|aab|=3,|ε|=0

语 言：确定字符表上字符串的集合 字符表上所有字符串的集合为最大，记为∑*

---例子---

(符号串s=banana) 前 缀：ε,b,ba,ban,bana,banan,banana

后 缀：banana,anana,nana,ana,na,a,ε

子 串: banana,anana,banan,anan,…,ε

真前缀，真后缀，真子串: x≠sx ≠ ε

子序列: baa(这些符号不要求是连续的)

逆 转(用SR表示)：ananab

长 度：|banana|=6

※“空串”是在Σ字母表上的唯一的长度为0的字符串，并通常被指示为ε（或λ），称为空白符，也可以作为终结符，做N次幂仍为本身。

※符号串运算

1.连接：x和y是符号串，连接xy就是把符号串y写在符号串x的之后得到的符号串。因此是遵循交换律的，即分前后顺序，xy和yx是不一样的。

例如x=ba,y=nana,xy=banana. εx=xε=ba

2.方幂：x^0=ε x^1=x x^2=xx … x^n=xn-1 x(x^n=xxn-1)

例如x=ba x1=ba x2=baba x3=bababa,…

※符号串集合（语言集合）运算

(设语言L={A_Z,az} D={0~9})

1. 合并：L∪M＝{s|s∈Lor s∈M} L∪D ={A_Z,az,0~9}
2. 连接：LM＝{st|s∈Land t∈M} LD 所有一字符一数字构成字串的集合（依然是有顺序的）
3. 方幂：L^0 = {ε} L^1＝L … L^n＝L(n-1)L L4 所有的四个字母的符号串构的集合
4. 语言L的Kleene闭包，记作L* L*＝L0∪L1∪L2∪L3∪…
5. 语言L的正闭包，记作L+(L+＝LL*) L+＝L1∪L2∪L3∪L4∪… L(L∪D)* C语言标识符定义 D+ 所有长度大于等于1的数字串构成的集合 奇数个0和奇数个1构成的二进制串

什么是闭包

V是一个符号集合，假设V指的是三个符号a, b, c的集合，记百为 V = {a, b, c } V* 读作“V的闭包”，它的数学定义是V自身的任意度多次自身连接（乘法）运算的积，也是一个集合。

也就是说，用V中的任意符号进行任意多次（包括0次）连接，得到的符号串，都是V*这个集合中的元知素。

0次连接道的结果是不含任何符号的空串，记为 ε 1次连接就是回只有一个符号的符号串，比答如，a，b， c 2次连接是两个符号构成的符号串，比如，aa, ab, ac, ba, bb, bc,等等 …… n次连接是一个长度为n、由a、b、c三个符号构成的符号串，比如abaacbbac……

因此，V*包含一切由a,b,c三个符号连接而成的、任意长度的符号串（以及空串ε）

追问

那如果题目中没给V包含什么，那是包含终结符号还是非终结符号？

追答

一般说来，Vt表示终结符集合，Vn表示非终结符集合，V表示文法符号集合（即既包含终结符，也包含非终结符）

文法和语言

1.文法和语言的总结

（1）文法的直观概念

人们无法列出全部句子，但人们可给出一些规则来组成句子结构。汉语句子可以由主语后随谓语而成，构成谓语的是动词和直接宾语，采用第一章的EBNF来表示这种构成规则。

（2）符号和符号串

字母表：符号的非空有限集合，典型的符号是字母、数字、各种标点和运算符等。

符号串：由字母表中的符号组成的任何有穷序列称为符号串.,允许有空符号串,用E表示,其长度为0,即|E|=0.

（3）文法和语言的形式定义

文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。 　　**任何一个文法都可以表示为一个四元组G=(VN,VT,P,S)。**其中： 　　VN是一个非空的有限集合，它的每个元素称为非终结符号。 　　VT是一个非空的有限集合，每个元素称为终结符号。 　　P是一个非空的有限集合，它的每个元素称为产生式。P是有穷非空的规则(产生式)集合，规则形如：A→α，其中A∈VN，α∈(VT∪VN)*,且开始符号S至少必须在P中的规则左部出现一次。 　　S是一个特殊的非终结符号，称为文法的开始符号，S∈VN 。

Chomsky文法分类 0123型文法 文法的类型

0型文法/无限制文法：α->β，其中α∈(Vn∪Vt)*且至少含有一个非终结符，β∈(Vn∪Vt)*。理解：推出前可以是至少包含一个非终结符的任意闭包中的串（显然不包括空串？），推出后的可以是闭包中任何的串（空串？）

1型文法/上下文有关文法：αAβ->αuβ，其中A∈Vn，α,β∈(Vn∪Vt)*，u∈(Vn∪Vt)+。

2型文法/上下文无关文法：A->β，其中A∈Vn，β∈(Vn∪Vt)*。常用于句法分析。理解：推导前是个非终结符，推导后是闭包中的任何串

3型文法/正规文法：常用于词法分析。

判断文法类型

3型文法遵循规范：

1. 左边必须只有一个字符，且必须是非终结符；
2. 其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。
3. 对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。反之亦然，要么，就全是：非终结符＋终结符。

再看2型文法如何判断：

1. 与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
2. 2型文法所有产生式的右边可以含有若干有限个终结符和非终结符（只要是有限的就行，没有个数限制）。

再看1型文法如何判断： 第一点：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。 第二点：与2型文法第二点相同。

最后是0型文法，这个就不用看了，只要你能描述出来，都属于这个类型，即0型。

直接推导和推导

*推导是有目的性的，即最终生成式是什么。根据生成式来选择文法中的规则，例如有或符号“|”的地方。

总结一些概念

文法 根据概念，任何一个文法都可以用一个四元组来表示。 句型 由开始符号推导出的是句型 句子 只包含终结符的句型是句子 语言 是所有句子的集合

语言

设文法G＝(VT,VN,S,P)。如果S*推导α,则称α是一个句型。仅含终结符号的句型是一个句子。语言L(G)是 由文法G产生的所有句子 所组成的集合： L(G) = {α| S*推导α,且α(的每个符号？)∈VT

最左推导和最右推导

最左推导：如果a =>β，并且在每“一步推导”中，都替换α中最左边的非终结符号，则称这样的推导为最左推导。 即任何一步都是对最左非终结符替换，对应最右规约

最右推导：如果a =>β，并且在每“一步推导”中，都替换α中最右边的非终结符号，则称这样的推导为最右推导。也称作规范推导，对应最左规约。

二义性：如果一个文法的某个句子有不止一棵分析树，则这个句子是二义性的句子。 含有二义性句子的文法是二义性的文法。

有部分语言不存在无二义性的文法，这样的语言称为二义性的语言，二义性问题是不可判定的。

句型分析

短语：是句型中的某个非终结符所能推出的符号串。

直接短语：不能再推导出其他式子的符号串

句柄：最左的直接短语。

分析树

定义 每个结点的标记是Vt Vn 或 空串 中的符号 根结点标记为S（开始符号） 如果是内部结点，则标记必在Vn中（还能继续化成终结符和非终结符）

语法分析树不唯一，具体问题具体分析。

分析树不描述推导过程，对于同一个句子的多种推导（前提是文法无二义性），则画出的分析树应该是一样的。

子树

一个结点和他的所有后代结点以及边

如何用子树解释短语、直接短语、句柄（见自底向上语法分析）

词法分析

主要任务

1. 词法分析的主要任务：
2. 从左至右逐个字符地对源程序进行扫描，产生一个一个单词符号；
3. 滤掉空格，跳过注释、换行符； 追踪换行标志，复制出错源程序

词法分析器概要设计

输入、预处理

单词符号的识别：超前搜索 需要超前搜索才能确定基本字

1. 基本字识别
2. 标识符识别
3. 常数识别
4. 算符和界符的识别

状态转换图

1 概念

• 状态转换图是一张有限方向图

• 结点代表状态，用圆圈表示

• 状态之间用箭弧连结，箭弧上的标记(字符)代表 射出结状态下可能出现的输入字符或字符类

• 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态

左线性文法 G（Z）

形如Q→Rt或Q→t，有非终结符则在左边

文法的字汇表中不包含符号S，即开始状态

左线性文法需要一个初始状态F，终态（起始符号）用双圈表示； 初始状态需要标明；

可以先从Z（终态）画起，箭头倒置（如：U →Z1∣1，箭头全部指向U，连线上是1） 分析过程自下而上规约；

右线性文法 G（S）

形如Q→tR或Q→t，有非终结符则在右边

不包含符号Z，即终止符号

右线性文法需要一个终结状态F，双圈表示；

初始状态需要标明；

转换很简单，直接可以看出；

分析过程自上而下推导；

总结：左线性文法的右边非终结符在前，终结符在后。从终态反推，输入是终结符，推出非终结符。文法中有终态F，需要自己构造初态S。右线性文法反之。右线性文法的过程更符合人的习惯，即自上而下自左向右。

G[Z](左线性)： Z→Cb C→Bb| b B→Ab A→a| Ba

G[Z](右线性)： S→aA|bC A→bB B→bC|bA C→bZ

确定的有限自动机DFA(Deterministic finite automata, DFA)

M是一个五元组M =（S，∑，δ ，S0 ，F )

(1) S：有穷 是一个非空有限集，状态集，每个元素称为一个状态

(2)∑是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表

(3)δ是状态转换函数，是在S×å→S上的单值映射

(4) s0 s0∈S，是唯一初态

(5) F F⊆ S，可空,是一个终态集,终态也称可接受状态或结束状态

3.2 一个NFA M是五元式 M=(S,S,δ,S0,F)非确定的FA (Nondeterministic finite automata, NFA)

（1）S 有穷非空状态集合

（2）∑ 有穷的输入字母表集合

（3）δ 从S´∑*到S的子集的映射

（4）开始状态 (或初始状态)，s0∈S,S是的非空子集，称为初始状态集合

（5）F F⊆S，是S的子集(可空),称为终止状态集合

正则式转换为NFA

正则表达式三种基本运算:

1. 连接(Concatenation), 例如 abc, 由a, b, c组成

2. 联合(Union), 例如 a|b|c, 表示a或者b或者c

3. Kleene闭包(Kleene ), 例如 (ab), 表示ab串不出现，或者出现1次或1次以上

其它的运算如+, {}等都可以用以上三种基本运算或者运算的组合来表示。

NFA转化DFA

https://www.jianshu.com/p/de84d27264cc

3个概念： 运用子集法的3个概念： (1)状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合，定义为状态集I的ε -闭包，表示为

ε -closure()

不要忘记自己经过ε还是本身，所以该状态的闭包包含自己

(2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合，定义为状态集1的a弧转换，表示为

move(l,a)

求的时候无视途径的空串，只看第一个经过的a

(3)状态集的a弧转换的闭包a

lg= ε-closure(move(l,a))

一般步骤：

1. 构造转换表

I	I a	I b

第一列第一行为初态的闭包，之后的规则是：

I	I a	I b
初态的闭包	ε-closure(move(l,a))	ε-closure(move(l,b))
l	ε-closure(move(l,a))	ε-closure(move(l,b))
……

有新的集合就写到最左边，直到没有新集合生成

2. 新的终态的判断方法就是所有包含原来终态的集合都是终态，用双圈代表终态；

3. 新的初态就是包含原来初态的集合就为初态，例如原来初态为0，所以包含0的集合就为初态

4. 将转换表改为如下形式：

S	a	b
0	1	4
1	3	2

这样的转换表，第一列为整理后的新状态

FA的最小化（分割法）

目标：寻求最小状态NFA

最小状态DFA的特征:

1.没有多余状态(死状态) 什么是多余状态？

从这个状态没有通路到达终态；

从开始状态出发，任何输入串也不能到达的那个状态。

如何消除多余状态？ 删除

两个都是无关状态

2.没有两个状态是互相等价（不可区别）

两个状态s和t等价的充要条件：

兼容性（一致性）条件——同是终态或同是非终态
传播性（蔓延性）条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里

一般步骤：

1. 首次划分将状态分成终态和非终态，即：将DFA的状态集进行初始化，分成Π=(Z,S-Z) S为总状态集，Z为终态集

2. 可以先对非终态集分析，用下面的过程对Π构造新的划分Π new

for (Π中每个组G) do //每个组都是一个状态集
begin
把G划分成小组，G中的任意两个状态Si和Sj在同一组中，当且仅当对于Σ中任意输入符号a ，Si和Sj的a转换是到同一组中，move(Si,a) ∈Gi ，move(Sj,a) ∈Gi。这样，只要Si和Sj的a转换是到不同的组中，则说明Si和Sj是可区别的，可进行划分。在Π new中用刚完成的对G的划分代替原来的G。
end ; 
Π := Π new；

3. 重复执行(2)，直到Π中每个状态集不能再划分(Π new= Π)为止;
4. 合并等价状态 ,在每个G中，取任意状态作为代表，删去其它状态;
5. 删去无关状态，从其它状态到无关状态的转换都成为无定义。

自上而下的LL（1）语法分析

计算FIRST集 终结首符集

不断运用以下规则直到没有新的终结符或者空串ε可以加入任何一个First集为止

两种情况，First（X）

x是终结符：first（x）=

x是非终结符：有X→Y1Y2Y3……Yi，将Y1的first集中的终结符加入到First（X）中。此时如果Y1的first集中有空串，则Y2的first中的终结符也可以加入到X的first集合中，依此类推，如果Y1到Yi所有的First集合中都有空串，就都可以加入X的first集。 如果X存在空产生式，空串也可以加入X的first集。

总结以上规则： 产生式右边的最左的非终结符的first集里如果没有ε，那么产生式左边的first集就与之相等；如果有，就将其非ε元素置入first集合并且计算下一个符号。以此类推，遇没有ε就停止。但是若所有都包含ε，ε也要加入first集中。

计算FOLLOW集

原文链接：https://blog.csdn.net/weixin_44142279/article/details/89365277

将右端结束标记 $ 放到FOLLOW(S)中，S是开始符号。

按下面的两个规则不断迭代，直到没有新的终结符或者是ε加入。

①如果存在产生式A->αBβ，那么FIRST(β)-{ε}【表示除了ε之外的符号】的符号都在FOLLOW(B)中。

②如果存在产生式A->αB，或者A->αBβ且FIRST(β)包含ε，那么FOLLOW(A)中所有符号都加入到FOLLOW(B)中。

如：对于产生式 A -> BC，求FOLLOW(B).

① FOLLOW(B) += FIRST© - {ε},
② 如果 ε ∈ FIRST©，FOLLOW(B) += FOLLOW(A)
③ FOLLOW(B) = ① + ②

①在产生式的右边找非终结符，如果求FOLLOW（A），则找右边含有A的产生式 ②看后面的串 follow集中一定没有空串

FIRST集合和FOLLOW集合的区别

①FIRST集合 集合元素是终结符和ε。

②FOLLOW集合 集合元素是终结符。

③求FOLLOW集合之前要先求FIRST集合。

注意：求first本质是对符号串

构造预测分析表

参考链接：https://blog.csdn.net/Jane_96/article/details/79897944

先求非终结符的first和follow集

列号为终结符，行号为非终结符构建表格。看文法的每一个产生式，一行一行按如下规则填表：

对于文法G的每个产生式A -> α ，进行如下处理：

1. 对于FIRST(α)中的每个终结符号a，将A -> α加入到M[A , a]中。

2. 如果 ε 在FIRST(α) 中，那么对于FOLLOW(A)中的每个终结符号b，将A -> α加入到M[A , b]中。如果 ε 在FIRST(α) 中，且$在FOLLOW(A)中，也将A -> α加入到M[A , $]中。 在完成上面的操作之后，如果没有M[A , a]中没有产生式，那么将M[A , a]设置为error(我们通常采用一个空条目表示)

对α求first集即对产生式右边的符号串求first集，和求左边一样，而不是求并集的意思

LL（1）分析过程

消除左递归

作者：Yinvoker 链接：https://www.jianshu.com/p/875a0f519ef3

什么是左递归？

立即左递归： A ——> Aα | β

非立即左递归： 1）A→aB 2）A→Bb 3）B→Ac 4）B→d

如果一个文法中有一个非终结符号A使得对某个串α存在一个推导A=》Aα，那么这个文法就是左递归的。递归分为立即左递归和非立即左递归。立即左递归单步即可看出来，非立即左递归 举个例子：

将A ——> Aα | β 转换为

A ——> β A' 
A' ——> α A'|ε

原文法（保证β不含P）：

P→Pα1∣Pα2∣Pα3∣...∣Pαn∣β1∣β2∣β3∣...∣βn

消除后文法：

P→β1​P′∣β2​P′∣β3​P′∣...∣βn​P′
P′→α1​P′∣α2​P′∣α3​P′∣...∣αn​P′∣ϵ

注意：最后需要删除多余的规则

提取左公因子

什么是左公因子？

——和数学中的公因子含义相同，就是公共的因子，而左公因子就是最左边的公因子。

例如：

S → aB1|aB2|aB3|aB4|...|aBn|y

可以看出前n项拥有一个共同的左公因子：a，所以可以把他提取出来。

S → aS'|y
S'→ B1|B2|B3|...|Bn

自底向上分析

短语

利用子树求 短语，直接短语，句柄，素短语，最左素短语

1. 画出语法分析树

2. 拆出所有子树（有几个根节点就有几棵）

3. 所有的子树的叶子写成式子就是短语

4. 共只有两层（含根结点）的子树为直接短语，最左边的为句柄（最左直接短语）。

进一步分出素短语和最左素短语：

5. 素短语 定义： 是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语

6. 最左素短语 定义： 最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。语法树： 通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。

7. 先找出所有素短语（包含一个或更多终结符的短语），注意素短语中不能有更小的素短语

最右推导

最右推导：在推导的任何一步α→β，其中α、β是句型，都是对α中的最右非终结符进行替换最右推导被称为规范推导。 由规范推导所得的句型称为规范句型

自底向上的分析 LR(0)分析表

链接：https://www.jianshu.com/p/dd89025f95c1

LR分析表的结构：其分为两个部分Action Goto

Action

两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）

移入j：j是一个状态，把j压入栈（同时移入a）
归约A->B：把栈顶的B归约到A（并根据Goto表项压入新状态）
接受：接受输入，完成分析
报错：在输入中发现语法错误

Goto

Goto[i,A]=j

LR(0)分析表构造过程

原文链接：https://blog.csdn.net/scottwei_007/article/details/90244531

1.文法扩充。把带有或符号的合并的产生式拆成两个。如果有两个入口时（起始状态对应两个产生式），需要增加一个新产生式A'->A

2.在E’->.E右部开头加上点号，看小圆点后字符是否为非终结符，是，将左部为该非终结符的文法加入其中,并为其添加小圆点；反之直接跳过本步骤直接进行下一步。（I0变成E’->.E E->.aA E->.bB）

对I项目中的文法进行分析，若小圆点在最后，则不做处理，该状态没有射出；若小圆点不在最后，则将根据每个文法的小圆点后的字符来开辟出新的I项目，该文法为新项目的首句文法

I0的文法进行开辟，I0不变，生成I1、I2和I3
I1：E’>.E
I2:E->.aA
I3:E->.bB

然后将新开辟项目的文法小圆点向后移一位，并将小圆点越过的终结符或非终结符标记在射出的有向线上。

I1：E’>E.
I2:E->a.A
I3:E->b.B
(注：若开辟的项目和重复，则不开辟新的项目，再次利用已存在的项目,射出线指向该已存在的项目）

对开辟的项目重复3-4步骤，直到不再有项目开辟

最终的项目有向图有以下特征：

1. 没有重复的项目
2. 每个项目（除了初始项目）的首句产生式的点号不在第一位，其他新加入的文法产生式的点号都在第一位
3. 起始状态0没有入射，射出应当有若干终结符或非终结符

按照以下规则构建分析表：

1. 起始状态标记为0
2. 既有入射也有射出的状态标记为移进si
3. 只有入射没有出射的状态标记为规约ri
4. 填表：填入M（A，a）。当输入（有向线上标记的符号）为终结符时，填入action表；为非终结符时，填入goto表

三元式

三元式是把表达式及语句表示成一组三元式，每个三元式由运算符op，运算对象arg1，运算对象2arg2组成，形如(op,arg1,arg2)

举例： a:=bc+bd

(1) (* b,c)

(2) (* b,d)

(3) (+ (1),(2))

(4) (:= (3),a)

四元式

四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。

四元式实际上是一种“三地址语句”的等价表示。它的一般形式为：

(op,arg1,arg2,result)

其中，op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：

result ∶= arg1 op arg2

需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列

T1∶=B*C

T2∶=A+T1

其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，即result∶=op arg1或 op result ；对应的一般形式为：

(op,arg1,,result)

或

(op,,,result)

四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG@及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a∶=bc+bd的四元式表示如下： （1）（，　b，　c，　t1） （2）（，　b，　d，　t2） （3）（+， t1， t2， t3） （4）（∶=，t3， －， a） 四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。 有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成： （1）t1∶=bc （2）t2∶=bd （3）t3∶=t1+t2 （4）a∶=t3 把（jump，－，－，L）写成goto L 把（jrop，B，C，L）写成if B rop C goto L

如何写出以上式子

先写出波兰式可以得到运算顺序，波兰式中算符出现的顺序就是三元式和四元式中的运算顺序，有多少算符，就有几行式子。

---

三元式

每一行为(op,arg1,arg2)，最前面标上序列号，出题的时候如果说当前序列号是100，那你的答案应该从100开始，不是1，下面四元式也是一样。两个arg按照从左向右读填写。

四元式

每一行为(op,arg1,arg2,result)，最前面标上序列号，出题的时候如果说当前序列号是100，那你的答案应该从100开始，不是1。两个arg按照从左向右读填写。和三元式的区别是，每一行得到的结果都写进result，下一行如果需要用到前面的结果，只需要调用result就可以，而不是前面的序列号。

例如： A + B * ( C -D ) + E / ( C -D ) ^N

逆波兰: A B C D -* + E C D –N ^ / +

四元式:

(1)  ( - C     D     T1)
(2)  (  *   B    T1    T2)
(3)  (  +   A    T2   T3)
(4)  (  - C     D     T4)
(5)  ( ^   T4    N    T5)
(6)  (  /    E    T5   T6)
(7)  (  +  T3   T6   T7)

三元式:

(1)   ( - C     D      )
(2)   (  *     B     (1)   ) 
(3)   (  +    A     (2)   ) 
(4)   (  - C       D    ) 
(5)   (  ^    (4)    N    ) 
(6)   (  /      E     (5)  ) 
(7)   (  +     (3)   (6)  ) 

典型语句翻译示例

四元式形式: t := arg1 op arg2

四元式的标准形式是(op,arg1,arg2,result)，做题时先分析写成赋值代码形式，然后按照规范写成标准四元式

规则

例子：

四元式是一种比较普遍采用的中间代码形式。

代码段的四元式表达式：

101 T:=0 （表达式为假的出口）

103 T:=1 （表达式为真的出口）

因为用户的表达式只有一个A<B，因此A<B的真假出口就是表达式的真假出口，所以

100: if a<b goto 103 （a<b为真，跳到真出口103）

101: T:=0（否则，进入假出口）

102: goto 104 （要跳过真出口，否则T的值不就又进入真出口了，为真）

103: T:=1

104:（程序继续执行）

参数传递方式

1. 传地址（间接访问，操作的是地址所以实时修改实参）

所谓传地址就是把实参的地址传递给相应的形参。在过程中每个形参对应一个单元，称为形式单元。形式单元用来存放相应的实参地址。当调用一个过程时，调用段必须预先把实参的地址传递到一个被调用段可以得到的地方。如果实参是一个变量(包括下标变量)，则直接传递它的地址。如果实参是常数或者其它表达式（如A+B）就先计算它的值并存放在某一临时单元中。然后传递这个临时单元的地址，当程序转入被调用段之后，被调用段首先把实参地址抄进自己相应的形式单元中，过程体对形参的任何赋值都被处理成对形式单元的间接访问（即对形势单元中存储的实参地址对实参进行访问）。这样，当被调用段的工作完毕进行返回时，实参单元已经持有所期望的值。

2. 得结果（直接访问内部形参，最后返回给外部实参）

和传地址相似但不等价的另一种传值方式是传结果。这种方法的实质是形参具有两个单元。第一个单元存放的实参的地址。第二个单元存放的实参的值，在过程中对形参的任何引用和赋值看成是对它的第二个单元的直接访问。但是在调用返回之前必须把第二个单元的值存放到第一个单元指示的地址中。

3. 传值（抄写实参到形参，之后仅调用形参）

传值是一种最简单的参数传递方法。调用段把实参的值计算出来并存放在被调用段可以获得的地方。被调用段开始工作时，将这个值拷贝到自己相应的形式单元中，就像使用局部名一样使用这些形式单元，即形参是如同一种先从实参获得初值的局部变量，获得初值后就没有联系了。这点与传地址不同。

4. 传名

传名是ALGOL语言定义的一种特殊形式的形参结合方式。使用替换规则解释传名的参数的意义。过程调用的作用相当于把被调用的过程体抄到调用出现的地方，但把其中任何一个出现的形参都替换成相应的实参（文字替换）。如果在替换过程中出现了和局部变量相同的标志符，则使用不同的标识替换。

在进入被调用段的之前不对实参预先进行计值， 而是让过程体中每当使用到相应的形参时才逐次 对它实行计值（或计算地址）。由此，通常视实 参为一个子程序（称为参数子程序），每当过程体中使用到相应的形参时就调用这个子程序

总结

传值不影响实参，因为是使用实参的拷贝。

对于传地址和传结果，他们的区别在于：

传地址是实时改变实参的值，也就是被调用段（函数）中每次执行对形参的赋值操作时，实参都会相应地被改变。

传结果是最后返回时改变实参的值，也就是被调用段的所有操作执行完后，按照从左到右的次序将形参的值写入实参。换句话说，如果形参中有相同的值，那么只有最后一个才是最终实参的值，之前的会被覆盖掉。

对于传地址和传名，他们的区别在于：

传地址在实参地址传入形参时，需要预先计值，因此虽然实参被实时改变，但形参预计的值不变，被调用时的值不受其他形参运算的影响。

传名不对实参预先计值，只有使用时计值，所以被调用段中对实参的改变有可能影响后续形参在计算中的值。

因此，又根据传名本质上是直接替换了程序体中的参数名，所以也可以认为是一个将被调用段耦合进程序体中、仅包含实参的程序段，因此同一个参数名的值在不同位置有变化就可以理解了。

局部优化

基本块是什么

基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句（第一个语句）和一个出口语句（最后一个语句）

对于一个基本块来说，执行时只能从其入口语句进入，从其出口语句退出

语句
出口语句	任何控制转移四元式
入口语句	所转向的目标语句

划分基本块

1、求四元式序列中各个基本块的入口语句的规则

① 程序的第一个语句
② 能由条件或无条件转移语句转移到的语句
③ 紧跟在条件转移语句后面的语句

2、对每一入口语句，构造所属的基本块，该基本块由：

1）该入口语句到下一入口语句（不包括下一入口语句）之间的语句序列组成
2）该入口语句到一转移语句（包括该转移语句）之间的语句序列组成
3）该入口语句到一停语句（包括该停语句）之间的语句序列组成

3、凡是未包含在某一基本块中的语句，都是程序中控制流程不可达的语句，可删除它们。

控制流图

原文链接：https://blog.csdn.net/qq_40147863/article/details/93376991

定义： 以基本块为结点，控制程序流向作为有向边，画出的有向图称为流图。

特点：

具有唯一首结点的有向图
从首结点开始到流图中任何结点都有通路

如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点

程序控制流程流图的表示

一个控制流程图可表示成一个三元组： G=(N，E，n0 )

N：所有结点(基本块)集； E：所有有向边集； n0 ：首结点。

有向边：

当下述条件有一个成立时，从结点i有一有向边引向结点 j：

① 基本块 j 在程序的位置紧跟在i后，且 i 的出口语句不是无条件转移或停语句
② i 的出口是 goto(S) 或 if goto(S)，而 (S) 是 j 的入口语句

画出的控制流图为一些表示基本块的方块和有向线段，每个方块中填充基本块里的代码，其中：

1. 首结点（没有入射）的第一条语句即为整个程序段的第一条语句

基本块DAG表示

原文链接：https://blog.csdn.net/qq_40147863/article/details/93376991

DAG 图（Directed Acylic Graph）无环路有向图

定义：

(1) 在一个有向图中，若结点 ni 有弧指向结点 nj，则 ni 是 nj 的父结点，nj 是 ni 的子结点；

(2) 若 n1,n2,…,nk 间存在有向弧 n1→n2→…→nk，则称 n1 到 nk 之间存在一条通路，若有 nk=n1，则称该通路为环路；

(3) 若有向图中任意通路都不是环路，则称该图为无环路有向图（DAG）

四元式对应的 DAG 结点形式

按其四元式对应结点的后继个数分成四种类型：0型、1型、2型、3型

解题步骤：

1. 按照四元式序列画出DAG图（注意合并、重用）
2. 根据图重写四元式序列
3. 根据题目对保留某些符号（某些符号在基本块后面还要用）的描述，仅保留这些符号的四元式，如果有不可进一步优化的冗余符号，需单独指出为【临时变量】