文档章节

Lua4.0 语法分析

晓寒
 晓寒
发布于 2015/08/14 13:19
字数 1695
阅读 217
收藏 1

Lua 最初使用的是 Yacc 生成的语法分析器,后来改为手写的递归下降语法分析器(Recursive descent parser)。因为一般在语言发展的早期,语言的语法还没有稳定下来,变动可能会比较多,用工具可以快速的验证自己的想法。当语法稳定下来之后,一般都会采用手写的语法分析器。因为这样程序员是调试可控的,并且一般也能有更好的性能表现。递归下降的语法分析对编程语言的语法有要求。因 Lua 的语法比较简单,是 LL(1) 文法。所以,手工编写语法分析也就是情理之中的事了。


关于递归下降的语法分析,网上资料不少,比如维基百科:

https://en.wikipedia.org/wiki/Recursive_descent_parser

比如这篇:

http://www.cnblogs.com/Ninputer/archive/2011/06/21/2085527.html

里面都有很不错的示例。

具体内容就不贴出来了,感兴趣的同学可以自行阅读。


说到这儿,再往下说,就是具体的代码了。

对照 Lua 的 EBNF 语法(在 Lua 手册的最后面,有完整的语法表),一点点的套代码吧。


看一个经典的“hello world”程序吧。

程序的内容如下所示:


print("hello world! (using print)\n")


假设把它保存为 hello.lua 文件。

通过执行下面的命令,打印出它的字节码。

luac.exe -l hello.lua


下面是程序的输出:

main <0:@hello.lua> (4 instructions/16 bytes at 0087A0E8)

0 params, 2 stacks, 0 locals, 2 strings, 0 numbers, 0 functions, 2 lines

     1  [1]     GETGLOBAL       0       ; print

     2  [1]     PUSHSTRING      1       ; "hello world! (using print)\n"

     3  [1]     CALL            0 0

     4  [1]     END


程序输出的意思:

main 表示是顶层主程序,如果是函数定义的话,这里显示为 function

0:@hello.lua 程序从第 0 行开始,文件名为 hello.lua

后面的表示 4 条指令,共 16 个字节,位于内存 0087A0E8 处。


再下一行表示,有多少个参数,占用了多少个栈空间,局部变量个数,多少个字符串,数字,函数,及行数。


再下面就是字节码指令的具体内容(以方便阅读的形式表示出来的)。

每行的内容分别为 指令号,对应源代码的行号,指令,分号后面的为注释。


再来看看指令的具体内容:

GETGLOBAL   取得一个全局变量,由注释可以看到,取得的全局变量为 print

PUSHSTRING   字符串压栈

CALL        函数调用

END   结束

取得全局变量的时候,把取出来的全局变量放到什么地方?放到了数据栈上,就是下面字符串压栈的那个同样的栈。

在字节码运行的时候,Lua 虚拟机根据字节码指令指示,把相关的数据放到数据栈上,而后进行相应的操作。

因为虚拟机对数据栈的操作只会在栈顶进行,所以,我们说 Lua4.0 的虚拟机是栈式虚拟机。


看一看这个语法分析的函数调用流程:

从 luaY_parser 开始看。

Proto *luaY_parser (lua_State *L, ZIO *z) {
  struct LexState lexstate;
  struct FuncState funcstate;
  luaX_setinput(L, &lexstate, z, luaS_new(L, zname(z)));
  open_func(&lexstate, &funcstate);
  next(&lexstate);  /* read first token */
  chunk(&lexstate);
  //...
  return funcstate.f;
}

程序上来先设置好 LexState, FuncState

调用 next 取得第一个 token,就是 print 。

进入 chunk

static void chunk (LexState *ls) {
  /* chunk -> { stat [';'] } */
  int islast = 0;
  while (!islast && !block_follow(ls->t.token)) {
    islast = stat(ls);
    optional(ls, ';');
    //...
  }
}


进入语句 stat

static int stat (LexState *ls) {
  int line = ls->linenumber;  /* may be needed for error messages */
  switch (ls->t.token) {
    // other cases
    case TK_NAME: case '%': {  /* stat -> namestat */
      namestat(ls);
      return 0;
    }
    // other cases
  }
}

里面是个大的 switch case 。

这里触发的是 TK_NAME:


进入 namestat

