Lua源码剖析（六）词法分析

发表于   |   更新于 | 分类于 | | 访问次数： 次
字数统计: 4k | 阅读时长 ≈ 15

一. 简介

  前文中，我们先后介绍了Lua总体设计的思路，栈结构体及执行逻辑，基本数据结构极其实现，虚拟机的执行逻辑等，但是尚未涉及到脚本如何加载并转化为一个一个的字节码从而执行的过程。本文就此进行分析讨论。脚本语言的编译可以分为词法分析、语法分析阶段。词法分析阶段顾名思义就是将脚本加载并进行解析，分解为一个一个的基础的词并保存起来，由于后面的语法分析使用。而语法分析就是分析解释这些词的合理性及逻辑，并生成对应的字节码。这些字节码则将交给虚拟机去挨个执行，从而实现脚本的逻辑功能。

二. 基础结构体

  词法分析的大致功能包括了加载、解析，因此其总的状态管理类至少需要包括：

  • 文件名、当前读取的字符、行号
  • 一个用于保存当前已读取的内容的缓存Buffer，读取完毕之后才转化为一个词，即token。这里缓存区可以预先申请一块大小，然后记录当前用了多少以及总大小，如果全部用尽还没有完成一个token的读取，则重新分配缓冲区。
  • 当前的token
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Buffer
{
    void* buff;
    int   nUsedSize;
    int   nBuffSize;
}

struct LexState
{
    TString* FileName;
    int nCurrent;
    int nCurrentLine;
    Buffer *buf;
    Token t;
}

  除此之外，读取的文件如果一次性全读完或者按字节来读和操作，效率均会有所影响，比较合适的是建立一块缓冲区域，每次从缓冲区域读取，缓冲区用尽则从文件继续读。除了缓冲区的数据块pData以外，尚需要一个指针指向当前读的字符，以及一个变量来存储还剩多少字节可读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct FileIO
{
    int nUnreadSize;
    char* pCurr;
    void* pData;
}

struct LexState
{
    TString* FileName;
    int      nCurrent;
    int      nCurrentLine;
    Buffer*  buf;
    FileIO*  pIO;
    Token    t;
}

  现在我们有了文件缓冲区，当前token的状态及读取缓冲区，但是我们还需要一个很重要的东西：当前函数的信息记录。lua脚本设计为多级函数的关系，而整个文件初始就是一个函数。前文中我们已经详细叙述了闭包Closure和函数原型Proto，而文件解析编译的任务中自然也包括了Proto的新建和填充，供以最终生成Closure以及执行Proto中的众多指令。

  这里当然可以直接再LexState中加入Proto链表，后续语法解析完，实际调用函数的时候生成Closure并装载对应的Proto从而执行。但是在词法、语法解析的过程中，我们需要存储诸多的中间变量以及当前的状态信息，这些东西用一个结构体来统一保存，并在Proto成功解析完成后清除。我们取名为FuncState。

  所以这里我们主要关心的是，在词法解析过程中需要哪些中间变量来存储状态呢？

   首先肯定需要一个Proto，作为最终存储的函数内容，然后就是Proto对应的一些记录

  • 函数中的常量（如数字、字符串和其他不可变值），需要集中存储，当然也就是一个Table
  • 常数、内部嵌套Proto以及局部变量的数量当然也要记录
  • 上值的记录：关于Proto的上值我们需要记录其属于常量还是属于变量，以及对应的索引，所以单独建立一个数据结构upvaldesc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct FuncState
{
    Proto* p;
    Table* h;
    int nk;
    int np;
    int nlocvars;
    upvaldesc upvalues[LUAI_MAXUPVALUES];
}

typedef struct upvaldesc {
  lu_byte k;         //类型判断
  lu_byte info;      //索引
} upvaldesc;

   然后需要考虑翻译为字节码的过程中，需要记录的东西

  • 首先当然要记录当前所在的解析位置pc以及上一步解析的位置lasttarget
  • 目前空闲的寄存器freereg也要记录，便于生成字节码的时候使用
  • 解析的过程中有着众多的代码块，需要详细记录，因此单独新建结构体Block
    • Block以链表bl形式记录保存的多个代码块
    • Block内部至少需要保存跳转点信息、以及局部变量/上值相关的标记
    • Funcstate记录当前所处代码块使用的局部变量数nactvars
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct FuncState
{
    Proto* p;
    Table* h;
    int nk;
    int np;
    int nlocvars;
    upvaldesc upvalues[LUAI_MAXUPVALUES];    
    int pc;
    int lasttarget;
    int freereg;
    Block* bl;
    short nactvars;
}

