编译原理之学习 lua 1.1 笔记 (一)

原文地址：

下面开始第一部分: 如何研究 lua 1.1 虚拟机

lua 1.1 使用的是简单的堆栈式虚拟机, 加减乘除等运算都在堆栈中进行. 关于虚拟机的各种形式,
以后有机会仔细再研究.

lua1.1 的虚拟机代码 (下载展开后)在文件 opcode.c 中, 查找函数 lua_execute(Byte *pc)
即可找到. 下面用伪代码方式列出该函数(也即虚拟机的执行):

lua_execute(Byte *pc)  // pc 是代码开始的指令指针
  while (true) {
    switch (*pc++) { // 取得当前指令, 并递增指令指针(pc)
      case XXX: do XXX // 根据是 XXX 指令, 执行该指令...
      很多 case XXX ..., 指令 HALT 表示程序正常结束, 即 return.
    }
  } // 循环 while 结束

简而言之, 这个虚拟机如此的简单, 甚至可称简陋了(再次强调这是 1994 年的程序...)

指令大约有几十种, 这里不打算像字典一样列出所有指令, 并说明各个指令是如何运作的, 因为
学一遍字典的方法似乎不是很有效, 不能突出学习的重点. 为此, 我是打算按照小的功能来分别
研究在 lua 中是如何实现的, 这种方式来学习.

 

因此用案例方式, 从一个数学表达式开始, 研究其涉及的"全局变量" (gvar) 的情况:

   a = 12
   b = a + 34
   print (a, b)  --- 输出应为 12   46

 在第二个表达式 b=a+34 中, 从全局变量 a 中 "读取" 值 12, 经过一个运算(+, 加法), 与立即数 34
相加得到结果 46, 然后 "写入" 到全局变量 b 中. 因此下面研究全局变量相关的几个问题:

    1. 全局变量放在什么地方? (运行时布局问题)
    2. 对全局变量访问的指令是什么? (虚拟机及指令问题)
    3. 从词法器(lex), 到语法分析(parse), 如何生成全局变量(gvar)的读取/写入代码? (代码生成问题)
    4. 顺带说明数字立即数的相关指令(指令问题)

 

问题1: 全局变量放在什么地方? (lua 1.1)

全局变量存放在 lua_table[] 数组中, 该数组位于文件 table.c 中. 当使用 lua_findsymbol() 函数
查找一个标识符的时候, 如果已经存在, 则返回该符号在 lua_table[] 表中的索引; 否则添加一个
新的符号. 数组 lua_table[] 的元素类型为 Symbol, 该类型可形式化为三元组表示: 
  {symbol-name, tag, value}
其中 tag, value 实际为类型 Object, 表示一个对象的类型(tag)和值(value)的结构.

全局变量的值(tag, value) 即存放在此 lua_table[] 中, 其表也充当全局的符号表(symbol-table).
对全局变量的寻址可以通过一个 word 类型的索引 #gvar-idx 到表格 lua_table[] 寻址.

 

问题2: 对全局变量访问的指令是什么?

我们知道, 现在有了这样设计的全局变量, 已知是通过 word 类型的 #gvar-idx 索引可在程序内部
访问到全局变量, 对应的指令为:
   PUSHGLOBAL gvar-idx:word  --- 将第 gvar-idx 位置的全局变量的值压入堆栈中
   STOREGLOBAL gvar-idx:word --- 栈顶元素弹出, 并复制给第 gvar-idx 位置的全局变量

这里有一点点细微的问题, gvar-idx 是指令 push/store 的参数(立即数), 其是 word 类型的, 存在
字节对齐问题, 以及不同机器的 endian 问题. 对比 lua 1.0, 1.1 的代码, 取这种 word 立即数从 *pc
位置就略有不同.

   虚拟机中 case PUSHGLOBAL 指令实现:
     word w = get_word(pc);   // 取 word 的立即数, 其是全局变量在 lua_table[] 中的索引.
     *top++ = lua_table[w].object;   // 得到 lua_table[] 表中 w 位置的全局变量的值 object
          // top 表示堆栈顶部, 也即压入堆栈.

   虚拟机中 case STOREGLOBAL 指令实现:
      word w = get_word(pc); // 取 word 立即数, 同时增加 pc 指针
      lua_table[w].object = *(--top);  // 栈顶值出栈, 并赋值给全局变量 [w]

 

