egmkang 服务端开发工程师

[翻译]Lemon Parser Generator Tutorial

2014-05-31

原文链接:http://freecode.com/articles/lemon-parser-generator-tutorial

lemon是Dr. Richard Hipp写的一个小巧, 线程安全, 经过良好测试的parser generator. 用parser generator, 就会和使用flex这种扫描程序一样, 通过写少许代码就能达到目的. 你只需要给parser写语法代码.

Example1: 计算器上手

用下面的示例和完全手写代码相比. 比如, 跟C++实现的计算器相比. 下面这个文件是parser用的语法文件. example1.y是一个非常简单的计算器语法文件.

%token_type {int}

%left PLUS MINUS.
%left DIVIDE TIMES.

%include {
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include "example1.h"
}

%syntax_error {
  std::cout << "Syntax error!" << std::endl;
}

program ::= expr(A).   { std::cout << "Result=" << A << std::endl; }

expr(A) ::= expr(B) MINUS  expr(C).  { A = B - C; }
expr(A) ::= expr(B) PLUS   expr(C).  { A = B + C; }
expr(A) ::= expr(B) TIMES  expr(C).  { A = B * C; }
expr(A) ::= expr(B) DIVIDE expr(C).  {
  if(C != 0){
    A = B / C;
  }else{
    std::cout << "divide by zero" << std::endl;
  }
}  /* end of DIVIDE */
expr(A) ::= INTEGER(B). { A = B; }

正如你所看到的, 这个文件只有27行(不包含空行). 这样就会很容易修改语法文件, 而不是重新手写很多代码.

parser generator(lemon.c和lempar.c) 通过读取语法文件example1.y来创建parser文件example1.c, 和包含token定义的example1.h, 和example1.out文件, 里面包含了example1.y语法所包含的所有移位规约状态(shift reduce states). 让我们来跑完所有的步骤, 首先来编译lemon的代码(ubuntun上面可以直接apt-get). 第一步就是:

$ gcc -o lemon lemon.c

现在我们有了parser generatorlemon, 然后运行语法文件example1.y:

$ ./lemon example1.y

然后就会输出example1.h, example1.cexample1.out三个文件. lempar.c是干什么的? 比较example1.clempar.c, 你就会发现这俩文件里面包含很多相同的代码. lempar.c是一个模板文件. 只要你有需求, 你可以修改那个文件, 然后修改后的代码就会出现在example1.c(包括注释等).

但是example1.c还没有完成. 我们将要写的main_part, 里面包含main函数和tokens. main_part就是驱动程序.

int main()
{
  void* pParser = ParseAlloc (malloc);

  /* First input:
     15 / 5
   */
  Parse (pParser, INTEGER, 15);
  Parse (pParser, DIVIDE, 0);
  Parse (pParser, INTEGER, 5);
  Parse (pParser, 0, 0);

  /*  Second input:
      50 + 125
   */
  Parse (pParser, INTEGER, 50);
  Parse (pParser, PLUS, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, 0, 0);

  /*  Third input:
      50 * 125 + 125
   */
  Parse (pParser, INTEGER, 50);
  Parse (pParser, TIMES, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, PLUS, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, 0, 0);

  ParseFree(pParser, free );
}

那么, main_part是做什么的? 恩, 第三行是初始化parser. 你会注意到从第7行开始,pParser会被传给每一个Parser函数. 表达式15/5, 或者15 DIVIDE 5, 就像第7到10行那样执行, 传入第一个整形参数15, 然后DIVIDE操作符, 操作符不需要取一个值, 所以就选择了0. 最后第10行, 第二个0作为参数的函数调用Parse(pParser, 0, 0);来结束整个表达式. (请注意在example4.y里面, 语法可以处理NEWLINE, Parse(pParser, 0, ...);只会在语法文件的最后调用.)

main_part要被添加到example1.c文件的末尾. 你也许想弄成下载就能编译好的例子, 其实他是这么做的:

$ cat main_part >> example1.c

下来就比较容易了, 只需要编译这个文件.

$ g++ -o ex1 example1.c

现在执行ex1, 你可以看到15/5的结果, 就是3… 50+125的结果就是175, (50*125)+125的结果是6375. 最后一个例子里面, TIMES操作符的优先级高于PLUS.

$ ./ex1
Result=3
Result=175
Result=6375

