↓Skip to main content
A cup of beer
  1. Posts/

编译原理期末复习

·250 words·2 mins
笔记
Table of Contents

General #

陈康肃公善射，当世无双 ，公亦以此自矜。尝射于家圃，有卖油翁释担而立，睨之久而不去。见其发矢十中八九，但微颔之。 康肃问曰：“汝亦知射乎？吾射不亦精乎？”翁曰：“无他， 但手熟尔。”

康肃忿然曰：“尔安敢轻射！”翁曰：“以我酌油知之。”乃取一葫芦置于地，以钱覆其口，徐以杓酌油沥之，自钱孔入，而钱不湿。因曰：“我亦无他，惟手熟尔。”康肃笑而遣之。

image-20220612212809676

编译程序总框 #

image-20220620213332656

消除二义性 #

如果用**同一种推导(最左推导)**一个句子，有不同的推导过程，那就是有二义性的。

ε

短语和句柄 #

短语：一个句型的语法树中所有子树的叶节点所组成的符号串（可以从最靠下的那种总共一层的子树开始，依次往上找总共更多层的）

直接短语：一个句型的语法树中任一高度最小的子树的叶节点所组成的符号串都是该句型的直接短语

句柄：句柄是最左边的直接短语（处在最左边的高度最小的子树的叶结点）

image-20220620213459645

正规式构造NFA #

image-20220620214029489

image-20220620214145118

