编译原理第六到七章（知识点学习/期末复习/笔试/面试）

第六章 句法制导翻译概述

句法制导翻译概述

什么是句法制导翻译

编译的阶段：词法分析→句法分析→语义分析→中间代码生成→代码优化→目标代码生成

语义翻译：语义分析和中间代码生成

句法制导翻译 ：句法分析和语义分析和中间代码生成

句法制导翻译使用CFG来引导对语言的翻译， 是一种面向文法的翻译技术

句法制导翻译的基本思想

如何表示语义信息？

• 为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息

如何计算语义属性？

• 文法符号的语义属性值是用与文法符号所在产生式（句法规则）相关联的语义规则来计算的
• 对于给定的输入串x ，构建x的句法分析树，并利用与产生式（句法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

两个概念

将语义规则同句法规则（产生式）联系起来要涉及两个概念

• 句法制导定义(Syntax-Directed Definitions, SDD)
• 句法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

句法制导定义(SDD)

SDD是对CFG的推广

• 将每个文法符号和一个语义属性集合相关联
• 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值

如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值

句法制导翻译方案(SDT)

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内

例子

D → T { L.inh = T.type } L

T → int { T.type = int }

T → real { T.type = real }

L → { L1.inh = L.inh }L1, id       

 …

一个语义动作在产生式中的位置决定了这个动作的执行时间

SDD与SDT

SDD

• 是关于语言翻译的高层次规格说明
• 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序

SDT

• 可以看作是对SDD的一种补充，是SDD的具体实施方案
• 显式地指明了语义规则的计算顺序，以便说明某些实现细节

句法制导定义SDD

句法制导定义SDD是对CFG的推广

• 将每个文法符号和一个语义属性集合相关联
• 将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值

文法符号的属性

• 综合属性 (synthesized attribute)
• 继承属性 (inherited attribute)

综合属性(synthesized attribute)

在分析树结点 N上的非终结符A的综合属性只能通过 N的子结点或 N本身的属性值来定义

例子：

产生式                  语义规则

E → E1 + T       E.val = E1.val + T.val

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则。

继承属性(inherited attribute)

在分析树结点 N上的非终结符A的继承属性只能通过 N的父结点、N的兄弟结点或 N本身的属性值来定义

例子：

产生式             语义规则

D → T L       L. inh = T. type

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值 

例子：

带有综合属性的SDD

SDD：

输入： 3*5+4n

注释分析树 ( Annotated parse tree ) ： 每个节点都带有属性值的分析树

带有继承属性L.in的SDD

SDD：

 输入： real a , b , c

D → T L              （使用规则 1）
T → real             （使用规则 3）
L → L1 , id          （使用规则 4）
L1 → L2 , id        （再次使用规则 4）
L2 → id               （使用规则 5）

属性传递过程（也就是“语义规则”的作用）

1️⃣ T → real：

• T.type = real

2️⃣ D → T L：

• L.inh = T.type = real

3️⃣ L → L1 , id(c)：

• L1.inh = L.inh = real

• addtype("c", real)

4️⃣ L1 → L2 , id(b)：

• L2.inh = L1.inh = real

• addtype("b", real)

5️⃣ L2 → id(a)：

• addtype("a", real)

最终效果：构建符号表

通过这些继承属性 + 语义动作，我们完成了：

符号表：
a : real
b : real
c : real

在这个例子中，T.type 是一个综合属性（自己决定），L.inh 是继承属性（从左边的 T 传来的类型信息），所有变量都通过 L.inh 拿到自己的类型，最后用 addtype(...) 加进符号表。

属性文法 (Attribute Grammar)

一个没有副作用的SDD有时也称为属性文法 （属性文法的规则仅仅通过其它属性值和常量来定义一个属性值）

例子：

副作用指的是：一个操作除了计算返回值之外，还改变了外部状态（比如内存、符号表、输出等）。

常见的副作用包括：

• 改变一个变量的值（写入内存）

• 修改符号表

• 打印输出（如 print(...)）

• 执行文件或网络操作

在 SDD（语法制导定义）中，副作用表现在哪？

在 SDD 中：如果一个语义规则只是用来计算属性值，不对外部状态造成影响，那就是无副作用的 SDD，也叫属性文法（Attribute Grammar）。

有副作用的 SDD 举例：

L → id
语义规则：addToSymbolTable(id.lexeme, type)

这个规则调用了 addToSymbolTable(...)，修改了符号表 ⇒ 就是有副作用的。

SDD的求值顺序

SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

按照什么顺序计算属性值？ 语义规则建立了属性之间的依赖关系，在对句法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图(Dependency Graph)

依赖图是一个描述了分析树中结点属性间依赖关系的有向图

分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点

如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

例子

 如果一条语义规则的作用和求值无关，如打印一个值或向符号表中添加记录，则成为生成式左侧非终结符的虚拟综合属性。

常见的虚拟综合属性：        

1）print(any) 打印any；        

2）addtype(id.entry, type) 在符号表中为符号id添加符号类型（变量类型）type id.entry指明符号id在符号表中的入口

属性值的计算顺序 

