在对语法制导的语义计算进行了概述后，将进入其真正的应用：语义分析和中间代码生成步骤

语义分析

与语义分析相关的工作有：

  • 静态语义检查
    • 编译期间进行的语义检查
  • 动态语义检查
    • 运行期间进行的语义检查
  • 收集语义信息
    • 为语义检查进行信息收集
    • 为后续阶段进行信息收集

静态语义检查

在代码生成前的最后阶段，具体地包括：

  • 静态类型检查
  • 名字的作用域分析
  • 控制流检查（如break语句必须在循环内）
  • 唯一性检查
  • 名字的上下文相关性检查

类型检查

类型检查程序用来检查代码的类型是否匹配，实现一个类型系统

类型系统

以编译原理实验实现的MiniDecaf小语言为例：

类型表达式

  • 基本类型：int\rm int
  • 数组类型：array(t){\rm array}(t)
  • 函数类型：(t1,...,tn)→t0(t_1,...,t_n)\to t_0
  • 本身没有类型，但内部有类型错误：error\rm error
  • 本身没有类型，但内部类型没有错误：ok\rm ok

类型环境

  • 是一个从程序的标识符集合到类型表达式集合的函数
  • 用Γ: I→T\Gamma:\ I\to T表示

类型环境的更新

Γ[id‾↦t]\Gamma[\underline{id}\mapsto t]

表示一个定义域为I∪{id‾}I\cup\{\underline{id}\}的类型环境，它将非id‾\underline{id}的xx映射到Γ(x)\Gamma(x)，将id‾\underline{id}映射到tt

对一个语句序列ss，假设它最外层作用域的声明了类型为tkt_k的变量id‾k\underline{id}_k共nn个，则定义

Update(Γ,s)=Γ[id‾1↦t1]...[id‾n↦tn]{\rm Update}(\Gamma, s)=\Gamma[\underline{id}_1\mapsto t_1]...[\underline{id}_n\mapsto t_n]

类型规则

类型规则将使用断言形式描述

先考虑**表达式(expression)**的类型，它可以有以下的类型规则：

  • E-int：整数字面量规则（int‾\underline{\rm int}表示整数字面量）

Γ⊢int‾:int\frac{}{\Gamma\vdash\underline{\rm int}:{\rm int}}

  • E-id：标识符规则

Γ(id‾)=tΓ⊢id‾:t\frac{\Gamma(\underline{\rm id})=t}{\Gamma\vdash\underline{\rm id}:t}

  • E-bop：二元运算符规则

Γ⊢e1:tΓ⊢e2:tΓ⊢e1 bop‾ e2:t\frac{\Gamma\vdash e_1:t\qquad\Gamma\vdash e_2:t}{\Gamma\vdash e_1\ \underline{\rm bop}\ e_2:t}

  • E-access：数组访问规则

Γ⊢e1:array(t)Γ⊢e2:intΓ⊢e1[e2]:t\frac{\Gamma\vdash e_1:{\rm array}(t)\qquad\Gamma\vdash e_2:{\rm int}}{\Gamma\vdash e_1[e_2]:t}

  • E-call：函数调用规则

Γ⊢id‾:(t1,...,tn)→t0Γ⊢e1:t1...Γ⊢en:tnΓ⊢id‾(e1,...,en):t0\frac{\Gamma\vdash\underline{\rm id}:(t_1,...,t_n)\to t_0\qquad\Gamma\vdash e_1:t_1\quad ...\quad \Gamma\vdash e_n:t_n}{\Gamma\vdash\underline{\rm id}(e_1,...,e_n):t_0}

然后是**语句(statement)**的类型：

  • S-if：if语句规则，这里的ll有两种取值in\rm in和out\rm out，表示当前语句块是否在循环内