现在再进一步看语法文件example1.y. 为什么TIMES的优先级比PLUS高? 第3到4行决定了四种操作符的优先级PLUS, MINUS, DIVIDETIMES.

%left PLUS MINUS.
%left DIVIDE TIMES.

越靠上的优先级越低, 这一点要记住了. PLUSMINUS的优先级要比DIVIDETIMES的优先级要低, 因为PLUS在第3行, DIVIDE在第4行. 假如我们新加一个求幂EXP操作符进来, 因为EXP操作符的优先级要要比TIMESDIVIDE高, 那么他就应该被添加到第4行之后.

如果你想用浮点数来当做输入, 比如15.5, 5.2这种来代替整数, 你应该怎么做? 这个简单啊. 这些tokens之所以是整数类型是因为在example1.y里面写着:

%token_type {int}

所以, 为了变成浮点数, 只需要把第1行改成:

%token_type {double}

再来接着往下看, 在第6行有一个include. example1.y里面的include语句会被原封不动的插入到example1.c文件头部, 而这些头文件都是后面所需要的.

...
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include "example1.h"
...

还没忘记example1.h这个头文件是$ ./lemon example1.y生成的吧. 这个头文件里面定义着所有的tokens, 换句话说, 就是给每一个token从1开始赋值. 为什么从1开始, 为啥不是0? 因为0是被Parse函数所保留. 还记得Parse(pParser, 0, 0);函数调用吗, 第二个参数是0, 用来结束输入的.

#define PLUS                            1
#define MINUS                           2
#define DIVIDE                          3
#define TIMES                           4
#define INTEGER                         5

Example2: 自定义类型

example2.yexample1.y的区别就是在定义token时增加了结构体类型. 具体地说, 这个token类型定义在ex2def.h里面. 自定义类型可以让我们灵活的处理语义, 或者说是一种正确处理语义的原则. 看这个例子:

expr(A) ::= expr(B) TIMES  expr(C).   { A.value = B.value * C.value;
                                        A.n = B.n+1  + C.n+1;
                                      }

token_type被定义在example2.y的第6行.

%token_type {Token}

这个结构体类型的token在后面的ex2def.h里面:

struct Token {
  const char *z;
  int value;
  unsigned n;
};

需要说明一下, const char *z在这些例子里面并没有用到, 但是我还是把它留在这个结构体内, 因为这是完善计算把一个表达式复制给一个变量所需要的. 比如, variable1=2+5, 在符号表里面就应该能看到variable1.

再来直接看看头文件里面的变化, 那个额外的ex2def.h头文件, 里面包含了自定义token的定义.

%include {
#include <iostream>
#include "ex2def.h"
#include "example2.h"
}
%token_type {Token}
%default_type {Token}

%type expr {Token}
%type NUM {Token}
%left PLUS MINUS.
%left DIVIDE TIMES.

%syntax_error {
  std::cout << "Syntax error!" << std::endl;  
}

program ::= expr(A). {
  std::cout << "Result.value=" << A.value << std::endl; 
  std::cout << "Result.n=" << A.n << std::endl; 
}

expr(A) ::= expr(B) MINUS  expr(C). {
  A.value = B.value - C.value; 
  A.n = B.n+1  + C.n+1;
}

expr(A) ::= expr(B) PLUS  expr(C). {
  A.value = B.value + C.value; 
  A.n = B.n+1  + C.n+1;
}

expr(A) ::= expr(B) TIMES  expr(C). {
  A.value = B.value * C.value;
  A.n = B.n+1  + C.n+1;
}

expr(A) ::= expr(B) DIVIDE expr(C). {
  if(C.value != 0) {
    A.value = B.value / C.value;
    A.n = B.n+1 + C.n+1;
  } else {
    std::cout << "divide by zero" << std::endl;
  }
}  /* end of DIVIDE */

expr(A) ::= NUM(B). { A.value = B.value; A.n = B.n+1; }

正如我们下面就要看到的, 仔细看一下23到25行, 结构体A这个token使用了A.valueA.n这两个成员, .value获得了表达式的值, .n获取到各个变量被使用的次数: expr(A) ::= expr(B) MINUS expr(C). { A.value = B.value - C.value; A.n = B.n+1 + C.n+1; }