可行的求值顺序是满足下列条件的结点序列N1, N2, … , Nk ：如果依赖图中有一条从结点Ni到 Nj 的边(Ni→Nj),  那么i < j（即：在节点序列中，Ni 排在Nj 前面）

这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)

例子

对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值

对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值 

例子

产生式      语义规则  

A→ B         A.s = B.i

                   B.i = A.s +1

如果图中没有环，那么至少存在一个拓扑排序

S-属性定义与L-属性定义

S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD

例：

如果一个SDD是S属性的，可以按照句法分析树节点的任何自底向上顺序来计算它的各个属性值

S-属性定义可以在自底向上的句法分析过程中实现

L-属性定义

L-属性定义(也称为L属性的SDD或L-SDD)的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性的，L是Left的首字母)

L-SDD的正式定义

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性：

• A的继承属性
• 产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
• Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路

每个S-属性定义都是L-属性定义

例子：L-SDD

L型 SDD：每个属性的求值从左往右按顺序就能完成，只依赖左边的兄弟或父节点的信息。

什么是综合属性（synthesized attributes）

->从子节点计算并“传回”父节点的属性值。下往上传（由子决定父）

什么是继承属性（inherited attributes）

->是从父节点或左兄弟“传递给”当前节点的属性值。从左往右传（父兄决定子）

综合属性有：T.val、T′.syn、F.val

继承属性有：T′.inh、T1′.inh

非L属性的SDD

L-属性（L-attributed）SDD 是指：每个继承属性的值，只依赖于 父节点 和 左边的兄弟节点的综合属性（syn）。

而如果一个 SDD 的属性依赖了“右边的兄弟”，那它就 不是 L 属性的，叫做 非 L 属性的 SDD，这类在自顶向下翻译中不适用。

例子：

综合属性有：A.s

继承属性有：L.i、M.i、R.i、Q.i

句法制导翻译方案SDT

句法制导翻译方案(SDT )是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

SDT可以看作是SDD的具体实施方案 本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在句法分析过程中实现

• 基本文法可以使用LR分析技术，且SDD是S属性的
• 基本文法可以使用LL分析技术，且SDD是L属性的

• S 属性（Synthesized）SDD：只有综合属性，从子节点传上来的（适合 LR）

• L 属性（Left-attributed）SDD：属性可以从左兄弟或父节点传来（适合 LL）

将S-SDD转换为SDT

将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后

例子：

S-属性定义的SDT 实现

如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR句法分析过程中实现

当归约发生时执行相应的语义动作

 扩展的LR句法分析栈

在分析栈中使用一个附加的域来存放综合属性值

若支持多个属性：使栈记录变得足够大；在栈记录中存放指针

将语义动作中的抽象定义式改写成具体可执行的栈操作

例子：

在自底向上句法分析栈中实现桌面计算器

SLR自动机：

输入： 3*5+4

将L-SDD转换为SDT

将L-SDD转换为SDT的规则

• 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

例子

L-SDD

SDT

1) T → F { T′.inh = F.val } T′ { T.val = T′.syn }

2) T′ → *F { T1′.inh = T′.inh×F.val } T1′ { T′.syn = T1′.syn }

3) T′ → ε { T′.syn = T′.inh }

4) F → digit { F.val = digit.lexval }

L-属性定义的SDT 实现

如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR句法分析过程中实现

• 在非递归的预测分析过程中进行语义翻译
• 在递归的预测分析过程中进行语义翻译
• 在LR分析过程中进行语义翻译

在非递归的预测分析过程中进行翻译

扩展句法分析栈

例子

1) T → F { T′.inh = F.val } T′ { T.val = T′.syn }

2) T′ → *F { T1′.inh = T′.inh×F.val } T1′ { T′.syn = T1′.syn }

3) T′ → ε { T′.syn = T′.inh }

4) F → digit { F.val = digit.lexval }

转为

分析栈中的每一个记录都对应着一段执行代码

• 综合记录出栈时，要将综合属性值复制给后面特定的语义动作（如果有需要）
• 变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作（位于即将扩展的产生式右部）

例子

1) T → F {a1:T′.inh=F.val} T′ {a2:T.val=T′.syn}

 2) T′ → *F{a3:T1′.inh=T′.inh×F.val}T1′{a4:T′.syn=T1′.syn}

 3) T′ → ε {a5:T′.syn = T′.inh }

 4) F → digit {a6:F.val = digit.lexval}

输入: 3 * 5 

在递归的预测分析过程中进行翻译

算法

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量  
• 非终结符A的代码根据当前的输入决定使用哪个产生式

与每个产生式有关的代码执行如下动作：

从左到右考虑产生式右部的词法单元、非终结符及语义动作  

• 对于带有综合属性x的词法单元 X，把x的值保存在局部变量X.x中；然后产生一个匹配 X的调用，并继续输入
• 对于非终结符B，产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk是代表B的继承属性的变量，c是代表B的综合属性的变量
• 对于每个动作，将其代码复制到句法分析器，并把对属性的引用改为对相应变量的引用

 例子：

SDT

1) T → F { T′.inh = F.val } T′     { T.val = T′.syn }

2) T′ → *F { T1′.inh = T′.inh×F.val } T1′  { T′.syn = T1′.syn }