static void namestat (LexState *ls) {
  /* stat -> func | ['%'] NAME assignment */
  FuncState *fs = ls->fs;
  expdesc v;
  var_or_func(ls, &v);
  if (v.k == VEXP) {  /* stat -> func */
    check_condition(ls, luaK_lastisopen(fs), "syntax error");  /* an upvalue? */
    luaK_setcallreturns(fs, 0);  /* call statement uses no results */
  }
  else {  /* stat -> ['%'] NAME assignment */
    int left = assignment(ls, &v, 1);
    luaK_adjuststack(fs, left);  /* remove eventual garbage left on stack */
  }
}


进入 var_or_func,设置表达式描述符 expdesc

static void var_or_func (LexState *ls, expdesc *v) {
  /* var_or_func -> ['%'] NAME var_or_func_tail */
  if (optional(ls, '%')) {  /* upvalue? */
    pushupvalue(ls, str_checkname(ls));
    v->k = VEXP;
    v->u.l.t = v->u.l.f = NO_JUMP;
  }
  else  /* variable name */
    singlevar(ls, str_checkname(ls), v);
  var_or_func_tail(ls, v);
}

显然,这里不是 upvalue,只是一个简单的变量名。


进入 singlevar, 先取得一个 TString 的值:

static TString *str_checkname (LexState *ls) {
  TString *ts;
  check_condition(ls, (ls->t.token == TK_NAME), "<name> expected");
  ts = ls->t.seminfo.ts;
  next(ls);
  return ts;
}

取得一个 TString

static void singlevar (LexState *ls, TString *n, expdesc *var) {
  int level = search_local(ls, n, var);
  if (level >= 1)  /* neither local (0) nor global (-1)? */
    luaX_syntaxerror(ls, "cannot access a variable in outer scope", n->str);
  else if (level == -1)  /* global? */
    var->u.index = string_constant(ls->fs, n);
}

查看是否是局部变量,显然不是。这里 level 值为 -1。

取得 string 在全局字符串表中的下标:

static int string_constant (FuncState *fs, TString *s) {
  Proto *f = fs->f;
  int c = s->u.s.constindex;
  if (c >= f->nkstr || f->kstr[c] != s) {
    luaM_growvector(fs->L, f->kstr, f->nkstr, 1, TString *,
                    "constant table overflow", MAXARG_U);
    c = f->nkstr++;
    f->kstr[c] = s;
    s->u.s.constindex = c;  /* hint for next time */
  }
  return c;
}

回到 var_or_func, 进入 var_or_func_tail

static void var_or_func_tail (LexState *ls, expdesc *v) {
  for (;;) {
    switch (ls->t.token) {
      // other cases:
      case '(': case TK_STRING: case '{': {  /* var_or_func_tail -> funcargs */
        luaK_tostack(ls, v, 1);  /* `v' must be on stack */
        funcargs(ls, 0);
        v->k = VEXP;
        v->u.l.t = v->u.l.f = NO_JUMP;
        break;
      }
      default: return;  /* should be follow... */
    }
  }
}

因为当前的 token 为 '(',所以进入上面的 case。

进入 luaK_tostack(位于 lcode.c 文件中),生成字节码 GETGLOBAL 0

进入 funcargs,设置函数 print 的参数。

static void funcargs (LexState *ls, int slf) {
  FuncState *fs = ls->fs;
  int slevel = fs->stacklevel - slf - 1;  /* where is func in the stack */
  switch (ls->t.token) {
    case '(': {  /* funcargs -> '(' [ explist1 ] ')' */
      int line = ls->linenumber;
      int nargs = 0;
      next(ls);
      if (ls->t.token != ')')  /* arg list not empty? */
        nargs = explist1(ls);
      check_match(ls, ')', '(', line);
#ifdef LUA_COMPAT_ARGRET
      if (nargs > 0)  /* arg list is not empty? */
        luaK_setcallreturns(fs, 1);  /* last call returns only 1 value */
#else
      UNUSED(nargs);  /* to avoid warnings */
#endif
      break;
    }
    // other cases
  }
  fs->stacklevel = slevel;  /* call will remove function and arguments */
  luaK_code2(fs, OP_CALL, slevel, MULT_RET);
}


因为有参数,所以进入 explist1

static int explist1 (LexState *ls) {
  /* explist1 -> expr { ',' expr } */
  int n = 1;  /* at least one expression */
  expdesc v;
  expr(ls, &v);
  while (ls->t.token == ',') {
    luaK_tostack(ls, &v, 1);  /* gets only 1 value from previous expression */
    next(ls);  /* skip comma */
    expr(ls, &v);
    n++;
  }
  luaK_tostack(ls, &v, 0);  /* keep open number of values of last expression */
  return n;
}

