看看lua是怎么做的 -- 系列 <一> faTe 编程珠玑 2019-01-23 访问: 102 次 从低版本lua逐渐入手，追寻设计思想演化过程。 <!--more--> [TOC] #前言 lua 最初版本为 1.0, 其中词法分析与语法分析部分均使用外部工具生成`< Lex & Yacc >` 由于 1.0 版本并未发布，所以跳过该版本。 从 1.0 到 1.1，主要工作为 重写了 lex.c, 修改了 hash.c 中的部分。 #总览 文件概览 > floatingpoint 空文件 hash模块 提供变长数组支持 inout模块 主要为文件操作，并给 opcode 模块提供支持 iolib 运行库 为lua语言提供文件io支持 lex模块 词法分析器 lua模块 入口 lualib 为公共头文件 mathlib 运行库 为lua语言提供数学<科学>计算支持 mm模块 未实现 opcode模块，核心模块，提供虚拟机 strlib 运行库 为lua语言提供字符串操作支持 table模块，核心模块，为编译提供符号表 y.tab模块，核心模块，由yacc生成，提供语法分析 ##lua.c 在 `main` 函数中，首先加载运行时库，这个放在后面， 下面提供了两种使用方式: 1. `lua_dostring` 2. `lua_dofile` 顾名思义，一种是从控制台输入流中执行，一种从文件加载lua源码运行。 二者均实现于 `opcode.c` 中, 进一步调用 `inout.c` 中真正的文件io。 `lua_openfile` 和 `lua_openstring` 其核心是调用了位于 `lex` 模块中的 `lua_setinput`, 类似于适配器模式，将两种接口抽象为一致。 原本接下来是应该看语法解析部分，但是由于该代码由yacc直接生成，这里就不提了。 有兴趣可以阅读 `lua.stx`。 ##lex.c 按照正常路线是语法分析器驱动词法分析器，由于跳过语法分析部分，这里直接就到达了词法部分了。 结构 reserved 内存放了当前版本的保留字， 其中token属性字段为位于 `y.tab.h` 文件中的枚举。 宏 `RESERVEDSIZE` 是一个求数组元素个数的算法。 `findReserved` 是一个简易的保留字识别函数。 `yylex` 为词法分析器核心，该函数是一个简易的自动机。 `yytextLast` 和 `yytext` 是一个有趣的组合，模拟了一个变长字符串(当然存在最大字符个数限制),不过代码中并未限制，也就是说存在溢出风险。 该词法分析器思路简单，略臃肿。 另外 虽然存在保留字 `debug`,但是并没有感觉到实用性。 从上到下依次是: > 空白符 调试符号 < $debug | $nodebug > -- 注释一行 逻辑运算符 字符串 < while (current != del) 配对 > 标识符 | 保留字 连接符 | 小数 整数 | 指数计数 其中四则操作符，赋值符，负号等在语法分析器中识别。 ##inout.c 这个函数本身是负责的文件io工作，同时也牵扯部分调试工作， 其中 `funcstack` `nfuncstack` `lua_error` `lua_pushfunction` `lua_popfunction` `lua_reportbug` 均与调试有关， 在 opcode 中存在名为 `SETFUNCTION` 的指令将`函数符号序列号`及`文件符号序列号`压入栈，而 `RESET` 指令则是清理该栈。 一种类似调用栈的处理方式，在进出一个函数时会根据 `lua_debug` 来决定是否操作该栈。 根据`函数符号序列号`和`文件符号序列号`取出的符号名会作为`lua_reportbug`的参数，以供得到更为详细的错误信息。 在 `lua.stx` 239~283 部分，我们可以窥得该指令生成过程。 由于足够简单， 这里不细分析了。 ##hash.c 首先看其头文件中的两个结构 ```c typedef struct node { Object ref; // 引用方式 key Object val; // 值 value struct node *next; } Node; typedef struct Hash { char mark; unsigned int nhash; Node **list; } Hash; ``` 另外c文件存在一个结构 ```c typedef struct ArrayList { Hash *array; struct ArrayList *next; } ArrayList; ``` 以及 opcode.h 中的 这两个结构体是构成 hash表的核心结构，同时 在 Hash 中存在字段 mark，表明这里实际已经出现了GC的雏形。使用的标记清除法。 ```c Hash *lua_createarray (int nhash); // 创建 Hash节点,并串接至 ArrayList void lua_hashmark (Hash *h); // 标记 hash 并检查 其成员 void lua_hashcollector (void); // 垃圾收集器 Object *lua_hashdefine (Hash *t, Object *ref); // 根据引用判断是否存在与之对应的 node节点, 存在则返回对应的val //，不存在则构造 void lua_next (void); // 获取下一个元素，并替换当前栈上元素 ``` 其中还包含有几个内部函数，略简洁，后文我将提供一个使用示例，以便理清该结构的运作过程。 该模块主要提供 lua 以 变长数组(关联数组)支持。 ##table.c 各类静态表 从上到下能看到 `符号表` `字符串表` `文件表` 其中值得注意的是 `lua_pack` 函数会在 `lua_createstring` 中被调用， `lua_pack` 会标记出栈上和符号表中在使用的字符串或数组，同时回收掉未标记字符串或数组。 另外 全局变量 库函数 和 内置函数的存储方式略有不同。 全局变量 和 库函数 通过栈传递 到符号表, 是运行时构造，使用堆内存。 内置函数，如 `print` 是静态构造，使用静态区内存。 其中 `tablebuffer` `searchlist` `ua_table` 均指向同一块内存。 `searchlist` 为了方便迭代寻址。 需要提的是 `lua_ntable` 只能自增，却无法减少。故不能出现过多的全局字符串，否则很容易到达 `MAXSYMBOL` 而导致溢出。 符号表中仅记录了全局变量，而局部变量记录于局部的符号表中，在语法分析阶段完成<此时代码也基本生存完成>后即抛弃。 ##opcode.c 最后来谈一下 `opcode` 模块， 其虚拟机的核心模块。 一般来说 解释型语言分为两大部分，一是解释器，二是虚拟机，当然，本人水平有限，不讨论性能问题，单单简单阅读其指令集和运行思路。 虚拟机部分是整个代码最复杂的部分之一，好在由于是初级版本，选用的是栈式虚拟机，故没有过于高深复杂的算法。 `int lua_execute (Byte *pc);` 重点需要观察的函数。 `int lua_parse (void)` 是语法分析器的核心部分，兼顾了代码生成职责，在生成完成后，为了保证生成指令的正确性会调用上述函数。 ```c function _() end CODE 1 ADJUST 0 3 RETCODE 0 CODE 0 HALT ``` lua中并不存在入口函数，会以一种线性方式执行全局区语句 需要说明的全局代码存放于 `initcode` 中，而函数的代码存放于各函数自身 `object` 的 `b` 成员所指向的数组中。 尝试调用该函数，结果如下 ```c _() CODE 0 PUSHGLOBAL 7 3 PUSHMARK 4 CALLFUNC 6 ADJUST 0 7 HALT ``` `PUSHGLOBAL` 指令会将一个 `function` 对象压入栈中，虚拟机在仿真 `CALLFUNC`指令时，会将当前指令的下一条指令地址与栈上对象的`b` 成员交换，以实现记录返回地址操作。而在调用`cfunction`时，则不需要记录返回地址，但是需要对返回值做处理同时需要修正栈。 lua栈以对象作为其最小粒度，每一个对象可以代表一个任意类型，函数也是一种对象。 关于 `PUSHLOCAL0` `STORELOCAL0` `PUSH0` 等宏的作用均是为了简短生成的指令，当大于宏限定值时，会使用双字节指令代替。 其他的指令模拟过程都较为简单，此处不一一解释。 #Hash模块 hash 模块可以认为是这份代码的核心数据结构体之一，具体应用如下。 ```c // lua_Hash.c #include "opcode.h" #include "hash.h" #include <stdio.h> #include <assert.h> int main() { // temp Object * t = NULL; // 初始化一个数组 Object array = { 0 }; Object ref = { 0 }; array.tag = T_ARRAY; // 默认创建 101个，最少创建 1个 /* array = @(1) */ array.value.a = lua_createarray(1); ref.tag = T_NUMBER; ref.value.n = 0; /* array[0] = 1 */ t = lua_hashdefine(array.value.a, &ref); assert(t); t->tag = T_NUMBER; t->value.n = 1; printf("array[0] == %f\r\n", lua_hashdefine(array.value.a, &ref)->value.n); /* array['0'] = 100 在lua中 ' " 同义 */ ref.tag = T_STRING; ref.value.s = "0"; t = lua_hashdefine(array.value.a, &ref); assert(t); t->tag = T_NUMBER; t->value.n = 100; printf("array['0'] == %f\r\n", lua_hashdefine(array.value.a, &ref)->value.n); /* 演示迭代 r,v = next(array,nil) while r ~= nil do print ("array["..r.."] = "..v) r,v = next(array,r) end */ ref.tag = T_NIL; ref.value.n = 0; lua_pushobject(&array); lua_pushobject(&ref); lua_next(); Object * v = lua_pop(); Object * r = lua_pop(); while (1) { lua_pop(); lua_pop(); printf("v %f\r\n", v->value.n); lua_pushobject(&array); lua_pushobject(r); lua_next(); // 需要注意的是 lua_pushnil 函数并不会改变栈 // 而是直接修改了当前参数 if (r->tag == T_NIL) break; v = lua_pop(); r = lua_pop(); } lua_pop(); lua_pop(); } ``` 执行结果: ``` array[0] == 1.000000 array['0'] == 100.000000 v 100.000000 v 1.000000 ``` #总结 本文只是从整体上简要分析了 lua 1.1 版本的实现，由于没有仔细阅读词法分析器及代码生成部分，并不能很好解读其实现。 其中的 `opcode` 部分也只是挑选了几个较为复杂的指令说明。 `lua.lex` `lua.stx` 实际上是推荐一读的，`lua.stx` 中涉及了代码生成，但是介于篇幅问题，没有办法拿出来一一分析。 另外运行时部分并没有能够说明，只要能从高的层面理解该版本虚拟机的 pc 及 对象栈 是怎么工作的，那么阅读起来也较为容易。 总体来说算是囫囵吞枣的过了一遍，在系列后续没有使用 yacc 的词法分析器而是自行构造词法分析的版本中，再来重新理一理代码生成的思路 及 整体的指令设计思路。 #附件 [lua-1.1.rar](http://www.holdheart.com/usr/uploads/2019/01/3524003153.rar) #参考 [SEMISH'94 paper](http://www.lua.org/semish94.html) 本文由 faTe 创作，采用 知识共享署名 3.0，可自由转载、引用，但需署名作者且注明文章出处。
还不快抢沙发