LuaJIT源码分析(六)语法分析

embedded/2024/11/15 3:32:41/

LuaJIT源码分析(六)语法分析

lua虚拟机在编译lua脚本时,在对源代码进行词法分析之后,还需要进行语法分析,把源代码翻译成字节码。lua 5.1完整的语法描述如下:

在这里插入图片描述

LuaJIT采用的是递归下降的解析方式,也就是自顶向下开始解析。LuaJIT的语法分析过程并不会显式地生成语法树,而是直接生成对应的字节码。上述EBNF描述中,{}包住的部分表示可以出现0次或者多次,[]包住的部分表示可以出现0次或者1次,大写字母开头(如Name,String,Number)和字体加粗的部分表示lua词法分析的token,它们不能继续用子表达式来进行描述。

通过语法描述,我们可以知道,lua代码是以chunk为单位组成的,chunk又是由若干语句(statement)组成的,statement又分为普通的statement和最后结尾的last statement组成。所谓的last statement,就是看是否包含return或者break关键字。也就是说,如果在解析chunk的时候,看到了return或者break,则说明chunk要结束了。但是last statement是可选的,如果last statement不存在的情况下,又要如何判断chunk是否结束呢?通过观察statement的规则,可以发现chunk只能以关键字end,else,elseif或者until结尾。LuaJIT解析chunk的代码如下:

// lj_parse.c
/* A chunk is a list of statements optionally separated by semicolons. */
static void parse_chunk(LexState *ls)
{int islast = 0;synlevel_begin(ls);while (!islast && !parse_isend(ls->tok)) {islast = parse_stmt(ls);lex_opt(ls, ';');lj_assertLS(ls->fs->framesize >= ls->fs->freereg &&ls->fs->freereg >= ls->fs->nactvar,"bad regalloc");ls->fs->freereg = ls->fs->nactvar;  /* Free registers after each stmt. */}synlevel_end(ls);
}

其中parse_isend函数就是处理普通statement的情况:

// lj_parse.c
/* Check for end of block. */
static int parse_isend(LexToken tok)
{switch (tok) {case TK_else: case TK_elseif: case TK_end: case TK_until: case TK_eof:return 1;default:return 0;}
}

parse_stmt函数负责解析所有的statement,如果是last statement返回1。

/* Parse a statement. Returns 1 if it must be the last one in a chunk. */
static int parse_stmt(LexState *ls)
{BCLine line = ls->linenumber;switch (ls->tok) {case TK_if:parse_if(ls, line);break;case TK_while:parse_while(ls, line);break;case TK_do:lj_lex_next(ls);parse_block(ls);lex_match(ls, TK_end, TK_do, line);break;case TK_for:parse_for(ls, line);break;case TK_repeat:parse_repeat(ls, line);break;case TK_function:parse_func(ls, line);break;case TK_local:lj_lex_next(ls);parse_local(ls);break;case TK_return:parse_return(ls);return 1;  /* Must be last. */case TK_break:lj_lex_next(ls);parse_break(ls);return !LJ_52;  /* Must be last in Lua 5.1. *//* fallthrough */default:parse_call_assign(ls);break;}return 0;
}

lua5.1的语法总共支持13种statement,通过当前token,就可以把大部分statement区分开,例如上述的代码,就把statement划分为了9种情况分别处理。可以看到,除了for,local,以及赋值函数调用statement之外,其他的statement通过当前的token就能区分。我们以if语句为例,来看一下一般的解析过程:

在这里插入图片描述

// lj_parse.c
/* Parse 'if' statement. */
static void parse_if(LexState *ls, BCLine line)
{FuncState *fs = ls->fs;BCPos flist;BCPos escapelist = NO_JMP;flist = parse_then(ls);while (ls->tok == TK_elseif) {  /* Parse multiple 'elseif' blocks. */jmp_append(fs, &escapelist, bcemit_jmp(fs));jmp_tohere(fs, flist);flist = parse_then(ls);}if (ls->tok == TK_else) {  /* Parse optional 'else' block. */jmp_append(fs, &escapelist, bcemit_jmp(fs));jmp_tohere(fs, flist);lj_lex_next(ls);  /* Skip 'else'. */parse_block(ls);} else {jmp_append(fs, &escapelist, flist);}jmp_tohere(fs, escapelist);lex_match(ls, TK_end, TK_if, line);
}

