语义分析 sematic analysis

之所以叫做符号表,而不是"字符串"表, 是因为这个表的key不单单是一个字符串. 字符串在计算hash值, 测试相等性, 比较两个字符串的大小上是低效的.(线性时间,因为要遍历每个字符)

因此要创建一个符号类型, 并用它作为key.这样的表叫做符号表.

每当进入一个新的作用域时, 将当前的符号表复制一份作为当前scope的符号表.并将旧的保存下来. 每当下面遇到一个声明, 将其添加到符号表.

当离开一个scope后, 将保存的符号表恢复为当前符号表.

1. 用符号表实现"环境"

   使用存放scope(符号表)的 Stack

   enter_scope(): 创建并push一个新的scope 
   exit_scope(): 离开pop当前scope
   
   find_symbol(x): 从栈顶的scope中开始寻找符号x
   add_symbol(x): 将符号x加入当前的(栈顶)scope
   check_scope(x): 检查x是否在当前(栈顶)scope中存在定义, 用于防止在同一scope发生重定义
   

   例如在C++这样的语言中, 可以先使用一个未定义但已经声明的标识符.(class的forward声明), 将其具体定义写在使用处的后面. 因此这样的语法无法通过遍历一次AST就能解析完所有的符号使用.因此至少需要两次遍历: 第一遍, 收集所有scope中的 声明 第二遍, 用符号表来解析使用.

所谓函数是一段代码, 位于代码段, 是只读的. 但是每个函数被调用时都包含着对应当前实例的特有数据: 入参, 局部变量, 中间结果 … 这些数据是运行时动态创建的, 不能放在代码段中. 因此需要有某种数据结构来管理每个函数调用对应的特有数据.这种结构就是栈stack.

一门语言中的函数的语法决定了如何实现函数调用. 比较复杂的函数实现就是所谓的高阶函数: 入参和返回值都可以是函数. 并且为了支持能够返回一个函数对象, 语法也必须支持嵌套的函数定义. 这些函数的特性增加了实现的难度:

let myfunc x = 
  let
    bar y = x + y 
  in 
  bar 
;;

# let bar =myfunc 2 ;;
val bar : int -> int = <fun>

为了实现上的简单, 暂时不考虑返回一个函数对象的情况. 仅允许嵌套函数定义.

这里的栈不是标准的栈 – 仅支持push/pop/peek. 因为要访问变量, 因此要实现为数组.并用一个指针来标记栈顶, 即栈指针sp. 这个数组是从高地址向低地址方向生长的.就像山洞中的钟乳石.

存放于栈的每个函数调用对应的特有数据被称为一个frame. 一个栈帧中通常包含这些部分: 入参,函数内声明的局部变量,返回地址,计算的中间结果,保存的寄存器.

某些局部变量不放在寄存器中, 而是存放于stack中, 这些被占用的寄存器可能会与该函数调用的其他函数相冲突. 因此需要将其保存栈中.

int foo(int x , int y)
{
  int temp = x + 1;
  int temp2 = x - y ;
  return temp * temp2 ;
}

foo:                                    # -O0
        pushq   %rbp            # 保存帧指针 
        movq    %rsp, %rbp      # 
        movl    %edi, -4(%rbp)  # x
        movl    %esi, -8(%rbp)  # y
        movl    -4(%rbp), %eax  # x
        addl    $1, %eax        # x+1 
        movl    %eax, -12(%rbp) # x+1 -> temp 
        movl    -4(%rbp), %eax  # x
        subl    -8(%rbp), %eax  # x - y 
        movl    %eax, -16(%rbp) # x - y -> temp2  
        movl    -12(%rbp), %eax # temp
        imull   -16(%rbp), %eax # temp * temp2 -> return value 
        popq    %rbp            # 恢复 帧指针 
        retq

int foo(int x , int y){
  //char a = 0;
  int temp = x + 1;
  int temp2 = x - y ;
  return temp * temp2 ;
}

/* Type your code here, or load an example. */
int  __attribute__((noinline)) square() {
  char aa = 'a' ;
  long long le = 0;
  long long hi = 12;
  long long le1 = 0;
  long long hi1 = 12;
  long long le2 = 0;
  long long hi2 = 12;
  //foo(3,7); 使得 square()  是否为叶子过程 
  return le + hi;
}
struct foo { // > 16 字节, 在栈中要为其分配 32 字节. rsp -= 32  
  int i;
  long long l;
  long long ll;
};

int main() {
  struct foo myfoo;
  myfoo.i = 100;
  //square(); 使得 square()  是否为叶子过程 
  return 0;
}

// rsp 增长 按16字节对齐.

// 叶子过程可以不为其分配栈帧, 可直接使用 rbp - N 处的内存. 栈顶之外的128 字节都可以使用. 

  foo:                                    # @foo
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        movl    -4(%rbp), %eax
        addl    $1, %eax
        movl    %eax, -12(%rbp)
        movl    -4(%rbp), %eax
        subl    -8(%rbp), %eax
        movl    %eax, -16(%rbp)
        movl    -12(%rbp), %eax
        imull   -16(%rbp), %eax
        popq    %rbp
        retq
