lua源码分析之语法分析 (干货)

FeastSC

本文借鉴：
原作者：Manistein
博客地址：构建Lua解释器Part7：构建完整的语法分析器(上)
特此感谢。
前面的文章的我们讲解了lua源码分析之词法分析的内容，这章我们讲讲语法分析的内容，如果不了解之前内容的朋友可以点击下面的链接。
在进行源码分析，我们先来了解一些概念，因为有些概念我们搞不清楚我们就不清楚它的内在逻辑是怎样的，也就不知道代码所要干的事是怎么样的。所以我们带着几个问题来看这篇文章
1、statement和expression是什么？
2、语法分析用到的数据结构都有哪些？
3、lua parser的运作流程是怎样的？

下面带着上面的三个问题我们开始我们的分析，注：本文中部分图引用了Manistein的，对此表示感谢
一、statement和expression是什么？


expression是一个表达式，表达式最终能够演变成一个值，并且这个值可以被赋值到一个变量中，符合这个条件的就是expression否则就是statement。

statement则是一系列操作的集合，它其实包含一系列的expression或者statement。statement是一门语言中单独的一个单元，一门语言中，有不同的statement类别，并且这些有限类别的statement组成的序列，构成一门语言的逻辑代码。

我们现在来看一个例子，如下所示：
a = 1
b = 1+2*(3-4)
c = true
d = nil左边所示的a、b、c、d是变量，右边的1、1+2*(3-4)、true和nil，最终能够演变成一个值，并且可以赋值给左边的变量，因此他们是表达式，而每一行的赋值语句，则是单独的statement。

此外，我们还有以下几种statement，并且这些statement都不能演变成一个值，并赋值到一个变量中：
// do end statement
do block end

// while statement
while exp do block end

// repeat statement
repeat block until exp

// if statement
if exp then block {elseif exp then block} [else block] end

// for statement
for Name `= exp `, exp [`, exp] do block end
for namelist in explist1 do block end

// function statement
function funcname funcbody

// local statement
local function Name funcbody
local namelist [`= explist1]