struct Block
{
    struct Block *previous;  /* chain */
    int breaklist;  /* list of jumps out of this loop */
    lu_byte nactvar;  /* # active locals outside the breakable structure */
    lu_byte upval;  /* true if some variable in the block is an upvalue */
    lu_byte isbreakable;  /* true if `block' is a loop */   
}

  回头再来看Token。所有的词，都可以解释为一个类型及其对应的数据，即如下形式。

1
2
3
4
5
struct Token
{
    int nType;
    void* data;
}

  根据前文中已经封装的数据类型，这里的data我们可以替换为一个联合，即要么是数字，要么是字符串。这样简单的结构体就足够表达所有可能读到的词了。

1
2
3
4
5
6
7
8
9
10
11
union SematicInfo
{
    lua_Number r;
    TString *ts;    
}

struct Toke
{
    int nType;
    SematicInfo data;
}

  至此，我们基本上有了词法解析需要的一些数据结构，下面需要做的事是确定词法解析的逻辑流程。

三. 解析逻辑

  词法解析最重要的就是将整个脚本解析成一个一个的token，所以最重要的函数就是解析分割token的函数，我们称之为next()。加载并解析一个脚本文件的整体流程应该包括：

  • 初始化解析结构体LexState
  • 初始化函数结构体FuncState
  • 调用next()解析第一个token
  • 重复分析token->取下一个token，直至文件结束
  • 返回Proto并新建Closure存储

初始化操作较为简单，挨个赋值即可，核心在于next()如何解析。毫无疑问，这里需要读取字符串，以一定的规则（空格、换号、特定符号）作为分割，然后对字符串通过switch来进行不同的处理，大致可以包括如下几类

  • 预定的符号
  • 数字
  • 字符串

预定的符号需要包括

  • 文本格式相关，如空格、换行、文件结束符等
  • 标记符，如注释、字符串、下划线等
  • 操作符，如表的操作符. [ ]:、数字的加减乘除、字符串连接等

除了符号之外的，数字直接读取多位直至操作符结束，字符串同理。当读取完成且没有问题，则返回此次读取的token类型，并保存seminfo。完成了token的读取后，就需要进入下一阶段：对token的解析分析。

这里涉及到一个概念：代码块。一个函数当然是一个代码块，函数中多级调用可以视为多级代码块，而一个脚本本身，也可以是做一个代码块，所以脚本本身定义的函数、变量，相当于是在一个大的隐藏函数内部进行的定义。因此对各种代码块，均可以用统一封装函数解析，我们取名chunk()。

chunk()的主要逻辑应该是在一个代码块中，不停的读取token，并且解析当前token，根据token类型选择不同的处理方式，该处理逻辑取名为statement()，大致逻辑如下

1
2
3
4
5
6
7
8
9
10
11
12
static void chunk (LexState *ls) {
  /* chunk -> { stat [`;'] } */
  int islast = 0;
...
  while (!islast && !block_follow(ls->t.token)) {
    islast = statement(ls);
    testnext(ls, ';');
...
    ls->fs->freereg = ls->fs->nactvar;  /* free registers */
  }
...
}

下面需要考虑的就是如何去根据token的类型进行相应的处理。

首先我们要对token进行一个分类：

  • 逻辑控制，如条件、循环等
  • 声明，如函数、局部变量等
  • 跳转，如返回、打断等
  • default，包括如TK_NAME等的表达式、上值等的判断处理。

说到这里，不得不说一下lua采用的语法规则范式：EBNF范式（扩展巴科斯范式）。其中::=表示定义，左边的符号可以被右边的符号所替换。|符号表示或的意思，也就是说左边的符号，可以通过|符号左边或者右边的符号来代替。被“”包起来的字符，就是我们实际会显示的字符。被{}包起来的，表示它可以重复0次或者多次。包含在[]内的内容，表示可以被省略或者只出现一次。

下面所列的就是lua的全部规则内范式，在token的解读时，就需要依据这些范式来检查是否符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
chunk ::= {stat [`;´]} [laststat[`;´]]

block ::= chunk

stat ::=  varlist1 `=´ explist1  |
         functioncall  |
         do block end  |
         while exp do block end  |
         repeat block until exp  |
         if exp then block {elseif exp then block} [else block] end  |
         for Name `=´ exp `,´ exp [`,´ exp] do block end  |
         for namelist in explist1 do block end  |
         function funcname funcbody  |
         local function Name funcbody  |
         local namelist [`=´ explist1]

laststat ::= return [explist1]  |  break

funcname ::= Name {`.´ Name} [`:´ Name]

varlist1 ::= var {`,´ var}