square:                                 # @square
        pushq   %rbp
        movq    %rsp, %rbp
        movb    $97, -1(%rbp)
        movq    $0, -16(%rbp)
        movq    $12, -24(%rbp)
        movq    $0, -32(%rbp)
        movq    $12, -40(%rbp)
        movq    $0, -48(%rbp)
        movq    $12, -56(%rbp)
        movq    -16(%rbp), %rax
        addq    -24(%rbp), %rax
        popq    %rbp
        retq
main:                                   # @main
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $0, -4(%rbp)
        movl    $100, -32(%rbp)
        xorl    %eax, %eax
        popq    %rbp
        retq

let f x =
  g x
;;

   高
 ______
| f的  |
| 栈帧 |
|______|
| g的  |
| 栈帧 |
|______|

   低

let myfunc x = 
   let
     bar y = x + y 
   in 
   (bar 100)
;;

高阶函数 -> 嵌套定义的函数 -> 逃逸变量(内存中) -> 静态链访问

    Semant 
  TRANSLATE    接口 
  Translate    实现
FRAME    TEMP  接口
Frame    Temp  实现

在语义分析阶段之前, 先对AST调用 FindEscape 将是否为逃逸变量标记好.

函数声明:

Semant.transDec -> Translate.newlevel -> Frame.newFrame

Frame 层不知道静态链的存在, 而上层的 Translate 负责静态链的分配.

局部变量声明:

Frame.access 代表了变量存放的位置: 内存/寄存器?

Translate.access 比它多了level信息

Semant + lev -> Translate.allocLocal lev esc -> Frame.allocLocal ==> 返回 access

函数中可以有局部变量. 每次函数调用都会创建一份其局部变量的实例.

Tiger编译器的栈帧

栈帧的接口:

module type FRAME = sig
  type frame
  type access

  val newFrame: {name:Temp.label,formals:bool list} -> frame
  val allocLocal: frame -> bool -> access

  val name: frame -> Temp.label
  val formals: frame -> access list
  ...
end

module type FRAME =  sig
  type register = string
  val RV: Temp.temp (*p. 168*)
  val FP: Temp.temp (*p. 155*)
  val registers: register list
  val tempMap: register Temp.Table.table
  val wordSize: int (*p. 155*)
  val externalCall: string * Tree.exp list -> Tree.exp (*p. 165*)

  type frame (*p. 134*)
  val newFrame: {name: Temp, label, formals: int} -> frame * int list  (*p. 135*)
  val formals: frame -> access list (*p. 135*)
  val name: frame -> Temp.label (*p. 134*)
  val allocLocal: frame -> int (*p. 137*)
  val string: Tree.label * string -> string (*p. 262*)
  (* (L3,"hello") ==> "L3: .ascii "hello" \n" *)
  val procEntryExitl: frame * Tree.stm -> Tree.stm (*p. 261*)
  val procEntryExit2: frame * Assem.instr list -> Assem.instr list  (*p. 208*)
  val procEntryExit3 : frame * Assem.instr list -> (*p. 261*)
{prolog: string, body: Assem.instr list, epilog: string}

  type frag = PROC of { body: Tree.stm, frame: frame}  (*p. 169*)
    | STRING of Temp.label * string
end

特定的目标机器:

module MipsFrame : FRAME = struct
  ...
end

实现:

module Frame : FRAME = MipsFrame ;; 

创建一个新的栈帧对象:

Frame.newFrame { name=g; formals= [true;false;false] };;

module MipsFrame: FRAME = struct
  ...
  type access = InFrame of int
      | InReg of Temp.temp 
  ...
end

Frame.allocLocal f true ;;
(* 返回一个 Frame.access of InFrame 类型的值 *)

module FIND_ESCAPE = sig
  val findEscape: Absyn.exp -> unit
end

module FindEscape : FIND_ESCAPE = struct
  type depth = int
  type escEnv = (depth * bool ref) Symbol.table (* symbol --> (嵌套层级深度, 是否为逃逸变量) *)

  let traverseVar (env:escEnv) (d:depth) (s:Absyn.var) : unit = (* ... *) ;;
  and traverseExp (env:exvEnv) (d:depth) (s:Absyn.exp) : unit = (* ... *) ;;
  and traverseDecs (env:exvEnv) (d:depth) (s:Absyn.dec list) : escEnv =  (* ... *) ;;

  let findEscape (prog: Absyn.exp) : unit = (* ... *) ;;
end

当在静态函数嵌套深度为 d 处发现了一个 变量声明 / 形参声明, 例如:

VarDec {name=symbol("a"); escape=r; (* ... *)} 

则将类型为 bool ref 的值设为 false. 将绑定 "a" -> (d,r) 加入到环境(escEnv)中.