Γ⊢e:intΓ⊢ls1:okΓ⊢ls2:okΓ⊢lif(e)s1s2:ok\frac{\Gamma\vdash e:{\rm int}\quad\Gamma\vdash_ls_1:{\rm ok}\quad \Gamma\vdash_ls_2:{\rm ok}}{\Gamma\vdash_l{\rm if}(e)s_1s_2:{\rm ok}}

  • S-break：

Γ⊢inbreak:ok\frac{}{\Gamma\vdash_{\rm in}{\rm break}:{\rm ok}}

  • S-S：语句连接规则

Γ⊢lsl:okUpdate(Γ,s1)⊢ls2:okΓ⊢ls1s2:ok\frac{\Gamma\vdash_ls_l:{\rm ok}\quad{\rm Update}(\Gamma,s_1)\vdash_ls_2:{\rm ok}}{\Gamma\vdash_ls_1s_2:{\rm ok}}

真正的类型系统还要比这复杂得多，需要对类型等价、类型推导、类型转换、多态、重载等进行判断，上面只是一个很简单的理论模型

类型检查程序的设计

借助翻译模式实现，具体地：

  • 将类型表达式作为属性值
  • 设计恰当的翻译模式
  • 可以用于实现类型系统

中间代码生成

语法制导的中间代码生成是通过翻译模式实现的中间代码生成，可以在语法分析时一遍完成语法分析、语义分析、中间代码生成

简单的中间代码生成基本就是进行指令选择和替换，但当代码涉及控制流转移和对应的布尔表达式短路求值时，问题会变得比较复杂

下面介绍两种基于翻译模式进行控制流和短路求值代码生成的思路

利用L-翻译模式的思路

在布尔表达式翻译时，对每个表达式非终结符EE定义继承属性true\rm true和false\rm false，分别表示此表达式为真和假时需要跳转到的位置

为什么需要是继承属性？因为表达式真值对应的跳转位置是根据表达式所属的父表达式或语句决定的，无法在表达式内部判断

而每个EE定义综合属性code\rm code表示其计算代码

基础的字面布尔值产生式如下：

E→false {E.code:=gen(′goto′E.false)}E\to {\rm false}\ \{E.\rm code := gen('goto' {\it E}.false)\}

E→true {E.code:=gen(′goto′E.true)}E\to {\rm true}\ \{E.\rm code := gen('goto' {\it E}.true)\}

这意味着，表达式计算出结果时会直接跳转至对应的目标标号，从而利用这个机制实现短路求值，例如

E→ {E1.true:=newlabel; E1.false:=E.false} E1∧E\to\ \{E_1.\rm true:=newlabel;\ {\it E}_1.false :={\it E}.false\}\ E_1\land

 {E2.true:=E.true; E2.false:=E.false} E2\ \{E_2.\rm true:={\it E}.true;\ {\it E}_2.false :={\it E}.false\}\ E_2

{E.code:=E1.code∥gen(E1.true ′:′)∥E2.code}\{E.\rm code:={\it E}_1.code \|gen({\it E}_1.true\ ':')\|{\it E}_2.code\}

这意味着：当E1E_1计算出false\rm false时，它会直接跳转至E.falseE.\rm false，从而跳过E2E_2实现短路求值

有了上面的表达式基础，实现条件语句就变得容易了：

S→if ( {E.true:=newlabel; E.false:=S.next} E )S\to \rm if\ (\ \{\mathit{E}.true:=newlabel;\ {\it E}.false := {\it S}.next\}\ {\it E}\ )

{S1.next:=S.next} S1 {S.code:=E.code∥gen(E.true ′:′)∥S1.code}\{S_1.\rm next:={\it S}.next\}\ {\it S}_1\ \{\mathit{S}.code:={\it E}.code\|gen({\it E}.true\ ':')\|{\it S}_1.code\}

这里对语句SS引入了继承属性next\rm next，表示其下一条语句的标号，此时如果EE求值为false\rm false，它将直接跳转至下一条语句的标号，否则继续执行S1S_1