3) T′ → ε { T′.syn = T′.inh }

4) F → digit { F.val = digit.lexval }

T′syn T′ (token, T′inh)

//为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值

{  

    D: Fval, T1′inh, T1′syn；

//对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量

    if token=“*”  then

    {  Getnext(token)；

       Fval=F(token)；

       T1′inh= T′inh×Fval；

       Getnext(token)；

       T1′syn=T1′(token, T1′inh)；

       T΄syn=T1′syn；

       return T′syn；

     }

    else if token= “ $” then

     {  

      T′syn= T′inh；

       return T′syn；

     }

//

     else Error；

}

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR句法分析过程中计算这个新文法之上的SDD

（ 原本设计为 LL 分析 + L-属性 SDD 的程序，只要重写文法 + 插入中间动作（@pass），
就可以变成适用于 LR 分析的 SDT 实现方式。）

 例子

1) T → F { T′.inh = F.val } T′ { T.val = T′.syn }

2) T′ → *F { T1′.inh = T′.inh×F.val } T1′ { T′.syn = T1′.syn }

3) T′ → ε { T′.syn = T′.inh }

4) F → digit { F.val = digit .lexval }

这是一个典型的 LL 分析 + L 属性 SDD 的写法：

重点问题是：

• 继承属性 T′.inh = F.val 是要在处理 T′ 之前就先计算的

• 所以只能在 LL 分析中执行

LR 分析器是归约式，不能在中间执行动作，所以我们引入中间产生式来提前执行语义动作

变成：修改后的SDT，所有语义动作都位于产生式末尾

1) T → F M T′             { T.val = T′.syn }

2) M → ε                  { M.i = F.val; M.s = M.i }
3) T′ → * F N T1′         { T′.syn = T1′.syn }
4) N → ε                  { N.i1 = T′.inh; N.i2 = F.val; N.s = N.i1 × N.i2 }
5) T′ → ε                 { T′.syn = T′.inh }
6) F → digit              { F.val = digit.lexval }

T → F M T′               { T.val = T′.syn }
M → ε                   { M.i = F.val; M.s = M.i }

• 引入了中间符号 M，让 M → ε 的动作在 F 之后、T′ 之前执行

• 利用 M 计算 F.val，保存起来供 T′ 使用

• 在 LR 归约中，我们可以先归约 F、然后归约 M，就能保证 F.val 在 T′ 用之前被计算

T′ → * F N T1′          { T′.syn = T1′.syn }
N → ε                   { N.i1 = T′.inh; N.i2 = F.val; N.s = N.i1 × N.i2 }

• 插入了 N → ε，把中间继承计算提早执行

• N.s 实际上就是 T1′.inh

• 如果你愿意，后续还可以写 T1′.inh = N.s，或者直接把 N.s传给 T1′

T′ → ε                  { T′.syn = T′.inh }
F → digit               { F.val = digit.lexval }

我们要把SDT 中的语义动作 {} 替换成文法中的“标记非终结符”（dummy symbol），这样就可以用 LR 分析器来处理这些语义动作了

把这种形式A → α {a} β

变成这种形式：

A → α M β
M → ε   // 把原来的动作 a 放到 M 这个产生式里去

• 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性， 并在产生式后端放置语义动作计算综合属性

• 每当想计算一个继承属性，就把语义动作 {} 放在它前面

• 每当想计算一个综合属性，就把语义动作 {} 放在它后面

• 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε

例如这条产生式：T → F { T′.inh = F.val } T′ { T.val = T′.syn }

我们就加两个标记符号 M1 和 M2，变成：T → F M1 T′ M2

然后加两个新产生式：

M1 → ε       // 执行 { T′.inh = F.val }
M2 → ε       // 执行 { T.val = T′.syn }

• 每个 {} 都变成不同的 M1, M2, M3...

• 每个 Mi 都是一个产生式 Mi → ε，但它背后执行的是原来的动作

• 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a' ，并且将a'关联到M→ε 上。动作a'

• 把 {a} 拆出去，扔到 M → ε 里去执行

• a' 其实和 a 做的是一回事，只是你要明确它用到哪些继承/综合属性

• (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制

• 假如原来写的是：T′.inh = F.val

• 那现在 M1 → ε 这个动作，就要通过 M1.i = F.val 来模拟继承传值

• 换句话说：把 F.val 传给 M1 的继承属性

• (b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性

• 原来 { T′.inh = F.val } 是在产生式中直接执行

• 现在你要在 M1 → ε 这个动作中执行它

• 所以结果比如 M1.s = F.val（综合属性），后续由 M1.s 传给 T′.inh

将语义动作改写为可执行的栈操作

例子：

1) T → F M T′             { T.val = T′.syn }

2) M → ε                  { M.i = F.val; M.s = M.i }

3) T′ → * F N T1′         { T′.syn = T1′.syn }

4) N → ε                  { N.i1 = T′.inh; N.i2 = F.val; N.s = N.i1 × N.i2 }

5) T′ → ε                 { T′.syn = T′.inh }

6) F → digit              { F.val = digit.lexval }

1)

T→F M T′ {stack[top-2]. val = stack[top].syn; top = top-2;}      

