您当前的位置:首页 > lua

Lua解析脚本过程中的关键数据结构介绍

在这一篇文章中我先来介绍一下lua解析一个脚本文件时要用到的一些关键的数据结构,为将来的一系列代码分析打下一个良好的基础。在整个过程中,比较重要的几个源码文件分别是:llex.h,lparse.h、lobject.h和lopcode.h。RWjlinux系统宝典

在llex.h中RWjlinux系统宝典

1 typedef struct Token {RWjlinux系统宝典
2  int token;RWjlinux系统宝典
3  SemInfo seminfo;RWjlinux系统宝典
4 } Token;RWjlinux系统宝典

Token代表了一个词法单元,其中token表示词法类型如TK_NAME、TK_NUMBER等如果不是这些类型则存放则词素的字符表示,例如分析的代码会这么判断词素单元:RWjlinux系统宝典

RWjlinux系统宝典
 1 switch (ls->t.token) {RWjlinux系统宝典
 2    case '(': {RWjlinux系统宝典
 3      //...RWjlinux系统宝典
 4    }RWjlinux系统宝典
 5    case TK_NAME: {RWjlinux系统宝典
 6      //...RWjlinux系统宝典
 7    }RWjlinux系统宝典
 8    default: {RWjlinux系统宝典
 9      //...RWjlinux系统宝典
10    }RWjlinux系统宝典

 RWjlinux系统宝典

在Token中SemInfo存放了一些语义相关的一些内容信息RWjlinux系统宝典

1 typedef union {RWjlinux系统宝典
2  lua_Number r;RWjlinux系统宝典
3  TString *ts;RWjlinux系统宝典
4 } SemInfo;  /* semantics information */RWjlinux系统宝典

其中当token是数字是内容存放在r中,其他情况存放在ts指向的TString中。RWjlinux系统宝典

下面是最重要的一个数据结构之一RWjlinux系统宝典

 RWjlinux系统宝典

 1 typedef struct LexState {RWjlinux系统宝典
 2  int current;  /* current character (charint) */RWjlinux系统宝典
 3  int linenumber;  /* input line counter */RWjlinux系统宝典
 4  int lastline;  /* line of last token `consumed' */RWjlinux系统宝典
 5  Token t;  /* current token */RWjlinux系统宝典
 6  Token lookahead;  /* look ahead token */RWjlinux系统宝典
 7  struct FuncState *fs;  /* `FuncState' is private to the parser */RWjlinux系统宝典
 8  struct lua_State *L;RWjlinux系统宝典
 9  ZIO *z;  /* input stream */RWjlinux系统宝典
10  Mbuffer *buff;  /* buffer for tokens */RWjlinux系统宝典
11  TString *source;  /* current source name */RWjlinux系统宝典
12  char decpoint;  /* locale decimal point */RWjlinux系统宝典
13 } LexState;RWjlinux系统宝典

 RWjlinux系统宝典

LexState不仅用于保存当前的词法分析状态信息,而且也保存了整个编译系统的全局状态。current指向了当前字符,t存放了当前的toekn,lookahead存放了向前看的token,由此我认为lua应该是ll(1)的~哈哈(不知道对不对)。fs指向了parser当前解析的函数的一些相关的信息,L指向了当前lua_State结构,z指向输入流,buff指向了token buffer,其他的看注释吧。RWjlinux系统宝典

下面看看lparse.h文件中的重要结构:RWjlinux系统宝典

 RWjlinux系统宝典

1 typedef struct expdesc {RWjlinux系统宝典
2  expkind k;RWjlinux系统宝典
3  union {RWjlinux系统宝典
4    struct { int info, aux; } s;RWjlinux系统宝典
5    lua_Number nval;RWjlinux系统宝典
6  } u;RWjlinux系统宝典
7  int t;  /* patch list of `exit when true' */RWjlinux系统宝典
8  int f;  /* patch list of `exit when false' */RWjlinux系统宝典
9 } expdesc;RWjlinux系统宝典

 RWjlinux系统宝典

expdesc是存放了表达式的相关描述信息,k是表达式的种类,u在不同的表达式中有不同的含义。RWjlinux系统宝典

1 typedef struct upvaldesc {RWjlinux系统宝典
2  lu_byte k;RWjlinux系统宝典
3  lu_byte info;RWjlinux系统宝典
4 } upvaldesc;RWjlinux系统宝典

upvaldesc是存放了upval的相关描述信息。RWjlinux系统宝典

最后是本文件中最重要的结构:RWjlinux系统宝典

 RWjlinux系统宝典

 1 typedef struct FuncState {RWjlinux系统宝典
 2  Proto *f;  /* current function header */RWjlinux系统宝典
 3  Table *h;  /* table to find (and reuse) elements in `k' */RWjlinux系统宝典
 4  struct FuncState *prev;  /* enclosing function */RWjlinux系统宝典
 5  struct LexState *ls;  /* lexical state */RWjlinux系统宝典
 6  struct lua_State *L;  /* copy of the Lua state */RWjlinux系统宝典
 7  struct BlockCnt *bl;  /* chain of current blocks */RWjlinux系统宝典
 8  int pc;  /* next position to code (equivalent to `ncode') */RWjlinux系统宝典
 9  int lasttarget;  /* `pc' of last `jump target' */RWjlinux系统宝典
10  int jpc;  /* list of pending jumps to `pc' */RWjlinux系统宝典
11  int freereg;  /* first free register */RWjlinux系统宝典
12  int nk;  /* number of elements in `k' */RWjlinux系统宝典
13  int np;  /* number of elements in `p' */RWjlinux系统宝典
14  short nlocvars;  /* number of elements in `locvars' */RWjlinux系统宝典
15  lu_byte nactvar;  /* number of active local variables */RWjlinux系统宝典
16  upvaldesc upvalues[LUAI_MAXUPVALUES];  /* upvalues */RWjlinux系统宝典
17  unsigned short actvar[LUAI_MAXVARS];  /* declared-variable stack */RWjlinux系统宝典
18 } FuncState;RWjlinux系统宝典

 RWjlinux系统宝典

在编译过程中,使用FuncState结构体来保存一个函数编译的状态数据。其中,f指向了本函数的协议描述结构体,prev指向了其父函数的FuncState描述,因为在lua中可以在一个函数中定义另一个函数,因此当parse到一个函数的内部函数的定义时会new一个FuncState来描述内部函数,同时开始parse这个内部函数,将这个FuncState的prev指向其外部函数的FuncState,prev变量用来引用外围函数的FuncState,使当前所有没有分析完成的FuncState形成一个栈结构。bl指向当前parse的block,在一个函数中会有很多block代码,lua会将这些同属于同一个函数的block用链表串联起来。jpc是一个OP_JMP指令的链表,因为lua是一遍过的parse,在开始的时候有一些跳转指令不能决定其跳转位置,因此jpc将这些pending jmp指令串联起来,在以后能确定的时候回填,freereg为第一个空闲寄存器的下标,upvalues数组保存了当前函数的所有upvalue,nactvar是当前作用域的局部变量数。RWjlinux系统宝典

在lparse.c中定义了BlockCntRWjlinux系统宝典

 RWjlinux系统宝典

 1 /*RWjlinux系统宝典
 2 ** nodes for block list (list of active blocks)RWjlinux系统宝典
 3 */RWjlinux系统宝典
 4 typedef struct BlockCnt {RWjlinux系统宝典
 5  struct BlockCnt *previous;  /* chain */RWjlinux系统宝典
 6  int breaklist;  /* list of jumps out of this loop */RWjlinux系统宝典
 7  lu_byte nactvar;  /* # active locals outside the breakable structure */RWjlinux系统宝典
 8  lu_byte upval;  /* true if some variable in the block is an upvalue */RWjlinux系统宝典
 9  lu_byte isbreakable;  /* true if `block' is a loop */RWjlinux系统宝典
10 } BlockCnt;RWjlinux系统宝典

 RWjlinux系统宝典

Lua使用BlockCnt来保存一个block的数据。与FuncState的分析方法类似,BlockCnt使用一个previous变量保存外围block的引用,形成一个栈结构。RWjlinux系统宝典

 RWjlinux系统宝典

下面介绍一些在lobject.h文件里面的数据结构RWjlinux系统宝典

 RWjlinux系统宝典

 1 /*RWjlinux系统宝典
 2 ** Function PrototypesRWjlinux系统宝典
 3 */RWjlinux系统宝典
 4 typedef struct Proto {RWjlinux系统宝典
 5  CommonHeader;RWjlinux系统宝典
 6  TValue *k;  /* constants used by the function */RWjlinux系统宝典
 7  Instruction *code;RWjlinux系统宝典
 8  struct Proto **p;  /* functions defined inside the function */RWjlinux系统宝典
 9  int *lineinfo;  /* map from opcodes to source lines */RWjlinux系统宝典
10  struct LocVar *locvars;  /* information about local variables */RWjlinux系统宝典
11  TString **upvalues;  /* upvalue names */RWjlinux系统宝典
12  TString  *source;RWjlinux系统宝典
13  int sizeupvalues;RWjlinux系统宝典
14  int sizek;  /* size of `k' */RWjlinux系统宝典
15  int sizecode;RWjlinux系统宝典
16  int sizelineinfo;RWjlinux系统宝典
17  int sizep;  /* size of `p' */RWjlinux系统宝典
18  int sizelocvars;RWjlinux系统宝典
19  int linedefined;RWjlinux系统宝典
20  int lastlinedefined;RWjlinux系统宝典
21  GCObject *gclist;RWjlinux系统宝典
22  lu_byte nups;  /* number of upvalues */RWjlinux系统宝典
23  lu_byte numparams;RWjlinux系统宝典
24  lu_byte is_vararg;RWjlinux系统宝典
25  lu_byte maxstacksize;RWjlinux系统宝典
26 } Proto;RWjlinux系统宝典

 RWjlinux系统宝典

结构体Proto是lua函数协议的描述,在lua解析脚本时首先会将main chunk代码包裹为一个函数,用main proto描述,接着将里面定义的内部函数一一用Proto结构体描述,将这些Proto的关系用树来组合起来,例如有lua源码文件如下RWjlinux系统宝典

 RWjlinux系统宝典

1 a = 1RWjlinux系统宝典
2 function f1()RWjlinux系统宝典
3 -- ...RWjlinux系统宝典
4 endRWjlinux系统宝典
5 function f2()RWjlinux系统宝典
6    function f3()RWjlinux系统宝典
7    -- ...RWjlinux系统宝典
8    endRWjlinux系统宝典
9 endRWjlinux系统宝典

 RWjlinux系统宝典

则parse完成后会有如图如下关系RWjlinux系统宝典

 RWjlinux系统宝典

在Proto结构体中,k指向一个const变量数组,存放则函数要用到的常量;code指向lua parse过程中生成的本函数的instruction集合;p就是指向本函数内部定义的函数的那些proto;locvars指向本函数局部变量数组;upvalues指向本函数upvalue变量数组;nups为upvalue的数量;numparams为函数参数的数量;is_vararg表示函数是否接收可变参数;maxstacksize为函数stack的max大小。RWjlinux系统宝典

在编译期间lua使用Proto描述函数的,当lua vm开始运行vm时需要根据Proto生成相应的Closure来执行vm instructions。RWjlinux系统宝典

1 typedef union Closure {RWjlinux系统宝典
2  CClosure c;RWjlinux系统宝典
3  LClosure l;RWjlinux系统宝典
4 } Closure;RWjlinux系统宝典

Closure要么代表了c函数,要么为lua函数,在这里我们只看lua函数的LClosureRWjlinux系统宝典

 RWjlinux系统宝典

1 #define ClosureHeader /RWjlinux系统宝典
2    CommonHeader; lu_byte isC; lu_byte nupvalues; GCObject *gclist; /RWjlinux系统宝典
3    struct Table *envRWjlinux系统宝典
4 //... ...RWjlinux系统宝典
5 typedef struct LClosure {RWjlinux系统宝典
6  ClosureHeader;RWjlinux系统宝典
7  struct Proto *p;RWjlinux系统宝典
8  UpVal *upvals[1];RWjlinux系统宝典
9 } LClosure;RWjlinux系统宝典

 RWjlinux系统宝典

在LClousre中,p就是指向对应函数的Proto结构体啦,upvals顾名思义就是此closure的upvalue数组罗。在ClosureHeader宏中isC表示此closure是否是c函数,nupvalues为upvalue数目,env指向了此closue运行时的函数环境,在lua中可以用stefenv来改变当前函数的环境,就是改变env变量的指向啦。RWjlinux系统宝典

最后,在文件lopcode.h中定义了lua vm的指令结构RWjlinux系统宝典

 RWjlinux系统宝典

下面是vm指令的一些定义与描述,我在相应vm指令的上方添加了一些注释RWjlinux系统宝典

 RWjlinux系统宝典

 1 typedef enum {RWjlinux系统宝典
 2 /*----------------------------------------------------------------------RWjlinux系统宝典
 3 name        args    descriptionRWjlinux系统宝典
 4 ------------------------------------------------------------------------*/RWjlinux系统宝典
 5 OP_MOVE,/*    A B    R(A) := R(B)                    */RWjlinux系统宝典
 6 //Constants are usually numbers or strings. Each function has its own constant list, or pool.RWjlinux系统宝典
 7 OP_LOADK,/*    A Bx    R(A) := Kst(Bx)                    */RWjlinux系统宝典
 8 OP_LOADBOOL,/*    A B C    R(A) := (Bool)B; if (C) pc++            */RWjlinux系统宝典
 9 //The optimization rule is  a simple one: If no other instructions have been generated, RWjlinux系统宝典
10 //then a LOADNIL as the first instruction can be optimized away.RWjlinux系统宝典
11 OP_LOADNIL,/*    A B    R(A) := ... := R(B) := nil            */RWjlinux系统宝典
12 RWjlinux系统宝典
13 OP_GETUPVAL,/*    A B    R(A) := UpValue[B]                */RWjlinux系统宝典
14 OP_GETGLOBAL,/*    A Bx    R(A) := Gbl[Kst(Bx)]                */RWjlinux系统宝典
15 OP_GETTABLE,/*    A B C    R(A) := R(B)[RK(C)]                */RWjlinux系统宝典
16 RWjlinux系统宝典
17 OP_SETGLOBAL,/*    A Bx    Gbl[Kst(Bx)] := R(A)                */RWjlinux系统宝典
18 OP_SETUPVAL,/*    A B    UpValue[B] := R(A)                */RWjlinux系统宝典
19 OP_SETTABLE,/*    A B C    R(A)[RK(B)] := RK(C)                */RWjlinux系统宝典
20 RWjlinux系统宝典
21 OP_NEWTABLE,/*    A B C    R(A) := {} (size = B,C)                */RWjlinux系统宝典
22 RWjlinux系统宝典
23 //This instruction is used for object-oriented programming. It is only generated for method calls that use the colon syntax.RWjlinux系统宝典
24 //R(B) is the register holding the reference to the table with the method. RWjlinux系统宝典
25 OP_SELF,/*    A B C    R(A+1) := R(B); R(A) := R(B)[RK(C)]        */RWjlinux系统宝典
26 RWjlinux系统宝典
27 //The optimization rule is simple: If both terms of a subexpression are numbers, RWjlinux系统宝典
28 //the subexpression will be evaluated at compile time.RWjlinux系统宝典
29 OP_ADD,/*    A B C    R(A) := RK(B) + RK(C)                */RWjlinux系统宝典
30 OP_SUB,/*    A B C    R(A) := RK(B) - RK(C)                */RWjlinux系统宝典
31 OP_MUL,/*    A B C    R(A) := RK(B) * RK(C)                */RWjlinux系统宝典
32 OP_DIV,/*    A B C    R(A) := RK(B) / RK(C)                */RWjlinux系统宝典
33 OP_MOD,/*    A B C    R(A) := RK(B) % RK(C)                */RWjlinux系统宝典
34 OP_POW,/*    A B C    R(A) := RK(B) ^ RK(C)                */RWjlinux系统宝典
35 OP_UNM,/*    A B    R(A) := -R(B)                    */RWjlinux系统宝典
36 OP_NOT,/*    A B    R(A) := not R(B)                */RWjlinux系统宝典
37 //Returns the length of the object in R(B)RWjlinux系统宝典
38 OP_LEN,/*    A B    R(A) := length of R(B)                */RWjlinux系统宝典
39 RWjlinux系统宝典
40 //Performs concatenation of two or more strings.RWjlinux系统宝典
41 //The source registers must be consecutive, and C must always be greater than B. RWjlinux系统宝典
42 OP_CONCAT,/*    A B C    R(A) := R(B).. ... ..R(C)            */RWjlinux系统宝典
43 RWjlinux系统宝典
44 //if sBx is 0, the VM will proceed to the next instructionRWjlinux系统宝典
45 OP_JMP,/*    sBx    pc+=sBx                    */RWjlinux系统宝典
46 RWjlinux系统宝典
47 /*If the boolean result is not A, then skip the next instruction. RWjlinux系统宝典
48 Conversely, if the boolean result equals A, continue with the next instruction.*/RWjlinux系统宝典
49 OP_EQ,/*    A B C    if ((RK(B) == RK(C)) ~= A) then pc++        */RWjlinux系统宝典
50 OP_LT,/*    A B C    if ((RK(B) <  RK(C)) ~= A) then pc++          */RWjlinux系统宝典
51 OP_LE,/*    A B C    if ((RK(B) <= RK(C)) ~= A) then pc++          */RWjlinux系统宝典
52 RWjlinux系统宝典
53 OP_TEST,/*    A C    if not (R(A) <=> C) then pc++            */ RWjlinux系统宝典
54 //register R(B) is coerced into a boolean.RWjlinux系统宝典
55 OP_TESTSET,/*    A B C    if (R(B) <=> C) then R(A) := R(B) else pc++    */ RWjlinux系统宝典
56 RWjlinux系统宝典
57 //If B is 0, parameters range from R(A+1) to the top of the stack.If B is 1, the function has no parameters.RWjlinux系统宝典
58 //If C is 1, no return results are saved. If C is 0, then multiple return results are saved, depending on the called functionRWjlinux系统宝典
59 //CALL always updates the top of stack value.RWjlinux系统宝典
60 OP_CALL,/*    A B C    R(A), ... ,R(A+C-2) := R(A)(R(A+1), ... ,R(A+B-1)) */RWjlinux系统宝典
61 OP_TAILCALL,/*    A B C    return R(A)(R(A+1), ... ,R(A+B-1))        */RWjlinux系统宝典
62 //If B is 1, there are no return values. If B is 0, the set of values from R(A) to the top of the stack is returned. RWjlinux系统宝典
63 OP_RETURN,/*    A B    return R(A), ... ,R(A+B-2)    (see note)    */RWjlinux系统宝典
64 RWjlinux系统宝典
65 //FORPREP initializes a numeric for loop, while FORLOOP performs an iteration of a numeric for loop.RWjlinux系统宝典
66 OP_FORLOOP,/*    A sBx    R(A)+=R(A+2);RWjlinux系统宝典
67            if R(A) <?= R(A+1) then { pc+=sBx; R(A+3)=R(A) }*/RWjlinux系统宝典
68 OP_FORPREP,/*    A sBx    R(A)-=R(A+2); pc+=sBx                */RWjlinux系统宝典
69 RWjlinux系统宝典
70 //Performs an iteration of a generic for loop. RWjlinux系统宝典
71 OP_TFORLOOP,/*    A C    R(A+3), ... ,R(A+2+C) := R(A)(R(A+1), R(A+2)); RWjlinux系统宝典
72                        if R(A+3) ~= nil then R(A+2)=R(A+3) else pc++    */ RWjlinux系统宝典
73 //This instruction is used to initialize array elements in a table.RWjlinux系统宝典
74 //If B is 0, the table is set with a variable number of array elements, from register R(A+1) up to the top of the stack. RWjlinux系统宝典
75 //If C is 0, the next instruction is cast as an integer, and used as the C value.RWjlinux系统宝典
76 OP_SETLIST,/*    A B C    R(A)[(C-1)*FPF+i] := R(A+i), 1 <= i <= B    */RWjlinux系统宝典
77 RWjlinux系统宝典
78 /*If a local is used as an upvalue, then the local variable need to be placed somewhere, RWjlinux系统宝典
79 other wise it will go out of scope and disappear when a lexicalblock enclosing the local variable ends. RWjlinux系统宝典
80 CLOSE performs this operation for all affected local variables for do end blocks or loop blocks. RWjlinux系统宝典
81 RETURN also does an implicit CLOSE when a function returns.*/RWjlinux系统宝典
82 OP_CLOSE,/*    A    close all variables in the stack up to (>=) R(A)*/RWjlinux系统宝典
83 /*Each upvalue corresponds to either a MOVE or a GETUPVAL pseudo-instruction. RWjlinux系统宝典
84 Only the B field on either of these pseudo-instructions are significant.*/RWjlinux系统宝典
85 //MOVE pseudo-instructions corresponds to local variable R(B) in the current lexical block.RWjlinux系统宝典
86 //GETUPVAL pseudo-instructions corresponds upvalue number B in the current lexical block.RWjlinux系统宝典
87 OP_CLOSURE,/*    A Bx    R(A) := closure(KPROTO[Bx], R(A), ... ,R(A+n))    */RWjlinux系统宝典
88 RWjlinux系统宝典
89 //If B is 0, VARARG copies as many values as it can based on the number of parameters passed.RWjlinux系统宝典
90 //If a fixed number of values is required, B is a value greater than 1. RWjlinux系统宝典
91 OP_VARARG/*    A B    R(A), R(A+1), ..., R(A+B-1) = vararg        */RWjlinux系统宝典
92 } OpCode;RWjlinux系统宝典

Lua 语言 15 分钟快速入门 RWjlinux系统宝典

Lua程序设计(第2版)中文 PDF RWjlinux系统宝典

Lua程序设计(第二版)阅读笔记 RWjlinux系统宝典

NetBSD 将支持用 Lua 脚本开发内核组件 RWjlinux系统宝典

编译安装 Lua LuaSocket RWjlinux系统宝典

Lua 的详细介绍RWjlinux系统宝典
Lua 的下载地址RWjlinux系统宝典



沪ICP备10206494号-4