var ::=  Name  |  prefixexp `[´ exp `]´  |  prefixexp `.´ Name

namelist ::= Name {`,´ Name}

explist1 ::= {exp `,´} exp

exp ::=  nil  |  false  |  true  |  Number  |  String  |  `...´  |
         function  |  prefixexp  |  tableconstructor  |  exp binop exp  |  unop exp

prefixexp ::= var  |  functioncall  |  `(´ exp `)´

functioncall ::=  prefixexp args  |  prefixexp `:´ Name args

args ::=  `(´ [explist1] `)´  |  tableconstructor  |  String

function ::= function funcbody

funcbody ::= `(´ [parlist1] `)´ block end

parlist1 ::= namelist [`,´ `...´]  |  `...´

tableconstructor ::= `{´ [fieldlist] `}´

fieldlist ::= field {fieldsep field} [fieldsep]

field ::= `[´ exp `]´ `=´ exp  |  Name `=´ exp  |  exp

fieldsep ::= `,´  |  `;´

binop ::= `+´  |  `-´  |  `*´  |  `/´  |  `^´  |  `%´  |  `..´  |
         `<´  |  `<=´  |  `>´  |  `>=´  |  `==´  |  `~=´  |
         and  |  or

unop ::= `-´  |  not  |  `#´

以if语句为例

1
if exp then block {elseif exp then block} [else block] end

这里表明if后接表达式，然后then关键词，后续接一个block，至于是否有elseif/else都可以，最后以end收尾。

statement()中，对应token为if时，处理函数ifstat()逻辑主要也就根据这个范式解析来判断，大致的伪代码如下。

1
2
3
4
5
6
7
void ifstat(LexState *ls, int line)
{
    check_if();
    check_elseif();
    check_else();
    check_end_match();
}

下面我们分别讨论每部分的逻辑实现。

首先是第一个if then分支的检测。if和then均为关键词，相对简单，这里我们先看看表达式exp该如何处理。常见的表达式一般是a==b或者!a之类的一个判断，也可能是更为复杂的比如函数，所以需要做比较精细的处理。

首先，我们需要一个结构体expdesc来存储表达式的信息以及枚举类型expkind来表示表达式的各种不同类型。

expdesc定义如下，主要包括

  • 类型expkind
  • 表达式的值：因为表达式有很多种，因此值其实也有很多种不同的存储
    • 简单的数值直接用lua_Number(double)即可
    • 属于上值、寄存器里、栈上的值，则需要存其索引。使用一个info可以满足部分需要，但是仍然需要多一个aux来存储如table的中的值。
1
2
3
4
5
6
7
8
9
typedef struct expdesc {
  expkind k;
  union {
    struct { int info, aux; } s;
    lua_Number nval;
  } u;
  int t;  /* patch list of `exit when true' */
  int f;  /* patch list of `exit when false' */
} expdesc;

expkind类型定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef enum {
  VVOID,	/* no value */ // 表达式是空的，也就是void
  VNIL,     //表达式是nil类型
  VTRUE,    //表达式是TRUE
  VFALSE,   //表达式是FALSE
  VK,		/* info = index of constant in `k' */ // 表达式是常量类型，expdesc的info字段表示这个常量是常量表k中的哪个值
  VKNUM,	/* nval = numerical value */ //表达式为数字
  VLOCAL,	/* info = local register */  //表达式为local变量，expdesc的info字段表示该local变量在栈中的位置
  VUPVAL,       /* info = index of upvalue in `upvalues' */ //表达式是Upvalue，expdesc的info字段表示Upvalue数组的索引
  VGLOBAL,	/* info = index of table; aux = index of global name in `k' */ //表达式的值为全局变量
  VINDEXED,	/* info = table register; aux = index register (or `k') */ //索引类型，当exp是这种类型时，expdesc的ind域被使用
  VJMP,		/* info = instruction pc */  //表达式为跳转指令
  VRELOCABLE,	/* info = instruction pc */ //表达式可以把结果放到任意的寄存器上，expdesc的info表示的是instruction pc
  VNONRELOC,	/* info = result register */ //表达式已经在某个寄存器上了，expdesc的info字段，表示该寄存器的位置
  VCALL,	/* info = instruction pc */ // 表达式是函数调用，expdesc中的info字段，表示的是instruction pc, 也就是它指向Proto code列表的哪个指令
  VVARARG	/* info = instruction pc */
} expkind;