M→ ε {stack[top+1]. s = stack[top].val; top = top+1;}     

2)

T′→*F N T1′ {stack[top-3]. syn = stack[top].syn; top = top-3;}

N → ε {stack[top+1]. s = stack[top-2]. s × stack[top].val; top = top+1;}

3)

T′→ε{stack[top+1].syn = stack[top]. s; top = top+1;}

4)

F →digit {stack[top].val = stack[top]. lexval;}

例子

第七章 中间代码生成

类型表达式

基本类型是类型表达式

• integer
• real
• char
• boolean
• type_error (出错类型)
• void (无类型)

可以为类型表达式命名，类型名也是类型表达式

将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式

例如：

（1）数组构造符array

若T是类型表达式，则array ( I, T )是类型表达式( I是一个整数)

 （2）指针构造符pointer

若T 是类型表达式，则 pointer ( T ) 是类型表达式，它表示一个指针类型

（3）笛卡尔乘积构造符×

若T1 和T2是类型表达式，则笛卡尔乘积T1 × T2 是类型表达式

（4）函数构造符

若T1、T2、…、Tn 和R是类型表达式，则T1×T2 ×…×Tn→ R是类型表达式

（5）记录构造符record

若有标识符N1 、N2 、…、Nn 与类型表达式T1 、T2 、…、Tn ， 则     record ( ( N1  × T1 ) × ( N2 × T2 )× …× ( Nn × Tn )) 是一个类型表达式

例子

设有C程序片段

struct   stype                                     

{   char[8] name;

    int  score;                                   

};                                   

stype[50] table;                                   

stype* p;

• 和stype绑定的类型表达式：record ( (name× array(8, char)) × (score × integer) )
• 和table绑定的类型表达式 ：array (50, stype)
• 和p绑定的类型表达式 ：pointer (stype)

声明语句的翻译

局部变量的存储分配

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址

• 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
• 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

变量声明语句的SDT

enter( name, type, offset ):在符号表中为名字name创建记录,将name的类型设置为type,相对地址设置为offset

例子

① P →{ offset = 0 } D

② D → T id;{ enter( id.lexeme, T.type, offset ); offset = offset + T.width; }D

③ D → ε

④ T → B   { t =B.type; w=B.width;}  C   { T.type = C.type; T.width = C.width; }

⑤ T → ↑T1{ T.type = pointer( T1.type); T.width = 4; }

⑥ B → int { B.type = int; B.width = 4; }

⑦ B → real{ B.type = real; B.width = 8; }

⑧ C → ε  { C.type=t; C.width=w; }

⑨ C → [num]C1 { C.type = array( num.val, C1.type);   C.width = num.val * C1.width; }

 “real x; int i;”的语法制导翻译

 类型表达式“int[2][3]”的语法制导翻译

中间代码的形式

四元式是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)

其中，op为一个二元(也可是一元或零元)运算符; arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。

四元式还可写为类似于PASCAL语言的赋值语句的形式：result := arg1 op arg2

四元式的格式

每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。

例如，表达式A+B*C可写为序列     

T1:=B*C   

T2:=A+T1

当op为一元、零元运算（如无条件转移)，arg2甚至arg1应缺省，即result:=op arg1或 op result ；对应的一般形式为：  (op,arg1,-,result) 或  (op,-,-,result) 。

三元式的格式

为了节省临时变量的开销，有时也可采用一种三元式结构来作为中间代码，其一般形式为

(i) (op,arg1,arg2)     

其中，(i)为三元式的编号，也代表了该式的运算结果；op,arg1,arg2的含义与四元式类似，区别在于arg可以是某三元式的序号，表示用该三元式的结果作为运算对象。

例如，对于赋值语句a:=-b*(c+d)，若用三元式表示，则可写成       

 ①        (U_minus,  b,   -  )       

 ②        (  +   ,     c,    d  )         

③        (  *    ,     ①,  ② )         

④        (  :=  ,      ③,    a  )

式①中的运算符U_minus表示一元减运算。

逆波兰表示

每一运算符都置于其运算对象之后，故称为后缀表示。

特点:表达式中各个运算是按运算符出现的顺序进行的，无须使用括号来指示运算顺序，因而又称为无括号式。

例子

中缀表示               后缀表示

A+B                       AB+

A+B*C                   ABC*+

(A+B)*(C+D)          AB+CD+

* x/y^z-d*e              xyz^/de*-

 例子：

中缀：x / y ^ z - d * e

最终后缀表达式为：x y z ^ / d e * -

简单赋值语句的翻译

赋值语句翻译的任务

赋值语句的基本文法

① S → id = E；

② E → E1 + E2  

③ E → E1 * E2  

④ E → -E1       

⑤ E → (E1)  

⑥ E → id

赋值语句翻译的主要任务：生成对表达式求值的三地址码

例子：

源程序片段 x = ( a + b ) * c ;

三地址码 t1 = a + b；t2 = t1 * c；x  = t2

赋值语句的SDT

lookup(name)：查询符号表返回name 对应的记录

gen(code)：生成三地址指令code

newtemp( )：生成一个新的临时变量t，返回t的地址

例子：a = b + c * d;

生成：

t1 = c * d
t2 = b + t1
a = t2