继承属性next\rm next的定值和表达式的true\rm true很类似，以下面的语句连缀产生式为例：

S→{S1.next:=newlabel} S1 {S2.next:=S.next} S2S\to\{S_1.\rm next:=newlabel\}\ {\it S}_1\ \{\mathit{S}_2.next:={\it S}.next\}\ {\it S}_2

{S.code:=S1.code∥gen(S1.next ′:′)∥S2.code}\{S.\rm code:={\it S}_1.code\|gen({\it S}_1.next\ ':')\|{\it S}_2.code\}

对循环语句，问题会相对复杂，主要原因在于循环语句块的next\rm next的值需要仔细思考：

S→while ( {E.true:=newlabel; E.false:=S.next} E )S\to\rm while\ (\ \{\mathit{E}.true:=newlabel;\ {\it E}.false:={\it S}.next\}\ {\it E}\ )

{S1.next:=newlabel; S1.break:=S.next; S1.continue:=S1.next} S1\{S_1.\rm next:=newlabel;\ {\it S}_1.break:={\it S}.next;\ {\it S}_1.continue:={\it S}_1.next\}\ {\it S}_1

{S.code:=gen(S1.next ′:′)∥E.code∥gen(E.true ′:′)∥S1.code∥gen(′goto′ S1.next)}\{S.\rm code:=gen({\it S}_1.next\ ':')\|{\it E}.code\|gen({\it E}.true\ ':')\|{\it S}_1.code\|gen('goto'\ {\it S}_1.next)\}

这里的关键在于将S1.nextS_1.\rm next设置在了进入循环之前，同时在尾部生成goto\rm goto指令，这样即使是S1S_1块本身是一个条件语句，条件判假时也不会控制流错误

同时，为SS还引入了额外的继承属性break\rm break和continue\rm continue，用来表示当S1S_1内部出现break\rm break或continue\rm continue语句时的跳转目标

从上面的翻译模式中可以看出，编写翻译模式最重要的要点是完成所有属性的求值，具体地讲：

  • 首先需要明确每个非终结符有哪些属性，在上面的例子中，SS有继承属性next\rm next和综合属性code\rm code，EE有继承属性true\rm true，false\rm false和综合属性code\rm code
  • 在一个L-翻译模式的产生式中，必须在右端每个非终结符出现之前完成其继承属性的定值，并在产生式结束完成左端非终结符综合属性的定值
  • 具体定值逻辑根据语义决定，但不要漏掉任何一个属性，例如当为了实现循环引入了继承属性S.breakS.\rm break和S.continueS.\rm continue，以后每次在产生式右端遇到SS，都需要对此属性定值

改进为S-翻译模式：拉链与代码回填

L-翻译模式由于继承属性的存在，属性求值会比较繁琐，如果使用S-翻译模式，语义计算会变得简单很多

但带来的缺陷就是，翻译模式的设计会相应地复杂

考虑上面L-翻译模式中引入的所有继承属性，都是因为此属性表示的是此语句/表达式的某个跳转目标，而此跳转目标无法在语句/产生式内部确定，必须通过父节点确定后下传到子节点

鉴于所有继承属性都是跳转目标，如果我们在生成子节点代码时忽略跳转目标，将其暂时置空，等到父节点产生式归约时再进行跳转目标回填，就可以只用综合属性实现上面的语义

回忆L-翻译模式中的跳转目标确定思路：

  1. 在进入非终结符分析之前，将跳转目标传入其继承属性，这里的继承属性传入有两种形式：
    • 新值继承：传入一个newlabel\rm newlabel，此标号一般会被置于当前产生式对应语句片段的内部
    • 递归继承：传入一个产生式左端继承得来的标号，此标号被确定是在某个未知的祖先节点
  2. 当递归到叶子节点（例如字面的布尔值，或变量标识符、基本表达式）时，生成跳转代码，将继承属性填入跳转代码的跳转目标
  3. 从叶子结点开始一步步生成代码，将代码作为综合属性上传

