接上一篇：lua源碼剖析（一）
詞法分析
lua對(duì)與每一個(gè)文件(chunk)建立一個(gè)LexState來做詞法分析的context數(shù)據(jù)，此結(jié)構(gòu)定義在llex.h中。詞法分析根據(jù)語法分析的需求有當(dāng)前token，有l(wèi)ookahead token，LexState結(jié)構(gòu)如圖：
其中token結(jié)構(gòu)中用int存儲(chǔ)實(shí)際token值，此token值對(duì)于單字符token(+ - * /之類)就表示自身，對(duì)于多字符(關(guān)鍵字等)token是起始值為257的枚舉值，在llex.h文件中定義：
#define FIRST_RESERVED 257
/*
* WARNING: if you change the order of this enumeration,
* grep "ORDER RESERVED"
*/enum RESERVED {
/* terminal symbols denoted by reserved words */ TK_AND = FIRST_RESERVED, TK_BREAK,
TK_DO, TK_ELSE, TK_ELSEIF, TK_END, TK_FALSE, TK_FOR, TK_FUNCTION,
TK_GOTO, TK_IF, TK_IN, TK_LOCAL, TK_NIL, TK_NOT, TK_OR, TK_REPEAT,
TK_RETURN, TK_THEN, TK_TRUE, TK_UNTIL, TK_WHILE,
/* other terminal symbols */ TK_CONCAT, TK_DOTS, TK_EQ, TK_GE, TK_LE, TK_NE, TK_DBCOLON, TK_EOS,
TK_NUMBER, TK_NAME, TK_STRING
};
token結(jié)構(gòu)中還有一個(gè)成員seminfo，這個(gè)表示語義信息，根據(jù)token的類型，可以表示數(shù)值或者字符串。
lex提供函數(shù)luaX_next和luaX_lookahead分別lex下一個(gè)token和lookahead token，在內(nèi)部是通過llex函數(shù)來完成詞法分析。
語法分析
lua語法分析是從lparser.c中的luaY_parser開始：
Closure *luaY_parser (lua_State *L, ZIO *z, Mbuffer *buff,
Dyndata *dyd, const char *name, int firstchar) {
LexState lexstate;
FuncState funcstate;
Closure *cl = luaF_newLclosure(L, 1); /* create main closure */
/* anchor closure (to avoid being collected) */
setclLvalue(L, L->top, cl);
incr_top(L);
funcstate.f = cl->l.p = luaF_newproto(L);
funcstate.f->source = luaS_new(L, name); /* create and anchor TString */
lexstate.buff = buff;
lexstate.dyd = dyd;
dyd->actvar.n = dyd->gt.n = dyd->label.n = 0;
luaX_setinput(L, &lexstate, z, funcstate.f->source, firstchar);
mainfunc(&lexstate, &funcstate);
lua_assert(!funcstate.prev && funcstate.nups == 1 && !lexstate.fs);
/* all scopes should be correctly finished */
lua_assert(dyd->actvar.n == 0 && dyd->gt.n == 0 && dyd->label.n == 0);
return cl; /* it's on the stack too */
}
此函數(shù)創(chuàng)建一個(gè)closure并把LexState和FuncState初始化后調(diào)用mainfunc開始parse，其中FuncState表示parse時(shí)函數(shù)狀態(tài)信息的，如圖：
每當(dāng)parse到一個(gè)function的時(shí)候都會(huì)建立一個(gè)FuncState結(jié)構(gòu)，并將它與所嵌套的函數(shù)通過prev指針串聯(lián)起來，body函數(shù)就是完成嵌套函數(shù)parse。
static void body (LexState *ls, exposed *e, int ismethod, int line) {
/* body -> `(' parlist `)' block END */
FuncState new_fs;
BlockCnt bl;
new_fs.f = addprototype(ls);
new_fs.f->linedefined = line;
open_func(ls, &new_fs, &bl);
checknext(ls, '(');
if (ismethod) {
new_localvarliteral(ls, "self"); /* create 'self' parameter */
adjustlocalvars(ls, 1);
}
parlist(ls);
checknext(ls, ')');
statlist(ls);
new_fs.f->lastlinedefined = ls->linenumber;
check_match(ls, TK_END, TK_FUNCTION, line);
codeclosure(ls, e);
close_func(ls);
}
FuncState中的f指向這個(gè)函數(shù)的Proto，Proto中保存著函數(shù)的指令、變量信息、upvalue信息等其它信息，Proto的結(jié)構(gòu)如圖：
k指向一個(gè)這個(gè)Proto中使用到的常量，code指向這個(gè)Proto的指令數(shù)組，Proto **p指向這個(gè)Proto內(nèi)部的Proto列表，locvars存儲(chǔ)local變量信息，upvalues存儲(chǔ)upvalue的信息，cache指向最后創(chuàng)建的closure，source指向這個(gè)Proto所屬的文件名，后面的size*分別表示前面各個(gè)指針指向的數(shù)組的大小，numparams表示固定的參數(shù)的個(gè)數(shù)，is_vararg表示這個(gè)Proto是否是一個(gè)變參函數(shù)，maxstacksize表示最大stack大小。
FuncState中的ls指向LexState，在LexState中有一個(gè)Dyndata的結(jié)構(gòu)，這個(gè)結(jié)構(gòu)用于保存在parse一個(gè)chunk的時(shí)候所存儲(chǔ)的gt label list和label list以及所有active變量列表，其中g(shù)t label list存儲(chǔ)的是未匹配的goto語句和break語句的label信息，而label list存儲(chǔ)的是已聲明的label。待出現(xiàn)一個(gè)gt label的時(shí)候就在label list中查找是否有匹配的label，若出現(xiàn)一個(gè)label也將在gt label list中查找是否有匹配的gt。
LuaY_parser調(diào)用mainfunc開始parse一個(gè)chunk：
static void mainfunc (LexState *ls, FuncState *fs) {
BlockCnt bl;
expdesc v;
open_func(ls, fs, &bl);
fs->f->is_vararg = 1;
/* main function is always vararg */ init_exp(&v, VLOCAL, 0);
/* create and
*/ newupvalue(fs, ls->envn, &v);
/* set environment upvalue */ luaX_next(ls);
/* read first token */ statlist(ls);
/* parse main body */ check(ls, TK_EOS);
close_func(ls);
}
在mainfunc中通過open_func函數(shù)完成對(duì)進(jìn)入某個(gè)函數(shù)進(jìn)行parse之前的初始化操作，每parse進(jìn)一個(gè)block的時(shí)候，將建立一個(gè)BlockCnt的結(jié)構(gòu)并與上一個(gè)BlockCnt連接起來，當(dāng)parse完一個(gè)block的時(shí)候就回彈出最后一個(gè)BlockCnt結(jié)構(gòu)。BlockCnt結(jié)構(gòu)中的其它變量的意思是：nactvar表示這個(gè)block之前的active var的個(gè)數(shù)，upval表示這個(gè)block是否有upvalue被其它block訪問，isloop表示這個(gè)block是否是循環(huán)block。mainfunc中調(diào)用statlist，statlist調(diào)用statement開始parse語句和表達(dá)式。
statement分析語句采用的是LL(2)的遞歸下降語法分析法。在statement里面通過case語句處理各個(gè)帶關(guān)鍵字的語句，在default語句中處理賦值和函數(shù)調(diào)用的分析。語句中的表達(dá)式通過expr函數(shù)處理，其處理的BNF如下：
exp ::= nil | false | true | Number | String | ‘...’ | functiondef |
prefixexp | tableconstructor | exp binop exp | unop exp
expr函數(shù)調(diào)用subexpr函數(shù)完成處理。
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 */
}
當(dāng)分析exp binop exp | unop exp的時(shí)候lua采用的是算符優(yōu)先分析，其各個(gè)運(yùn)算符的優(yōu)先級(jí)定義如下：
static const struct {
lu_byte left; /* left priority for each binary operator */
lu_byte right; /* right priority */
} priority[] = { /* ORDER OPR */
{6, 6}, {6, 6}, {7, 7}, {7, 7}, {7, 7}, /* `+' `-' `*' `/' `%' */
{10, 9}, {5, 4}, /* ^, .. (right associative) */
{3, 3}, {3, 3}, {3, 3}, /* ==, <, <= */
{3, 3}, {3, 3}, {3, 3}, /* ~=, >, >= */
{2, 2}, {1, 1} /* and, or */
};
#define UNARY_PRIORITY 8 /* priority for unary operators */
代碼生成
lua代碼生成是伴隨著語法分析進(jìn)行的，指令類型Instruction定義在llimits.h中：
/*
** type for virtual-machine instructions
** must be an unsigned with (at least) 4 bytes (see details in lopcodes.h)
*/
typedef lu_int32 Instruction;
Instruction是一個(gè)32位的整形數(shù)據(jù)，其中0~5 bits表示optype，6~13 bits參數(shù)A，14~22 bits表示參數(shù)B，23~31 bits表示參數(shù)C，14~31 bits表示參數(shù)Bx或sBx，6~31 bits表示參數(shù)Ax。
代碼生成的函數(shù)聲明在lcode.h中，以luaK開頭，這一系列的函數(shù)大多都有expdesc *v的參數(shù)，expdesc的結(jié)構(gòu)定義在lparser.h，如下：
typedef struct expdesc {
expkind k;
union {
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;
int info; /* for generic use */
lua_Number nval; /* for VKNUM */
} u;
int t; /* patch list of `exit when true' */
int f; /* patch list of `exit when false' */
} expdesc;
expdesc中的t和f分別表示表達(dá)式為true和false時(shí)，待回填跳轉(zhuǎn)指令的下標(biāo)。k表示表達(dá)式的類型，u表示對(duì)應(yīng)類型的數(shù)據(jù)。
代碼生成過程中根據(jù)表達(dá)式類型做相應(yīng)的代碼生成操作，lua中每個(gè)函數(shù)最大有250個(gè)寄存器，表達(dá)式的計(jì)算就是選擇這些寄存器存放并生成數(shù)據(jù)，而寄存器的下標(biāo)是在代碼生成階段選擇好的，寄存器的釋放是根據(jù)變量和表達(dá)式的生命周期結(jié)束的時(shí)候釋放。代碼生成過程會(huì)將變量的生命周期的起始pc和結(jié)束指令pc分別存放在Proto中的LocVar的startpc和endpc里面，供調(diào)試使用。
posted on 2012-08-12 17:28
airtrack 閱讀(8560)
評(píng)論(0) 編輯 收藏 引用