这是一个快速理解动态的转换规约的办法. 转换次数是指一个token被压入栈的次数. 规约次数是指表达式规则被匹配的次数. 一旦一个表达式可以被匹配, 他就可以被规约. 你应该可以回忆起来, lemon运行的时候, 有*.c, *.h*.out三种文件会被创建. *.out文件就包含表达式匹配的每一步, 包含转换规约状态. 如果你想要一个减缓的版本, 只需要在lemon运行的时候加上-s参数:

$ ./lemon -s example2.y
Parser statistics: 6 terminals, 3 nonterminals, 6 rules
11 states, 0 parser table entries, 0 conflicts

然后你再用之前的例子main_part2, 添加到example2.c后面:

$ cat main_part2 >> example2.c

现在example2.c就可以被编译运行:

$ g++ -o ex2  example2.c
$ ./ex2
Result.value=17
Result.n=4
Result.value=-9
Result.n=4
Result.value=78
Result.n=10

Example3: token析构器

lemon比bison优秀的一点就是你可以非终结符来释放内存. 你可以选择调用函数来做到这一点. expr就是使用非终结符的例子. 当一个程序调用了非终结符, token_destructor这个函数就会被调用.

%include {
#include <iostream>
#include "ex3def.h"
#include "example3.h"

void token_destructor(Token t)
{
  std::cout << "In token_destructor t.value= " << t.value << std::endl;
  std::cout << "In token_destructor t.n= " << t.n << std::endl;
}
}

%token_type {Token}
%default_type {Token}
%token_destructor { token_destructor($$); }
...

第13行, 就是token_destructor函数调用的地方. token_destructor定义在第5行到第9行. 在这个简单的例子中, 没有申请内存, 所以也不需要调用free来释放内存. 反而, 通过std::cout的输出可以看到发生了什么. 程序被编译好了以后, 就可以像下面的方式来运行.

$ ./ex3
t0.value=4  PLUS t1.value=13
In token_destructor t.value= 4
In token_destructor t.n= 0
Result.value=17
Result.n=4
parsing complete!
...

当表达式已经规约了, 析构器也就会被调用, 但是只是在token.value=4之后被调用. 为什么是这样子? 为了寻找答案, 我们来看看main_part3的代码:

int main()
{
  void* pParser = ParseAlloc (malloc);

  struct Token t0,t1;
  struct Token mToken;

  t0.value=4;
  t0.n=0;

  t1.value=13;
  t1.n=0;

  std::cout << " t0.value=4  PLUS t1.value=13 " << std::endl;

  Parse (pParser, NUM, t0);
  Parse (pParser, PLUS, t0);
  Parse (pParser, NUM, t1);
  Parse (pParser, 0, t0);

  std::cout << " t0.value=4  DIVIDE t1.value=13 " << std::endl;

  Parse (pParser, NUM, t0);
  Parse (pParser, DIVIDE, t0);
  Parse (pParser, NUM, t1);
  Parse (pParser, 0, t1);
  ...

第14行, 以t0作为第三个参数结束整个语法. 第三个参数将作为token_destructor函数的输入$$. 如果紧接着调用Parse函数, 这就是为定义行为, 所以你只能在整个表达式都完成之后再调用析构函数. 换句话说, 你不能在Parse(pParser, 0, t0);之后马上再次调用Parse (pParser, 0, t0);. 在第19行, t1.value= 13表达式结束后调用了token_destructor. 如果你看过main_part3的代码, 你就会发现Parse的第三个参数是t1第二个参数是0.

再来继续看程序的输出:

t1.value=13  PLUS  t0.value=4
In token_destructor t.value= 13
In token_destructor t.n= 0
Result.value=17
Result.n=4
parsing complete!

t0在第14行被当作第三个参数, t1在19行. 这个理解起来应该没问题. 一个变量可以保存token的值. 比如, main_part3里面可以让token t0在第4和第14行都是用:

...
struct Token t0;

t0.value=4;
t0.n=0;

Parse (pParser, NUM, t0);
Parse (pParser, PLUS, t0);

t0.value=13;
t0.n=0;

Parse (pParser, NUM, t0);
Parse (pParser, 0, t0);
...

Example4: 以NEWLINE结束语法

你应该注意到上面三个例子, 都是以Parse(pParse, 0, ..)来结束表达式输入的. 这个方法比较笨拙. 不过语法应该强制让一个表达式结束规约.

example4.y包含着以下的内容:

%include {
#include <iostream>
#include "ex4def.h"
#include "example4.h"

void token_destructor(Token t)
{
  std::cout << "In token_destructor t.value= " << t.value << std::endl;
  std::cout << "In token_destructor t.n= " << t.n << std::endl;
}
}

%token_type {Token}
%default_type {Token}
%token_destructor { token_destructor($$); }

%type expr {Token}
%type NUM {Token}

%left PLUS MINUS.
%left DIVIDE TIMES.

%parse_accept {
  printf("parsing complete!\n\n\n");
}

%syntax_error {
  std::cout << "Syntax error!" << std::endl;
}

/*  This is to terminate with a new line */
main ::= in.
in ::= .
in ::= in state NEWLINE.

state ::= expr(A).   {
  std::cout << "Result.value=" << A.value << std::endl; 
  std::cout << "Result.n=" << A.n << std::endl; 
}

expr(A) ::= expr(B) MINUS  expr(C). { A.value = B.value - C.value;
                                      A.n = B.n+1  + C.n+1;
                                    }
...

注意29到35行, mainin在这里被定义了. 如果你是一个bsion用户, 你可以不定义一个非终结符main, 但是lemon需要这么做. 有了这种改变, main_part4就可以让任何表达式以NEWLINE来结束.

int main()
{
  void* pParser = ParseAlloc (malloc);

  struct Token t0,t1;
  struct Token mToken;

  t0.value=4;
  t0.n=0;

  t1.value=13;
  t1.n=0;

  std::cout << std::endl <<" t0.value=4  PLUS t1.value=13 " << std::endl << std::endl;

  Parse (pParser, NUM, t0);
  Parse (pParser, PLUS, t0);
  Parse (pParser, NUM, t1);
  Parse (pParser, NEWLINE, t1);

  std::cout << std::endl <<" t0.value=4  TIMES t1.value=13 " << std::endl << std::endl;

注意到14行把NEWLINE传递给程序, 并且检查一下example4.h. 在这个例子里面NEWLINE被定义成整数6. 再来执行以下ex4这个程序, 我们可以得到加了行号的输出:

$ ./ex4

1  t0.value=4  PLUS t1.value=13
2
3  In token_destructor t.value= 4
4  In token_destructor t.n= 0
5  Result.value=17
6  Result.n=4
7
8   t0.value=4  TIMES t1.value=13
9
10  In token_destructor t.value= 4
11  In token_destructor t.n= 0
12  Result.value=52
13  Result.n=4
14  parsing complete!

第5行就能得到结果, 现在不需要调用Parse(pParser, 0, t0);, 取而代之的是Parse(pParser, NEWLINE, t0);.

Example 5: 使用flex做tokenizer

下一个例子就直接从终端输入, flex会创建一个扫描程序找到合适的tokens. 首先来快速的看一下flex程序lexer.l, 为了清除期间加上了行号:

%{
#include "lexglobal.h"
#include "example5.h"
#include <string.h>
#include <math.h>

int line = 1, col = 1;
%}

%%
[0-9]+|[0-9]*\.[0-9]+  { col += (int) strlen(yytext);
                          yylval.dval = atof(yytext);
                          return NUM; }
[ \t]                 { col += (int) strlen(yytext); }  /* ignore but count white space */
[A-Za-z][A-Za-z0-9]*  { /* ignore but needed for variables */
                        return 0;
                      }

"+"           {  return PLUS; }
"-"           {  return MINUS; }
"*"           {  return TIMES; }
"/"           {  return DIVIDE; }
\n      { col = 0; ++line; return NEWLINE; }
.       { col += (int) strlen(yytext); return yytext[0]; }
%%

/**
* reset the line and column count
*/
void reset_lexer(void)
{
  line = 1;
  col  = 1;
}

/**
 * yyerror() is invoked when the lexer or the parser encounter
 * an error. The error message is passed via *s
 */
void yyerror(char *s)
{
  printf("error: %s at line: %d col: %d\n",s,line,col);
}

int yywrap(void)
{
  return 1;
}

flex程序的格式基本上就是左侧是规则右侧是C代码. 来看第9行, [0-9]+|[0-9]*\.[0-9]+, 这个表达式就可以匹配3, .3, 0.323.4, 并且会返回一个NUM. 不过NUM的值是什么呢? 他其实就在第三行, 被包含在example5.h里面, 是lemon parser生成的. 在第10行, yytext的值转化成浮点数之后被赋给yylval.dval. yylval则被定义在lexglobal.h里面. lexglobal.h是这样的:

#ifndef YYSTYPE
typedef union {
  double    dval;
  struct symtab *symp;
} yystype;
# define YYSTYPE yystype
# define YYSTYPE_IS_TRIVIAL 1
#endif

/* extern YYSTYPE yylval; */
YYSTYPE yylval;

yystype是一个包含dvalsymtabunion, symtab在这个例子里面没有用到, 但是你如果想要计算器的变量可以被赋值, 你就得这么搞. 索引3是一个使用flexbison做出来的完整计算器.

再来看看lexer.l的第9带11行:

...
[0-9]+|[0-9]*\.[0-9]+  { col += (int) strlen(yytext);
                          yylval.dval = atof(yytext);
                          return NUM; }
...

token的类型NUM和值都要被传出. 我们不仅要知道他是一个数字, 还要知道他的值是多少.

不像PLUS, MINUS, TIMEDIVIDE, 我们只需要知道token的类型. 所以, 在lexer.l的第6到19行是返回了token的值.

"+"           {  return PLUS; }
"-"           {  return MINUS; }
"*"           {  return TIMES; }
"/"           {  return DIVIDE; }
\n      { col = 0; ++line; return NEWLINE; }
.       { col += (int) strlen(yytext); return yytext[0]; }

第20行匹配到了一个NEWLINE, 虽然没有被用到, 行号和列是用来跟踪变量. 这是一个不错的注意, 可以很方便的来调试.

main_part5里的代码比较多. 使用stdin当作输入. 这个可以很容易的换成使用socket来当作输入, 所以如果你使用web程序, socket的文件描述符就可以替换13行的fileno(stdin).

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>

#define BUFS 1024


/**
 * We have to declare these here - they're not  in any header files
 * we can inclde.  yyparse() is declared with an empty argument list
 * so that it is compatible with the generated C code from bison.
 */

extern FILE *yyin;
typedef struct yy_buffer_state *YY_BUFFER_STATE;

extern "C" {
  int             yylex( void );
  YY_BUFFER_STATE yy_scan_string( const char * );
  void            yy_delete_buffer( YY_BUFFER_STATE );
}


int main(int argc,char** argv)
{
  int n;
  int yv;
  char buf[BUFS+1];
  void* pParser = ParseAlloc (malloc);

  struct Token t0,t1;
  struct Token mToken;

  t0.n=0;
  t0.value=0;

  std::cout << "Enter an expression like 3+5 <return>" << std::endl;
  std::cout << "  Terminate with ^D" << std::endl;

  while ( ( n=read(fileno(stdin), buf, BUFS )) >  0)
  {
    buf[n]='\0';
    yy_scan_string(buf);
    // on EOF yylex will return 0
    while( (yv=yylex()) != 0)
    { 
      std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
      t0.value=yylval.dval;
      Parse (pParser, yv, t0);
    }
  }

  Parse (pParser, yv, t0);
  ParseFree(pParser, free );
}

第16行, extern "C"是必须的, 因为lexer.l创建出来的代码是C代码, 如果要在C++里面使用就需要加这个代码:

$ flex lexer.l

可以看flex的手册, 索引7. flex++会输出C++代码. 不过如果你的扫描程序很复杂, 那么C程序跑的可能会快一些. main_part5将被以C++程序来编译, 做了一个折中的选择.

parser程序应该总是以输入Parse(pParser,0,..来结束. 如果flex程序里面没有任何输出了, 他会返回一个0, 所以38行的主循环以输入0结束了整个程序. 第33行的read程序, 不断接受输入. 这就是你想从一个socket那里读到输入, 所需要做的事情, 不过那边可能会被阻塞住.

但是如果read读取失败了, flex程序就会返回一个0. 所以45行用0当作了第二个参数.

...
while ( ( n=read(fileno(stdin), buf, BUFS )) >  0)
...
  while( (yv=yylex()) != 0)
  {
    std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
    t0.value=yylval.dval;
    Parse (pParser, yv, t0);
  }
...
Parse (pParser, 0, t0);
ParseFree(pParser, free );

Comments