正规式、正规集的写法 #

  • 字符
    • ‘c’ = {"c"}
  • 空串
    • ε = {""}
    • 注意，空串不是空集。它是一种特殊字符串。
  • 取并
    • A + B = {a|a in A} or {b|b in B}
  • 连接
    • AB = {ab|a in A and b in B}
  • 迭代（连续出现自身）
    • A^*是A的大于等于1次对自身的连接的并。也就是包含了1次（A^1）、2次(A^2）、…各种连接的结果。
    • A^i是指A对自身的i次连接。

提左公因子 #

例如：

image-20220610211103930

其中，产生式T->int和T->int*T具有公共左因子int。

T -> intY|(E)
Y -> ε|*T

同理，E的产生式也有这个问题，所以可以转化为：

E -> TX
X -> ε|+E

也就是把公共左因子的生成单独提出来作为一个产生式。

消除左递归 #

形如S-+>Sa的文法，就称为左递归文法。可以把左递归用右递归来代替（重写为等价的右递归）。根据S->Sa，那么一个S可以产生Sa，Saa，Saaa，…。

对于左递归文法 S->Sα|β，实际上是β后面跟着若干α，那不妨先用β把左边堵上，拆分成S->βS',S'->αS'| ε，也就是先把β拿出来，然后后面再去产生那些α。

一般地，对于推广的左递归文法 S->Sα1|Sα2|...|β1|β2|...，可以拆分成 S->β1S'|β2S'|...,S'->α1S'|α2S'|...| ε。即对于不同的α、β，构成和上述简单拆分相同形式的产生式即可。

间接左递归的消除 #

例如有如下文法。

S->Aα|δ
A->Sβ

因为存在推导 S->Sβα，所以也是左递归文法。只是你第一时间看不出来。

后缀式中间语言 #

后缀式的构成原则（递归定义）

  • 对于单独的标识符或常量，后缀式是其本身。
  • 对于二元操作符op，形如A1opB1被表示为A2B2op。其中A2、B2分别是A1、B1的后缀式。
  • 对于括号操作，例如(A)，那么其后缀式是A的后缀式。（因此可以看出，后缀式无需括号即可实现对任意运算顺序的无歧义表达。）

后缀式运算的代码实现

  • 从左向右扫描后缀式，并维护一个值栈，每次遇到数值就push进去，每次遇到k目运算符就对栈顶的k个值进行计算并替换他们。

中缀式转后缀式的属性文法

  • 这三条产生式对应了后缀式的三条递归定义。
image-20220617174403629
  • 代码实现如下。例如要归约E -> E1 op E2，那么认为现在POST的最大下标下分别已经是E1的后缀式和E2的后缀式了。因为他俩都归约完成了才能轮到这一条进行归约。那么只需要在k处（目前最小空闲下标）处放上op，再更新POST数组目前最小空闲下标k为k+1即可。
E -> E1 op E2	E.code := E1.code||E2.code||op
E -> (E1)	E.code := E1.code
E->id	E.code := id

E -> E1 op E2	|{POST[k]:=op;k:=k+1}
E -> (E1)	|{}
E->id	|{POST[k]:=id;k:=k+1}

有哪几种中间代码优化方式？ #

局部优化（局限在基本块范围）

  • 基于基本块的DAG优化

循环优化（在循环结构范围）

  • 代码外提
  • 强度削弱
  • 删除归纳变量

全局优化（全部代码的范围）

右线性文法转NFA #

所有的状态都是非终结符。

终态是f，代表终结符。

例如A->idB，就是从状态A向状态B引id边。

例如A->id，就是从状态A向终态f引id边。

文法转正规式 #

先把简单的几个产生式翻译成正规式。

复杂的那几个文法就是简单文法的连接而已，把已经翻译好的简单的产生式套进去即可。

不要忘记“|ε”。

右线性文法和左线性文法 #

右线性文法写出NFA后，倒着看NFA，从终态f开始，对于每个状态，依次找其入边来构成新的文法。除了原开始状态外都这么做。

https://blog.csdn.net/Greepex/article/details/80771975

正规式转NFA并进行NFA的确定化和DFA的最小化 #

  • 按照规则自顶向下地逐步对NFA进行展开，从而构造NFA。构造的时候，X是初态，Y是末态。
  • 写出NFA中各状态（包括X、Y）读入一个字符后，相应的可以到达的状态列表。注意不能直接使用ε边，而是要先走一个非ε边，才能使用到达了的状态的射出的ε边。
  • 借助可达状态列表，构造状态聚合表。该表的第一行是针对于开始状态X的ε闭包的，而不是X本身的。
  • 根据可达状态列表重新分配状态编号，可以从0开始，并重新写出新的可达状态列表，这个新的表就是DFA的状态转移表，利用它画出DFA。
  • 根据新的这个状态转移表对DFA的等价状态进行合并。初始化集合为全部的DFA状态，然后对于每个状态，分别看转移表中的各列出边的目的状态，如果该集合内某状态存在某状态转移边的目的状态不属于本集合内的状态的，就把该状态转移边的出发状态从该集合中划分出去。反复做直到不存在可以划分出去的边。

LL0分析 #

求非终结符的first集

  • 对于产生式A->B…，则直接把B的first加入到A的first中。终结符的first集是其本身。

求非终结符的follow集：只需寻找以下两种情况。一定要先记得把开始符号的follow初始化为“#”。注意是前面的follow加给后面，后面的first加给前面。

  • 对于右部任意的结构“…BC…”，把C的first除了ε加入到B的中。终结符的first集是其本身。
  • 对于产生式A->…BC，若C的first包含ε，则把A的follow加入到B的中。特别地，对于产生式A->…B，则直接把A的follow加入到B的中。其他不管。（因为产生式中B后面必须得没东西了，A换成B才能保证输入串中，原来A后面跟着的东西不发生变化。且“C的first包含ε”的意思是存在产生式C->ε。）

LR1分析 #

image-20220620204439826

在正式开始前，可以先求各符号的first集，因为一会加展望符的时候要用到。

例如图中的I0状态的构造。看蓝色框，S->·BB后面是#，因为将来归约成S的时候，因为S'->S，其后面没有符号，所以展望符是#。再看B->·aB,a和B->·aB,b，这两个合在一起可以写成左边的框子里的，即B->·aB,a|b，就像多个产生式被合并一样。这里的a和b是因为将来该产生式被归约为B后， 由于产生式S->·BB，它后面会紧跟着一个B。（这里特指该产生式里的第一个B被归约得到，因为后面的还没读呢。）而B的first集合里面有a和b，所以展望符是a和b，代表如果此时栈顶是aB，那么遇到符号串a或b都可以利用这一条产生式进行归约，否则就不能归约。如果是对形如S->B·B这种情况，那么此时应该再加上B的那些产生式，这些新的产生式的展望符应当和S->B·B里面的相同，因为这个到时候要被归约的B后面没有别的符号了，所以选择继承其父亲的展望符。

二义文法分析 #

else与最接近的if匹配，因此移进优先于归约。

DAG调整中间代码顺序 #

计算A:=B op C时，如果计算完右边左对象𝐵，紧接着计算𝐴，就可以及时 利用寄存器中的信息。

考虑先算DAG的右子树，再算左子树。

当右子树和左子树都计算完成，不应当继续向左边找，而是直接向上找，计算他们的父节点，直到无法计算。这个时候再到较低的别的左子树去找。

image-20220620221353611

根据待用信息和活跃信息写目标代码 #

同时还要写出RVALUE和AVALUE，这样才能证明你是根据这些信息写的。

image-20220620222029281

如图，因为左值已经在寄存器里了，所以不生成LD指令。

如下，我们假设Ri是分配给A的寄存器。

A = B op C，如果A已经在寄存器里面了，不生成第一句LD代码。如果C已经在寄存器里面了，则用寄存器表示。

LD Ri,B
OP Ri,C

A = B，如果A已经在寄存器里面了，不生成任何代码。

LD Ri,B

if A OP B goto X

LD Ri,A
CMP Ri,B
jtheta X

在最后，需要把还在寄存器中的在出口之后活跃的变量使用ST写回主存。

求first集

  • 对于产生是A->B…，则直接把B的first加入到A的first中。终结符的first集是其本身。

  • 直接加入：对形如U->a…的产生式（其中a是终结符），把a收入到First(U)中

  • 递归加入：对形入U->P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。

  • 终结符的first集是其本身。

求follow集

  • 直接加入：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。
  • 递归加入：对形如A->…U的产生式（其中U是非终结符），应把Follow(A)加到Follow(U)中。
  • 递归加入：对形如“A->…UP…”(P是非终结符)的组合，应把Follow(A)加到Follow(U)中。若First(P)包含ε，则把First(P)除ε直接收入到Follow(U)中。
  • 不需要求终结符的follow集。

5.1.2 句型的短语 #

现有句型αβγ。

若开始符号能星号推导出αAγ，且A能推导出β

那么β是该句型的相对于A的短语。特别地，如果A能单步推导出β，则是直接短语。

换言之，某句型相对于A的短语是该句型的子符号串（不一定是真子符号串）。且该子符号串能被A推导出（如果是能被A直接推导出，就是直接短语）

但是，需要保证该句型把其中的短语部分换成A后的句型（即上面的αβγ替换成αAγ）是可以被开始符号S星号推出的。

5.1.2 句柄 #

语法树的最左二层子树构成了句柄。因为最左二层子树父结点直接推出子节点，且最左，即对应最左直接短语。

（这里对句柄的定义屎一样。根本看不出来为什么。）

5.1.2 规范归约 #

如果有归约序列an,an-1,…,a0，且an是α，a0是开始符号S，且这之间的归约步骤（an-1，….,a1）都是通过把句柄替换成其对应的产生式左部实现的，那么这个归约序列称为规范归约。

规范归约即最左归约。它是最右推导的逆过程。

↑