然后我们来梳理一下一个简单的逻辑应该如何去分析确定。

假设一个简单的脚本里有如下语句

1
2
3
4
5
6
7
8
a = 1
b = 2

if a < b then
    print("b large")
else
    print("a large")
end

对应的解析则是luaX_next()读取首个token，然后chunk()中循环执行statement()逻辑，根据读到的token调用对应的函数

  • 首先luaX_next()读到“a”，对应TK_NAME，走statement()的default分支，调用exprstat()，该函数专门处理各种非关键字的表达式解析
    • 调用primaryexp()进行default分支表达式的检测
      • 调用prefixexp()，该函数针对当前token类型为NAME或者括号进行检测，对于NAME，进一步调用singlevar()
        • 调用singlevar()检查Name的类型
          • 调用str_checkname()，确认是TK_NAME后，调用luaX_next()读取下个token
          • 调用singlevaraux()判断NAME的类型属于哪一类，包括GLOBAL/UPVAL/LOCAL
            • 如果当前函数层级为NULL，则说明是最外层了，即脚本本身，那么该NAME一定是VGLOBAL，调用init_exp()初始化VGLOBAL并返回
            • 函数层级不为NULL，则调用searchvar()查看当前层级是否已有该NAME，有的话则返回对应位置，找不到返回-1
              • 找到了则调用Init_exp()初始化该表达式为VLOCAL类型，对于local还需要调用markupval()进行gc object的记录，然后返回VLOCAL
              • 找不到，则递归调用singlevaraux()，查看上级，即fs->prev的情况。
                • 递归多级后如果返回的是VGLOBAL，则照葫芦画瓢返回VGLOBAL即可
                • 如果是某一级别的VLOCAL，那么该级别则为VUPVAL，这里就需要做一些操作了。
                  • 首先调用indexupvalue()取出信息赋值给表达式的info字段
                  • k字段赋值VUPVAL
                  • 返回VUPVALL
          • 对于VGLOBAL，则调用luaK_stringK()将其添加到对应的proto的变量列表中
      • 完成prefixexp()的调用后，进入后面是否有.[:(等衔接符的检测，此处没有则直接跳过
    • 如果primaryexp()的结果表示表达式类型是VCALL，则调用getcode()，否则调用assignment()
      • assignment()主要处理NAME后的token，按照语法规定，这里只允许是","或者"="，别的则抛出异常
        • 对于”,”，则嵌套调用primaryexp() + assignment()进行递归处理
        • 对于”=“，说明NAME走到了赋值了
          • 首先当然是调用checknext()检查是不是”=“，不是则报错
          • 然后调用explist1()检测表达式另一边有几个赋值的值，因为Lua允许多赋值
            • 首先调用expr()，实际调用subexpr()函数，对操作符进行判断及处理
              • 调用getunopr()获取当前操作符的类型
              • 如果不是NOUNOPR，则需要继续读取后续的进行判断，否则调用syimpleexp()
                • simpleexp()会检查token类型并进行相应的expdesc赋值，对TK_NUMBER则调用init_exp()初始化为VKNUM，然后调用luaX_next()读取后续token
              • 调用getbinnopr()获取二元操作符并判断后续操作，对于等号这里直接跳转走
            • 然后循环调用testnext()检测”,“，检测到了则调用luaK_exp2nextreg()和expr()
              • luaK_exp2netreg()
              • expr()
          • 检查完赋值语句后，判断是否有多出来的值，有的话则需要进行调整，否则调用luaK_setoneret()和luaK_storevar设置表达式的返回并结束该语句
            • 首先调用luaK_setoneret()，对表达式为VCALL或者VVARARG进行赋值，此处我们是VNUM所以并无操作
            • 然后调用luaK_storevar()，对于VGLOBAL，处理如下
              • 调用luaK_exp2anyreg()
                • 调用luaK_dischargevars()，区分expkind，调用luaK_codeABx()或者luaK_codeABC()赋值OpCode。
                  • luaK_codeABx和luaK_codeABC区别在于机器码对应的寄存器数量不同，实际最后均调用luaK_code
                • 调用luaK_exp2nextreg()
              • 调用luaK_codeABx()赋值OP_SETGLOBAL
      • SETARG_C(getcode())针对=号后为函数，赋值对应的函数地址值。
      • 最后调用Init_exp()

总结

参考文献

坚持原创，坚持分享，谢谢鼓励和支持