LuaJIT是语法分析和代码生成一起进行的,因此这里包含了一些生成代码的逻辑,这里我们暂时先忽略。可以看到解析if语句的主逻辑并不复杂,首先解析第一个if和then,然后再不断地尝试解析elseif,最后再去解析可选的else。解析条件表达式和then之后的block的逻辑位于parse_then这个函数:

// lj_parse.c
/* Parse condition and 'then' block. */
static BCPos parse_then(LexState *ls)
{BCPos condexit;lj_lex_next(ls);  /* Skip 'if' or 'elseif'. */condexit = expr_cond(ls);lex_check(ls, TK_then);parse_block(ls);return condexit;
}

接下来看一下稍微麻烦一点的for语句。它需要再多看一个token,如果token为赋值运算符=,说明是数值for语句,否则是通用for语句,for的语法图如下:

在这里插入图片描述

// lj_parse.c
/* Parse 'for' statement. */
static void parse_for(LexState *ls, BCLine line)
{FuncState *fs = ls->fs;GCstr *varname;FuncScope bl;fscope_begin(fs, &bl, FSCOPE_LOOP);lj_lex_next(ls);  /* Skip 'for'. */varname = lex_str(ls);  /* Get first variable name. */if (ls->tok == '=')parse_for_num(ls, varname, line);else if (ls->tok == ',' || ls->tok == TK_in)parse_for_iter(ls, varname);elseerr_syntax(ls, LJ_ERR_XFOR);lex_match(ls, TK_end, TK_for, line);fscope_end(fs);  /* Resolve break list. */
}

同样稍微麻烦一点的还有local语句。它也需要前瞻一个token,判断到底是函数声明还是变量声明。

在这里插入图片描述

// lj_parse.c
/* Parse 'local' statement. */
static void parse_local(LexState *ls)
{if (lex_opt(ls, TK_function)) {  /* Local function declaration. */ExpDesc v, b;FuncState *fs = ls->fs;var_new(ls, 0, lex_str(ls));expr_init(&v, VLOCAL, fs->freereg);v.u.s.aux = fs->varmap[fs->freereg];bcreg_reserve(fs, 1);var_add(ls, 1);parse_body(ls, &b, 0, ls->linenumber);/* bcemit_store(fs, &v, &b) without setting VSTACK_VAR_RW. */expr_free(fs, &b);expr_toreg(fs, &b, v.u.s.info);/* The upvalue is in scope, but the local is only valid after the store. */var_get(ls, fs, fs->nactvar - 1).startpc = fs->pc;} else {  /* Local variable declaration. */ExpDesc e;BCReg nexps, nvars = 0;do {  /* Collect LHS. */var_new(ls, nvars++, lex_str(ls));} while (lex_opt(ls, ','));if (lex_opt(ls, '=')) {  /* Optional RHS. */nexps = expr_list(ls, &e);} else {  /* Or implicitly set to nil. */e.k = VVOID;nexps = 0;}assign_adjust(ls, nvars, nexps, &e);var_add(ls, nvars);}
}

最后就是最麻烦的赋值函数调用statement,它们无法直接通过前瞻token就能判断,因为前缀表达式(prefixexp)可以一直递归无限长。不过通过分析语法规则可以发现,前缀表达式再怎么长,最基本的形式一定是Name或者(exp)。通过解析最基本的形式,就可以一直往外扩展,直到解析完成完整的前缀表达式。前缀表达式的语法图如下:

在这里插入图片描述