S → id = E；

{ p = lookup(id.lexeme); if p == nil then error ;  S.code = E.code ||   gen( p ‘=’ E.addr ); }

这里的 || 不是逻辑或运算符，而是表示“代码的连接/拼接”，意思是把两段中间代码拼成一段完整的中间代码。（把表达式 E 的代码，接在前面，再加上一句 p = E.addr，合成 S.code）

• id = E 是赋值语句，例如 a = b + c;

• lookup(id.lexeme) 查找变量 a 是否已声明

• 如果 a 没有声明 → 报错

• E.code 是表达式右边的代码（可能是好几条）

• E.addr 是表达式的最终结果（临时变量或变量地址）

• gen(p = E.addr) → 生成最终赋值语句：a = t2

E → E1 + E2

{ E.addr = newtemp( );    E.code = E1.code || E2.code||   gen(E.addr ‘=’ E1.addr ‘+’ E2.addr); }

• 生成新临时变量 t

• 拼接左右两边的中间代码 E1.code || E2.code

• 然后再生成一条新代码：t = E1 + E2

• 最后把结果地址保存在 E.addr

b + t1
→ t2 = b + t1

E → E1 * E2

{ E.addr = newtemp( );     E.code = E1.code || E2.code ||  gen(E.addr ‘=’ E1.addr ‘*’ E2.addr); }

c * d
→ t1 = c * d

E → -E1   

 { E.addr = newtemp( );  E.code = E1.code||   gen(E.addr ‘=’ ‘uminus’ E1.addr); }

E → (E1)

{ E.addr = E1.addr;  E.code= E1.code;}

E → id       

{ E.addr = lookup(id.lexeme); if E.addr == nil then error ;    E.code = ‘’;}

增量翻译 (Incremental Translation)

在增量方法中，gen( )不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后

例子

例：x = ( a + b ) * c ; 

数组引用的翻译

赋值语句的基本文法     

S → id = E; | L = E;     

E→ E1 + E2 | -E1   | (E1) | id | L   

 L→ id [E] | L1 [E]

数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址

数组元素寻址 (Addressing Array Elements )

一维数组

假设每个数组元素的宽度是w，则数组元素a[i]的相对地址是：                                                

base+i×w    

其中，base是数组的基地址，i×w是偏移地址

二维数组

假设一行的宽度是w1，同一行中每个数组元素的宽度是w2，则数组元素a[i1] [i2]的相对地址是：  

base+i1×w1+i2×w2

k维数组

数组元素a[i1] [i2] …[ik]的相对地址是：                              

 base+i1×w1+i2×w2+…+ik×wk

w1 →a[i1] 的宽度；w2 →a[i1] [i2] 的宽度；… wk →a[i1] [i2] …[ik]的宽度

例子

假设type(a)= array(3, array(5, array(8, int) ) )， 一个整型变量占用4个字节，    

则addr(a[i1][i2][i3]) = base + i1 * w1  + i2*w2 + i3*w3  = base + i1*160 + i2*32 + i3*4

a[i1]的宽度：160；a[i1][i2]的宽度：32；a[i1][i2][i3]的宽度：4；

带有数组引用的赋值语句的翻译

例子1

假设 type(a)=array(n, int)

 源程序片段  c = a[i]；

三地址码

 t1  = i * 4    

 t2  = a [ t1 ]  

c   = t2

addr(a[i]) = base + i*4

例子2

假设 type(a)= array(3, array(5, int))，

源程序片段  c =a[i1][i2];

三地址码

t1 = i1 * 20        

t2 = i2 * 4        

t3 = t1 + t2        

t4  = a [ t3 ]        

c   =  t4

addr(a[i1][i2])= base + i1*20 + i2*4

数组引用的SDT

赋值语句的基本文法     

S → id = E; | L = E;     

E → E1 + E2 | -E1 | (E1) | id | L     

L → id [E] | L1 [E]

 base+i1×w1+i2×w2+…+ik×wk

假设 type(a)= array(3, array(5, array(8, int) ) )，翻译语句片段“a[i1][i2][i3]”

L的综合属性：

• L.type：L生成的数组元素的类型
• L.offset：指示一个临时变量，该临时变量用于累加公式中的ij × wj项，从而计算数组引用的偏移量
• L.array：数组名在符号表的入口地址

三地址码 ：t1 = i1*160 ；t2 = i2*32； t3 = t1+t2； t4 = i3*4； t5 = t3+t4 ；t6 = a[t5]

控制流语句及其SDT

控制流语句的基本文法

P → S

S →S1 S2

S →id = E ; | L = E ;      

S → if B then S1

        | if B then S1 else S2

        | while B do S1

控制流语句的代码结构

例子：S → if B then S1 else S2

布尔表达式B被翻译成由跳转指令构成的跳转代码

继承属性

• S.next：是一个地址，该地址中存放了紧跟在S代码之后的指令(S的后继指令)的标号
• B.true：是一个地址，该地址中存放了当B为真时控制流转向的指令的标号
• B.false：是一个地址，该地址中存放了当B为假时控制流转向的指令的标号

用指令的标号标识一条三地址指令

控制流语句的SDT