可以看到，这里确定跳转目标的时机是进入非终结符前，生成跳转代码的时机是离开非终结符前

为了将其转化成S-翻译模式，我们将之前的继承属性E.trueE.\rm true、E.falseE.\rm false和S.nextS.\rm next以链表的形式定义为以下综合属性：

  • E.truelistE.\rm truelist：链表，包含了一系列会在EE为真时执行的跳转指令
  • E.falselistE.\rm falselist：类似
  • S.nextlistS.\rm nextlist：类似

然后将上面的跳转目标确定思路改变为：

  1. 离开叶子节点时，生成跳转代码，预留跳转目标为空，并将其装入跳转链
  2. 离开内部节点时，将可以确定跳转目标的子节点的跳转链回填，将无法确定跳转目标的子节点的跳转链上传，等待更进一步的祖先节点处理

为此，需要定义一些链表控制函数：

  • makelist(i)\rm makelist({\it i})：创建一个链表，该链表只有一个节点ii，ii是一条跳转指令的引用
  • merge(p1,p2)\rm merge({\it p}_1,{\it p}_2)：连接链表
  • backpatch(p,i){\rm backpatch}(p,i)：将链表pp内每条指令的跳转目标都设置为ii，即回填
  • nextstm\rm nextstm：下一条指令的地址
  • emit(⋯ )\rm emit(\cdots)：输出一条指令，并使nextstm\rm nextstm加11

首先引入一个空非终结符

M→ϵ {M.gotostm:=nextstm}M\to \epsilon\ \{M.\rm gotostm:=nextstm\}

对布尔表达式的求值变为如下（其中goto _\rm goto\ \_表示待填入目标的跳转指令）：

E→true {E.truelist:=makelist(nextstm); emit(′goto _′)}E\to \rm true\ \{\mathit{E}.truelist:=makelist(nextstm);\ emit('goto\ \_')\}

E→E1∧ME2 {backpatch(E1.truelist,M.gotostm);E\to E_1 \land ME_2\ \{\rm backpatch({\it E}_1.truelist, {\it M}.gotostm);

E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist)}E.\rm truelist:={\it E}_2.truelist;\ {\it E}.falselist:=merge({\it E}_1.falselist,{\it E}_2.falselist)\}

可以看出，这里的E.truelistE.\rm truelist实际代表的是一系列同跳转目标的指令的集合，这些指令能够到达当且仅当EE的取值为true\rm true

接下来，在进行语句翻译时，进行代码回填：

S→if ( E ) M S1 {backpatch(E.truelist,M.gotostm);S\to \rm if\ (\ {\it E}\ )\ {\it M\ S}_1\ \{backpatch({\it E}.truelist, {\it M}.gotostm);

S.nextlist:=merge(E.falselist,S1.nextlist);}\rm {\it S}.nextlist:= merge({\it E}.falselist,{\it S}_1.nextlist);\}

与L-翻译模式类似，这里S-翻译模式也有一些必须注意的问题：

  • 在每个产生式结束时，必须确定每个左端符号综合属性的值
  • 此外，由于这里的所有链表都是等待回填的代码片段，必须保证每个链表都得到回填，具体地：
    • 立即回填：如果在这个产生式里已经可以确定某个子节点的某个链表的跳转目标，那么将其回填
    • 延迟回填：否则，必须通过链表赋值或链表合并的形式使这个链表进入左端符号的某个链表，等待父节点回填

事实上，S-翻译模式的回填策略和L-翻译模式的继承属性定值策略是对应的：

  • 立即回填对应新值继承，说明此标号的值在此产生式中被确定，于是可以回填
  • 延迟回填对应递归继承，说明此产生式实际上只是传递了这个标号，但不知道此标号的具体值

正如L-翻译模式中每个继承属性都需要从新值继承和递归继承中选择一种策略，S-翻译模式中每个链表也必须选择立即回填或延迟回填