// expr statement
varlist1 `= explist1
functioncall
所以lua代码是由一系列的statement组合而成，因此在在编译过程中，就是要将脚本代码中的statement识别出来，并且进入到对应的编译分支，将其编译为虚拟机指令。

现在我将对lua的exprstat的EBNF范式进行说明，其EBNF范式如下所示：
exprstat ::= func | assignment

assignment ::= suffixedexp {, suffixedexp} ['=' explist]
func ::= suffixedexp

suffixedexp ::= primaryexp {'.' NAME | '[' expr ']' | ':' NAME funcargs | funcargs}
primaryexp ::= NAME | '(' expr ')'

explist ::= expr {',' expr}
expr ::= (simpleexp | unop expr) {binop expr}
simpleexp ::= FLT|INT|STRING|NIL|TRUE|FALSE|...|constructor|FUNCTION body|suffixedexp
FUNCTION body ::= 'function' '('parlist')' statlist 'end'
parlist ::= {param [',' param]}
param ::= NAME | ...

constructor ::= '{' [field { sep field } [sep]] '}'
field ::= listfield | recfield
listfield ::= expr
recfield ::= (NAME | '[' expr ']') '=' expr
sep ::= ','|';'

funcargs ::= '('[explist]')' | constructor | STRING

unop ::= '-'|not|'#'|bnot
binop ::= '+' | '-' | '*' | '/' | '%' | '^' | '&' | '|' | '~' | '<<' | '>>' | '..' |
      '>' | '<' | '=' | '>=' | '<=' | '==' | '~=' | and | or
我们已经通过EBNF范式，来描述了我们即将实现的statement的语法结构和逻辑层次，可以看到，EBNF范式的表述比较抽象且复杂，为此，我引用了一张Manistein的图，用来展现它的逻辑层次：

图1

该图是对上述EBNF范式的归纳，向读者自顶向下地展示完整的exprstat的语法结构，展示完整的解析层次，展示各个部件的构成和联系，它也是我们展示Parse Tree生成的绝佳利器。我们后续需要根据这张图来分析exprstat的编译逻辑。

二、语法分析用到的数据结构都有哪些？


在lua的语法分析器中，主要用的数据结构分别是FuncState和Proto这两个结构了，我们先来看看FuncState结构，它的定义如下所示：
//lparser.h
typedef struct FuncState {
  Proto *f;     // 主要存放虚拟机指令，常量表等
  struct FuncState *prev;
  struct LexState *ls;
  struct BlockCnt *bl;  
  int pc;       // 下一个指令，应当存放在Proto结构中的code列表的位置
  int lasttarget;  
  int jpc;      // 当一个statement中同时存在，and和or的逻辑语句时，用来标记jump指令位置的
  int nk;       // 当前常量的数量
  int np;       // 被编译的代码，Proto的数量
  int firstlocal;   // 第一个local变量的位置
  short nlocvars;   // 当前local变量的数量
  lu_byte nactvar;  // 当前活跃变量的数量
  lu_byte nups;  // 当前upvalue的数量
  lu_byte freereg;  // 下一个可被使用的，空闲寄存器的位置
} FuncState;
现在我们只要对FuncState结构的变量，有一个初步的概念即可，要彻底理解它们，需要在编译流程的论述之后才能做到，我们接下来看看Proto的数据结构定义
//lobject.h
typedef struct Proto {
  CommonHeader;       // gc部分
  lu_byte numparams;      // 参数个数
  lu_byte is_vararg;    // 是否可变参数的函数
  lu_byte maxstacksize; // 经过编译后，需要栈的最大大小
  int sizeupvalues;  // upvalue列表的大小
  int sizek;        // 常量表的大小
  int sizecode;     // 指令列表的大小
  int sizelineinfo;
  int sizep;        // Proto结构列表的大小
  int sizelocvars;     // local变量列表的大小
  int linedefined;     //行定义 属于调试信息
  int lastlinedefined;  //上一行  调试信息
  TValue *k;          // 常量表
  Instruction *code;  // 指令列表
  struct Proto **p;  // Proto结构列表
  int *lineinfo;  //调试用的
  LocVar *locvars; // local变量列表
  Upvaldesc *upvalues;  // upvalue列表
  struct LClosure *cache;  /* last-created closure with this prototype */
  TString  *source;  // 源代码文件
  GCObject *gclist;  // gc列表
} Proto;
这个Proto 的数据结构我们在讲虚拟机那一章中提到过。一个lua脚本内部的代码本质上就是一个chunk，在chunk在编译后，本质上也是一个function对象，一般一个function对象对应一个Proto实例，在编译过程中，一个function则对应一个FuncState结构。

三、lua parser的运作流程是怎样的？

1、exprstat的构造

前面已经介绍过，statement是构成代码逻辑，最基础的单独单元，lua中同样有多种statement，比如ifstat、whilestat、forstat等等，每个statement执行不同的逻辑，并且在编译器中有独立的处理逻辑分支，而每个statement中，头一个token决定了我们应该进入哪个处理分支之中。下面我们看下源码
//lparce.c
static void statement (LexState *ls) {
  int line = ls->linenumber;  /* may be needed for error messages */
  enterlevel(ls);
  switch (ls->t.token) {
    case ';': {  /* stat -> ';' (empty statement) */
      luaX_next(ls);  /* skip ';' */
      break;
    }
    case TK_IF: {  /* stat -> ifstat */
      ifstat(ls, line);
      break;
    }
    case TK_WHILE: {  /* stat -> whilestat */
      whilestat(ls, line);
      break;
    }
    case TK_DO: {  /* stat -> DO block END */
      luaX_next(ls);  /* skip DO */
      block(ls);
      check_match(ls, TK_END, TK_DO, line);
      break;
    }
    case TK_FOR: {  /* stat -> forstat */
      forstat(ls, line);
      break;
    }
    case TK_REPEAT: {  /* stat -> repeatstat */
      repeatstat(ls, line);
      break;
    }
    case TK_FUNCTION: {  /* stat -> funcstat */
      funcstat(ls, line);
      break;
    }
    case TK_LOCAL: {  /* stat -> localstat */
      luaX_next(ls);  /* skip LOCAL */
      if (testnext(ls, TK_FUNCTION))  /* local function? */
        localfunc(ls);
      else
        localstat(ls);
      break;
    }
    case TK_DBCOLON: {  /* stat -> label */
      luaX_next(ls);  /* skip double colon */
      labelstat(ls, str_checkname(ls), line);
      break;
    }
    case TK_RETURN: {  /* stat -> retstat */
      luaX_next(ls);  /* skip RETURN */
      retstat(ls);
      break;
    }
    case TK_BREAK:   /* stat -> breakstat */
    case TK_GOTO: {  /* stat -> 'goto' NAME */
      gotostat(ls, luaK_jump(ls->fs));
      break;
    }
    default: {  /* stat -> func | assignment */
      exprstat(ls);
      break;
    }
  }
  lua_assert(ls->fs->f->maxstacksize >= ls->fs->freereg &&
             ls->fs->freereg >= ls->fs->nactvar);
  ls->fs->freereg = ls->fs->nactvar;  /* free registers */
  leavelevel(ls);
}


static void exprstat (LexState *ls) {
  /* stat -> func | assignment */
  FuncState *fs = ls->fs;
  struct LHS_assign v;
  suffixedexp(ls, &v.v);
  if (ls->t.token == '=' || ls->t.token == ',') { /* stat -> assignment ? */
    v.prev = NULL;
    assignment(ls, &v, 1);
  }
  else {  /* stat -> func */
    check_condition(ls, v.v.k == VCALL, "syntax error");
    SETARG_C(getinstruction(fs, &v.v), 1);  /* call statement uses no results */
  }
}
ls->t.token就是我们获得的在一个statement语句中的首个token，我们可以很容易地看到，首个token决定了我们要进入哪个case中。
上面的代码，与前面exprstat的EBNF范式吻合。

但我怎么知道当前的这个statement是funccall还是assignment？
我们进入exprstat逻辑分支的时候，当前的token是一个TK_NAME类型的，而刚进入exprstat这段逻辑时，我们只有statement中首个token的信息，单靠这个信息我们无法判定这个是funccall还是assignment。因此lua采取的方式就是，不管怎样，先把第一个exp识别出来，如果它是个变量，那么就必须当做赋值语句处理，如果是个funccall，那么处理直接结束。exprstat的逻辑是，不管三七二十一，先把expr识别出来再说，而做这件事情的是通过suffixedexp函数来识别。但是在开始讨论suffixedexp的编译流程之前，我们首先要看看expr的处理。

2、expr的构造与编译


expr是expression的缩写，意为表达式，在lua的语法分析器中，它的作用就是将表达式识别出来，并将对应的信息存储到一个中间的结构之中。为什么要先从它开始讨论呢？因为它是组成statement的基础，我们先来看一下它的EBNF范式：
expr ::= (simpleexp | unop expr) {binop expr}
simpleexp ::= FLT|INT|STRING|NIL|TRUE|FALSE|...|constructor|FUNCTION body|suffixedexp前面我们也介绍过，expr最终的归宿就是计算成一个确切的值，这个确切的值是什么意思呢？就是expr最后可以演变成simpleexp中，除了…和suffixedexp以外的任意一种类型的值，这些值实际上就是lua的基本类型的值。从上面的EBNF范式来看，它以simpleexp或者一个单目运算的exp为开头，后面可能跟一堆双目运算操作，但不论如何，最终的结果都是演变为一个lua基本类型的值。expr的逻辑如下所示：
//lparce.c
static const struct {
  lu_byte left;  /* left priority for each binary operator */
  lu_byte right; /* right priority */
} priority[] = {  /* ORDER OPR */
   {10, 10}, {10, 10},           /* '+' '-' */
   {11, 11}, {11, 11},           /* '*' '%' */
   {14, 13},                  /* '^' (right associative) */
   {11, 11}, {11, 11},           /* '/' '//' */
   {6, 6}, {4, 4}, {5, 5},   /* '&' '|' '~' */
   {7, 7}, {7, 7},           /* '<<' '>>' */
   {9, 8},                   /* '..' (right associative) */
   {3, 3}, {3, 3}, {3, 3},   /* ==, <, <= */
   {3, 3}, {3, 3}, {3, 3},   /* ~=, >, >= */
   {2, 2}, {1, 1}            /* and, or */
};

#define UNARY_PRIORITY  12  /* priority for unary operators */


/*
** subexpr -> (simpleexp | unop subexpr) { binop subexpr }
** where 'binop' is any binary operator with a priority higher than 'limit'
*/
static BinOpr subexpr (LexState *ls, expdesc *v, int limit) {
  BinOpr op;
  UnOpr uop;
  enterlevel(ls);
  uop = getunopr(ls->t.token);
  if (uop != OPR_NOUNOPR) {
    int line = ls->linenumber;
    luaX_next(ls);
    subexpr(ls, v, UNARY_PRIORITY);
    luaK_prefix(ls->fs, uop, v, line);
  }
  else simpleexp(ls, v);
  /* expand while operators have priorities higher than 'limit' */
  op = getbinopr(ls->t.token);
  while (op != OPR_NOBINOPR && priority[op].left > limit) {
    expdesc v2;
    BinOpr nextop;
    int line = ls->linenumber;
    luaX_next(ls);
    luaK_infix(ls->fs, op, v);
    /* read sub-expression with higher priority */
    nextop = subexpr(ls, &v2, priority[op].right);
    luaK_posfix(ls->fs, op, v, &v2, line);
    op = nextop;
  }
  leavelevel(ls);
  return op;  /* return first untreated operator */
}


static void expr (LexState *ls, expdesc *v) {
  subexpr(ls, v, 0);
}

static void simpleexp (LexState *ls, expdesc *v) {
  /* simpleexp -> FLT | INT | STRING | NIL | TRUE | FALSE | ... |
                  constructor | FUNCTION body | suffixedexp */
  switch (ls->t.token) {
    case TK_FLT: {
      init_exp(v, VKFLT, 0);
      v->u.nval = ls->t.seminfo.r;
      break;
    }
    case TK_INT: {
      init_exp(v, VKINT, 0);
      v->u.ival = ls->t.seminfo.i;
      break;
    }
    case TK_STRING: {
      codestring(ls, v, ls->t.seminfo.ts);
      break;
    }
    case TK_NIL: {
      init_exp(v, VNIL, 0);
      break;
    }
    case TK_TRUE: {
      init_exp(v, VTRUE, 0);
      break;
    }
    case TK_FALSE: {
      init_exp(v, VFALSE, 0);
      break;
    }
    case TK_DOTS: {  /* vararg */
      FuncState *fs = ls->fs;
      check_condition(ls, fs->f->is_vararg,
                      "cannot use '...' outside a vararg function");
      init_exp(v, VVARARG, luaK_codeABC(fs, OP_VARARG, 0, 1, 0));
      break;
    }
    case '{': {  /* constructor */
      constructor(ls, v);
      return;
    }
    case TK_FUNCTION: {
      luaX_next(ls);
      body(ls, v, 0, ls->linenumber);
      return;
    }
    default: {
      suffixedexp(ls, v);
      return;
    }
  }
  luaX_next(ls);
}
expr函数，会将我们输入的token，转化为一个被称之为expdesc结构变量的信息之中，在完成转化之后，我们获取下一个token。实际上expr可能会处理多个token，一般在单目运算或者是双目运算的expr里。

实际上，并非所有的token都能够被expr函数转化为expdesc的信息的，只有那些是exp的token才行，这些token都被定义在了EBNF范式中的simpleexp里，他们是TK_FLT、TK_INT、TK_STRING、TK_NIL、TK_TRUE、TK_FALSE、TK_FUNCTION、’{}‘、TK_NAME等，除了TK_NAME，其他都能在lua中找到对应的基本类型（因为TK_NAME表示变量，可以存储任意一种基本类型的值）。这些是输入信息的部分，现在我们来看一下经过expr转化，得到的数据结构是怎样的，以下是它的定义：
//lparser.h
typedef enum  {
    VVOID,          // 表达式是空的，也就是void
    VNIL,           // 表达式是nil类型
    VFLT,           // 表达式是浮点类型
    VINT,           // 表达式是整型类型
    VTRUE,          // 表达式是TRUE
    VFALSE,         // 表达式是FALSE
    VINDEXED,       // 表示索引类型，当exp是这种类型时，expdesc的ind域被使用
    VCALL,          // 表达式是函数调用，expdesc中的info字段，表示的是instruction pc
                    // 也就是它指向Proto code列表的哪个指令
    VLOCAL,         // 表达式是local变量，expdesc的info字段，表示该local变量，在栈中的位置
    VUPVAL,         // 表达式是Upvalue，expdesc的info字段，表示Upvalue数组的索引
    VK,             // 表达式是常量类型，expdesc的info字段表示，这个常量是常量表k中的哪个值
    VRELOCATE,      // 表达式可以把结果放到任意的寄存器上，expdesc的info表示的是instruction pc
    VNONRELOC,      // 表达式已经在某个寄存器上了，expdesc的info字段，表示该寄存器的位置
} expkind;

typedef struct expdesc {
  expkind k;
  union {
    lua_Integer ival;    /* for VKINT */
    lua_Number nval;  /* for VKFLT */
    int info;  /* for generic use */
    struct {  /* for indexed variables (VINDEXED) */
      short idx;  /* index (R/K) */
      lu_byte t;  /* table (register or upvalue) */
      lu_byte vt;  /* whether 't' is register (VLOCAL) or upvalue (VUPVAL) */
    } ind;
  } u;
  int t;  /* patch list of 'exit when true' */
  int f;  /* patch list of 'exit when false' */
} expdesc;
我们现在通过一个表格，来看一下这些exp是如何转化成expdesc结构变量的：



图2

这里需要注意的是，常量表k中不止可以存字符串，还可以存数值类型的值，要通过expdesc表示数值类型，同样可以用类似字符串的方式去表示。

那在什么情况下，数值类型要通过VK的方式展现呢？答案是生成指令的时候，比如生成OP_LOADK指令，这个指令要从常量表k中，load一个值到栈顶，我们首先要将数值存入常量表，然后再去索引它，用expdesc e来表示，就是e->k = VK, e->u.info = index_of_number_in_k 。而对于constructor的情况(也就是’{}‘)，expr会怎么处理呢？我们结合下图来进行说明：



图3

当我们的expr函数，检测到当前的token为’{‘时，会生成一个指令< OP_NEWTABLE 0 0 0 >，这里的含义是，在寄存器R(0)中创建一个table，同时它的array_size和hash_size都为0。此时，expdesc的值如下所示：
e->k = VNONRELOC
e->u.info = 0
类型VNONRELOC表示，它的值在lua stack中，e->http://u.info则说明了它的值在栈中所在的位置。在上图的例子中，它在R(0)。我们知道，OP_NEWTABLE指令是iABC模式，在生成指令后，e->http://u.info的值，就是A域的值，因为指令操作的目标在R(A)，所以e所代表的值，就是刚刚被处理过的R(A)值，不止OP_NEWTABLE是这样，其他指令也是这样。由于花括号内没有其他定义，因此expr会直接跳过’}‘，调用luaX_next获取下一个token。

接下来，要分析的则是expr函数如何处理类型为TK_NAME的token，TK_NAME其实是由primaryexp函数来处理的，而primaryexp又是suffixedexp的组成部分，但是suffixedexp又是simpleexp的组成部分，所以TK_NAME我们可以视为在expr内进行处理。现在我们来看一下这里的处理流程是怎样的。首先在开始讨论expr如何处理TK_NAME之前，我们需要明确几个概念，首先是我们的代码中，函数与upvalue、FuncState结构的关系，现在我们通过图4的例子来进行分析：



图4

如上图所示，我们现在有一个test.lua的脚本，里面定义了两个local变量和一个函数，那么这个test.lua本身里面所有的代码就是一个chunk，这个chunk实际上也是一个function类型，我们称之为top-level function。test.lua脚本里，定义了一个foo函数，我们在编译的过程中，chunk因为也是一个function，因此会有一个FuncState结构和它对应，这个结构主要用来存储编译结果的，另外foo函数，因为也是一个函数，因此它也有一个FuncState结构和它对应，并且它的prev指针，指向了chunk的FuncState结构。每个函数都有一个upvalue列表，其中第一个upvalue必定是_ENV，它默认指向全局表，如果我们没有对_ENV进行任何赋值操作，那么它就是全局表的象征。每个函数在运行时，都有独立的虚拟栈，local变量会被放入栈中。

图4帮助我们梳理了很多概念，我们现在可以根据图4来做一些逻辑分析了，同样是expr函数，当我们输入不同的token的时候，它会生成什么样的expdesc变量呢？现在来罗列一下这些在编译过程中的情况：

先到栈上找local变量，看看是否在local列表中，如果是则返回，此时e->k=VLOCAL，e->http://u.info为栈上的索引值
如果上一步找不到，则到自己函数的upvalue列表里去查找，如果找到，然后e->k=VUPVAL，e->http://u.info为upvalue列表里的索引值
如果上一步找不到，则到外层函数里查找它的local列表，如果找到，则将其添加到自己的upvalue列表中，如果找不到，则到外层函数的upvalue列表里查找，如果在那里找到，先添加到自己的upvalue列表中，再将e->k=VUPVAL，e->http://u.info为upvalue列表里的索引值。如果都没找到，则需要再到更外一层函数里查找，执行相似的逻辑，找不到就一直到外层函数找，直至到top-level function为止
如果还是找不到，就到_ENV表里查找，也就是upvalue[0]，也就是全局表_G里查找，此时e的值为e->k=VINDEXED，e->u.ind.vt=VUPVAL，e->u.ind.t=0，e->u.ind.idx=idx_of_name
结合图4，我们通过几个例子来看一下这个流程
首先我们来看一下，编译foo函数时的情况。如果当前token为< TK_NAME, c >的情况，此时执行expr的逻辑，它首先会查找foo函数的local列表，它在第0个位置找到了变量c，因此生成expdesc结构，e->k=VLOCAL，e->u.info=0

然后我们来看一下，当前token为< TK_NAME, b >的情况，此时执行expr逻辑，因为在foo的local列表中找不到变量b，所以到外层函数中查找，并且在外层函数的local列表中，找到变量b，此时foo函数将其添加到自己的upvalue列表中，并且生成expdesc结构，此时e->k=VUPVAL，e->u.info=1

最后我们来看一下，当前token为< TK_NAME, print >时，expr的编译执行情况，首先到foo函数体的local列表中查找print，因为没有找到，所以到自己的upvalue中查找，发现也没找到。此时到外层函数的local列表中查找，因为没有找到，所以去外层函数的upvalue列表里查找，也没找到，最后只能去_ENV里查找。编译器会先将print这个字符串，加入到foo函数对应的Proto结构的常量表k中，然后将e->k=VINDEXED，e->u.ind.vt=VUPVAL，e->u.ind.t=0，e->u.ind.idx=258(假设print在常量表第3个位置)。这个expdesc的含义是，因为e->k为VINDEXED，所以这是一个从一个table取值的处理，而且e->u.ind.vt为VUPVAL，所以这个被操作的表，要去upvalue表去查找，又因为e->u.ind.t为0，所以操作目标是UpValue[0]，最后idx为258，则是去常量表里找到访问table的key值。

我们在获得了expdesc结构以后，最终是要将这些信息转化为指令的，那么这个转化的过程是怎样的呢？我们现在来看一下：

当expdesc类型变量e->k为VNIL时，生成< OP_LOADNIL A B >指令，该指令会被写入code指令列表中，其中A为lua栈中，这个nil值要被写入的位置，B的值表示从A指向的位置开始，要将多少个栈上的变量变为NIL值，同时将e->k设置为VNONRELOC，将e->u.info设置为A值

当expdesc类型变量e->k为VFLT、VINT时，先将e包含的lua_Number或lua_Integer值存入常量表k，然后生成< OP_LOADK A Bx >，该指令会被写入code列表，其中A为lua栈中，这个常量要被写入的寄存器位置，Bx是刚被写入常量表k的数值的k表索引

当expdesc类型变量e->k为VTRUE、VFALSE时，直接生成< OP_LOADBOOL A, 1, 0 >或< OP_LOADBOOL, A, 0, 0 >表示分别将1或0的值，读入lua栈A值所指的位置，第三个参数为0表示pc寄存器不自增，这个值将在比较运算指令生成时用到。此时e->k设置为VNONRELOC，并且e->u.info设置为A的值

当expdesc类型变量e->k为VINDEXED时，如果e->u.ind.vt为VLOCAL则生成< OP_GETTABLE A, B, C >指令，意思是将R(B)[RK( C )]的值，赋值到R(A)上，RK我们之前也讨论过，当C>=256时，RK( C )=Kst(C-256)，即从常量表k中取C-256这个值。当C<256时，取R( C )的值，即从寄存器中取值；如果e->u.ind.vt为VUPVAL时，则生成< OP_GETTABUP A, B, C >指令，意思是将UpValue[B][RK( C )]的值，赋值到R(A)上。此时e->k设置为VNONRELOC，并且e->u.info设置为A的值

当expdesc类型变量e->k为VCALL时，直接生成< OP_CALL A, B, C >指令，其中A表示要被调用的函数的寄存器位置。当B>0时，参数个数为B-1个，当B=0时，表示从R(A+1)到栈顶都是参数。当C>0时，C-1表示返回值的个数，当C=0时，表示返回值是从R(A)到栈顶

当expdesc类型变量e->k为VLOCAL时，表示目标已经在栈中，因此直接将e->k改为VNONRELOC

当expdesc类型变量e->k为VUPVAL时，生成指令< OP_GETUPVAL A, B >，这个表示R(A)=UpValue[B]，此时e->k设置为VNONRELOC，并且e->u.info设置为A的值

当expdesc类型变量e->k为VK时，生成指令< OP_LOADK A, Bx >表示R(A)=Kst(Bx)，此时e->k设置为VNONRELOC，并且e->u.info设置为A的值

当expdesc类型变量e->k为VRELOCATE时，这个表示指令已经生成，只是寄存器A未指定，此时需要将一个空闲的寄存器位置赋值给A域即可，一般由freereg指定

当expdesc类型变量e->k为VNONRELOC时，生成指令< OP_MOVE A, B >即是，R(A)=R(B)，要生成这个指令，A不能等于B

3、suffixedexp构造与编译

接下来，我们来看一下suffixedexp的构造，我们前面论述了expr的构造，之所以要先论述它，是因为它是一切的基础。我们首先来回顾一下suffixedexp的EBNF范式：
suffixedexp ::= primaryexp {'.' NAME | '[' expr ']' | ':' NAME funcargs | funcargs}
primaryexp ::= NAME | '(' expr ')'
funcargs ::= '('[explist]')' | constructor | STRING
我们可以简单地归纳，suffixedexp的主要构成部分有三块，分别是primaryexp、table访问和函数调用三块。

前两者可以构成赋值语句中，=左边的variable，函数调用可以作为独立的exp存在，
//lparser.c
static void exprstat (LexState *ls) {
  /* stat -> func | assignment */
  FuncState *fs = ls->fs;
  struct LHS_assign v;
  suffixedexp(ls, &v.v);
  if (ls->t.token == '=' || ls->t.token == ',') { /* stat -> assignment ? */
    v.prev = NULL;
    assignment(ls, &v, 1);
  }
  else {  /* stat -> func */
    check_condition(ls, v.v.k == VCALL, "syntax error");
    SETARG_C(getinstruction(fs, &v.v), 1);  /* call statement uses no results */
  }
}exprstat函数，首先要调用suffixedexp函数的原因，因为我们前面也说过，exprstat中，不论是赋值语句还是函数调用，他们首先都要识别出第一个exp，然后根据后续的token，判定输入的statement是个赋值语句(遇到’=‘的时候)，或是函数调用(遇到’(‘的时候)，还是不合法。这也是suffixedexp函数这么去设计的原因。在分别开始讨论三个构造之前，我们先来看一下suffixedexp函数的代码：
//lparser.c
static void suffixedexp (LexState *ls, expdesc *v) {
  /* suffixedexp ->
       primaryexp { '.' NAME | '[' exp ']' | ':' NAME funcargs | funcargs } */
  FuncState *fs = ls->fs;
  int line = ls->linenumber;
  primaryexp(ls, v);
  for (;;) {
    switch (ls->t.token) {
      case '.': {  /* fieldsel */
        fieldsel(ls, v);
        break;
      }
      case '[': {  /* '[' exp1 ']' */
        expdesc key;
        luaK_exp2anyregup(fs, v);
        yindex(ls, &key);
        luaK_indexed(fs, v, &key);
        break;
      }
      case ':': {  /* ':' NAME funcargs */
        expdesc key;
        luaX_next(ls);
        checkname(ls, &key);
        luaK_self(fs, v, &key);
        funcargs(ls, v, line);
        break;
      }
      case '(': case TK_STRING: case '{': {  /* funcargs */
        luaK_exp2nextreg(fs, v);
        funcargs(ls, v, line);
        break;
      }
      default: return;
    }
  }
}
suffixedexp函数，首先要识别的就是primaryexp，它的EBNF范式在前面也已经展示过，这里展示一下它的实现逻辑：

static void primaryexp (LexState *ls, expdesc *v) {
  /* primaryexp -> NAME | '(' expr ')' */
  switch (ls->t.token) {
    case '(': {
      int line = ls->linenumber;
      luaX_next(ls);
      expr(ls, v);
      check_match(ls, ')', '(', line);
      luaK_dischargevars(ls->fs, v);
      return;
    }
    case TK_NAME: {
      singlevar(ls, v);
      return;
    }
    default: {
      luaX_syntaxerror(ls, "unexpected symbol");
    }
  }
}

static void singlevar (LexState *ls, expdesc *var) {
  TString *varname = str_checkname(ls);
  FuncState *fs = ls->fs;
  singlevaraux(fs, varname, var, 1);
  if (var->k == VVOID) {  /* global name? */
    expdesc key;
    singlevaraux(fs, ls->envn, var, 1);  /* get environment variable */
    lua_assert(var->k != VVOID);  /* this one must exist */
    codestring(ls, &key, varname);  /* key is variable name */
    luaK_indexed(fs, var, &key);  /* env[varname] */
  }
}
1)primaryexp
primaryexp的两个主要分支，一个是变量识别，还有一个是括号内的expr处理,其本质也和expr函数一样
expr和suffixedexp以及primaryexp的关系，他们其实是通过递归来实现嵌套逻辑的。我们的primaryexp，依然是输入一些token，输出一个expdesc结构
a => primaryexp => expdesc
(a + b * c) => primaryexp => expdesc
(((a))) => primaryexp => expdesc
...虽然EBNF范式，已经展示了primaryexp和suffixedexp的关系，但是我们也可以通过一张图来展现：



图5

2)table访问
我们要讨论的第二部分内容，就是table的访问。不论如何，首先我们都要先处理primaryexp，这是table的本体(即table自身)，而访问处理也是针对它来进行的。从上面的EBNF范式来看，table的组织，可以抽象为以下的形式：
primaryexp { .NAME | '[' expr ']' }直接通过’.‘来访问，和通过方括号来访问，现在我们来通过一个例子，来梳理一下table访问的流程
foo.bar["call"][a]首先，上面这个表达式，会交给suffixedexp函数来处理，而处理第一个token的，则是primaryexp，此时，parser会将foo直接装载到expdesc结构之中，得到图6的结果：



图6

此时，我们当前的token是’.‘，因此进入了通过点来访问table域的逻辑流程之中，对应代码片段fieldsel，此时需要做两件事情，第一件是将e中的信息转化为指令，第二件是，获取’.‘之后的那个simpleexp，并装载到新的expdesc结构之中，于是得到图7的结果



图7

接下来，我们需要整合e和k，并且获取下一个token，得到图8所示的结果：



图8

现在，我们当前的token是’[‘，此时进入到方括号的table域访问流程之中，到这里，先要把e中的信息转化为虚拟机指令，于是得到图9的结果：



图9

此时我们获得了一个OP_GETTABLE指令，B为0表示操作对象位于R(0)，C为257，表示key值为Kst(257-256)=Kst(1)，也就是bar字符串，A值为1，表示访问结果存储到R(1)中，这里需要注意一下freereg的变化。接下来，lua parser会调用luaX_next函数，获取下一个token，并且将字符串”call”的信息，装载到新的expdesc结构之中，于是得到图10的结果：



图10

接下来，lua parser会跳过下一个token ‘]‘，直接获得其后面的token ‘[‘，并且整合e和k，得到图11的结果：



图11

现在当前的token是’[‘，还是进入方括号访问table域的流程之中，此时，先将e中的信息，转化为虚拟机指令，然后通过luaX_next获取下一个token a，并且将a装载到新的expdesc结构之中，于是得到图12的结果：



图12

接下来，就是调用luaX_next函数，获得下一个token ‘]‘，并且将key中的信息转化为虚拟机指令，于是得到图13的结果：



图13

接下来就是要整合e和key了，得到图14的结果：



图14

到目前为止，suffixedexp对上面例子的处理就结束了

3)函数调用

suffixedexp是处理函数调用编译流程的，这里有两种模式，一种是通过’.‘访问，还有一种是通过’:‘访问，这里就不深入分析了，各位同学可以看源码了解更多详情

4、assignment构造和编译


我们现在回顾一下，assignment的EBNF范式，如下所示：

assignment ::= suffixedexp {, suffixedexp} ['=' explist]
这样的statement，一定要有一个等于号，位于等于号左边的是suffixedexp，但是不能是funccall类型的，而右边的则是exp列表，这个statement的工作，就是将右边的exp赋值到左边的variable，其函数实现如下所示：
// lparser.c
static void assignment (LexState *ls, struct LHS_assign *lh, int nvars) {
  expdesc e;
  check_condition(ls, vkisvar(lh->v.k), "syntax error");
  if (testnext(ls, ',')) {  /* assignment -> ',' suffixedexp assignment */
    struct LHS_assign nv;
    nv.prev = lh;
    suffixedexp(ls, &nv.v);
    if (nv.v.k != VINDEXED)
      check_conflict(ls, lh, &nv.v);
    checklimit(ls->fs, nvars + ls->L->nCcalls, LUAI_MAXCCALLS,
                    "C levels");
    assignment(ls, &nv, nvars+1);
  }
  else {  /* assignment -> '=' explist */
    int nexps;
    checknext(ls, '=');
    nexps = explist(ls, &e);
    if (nexps != nvars)
      adjust_assign(ls, nvars, nexps, &e);
    else {
      luaK_setoneret(ls->fs, &e);  /* close last expression */
      luaK_storevar(ls->fs, &lh->v, &e);
      return;  /* avoid default */
    }
  }
  init_exp(&e, VNONRELOC, ls->fs->freereg-1);  /* default assignment */
  luaK_storevar(ls->fs, &lh->v, &e);
}
我们可以看到assignment是递归调用的，我现在将通过一个例子，来阐述赋值语句的编译流程：
a, b = c, d我们通过图15来说明这个流程：



图15

从图15，我现在梳理出如下的信息：

在赋值语句中，等号左边的variable是直接被存储到expdesc结构中，并不会立即释放，生成虚拟机指令。等号右边的explist，会先生成虚拟机指令。
在explist编译完成之后，就会逐一从离等号最近的variable开始赋值
完成整个编译以后，得到图16的结果：



图16

赋值顺序，是根据variable列表，从右到左的顺序，赋值的内容，则是从freereg-1开始，朝R(0)方向的顺序。到现在为止，我就完成了assignment编译流程的论述了。

到现在为止我们对语法分析的讲解就讲完了，我们探索了exprstat的编译流程，包括expr、suffixedexp和assignment的构造和编译流程。本文并未展示过多的代码，而是通过EBNF范式描述lua的语法，然后仅仅只是展现了主要流程的代码，最后将一些关键函数，通过一系列构图的方式，展现其编译流程。抽象这些操作能够让我们更好地理解lua parser的运作流程。

关于语法分析这部分内容我觉得还是比较复杂的，本文并没有深入探讨其中的细节，只是展示了一些关键的步骤，让我们脑海里知道语法分析到底是怎么一回事就够了，这也是分享这篇文章的目的和初衷，毕竟我们不是要写一个编译器。

最后欢迎点赞 + 关注！