newlabel( ): 生成一个用于存放标号的新的临时变量L，返回变量地址

label(L): 将下一条三地址指令的标号赋给L

P → { S.next = newlabel(); }S{ label(S.next);}

S →{ S1.next = newlabel(); }S1 { label(S1.next); S2.next= S.next ; }S2

S →id = E ; | L = E ;      

S → if B then S1

        | if B then S1 else S2

        | while B do S1

if-then-else语句的SDT

S → if B then S1 else S2

S → if  { B.true = newlabel(); B.false = newlabel(); } B

        then { label(B.true); S1.next = S.next; } S1 { gen( ‘goto’  S.next ) }

        else { label(B.false); S2.next = S.next; }S2

if-then语句的SDT

S → if B then S1

S → if { B.true = newlabel(); B.false = S.next; } B

        then { label(B.true); S1.next = S.next; } S1

 while-do语句的SDT

S →while B do S1

S →while  {S.begin = newlabel();  label(S.begin);  B.true = newlabel();   B.false = S.next;}B

       do { label(B.true); S1.next = S.begin;} S1  { gen(‘goto’ S.begin); }

布尔表达式及其SDT

    B → B or B

           | B and B

           | not B

           | (B)

           | E relop E

           | true

           | false

优先级：not > and > or

E relop E 是关系表达式

relop（关系运算符）： <,  <=, >,  >=，==,  ! =

在跳转代码中，逻辑运算符&&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的

例子：

语句 ： if ( x<100 || x>200 && x!=y )    x=0;

三地址代码：

           if x<100 goto L2

           goto L3

L3 :     if x>200 goto L4

           goto L1

L4 :     if x!=y goto L2   

            goto L1    

L2 :    x=0      

L1 :

布尔表达式的SDT

B → E1 relop E2{ gen(‘if ’ E1.addr relop E2.addr ‘goto’  B.true)；gen(‘goto’ B.false); }    

B → true  { gen(‘goto’ B.true); }  

B → false  { gen(‘goto’ B.false); }      

B → ( {B1.true =B. true;  B1.false =B.false; } B1 )

B → not { B1.true = B.false; B1.false = B.true; } B1    

B → B1 or B2  的SDT

B →  { B1.true = B.true;  B1.false = newlabel(); } B1

       or { label(B1.false);  B2.true = B.true;  B2.false = B.false; }B2  

B → B1 or B2  

B → B1 and B2  的SDT

B → B1 and B2  

B → { B1.true = newlabel(); B1.false = B.false; }  B1

         and { label(B1.true); B2.true = B.true; B2.false = B.false; }B2 

控制流翻译的例子

控制流语句的SDT

P → {a}S{a}

S → {a}S1{a}S2

S → id=E;{a} | L=E;{a}      

E → E1+E2{a} | -E1{a} | (E1){a}| id{a}| L{a}

L → id[E]{a} | L1[E]{a}

S → if {a}B then {a}S1

          | if {a}B then {a}S1 else {a}S2

          | while {a}B do {a}S1{a}

B → {a}B or {a}B | {a}B and {a}B | not {a}B | ({a}B)

          | E relop E{a} | true{a} | false{a}

SDT的通用实现方法

任何SDT都可以通过下面的方法实现

首先建立一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作

例子

 语句“while a<b do if c<d then x=y+z  else x=y-z”的三地址代码

1: if a < b  goto 3                  1: ( j<,  a,  b ,  3 )

2: goto 11                              2: (  j ,  - ,  - , 11 )

3: if c < d  goto 5                  3: ( j<,  c,  d ,  5 )

4: goto 8                               4: (  j ,  - ,  - ,  8 )

5: t1 = y + z                          5: ( + ,  y , z ,  t1  ) 

6: x = t1                                6: ( = ,  t1,  - ,  x )

7: goto 1                               7: (  j ,  - ,  - ,  1 )

8: t2 = y - z                           8: (  - ,  y,  z ,  t2 )

9: x = t2                                 9: ( = ,  t2,  - ,  x )

10: goto 1                             10: (  j ,  - ,  - ,  1 )

11:                                        11: 

布尔表达式的回填

回填

基本思想：生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号。

非终结符B的综合属性

B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号

B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

• makelist( i ) 创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针
• merge( p1, p2 ) 将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
• backpatch( p, i ) 将 i 作为目标标号插入到 p所指列表中的各指令中

布尔表达式的回填

B → E1 relop E2

B→ E1 relop E2 {

     B.truelist = makelist(nextquad);

     B.falselist = makelist(nextquad+1);

     gen(‘if ’ E1.addr relop E2.addr ‘goto _’);

     gen(‘goto _’);

}

这段代码是为了给布尔表达式生成“如果为真/为假跳到哪里”的中间代码，它用的是延迟填充跳转地址（回填技术）。你可以先生成跳转语句，把地址留空，后面再统一填入真实目标。

表达式是：B -> E1 relop E2

表示布尔表达式 B 是两个表达式 E1 和 E2 之间的关系运算（例如 <, ==, >= 等）。

B.truelist = makelist(nextquad);