然后,如果下一个token是({或者String,就说明下面要解析的是args,也就是当前的statement是函数调用(functioncall);如果下一个token是:,则说明当前statement是带self语法糖的函数调用。除此之外的情况,就都按赋值语句的规则进行解析。

// lj_parse.c/* Parse call statement or assignment. */
static void parse_call_assign(LexState *ls)
{FuncState *fs = ls->fs;LHSVarList vl;expr_primary(ls, &vl.v);if (vl.v.k == VCALL) {  /* Function call statement. */setbc_b(bcptr(fs, &vl.v), 1);  /* No results. */} else {  /* Start of an assignment. */vl.prev = NULL;parse_assignment(ls, &vl, 1);}
}/* Parse primary expression. */
static void expr_primary(LexState *ls, ExpDesc *v)
{FuncState *fs = ls->fs;/* Parse prefix expression. */if (ls->tok == '(') {BCLine line = ls->linenumber;lj_lex_next(ls);expr(ls, v);lex_match(ls, ')', '(', line);expr_discharge(ls->fs, v);} else if (ls->tok == TK_name || (!LJ_52 && ls->tok == TK_goto)) {var_lookup(ls, v);} else {err_syntax(ls, LJ_ERR_XSYMBOL);}for (;;) {  /* Parse multiple expression suffixes. */if (ls->tok == '.') {expr_field(ls, v);} else if (ls->tok == '[') {ExpDesc key;expr_toanyreg(fs, v);expr_bracket(ls, &key);expr_index(fs, v, &key);} else if (ls->tok == ':') {ExpDesc key;lj_lex_next(ls);expr_str(ls, &key);bcemit_method(fs, v, &key);parse_args(ls, v);} else if (ls->tok == '(' || ls->tok == TK_string || ls->tok == '{') {expr_tonextreg(fs, v);if (ls->fr2) bcreg_reserve(fs, 1);parse_args(ls, v);} else {break;}}
}

到目前为止,statement层面算是分析完了,那么再往下走,就到了表达式(exp)层面了。解析表达式可能会遇到一元或是二元运算符,然后就会涉及到运算符的优先级和结合性。lua 5.1中的运算符从低到高的优先级如下:

在这里插入图片描述

其中,只有拼接..和乘方^是右结合性,其他均为左结合性。LuaJIT关于运算符优先级的定义如下:

// lj_parse.c
/* Priorities for each binary operator. ORDER OPR. */
static const struct {uint8_t left;		/* Left priority. */uint8_t right;	/* Right priority. */
} priority[] = {{6,6}, {6,6}, {7,7}, {7,7}, {7,7},	/* ADD SUB MUL DIV MOD */{10,9}, {5,4},			/* POW CONCAT (right associative) */{3,3}, {3,3},				/* EQ NE */{3,3}, {3,3}, {3,3}, {3,3},		/* LT GE GT LE */{2,2}, {1,1}				/* AND OR */
};#define UNARY_PRIORITY		8  /* Priority for unary operators. */

可以看到,两个右结合性的运算符left字段均大于right字段。所谓的left和right,应当是指操作数是在运算符的左边还是右边,例如a … b … c,b受两个..运算符影响,但b在第一个运算符的右边(优先级为4),第二个运算符的左边(优先级为5),所以b要先跟第二个运算符进行计算。通过这种方式就能比较容易地实现结合性的逻辑。

同时,LuaJIT为了避免回溯,在解析二元运算符表达式时,每次只解析一个运算符,然后就开始递归,让子函数就解析剩下的表达式。例如exp1 op1 exp2 op2 exp3,第一次只解析exp1和op1,子函数负责解析exp2 op2 exp3。如果op2的左优先级大于op1的右优先级(这里就把结合性和优先级统一起来了),说明就是要先解析子函数;反之,子函数只会解析exp2 op2这一部分,把解析结果记录下来后直接返回,表示实际要解析的是exp1 op1 exp2,并且解析完之后下一个运算符是op2。这样做就能保证词法分析器一次扫描即可,无需回溯。

// lj_parse.c
/* Parse binary expressions with priority higher than the limit. */
static BinOpr expr_binop(LexState *ls, ExpDesc *v, uint32_t limit)
{BinOpr op;synlevel_begin(ls);expr_unop(ls, v);op = token2binop(ls->tok);while (op != OPR_NOBINOPR && priority[op].left > limit) {ExpDesc v2;BinOpr nextop;lj_lex_next(ls);bcemit_binop_left(ls->fs, op, v);/* Parse binary expression with higher priority. */nextop = expr_binop(ls, &v2, priority[op].right);bcemit_binop(ls->fs, op, v, &v2);op = nextop;}synlevel_end(ls);return op;  /* Return unconsumed binary operator (if any). */
}

另外,一元运算符表达式,本质上也可以被认为是二元运算符表达式的特殊形式。例如-exp1 op exp2可能是exp1 op exp2之后的结果再取负,也可能是-exp1exp2进行计算。

// lj_parse.c
/* Parse unary expression. */
static void expr_unop(LexState *ls, ExpDesc *v)
{BCOp op;if (ls->tok == TK_not) {op = BC_NOT;} else if (ls->tok == '-') {op = BC_UNM;} else if (ls->tok == '#') {op = BC_LEN;} else {expr_simple(ls, v);return;}lj_lex_next(ls);expr_binop(ls, v, UNARY_PRIORITY);bcemit_unop(ls->fs, op, v);
}

除了运算符表达式之外,剩余比较复杂的就是前缀表达式,表构造器表达式,和函数定义表达式了。前缀表达式我们前面已经分析过了,函数定义表达式和前面函数的statement类似。表构造器表达式(tableconstructor)的语法图如下:

在这里插入图片描述

Reference

[1] The Complete Syntax of Lua

[2] Railroad Diagram Generator


http://www.ppmy.cn/embedded/137662.html

相关文章

前端呈现效果:鱼眼相机城市环境图像分割

鱼眼相机城市环境图像分割系统源码&数据集分享 [yolov8-seg-SPDConv&yolov8-seg-vanillanet等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI G…

爬虫补环境案例---问财网(rpc,jsdom,代理,selenium)

目录 一.环境检测 1. 什么是环境检测 2.案例讲解 二 .吐环境脚本 1. 简介 2. 基础使用方法 3.数据返回 4. 完整代理使用 5. 代理封装 6. 封装所有使用方法 jsdom补环境 1. 环境安装 2. 基本使用 3. 添加参数形式 Selenium补环境 1. 简介 2.实战案例 1. 逆向目…

C哈的刷题计划之输出数字螺旋矩阵(1)

1、盲听C哈说 都说数据结构与算法是编程的核心,它们两个是内功与心法😀,其它编程工具只是招式,学会了内功与心法,学习新事物(这里特指层出不穷的IT技术)就没有那么难了,实际上&#…

【面试全纪实 | Nginx 04】请回答,你真的精通Nginx吗?

🗺️博客地图 📍1、location的作用是什么? 📍2、你知道漏桶流算法和令牌桶算法吗? 📍3、Nginx限流怎么做的? 📍4、为什么要做动静分离? 📍5、Nginx怎么做…

thinkphp如何查出值是null的布尔类型的值

exp 是用原生表达式查询的意思 $resDb::table(tbcardlist)->where(qc_hr_wac_hadsend,exp,is null or qc_hr_wac_hadsend0)->order(ID,asc)->find();查询值是null的字段的值时,要写 name is null 写 name null 是查不出正确的数据的 要写 name is null …

【K8S问题系列 | 9】如何监控集群CPU使用率并设置告警?

监控 Kubernetes 集群的 CPU 使用率并设置告警是确保集群健康和性能的关键步骤。以下是详细的步骤,包括所需工具和配置方法。 1. 安装监控工具 1.1 Prometheus Prometheus 是一个开源监控系统,能够收集和存储时间序列数据。你可以通过 Helm 或 Kubernetes 清单来安装 Prom…

30.1 时序数据库TSDB的典型特点

本节重点介绍 : db-ranking网站对db进行排名时序数据特点时序数据库特点时序数据库遇到的挑战开源时间序列数据库 db-ranking 一个神奇的网站 https://db-engines.com/en/ranking 时序数据ranking https://db-engines.com/en/ranking/timeseriesdbms 排名方法 https://db-en…

Python 连接 Redis 进行增删改查(CRUD)操作

文章目录 Python 连接 Redis 进行增删改查(CRUD)操作介绍安装 redis-py连接 Redis增加(Create)查询(Read)更新(Update)删除(Delete)其他常用操作检查键是否存…