问题3: 全局变量的读写代码是如何生成的?

在 lua.stx (yyac) 文法文件中, 产生式 stat1 -> varlist1 '=' exprlist1 用于解析赋值语句,
我们以该产生及其相关子产生式为例子, 列出如下:

产生式P1: stat1 -> varlist1 '=' exprlist1 {代码块1}
产生式P2: varlist1 -> var {代码块2}
产生式P3: var -> NAME {代码块3}

在产生式 P3 中, 终结符 NAME 表示遇到一个标识符, 例如 "b", 对应代码块3为:
   Word s = lua_findsymbol(NAME)  // 查找 NAME 对应的符号,返回为索引
   int local = lua_localname(s)   // 查找是否是局部变量, 在研究全局变量的时候, 假设这里未找到
   if (local == -1)  // 是一个全局变量
      $$ = s+1        // 设置非终结符 var 的综合属性为 s+1 (一个大于 0 的值, 后面用到)

在产生式 P2 中, var 的综合属性(全局变量索引)被传递为 $1, 在代码块2中:
   varbuffer[nvarbuffer++] = $1    // 设置 varbuffer[] 数组中变量 nvarbuffer 
      // 的访问索引为 $1,即产生式 P3 中的 $$. 该值 > 0 表示全局变量.
   ... // 其它代码暂略

在产生式 P1 中, varlist1 为 $1, '=' 为 $2, exprlist1 为 $3, 代码块1 为:
   for (int i = nvarbuffer-1; i >= 0; --i)
      lua_codestore(i)  // 对 varbuffer[i] 所指的变量产生 "写入" 代码.
   ... 其它 codeadjust() 等代码暂时略.

 

在函数 lua_codestore(i) 中产生变量 STORE 代码, i 表示到 varbuffer[] 的索引:
   if (varbuffer[i] > 0)   // 该值在产生式 P2 中保存为变量的指示索引, > 0 表示是全局变量.
      产生代码: STOREGLOBAL (varbuffer[i]-1)   即存入全局变量的指令
   其它代码(如局部变量, 索引变量等)暂时略

 

同样, 在 exprlist1 系列的产生式中, 有对 gvar 读取的代码生成, 兹举例如下:
   exprlist1 -> expr {代码略} | ...
   expr -> ... | var {代码块1} | ...

在产生式 expr -> var 中, 代码块1 中:
    lua_pushvar($1) // $1 指 var.$$, 是变量的索引, 上面已经描述过
    $$ = 1   // 现在略(可能是表示是否需要堆栈 adjust 的)

在函数 lua_pushvar(i) 中, i 是变量索引:
   if (i > 0)  // 大于 0 表示是全局变量
      产生代码: PUSHGLOBAL (i-1)     即读取全局变量的值到栈顶的指令
      ntemp++   // 栈的使用量+1, ntemp 用于跟踪栈使用深度
   其它访问局部变量, 索引变量的暂时略.

 

这里略去的一个重要问题: lua 支持多个变量赋值, 例如 a,b,c = 12,34,'56'; 这里仅选择了
单个变量赋值的产生式形式, 以便于说明全局变量的读写代码生成. 多变量涉及 varbuffer[] 数组.

 

最后, 语句 b = a + 34 产生的代码为(设 a 的值为 12):
  PUSHGLOBAL a    全局变量a的值入栈, 此时堆栈为: [12   )
  PUSH 34              立即数 34 入栈, 堆栈为: [12, 34    )
  ADDOP                执行加法, 弹出 12,34, 加法后值入栈为 [46    )
  STOREGLOBAL b   栈顶值存入全局变量 b, 堆栈空 [     )

 

这里额外顺便说明入栈立即数(数字的)指令:

   PUSHBYTE byte --- 将一个字节立即数压入堆栈
   PUSHWORD word --- 将一个 word 立即数压入堆栈
   PUSHFLOAT float --- 将一个 float 立即数压入堆栈

当年可能没有 double, 或者 double 不太流行吧...

另, 几个常用数字 0,1,2 当做立即数入栈的指令, 应是为了减少代码大小:
   PUSH0  --- 立即数 0 入栈.
   PUSH1, PUSH2 --- 分别是立即数1,2 入栈.

Lua 这个麻雀虽小, 还是有一些适当的优化的!

log/186280