• B.truelist：布尔表达式为真的跳转目标位置列表。
• makelist(nextquad)：创建一个列表，里面是当前要生成的下一条指令的编号（因为这条指令就是当表达式为真时跳转的地方）。
• 作用：先占个位置，等确定真正跳转到哪时再回填。

B.falselist = makelist(nextquad+1);

• 同理，这里是创建布尔表达式为假时的跳转列表，是下一条指令之后的那条（即下一条是if，再下一条是goto）。
• 也是先占位，等以后知道“跳哪里”再填进去。

gen(‘if ’ E1.addr relop E2.addr ‘goto _’);

生成条件跳转语句，例如：if a < b goto _ 

下划线 _ 表示“回填位置”，现在不知道跳到哪里，就先留空。

gen(‘goto _’);

如果条件不满足，就执行这个跳转，也要回填：goto _

整体例子：

假设我们要处理：a < b

生成如下伪代码：

(100) if a < b goto _
(101) goto _

此时：

B.truelist = [100]

B.falselist = [101]

等你知道应该跳到哪儿时，比如：如果为真跳到 120 行，为假跳到 130 行，你就把 _ 回填成：

(100) if a < b goto 120

(101) goto 130

 B → true

B → true {     

     B.truelist = makelist(nextquad);      

     gen(‘goto _’);

}

 B → false

 B → false {

    B.falselist = makelist(nextquad);

     gen(‘goto _’);

}

 B →(B1)

B→ (B1) {

    B.truelist = B1.truelist ;

    B.falselist = B1.falselist ;

}

B→ not B1 

 B → not B1 {

    B.truelist = B1.falselist;

    B.falselist = B1.truelist;

}

B → B1 or B2

 B → B1 or M B2 {

     backpatch(B1.falselist, M.quad );  

    B.truelist= merge(B1.truelist,B2.truelist );

     B.falselist = B2.falselist ;

}

M → ε { 

   M.quad = nextquad ;

}

 B→ B1 and B2

B → B1 and M B2 {

     backpatch( B1.truelist, M.quad );  

    B.truelist = B2.truelist;

     B.falselist = merge( B1.falselist, B2.falselist );

}

 例子

B →  E1 relop E2 {

    B.truelist = makelist(nextquad);

    B.falselist = makelist(nextquad+1);  

    gen(‘if ’ E1.addr relop E2.addr ‘goto _’);   

   gen(‘goto _’);

}

 100: if a<b goto _

101: goto _

 B → B1 or M B2 {

     backpatch(B1.falselist, M.quad );  

    B.truelist= merge(B1.truelist,B2.truelist );

     B.falselist = B2.falselist ;

}

M → ε { 

   M.quad = nextquad ;

}

100: if a<b goto _

101: goto _

102: if c<d goto _

103: goto _

 B → B1 and M B2 {

     backpatch( B1.truelist, M.quad );  

    B.truelist = B2.truelist;

     B.falselist = merge( B1.falselist, B2.falselist );

}

100: if a<b goto _

101: goto _

102: if c<d goto _

103: goto _

104: if e<f goto _

105: goto _

 B → B1 or M B2 {

     backpatch(B1.falselist, M.quad );  

    B.truelist= merge(B1.truelist,B2.truelist );

     B.falselist = B2.falselist ;

}

控制流语句的回填

文法：

S→ S1 S2

S →id = E ; | L = E ;      

S →if B then S1

      | if B then S1 else S2

      | while B do S1

综合属性

S.next1ist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

S → if B then S1

S → if B then M S1 {

     backpatch(B.truelist, M.quad);  

    S.nextlist=merge(B.falselist, S1.nextlist);

}

 S → if B then S1 else S2

S → if B then M1 S1 N else M2 S2 {

    backpatch(B.truelist, M1.quad);

     backpatch(B.falselist, M2.quad);  

    S.nextlist = merge( merge(S1.nextlist,  N.nextlist), S2.nextlist );

}

N → ε   {

   N.nextlist = makelist(nextquad);

   gen(‘goto _’);

}

S → while B do S1

S → while M1 B do M2 S1 {

    backpatch( S1.nextlist, M1.quad );

    backpatch( B.truelist, M2.quad );

    S.nextlist = B.falselist;

     gen(‘goto’ M1.quad);

}

 S → S1 S2

S → S1 M S2 {

    backpatch( S1.nextlist,  M.quad );

    S.nextlist = S2.nextlist ;

}

 S → id = E ; | L = E ;

S→ id = E ; | L = E ;{ S.nextlist = null; } 

例子

while  a < b  do

      if  c < 5  then

          while x > y do z = x + 1;

      else

           x = y;

语句“while a<b do if c<5 then while x>y do z=x+1; else x=y;”的注释分析树

 while a<b do if c<5 then while x>y do z=x+1; else x=y;

100: if a < b  goto 102                      100:    ( j<, a ,b , 102 )

101: goto _                                       101:     ( j  , - ,  - ,  -     )

102: if c < 5  goto 104                       102:     ( j<, c , 5 , 104 )

103: goto 110                                    103:     ( j  , - ,  - , 110 )

104: if x > y  goto 106                       104:     ( j>, x , y , 106 )

105: goto 100                                    105:     ( j  , - ,  - , 100 )

106: t1 = x + 1                                   106:     ( + , x , 1 ,   t1  )