这个新环境被用在和这个变量处于同一作用域中的表达式中. 每当发现了符号 a 在深度大于 d 的地方被使用, 就将其绑定中的 r 设为 true.

temp 是局部变量的抽象名字. label 是静态内存地址的抽象名字.

模块 Temp 管理着两个不同名字的集合.

module type Temp = sig

  type temp
  module Table = Map.Make(temp)  (* 其中Table的key是temp类型的 *)
  val newtemp : unit -> temp
  val makestring : temp -> string

  type label = Symbol.symbol
  val newlabel: unit -> label
  val nemedlabel : string -> label

end

module type TRANSLATE = sig 
  type level  
  type access (** 和Frame.access不同,多了level这一信息. *)
  val outermost : level

  val newLevel: {parent: level; name:Temp.label; formals: bool list} -> level
  val allocLocal: level -> bool -> access
end


module Translate : TRANSLATE = struct
  ...
  type access = level * Frame.access  (* <<=!! *)
  ...
end
  ;;

语义分析阶段中的 transDec 通过调用 Translate.newLevel 为每个函数声明创建一个新的嵌套层级. 这个函数又调用 Frame.newFrame 创建了一个新的栈帧. Semant 将 level 保存在此函数的 FunEntry 数据结构中, 使得每遇到一个函数调用时, 可以将被调用函数( FunEntry )的 level 字段传回 Translate 模块. FunEntry 也需要函数的机器代码的入口处作为 label 字段.

module type Env = sig
  (** 新版本的VarEntry和FunEntry : *)
  type enventry =
  VarEntry of { access:Translate.access; ty:ty }
    | FunEntry of {
    level: Translate.level;
    label: Temp.label;
    formals: ty list;
    result: ty
  }

  ...
end

当 Semant 处理一个位于层级为 lev 的局部变量时, 它会调用 Translate.allocLocal lev esc 在本层级中创建一个变量. 参数 esc 表示是否是逃逸变量. 其返回结果为 Translate.access, 这是一个抽象数据类型(但不同于 Frame.access, 因为它必须包含关于静态链的信息). 之后, 当变量在一个表达式中被使用时, Semant 可以将其 access 传回 Translate , 以便于生成访问此变量的机器代码. 与此同时, Semant在值环境中记录着每个 VarEntry 中 access .

抽象数据类型 Translate.access 可以被实现为变量的level和其 Frame.access 的偶对:

type access = level * Frame.access

使得 Translate.allocLocal 能调用 Frame.allocLocal, 并且还可以记住变量是位于哪个层级的. 层级信息稍后在计算静态链时要用到, 变量可能从一个不同的层级中被访问.

Frame 应该独立于被编译的特定语言.许多语言没有嵌套的函数声明.因此Frame不应包含关于静态链的信息, 这是 Translate 的责任. Translate 知道每个栈帧包含着一个静态链. 静态链用寄存器被传给一个函数, 并将其存储到栈帧中.因为静态链表现得如此接近于一个形式参数, 我们将它看成是一个形参. 对于一个有着k个正常参数的函数,令 l 是标识其参数是否为逃逸变量的bool列表.则: l' = true::l 是一个新的list. 额外的true标识着静态链这个额外参数是逃逸的. 于是 newFrame(label,l') 创建了一个包含额外参数和其形参的栈帧.

例: 函数 f(x,y) 被嵌套在函数 g 中.并且g的level被记为 lev_g. 于是 Semant.transDec 可以调用:

Translate.newLevel {parent=lev_g;name=f;formals= [false;false] }

并假设 x,y 都不是逃逸变量.于是 Translate.newLevel 为形参的 bool 列表又加了一个元素:

Frame.newFrame { label, [true;false;false] } 

它会返回一个 frame . 在这个 frame 中,有三个栈帧偏移类型的值, 可以通过 Frame.formals(frame) 来访问. 返回值的首个元素是静态链在栈帧中的偏移量, 其它两个是参数 x, y 的偏移量.当 Semant 调用 Translate.formals(level) 时 , 它会得到这两个偏移量,并将其转换为 access 类型的值.

对层级保持追踪

每次对 Translate.newLevel 进行调用, Semant 必须传递外面这层的 level 值. 当为Tiger程序的main创建level时, Semant应当传递一个特殊的 level 值: Transale.outermost . 它不是Tiger的main函数的level, 而是包含了main的过程的level.所有库函数位于这个 outermost 层级.

函数 transDec 会为每个函数声明创建一个新的level, 但必须将外围函数的level传给newLevel. 这意味着 transDec 中必须包含了当前level的信息.

实现这点是很容易的, 为transDec增加额外的参数, 代表了当前的level. 并且也为transExp增加一个level参数, 这样当遇到一个函数声明时便可将level传递给 transDec.

transVar 也需要添加一个表示当前level的参数, 因为要通过计算level的差来决定访问几次静态链.