歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Lua解析腳本過程中的關鍵數據結構介紹

在這一篇文章中我先來介紹一下lua解析一個腳本文件時要用到的一些關鍵的數據結構,為將來的一系列代碼分析打下一個良好的基礎。在整個過程中,比較重要的幾個源碼文件分別是:llex.h,lparse.h、lobject.h和lopcode.h。

在llex.h中

1 typedef struct Token {
2  int token;
3  SemInfo seminfo;
4 } Token;

Token代表了一個詞法單元,其中token表示詞法類型如TK_NAME、TK_NUMBER等如果不是這些類型則存放則詞素的字符表示,例如分析的代碼會這麼判斷詞素單元:


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

 

在Token中SemInfo存放了一些語義相關的一些內容信息

1 typedef union {
2  lua_Number r;
3  TString *ts;
4 } SemInfo;  /* semantics information */

其中當token是數字是內容存放在r中,其他情況存放在ts指向的TString中。

下面是最重要的一個數據結構之一

 

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

 

LexState不僅用於保存當前的詞法分析狀態信息,而且也保存了整個編譯系統的全局狀態。current指向了當前字符,t存放了當前的toekn,lookahead存放了向前看的token,由此我認為lua應該是ll(1)的~哈哈(不知道對不對)。fs指向了parser當前解析的函數的一些相關的信息,L指向了當前lua_State結構,z指向輸入流,buff指向了token buffer,其他的看注釋吧。

下面看看lparse.h文件中的重要結構:

 

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

 

expdesc是存放了表達式的相關描述信息,k是表達式的種類,u在不同的表達式中有不同的含義。

1 typedef struct upvaldesc {
2  lu_byte k;
3  lu_byte info;
4 } upvaldesc;

upvaldesc是存放了upval的相關描述信息。

最後是本文件中最重要的結構:

 

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

 

在編譯過程中,使用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是當前作用域的局部變量數。

在lparse.c中定義了BlockCnt

 

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

 

Lua使用BlockCnt來保存一個block的數據。與FuncState的分析方法類似,BlockCnt使用一個previous變量保存外圍block的引用,形成一個棧結構。

 

下面介紹一些在lobject.h文件裡面的數據結構

 

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

 

結構體Proto是lua函數協議的描述,在lua解析腳本時首先會將main chunk代碼包裹為一個函數,用main proto描述,接著將裡面定義的內部函數一一用Proto結構體描述,將這些Proto的關系用樹來組合起來,例如有lua源碼文件如下

 

1 a = 1
2 function f1()
3 -- ...
4 end
5 function f2()
6    function f3()
7    -- ...
8    end
9 end

 

則parse完成後會有如圖如下關系

 

在Proto結構體中,k指向一個const變量數組,存放則函數要用到的常量;code指向lua parse過程中生成的本函數的instruction集合;p就是指向本函數內部定義的函數的那些proto;locvars指向本函數局部變量數組;upvalues指向本函數upvalue變量數組;nups為upvalue的數量;numparams為函數參數的數量;is_vararg表示函數是否接收可變參數;maxstacksize為函數stack的max大小。

在編譯期間lua使用Proto描述函數的,當lua vm開始運行vm時需要根據Proto生成相應的Closure來執行vm instructions。

1 typedef union Closure {
2  CClosure c;
3  LClosure l;
4 } Closure;

Closure要麼代表了c函數,要麼為lua函數,在這裡我們只看lua函數的LClosure

 

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

 

在LClousre中,p就是指向對應函數的Proto結構體啦,upvals顧名思義就是此closure的upvalue數組羅。在ClosureHeader宏中isC表示此closure是否是c函數,nupvalues為upvalue數目,env指向了此closue運行時的函數環境,在lua中可以用stefenv來改變當前函數的環境,就是改變env變量的指向啦。

最後,在文件lopcode.h中定義了lua vm的指令結構

 

下面是vm指令的一些定義與描述,我在相應vm指令的上方添加了一些注釋

 

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

Lua 語言 15 分鐘快速入門 http://www.linuxidc.com/Linux/2013-06/86582.htm

Lua程序設計(第2版)中文 PDF http://www.linuxidc.com/Linux/2013-03/81833.htm

Lua程序設計(第二版)閱讀筆記 http://www.linuxidc.com/Linux/2013-03/81834.htm

NetBSD 將支持用 Lua 腳本開發內核組件 http://www.linuxidc.com/Linux/2013-02/79527.htm

CentOS 編譯安裝 Lua LuaSocket http://www.linuxidc.com/Linux/2011-08/41105.htm

Lua 的詳細介紹:請點這裡
Lua 的下載地址:請點這裡

Copyright © Linux教程網 All Rights Reserved