107: z = t1                                         107:     ( = , t1 , - ,   z   )

108: goto 104                                    108:     ( j  , - ,  - , 104 )

109: goto 100                                    109:     ( j  , - ,  - , 100 )

110: x = y                                          110:     ( = , y ,  - ,   x  )

111: goto 100                                    111:     ( j  , - ,  - , 100 )

112:                                                   112:

switch语句的翻译

switch E

    begin

        case V1: S1

        case V2: S2

        . . .

        case Vn – 1: Sn – 1

        default: Sn

    end

switch E { t = newtemp(); gen( t ‘=’ E.addr ); }

case V1:{ L1= newlabel(); gen(‘if’ t ‘!=’ V1 ‘goto’ L1 ); } S1{ next = newlabel()；gen(‘goto’ next); }

case V2:{ label(L1); L2=newlabel();  gen(‘if’ t ‘!= ’ V2 ‘goto’ L2 ); } S2{ gen(‘goto’ next); }

        . . .

case Vn -1:{ label(Ln-2); Ln-1=newlabel(); gen(‘if’ t ‘!=’ Vn-1 ‘goto’ Ln-1 );} Sn – 1{ gen(‘goto’ next);}

default:{ label(Ln-1);} Sn{label(next);}    

switch语句的另一种翻译

在代码生成阶段，根据分支的个数以及这些值是否在一个较小的范围内，这种条件跳转指令序列可以被翻译成最高效的n路分支

switch E { t = newtemp(); gen(t ‘=’E.addr); test = newlabel(); gen(‘goto’ test); }

case V1 : { L1= newlabel(); label(L1); map(V1, L1); }  S1    { next = newlabel();  gen(‘goto’ next); }

case V2 : { L2 = newlabel(); label(L2); map(V2, L2); }   S2    { gen(‘goto’ next); }  

       . . .

case Vn-1:{ Ln-1= newlabel(); label(Ln-1); map(Vn-1, Ln-1); }   Sn-1  { gen(‘goto’ next); }

default :  { Ln= newlabel(); label(Ln); } 

        Sn  { gen(‘goto’ next)；label(test);

                gen(‘if ’ t ‘=’ V1 ‘goto’ L1);

                gen(‘if ’ t ‘=’ V2 ‘goto’ L2);

                . . .

                gen(‘if ’ t ‘=’ Vn-1 ‘goto’ Ln-1);  

                gen(‘goto’ Ln);

               label(next);   }

增加一种case指令

test :    if t = V1 goto L1                                      test :    case t  V1      L1

           if t = V2 goto L2                                                  case t  V2    L2

           . . .                                                                       . . .

           if t = Vn-1 goto Ln-1                                            case t  Vn-1  Ln-1

           goto Ln                                                                case t   t      Ln

next :                                                                 next :

指令 case t Vi  Li  和 if t = Vi  goto Li 的含义相同，但是case指令更加容易被最终的代码生成器探测到，从而对这些指令进行特殊处理

过程调用语句的翻译

文法

S → call id (Elist)   

Elist → Elist, E     

Elist → E

过程调用语句的代码结构

id( E1, E2, … , En )

 需要一个队列q存放E1.addr 、E2.addr、…、 En.addr，以生成

param E1.addr

param E2.addr …

param En.addr

call id.addr  n

过程调用语句的SDD

S → call id ( Elist )

    {    n=0;  // 参数个数计数

          for q中的每个t  do

        {    gen(‘param’ t );  // 生成 param 指令

            n = n+1；

          }

        gen(‘call’ id.addr ‘,’ n);   // 生成函数调用指令

    }

Elist → E 

 {      将q初始化为只包含E.addr;     }  // 一个参数时，队列中只有一个元素

Elist →Elist1, E  

  {     将E.addr添加到q的队尾;     }    // 多个参数就一个个拼进去

S → call id (Elist)

这就是一个函数调用，比如 call f(...)，Elist 是参数列表。

在翻译时我们：

1. 先翻译每个实参 E，把结果临时变量加入到 q（参数队列）里；

2. 然后一条条地生成 param 参数 的中间代码；

3. 最后调用函数：call f, 参数个数

例子

翻译以下语句f ( b*c-1, x+y, x, y )

t1 =b*c

t2 =t1 - 1

t3 =x+y

param t2

param t3

param x

param y

call f, 4

源代码是：f(b*c-1, x+y, x, y)

这是一个调用函数 f，传入了 4 个实参：

• b * c - 1

• x + y

• x

• y

第一个参数：b*c - 1

• t1 = b * c

• t2 = t1 - 1

• 加入队列：q = [t2]

第二个参数：x + y

• t3 = x + y

• 加入队列：q = [t2, t3]

第三个参数：x（变量）

• 加入队列：q = [t2, t3, x]

第四个参数：y（变量）

• 加入队列：q = [t2, t3, x, y]

最终生成中间代码：

t1 = b * c         // 第一个参数的第一步
t2 = t1 - 1        // 第一个参数的第二步
t3 = x + y         // 第二个参数
param t2           // 参数从左到右一个个入栈
param t3
param x
param y
call f, 4          // 调用 f，传 4 个参数