先通过 expr 取得表达示描述信息。

进入 expr, subexpr, simpleexp

因为是一个简单的表达式,只有一个字符串 "hello world! (using print)\n",

static void simpleexp (LexState *ls, expdesc *v) {
  FuncState *fs = ls->fs;
  switch (ls->t.token) {
    // other cases
    case TK_STRING: {  /* simpleexp -> STRING */
      code_string(ls, ls->t.seminfo.ts);  /* must use `seminfo' before `next' */
      next(ls);
      break;
    }
    // other codes


code_string 设置字节码,PUSHSTRING 1

回到 funcargs。设置函数调用字节码:

luaK_code2(fs, OP_CALL, slevel, MULT_RET);

回到 namestat,设置返回字节码:END

回到 chunk,luaY_parser 语法分析结束。


语法分析过程再跟踪下去基本就是个体力活了,不再举例子了。

对照着 EBNF 及生成的字节码,一步步的跟踪就是了。

其它的语法分析的理论,参见编译原理。

或者是看开头部分的那些简要的描述,也可以了解了大概。

----------------------------------------

到目前为止的问题:

> TString 数据结构和 luaS_new 

> 函数原型优化 luaU_optchunk

> 打印函数原型 luaU_printchunk

> dump 函数原型 luaU_dumpchunk

----------------------------------------


© 著作权归作者所有

上一篇: Lua4.0 字符串相关
下一篇: Lua4.0 词法分析
晓寒
粉丝 35
博文 119
码字总数 133745
作品 0
海淀
私信 提问
Lua5.0 语法分析

写着写着,又来到了这里。 这次是写还是不写,嗯,这是一个问题。 先说点题外话,没准也算是题内。 经过这段时间的代码阅读,分析,调试,感觉自己的代码控制力提高了一些。 当然了,不单是 ...

晓寒
2015/09/06
133
2
Lua4.0 lua_dofile,lua_dostring

这两个函数的定义都位于 ldo.c 中,看看这两个函数都做了什么事儿? 先来看一下 lua_dofile 执行文件 LUAAPI int luadofile (lua_State *L, const char *filename) { int status = parse_fil...

晓寒
2015/08/21
3.7K
0
Lua4.0 参考手册(三)4.5

(接上篇) ------------------- 4.5 表达式 ------------------- --------- 4.5.1 基本表达式 --------- Lua 中基本表达式是: exp ::= )' exp ::= nil exp ::= number exp ::= literal ex......

晓寒
2014/11/04
121
0
Lua4.0 参考手册(二)4.1-4.4

(接上篇) -------------------------------------- 4 语言 -------------------------------------- 这节描述 Lua 的词法,语法和语义。 ------------------- 4.1 词法约定 --------------......

晓寒
2014/11/03
206
0
Lua4.0 参考手册(一)1-3

说明: 这个文档是 doc 目录里的 manual.html 文件。 原文版权归原作者所有,这篇翻译只是作为学习之用。如果翻译有不当之处,请参考原文。 -------------------以下是正文-----------------...

晓寒
2014/10/30
223
0

没有更多内容

加载失败,请刷新页面

加载更多

面向对象编程

1、类和对象 类是对象的蓝图和模板,而对象是实例;即对象是具体的实例,类是一个抽象的模板 当我们把一大堆拥有共同特征的对象的静态特征(属性)和动态特征(行为)都抽取出来后,就可以定...

huijue
今天
8
0
redis异常解决 :idea启动本地redis出现 jedis.exceptions.JedisDataException: NOAUTH Authentication required

第一次安装在本地redis服务,试试跑项目,结果却出现nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required错误,真是让人头疼 先检查一...

青慕
今天
10
0
Spring 之 IoC 源码分析 (基于注解方式)

一、 IoC 理论 IoC 全称为 Inversion of Control,翻译为 “控制反转”,它还有一个别名为 DI(Dependency Injection),即依赖注入。 二、IoC方式 Spring为IoC提供了2种方式,一种是基于xml...

星爵22
今天
25
0
Docker安装PostgresSql

Docker安装PostgresSql 拉取docker镜像 # docker pull postgres:10.1010.10: Pulling from library/postgres9fc222b64b0a: Pull complete 38296355136d: Pull complete 2809e135bbdb: Pu......

Tree
今天
8
0
内容垂直居中

方法一: 采用上下 padding 形式,将内容放置在垂直居中 .line { padding: 2% 0; text-align: center; height: 5px;} <div class="line"> 内容垂直居中</div> 方法二: 采......

低至一折起
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部