标签归档：词法分析

使用Bison和re2c构建词法分析和语法分析器

发表回复

使用说明： 本文需要读者对C语言有一定的基础，对于re2c和bison有一些了解，最好也熟悉linux命令

我们在前面介绍了PHP的语法分析器-Bison入门 和PHP的词法解析器：re2c，那么如何将re2c与bison集成在一起的呢？ 我们以一个从PHP源码中剥离出来的示例来说明整个过程。这个示例的功能与词法分析器的示例类似，作用都是识别输入参数中的字符串类型。 本示例是在其基础上添加了语法解析过程。 首先我们看这个示例的语法文件：demo.y

%{
#include <stdio.h>
#include "demo_scanner.h"
extern int yylex(znode *zendlval);
void yyerror(char const *);

#define YYSTYPE znode   //关键点一，znode定义在demo_scanner.h   
%}

%pure_parser    //  关键点二

%token T_BEGIN
%token T_NUMBER
%token T_LOWER_CHAR
%token T_UPPER_CHAR
%token T_EXIT
%token T_UNKNOWN
%token T_INPUT_ERROR
%token T_END
%token T_WHITESPACE

%%

begin: T_BEGIN {printf("begin:\ntoken=%d\n", $1.op_type);}
     | begin variable {
        printf("token=%d ", $2.op_type);
        if ($2.constant.value.str.len > 0) {
            printf("text=%s", $2.constant.value.str.val);
        }
        printf("\n");
}

variable: T_NUMBER {$$ = $1;}
|T_LOWER_CHAR {$$ = $1;}
|T_UPPER_CHAR {$$ = $1;}
|T_EXIT {$$ = $1;}
|T_UNKNOWN {$$ = $1;}
|T_INPUT_ERROR {$$ = $1;}
|T_END {$$ = $1;}
|T_WHITESPACE {$$ = $1;}

%%

void yyerror(char const *s) {
    printf("%s\n", s);
}

这个语法文件有两个关键点：

1、znode是复制PHP源码中的znode，只是这里我们只保留了两个字段，其结构如下：

typedef union _zvalue_value {
    long lval;                  /* long value */
    double dval;                /* double value */
    struct {
        char *val;
        int len;
    } str;
} zvalue_value;

typedef struct _zval_struct {
    /* Variable information */
    zvalue_value value;     /* value */
    int type;    /* active type */
}zval;

typedef struct _znode {
    int op_type;
    zval constant;
}znode;

这里我们同样也复制了PHP的zval结构，但是我们也只取了关于整型，浮点型和字符串型的结构。 op_type用于记录操作的类型，constant记录分析过程获取的数据。 一般来说，在一个简单的程序中，对所有的语言结构的语义值使用同一个数据类型就足够用了。比如在前一小节的逆波兰记号计算器示例就只有double类型。 而且Bison默认是对于所有语义值使用int类型。如果要指明其它的类型，可以像我们示例一样将YYSTYPE定义成一个宏:

#define YYSTYPE znode

2、%pure_parser 在Bison中声明%pure_parse表明你要产生一个可重入(reentrant)的分析器。默认情况下Bison调用的词法分析函数名为yylex，并且其参数为void，如果定义了YYLEX_PARAM，则使用YYLEX_PARAM为参数， 这种情况我们可以在Bison生成的.c文件中发现其是使用#ifdef实现。

如果声明了%pure_parser，通信变量yylval和yylloc则变为yyparse函数中的局部变量，变量yynerrs也变为在yyparse中的局部变量，而yyparse自己的调用方式并没有改变。比如在我们的示例中我们声明了可重入，并且使用zval类型的变更作为yylex函数的第一个参数，则在生成的.c文件中，我们可以看到yylval的类型变成

一个可重入(reentrant)程序是在执行过程中不变更的程序；换句话说,它全部由纯(pure)(只读)代码构成。 当可异步执行的时候，可重入特性非常重要。例如，从一个句柄调用不可重入程序可能是不安全的。 在带有多线程控制的系统中，一个非可重入程序必须只能被互锁(interlocks)调用。

通过声明可重入函数和使用znode参数，我们可以记录分析过程中获取的值和词法分析过程产生的token。 在yyparse调用过程中会调用yylex函数，在本示例中的yylex函数是借助re2c生成的。 在demo_scanner.l文件中定义了词法的规则。大部分规则是借用了上一小节的示例， 在此基础上我们增加了新的yylex函数，并且将zendlval作为通信变量，把词法分析过程中的字符串和token传递回来。 而与此相关的增加的操作为：

SCNG(yy_text) = YYCURSOR;   //  记录当前字符串所在位置
/*!re2c
  <!*> {yyleng = YYCURSOR - SCNG(yy_text);} //  记录字符串长度

main函数发生了一些改变：

int main(int argc, char* argv[])
{
    BEGIN(INITIAL); //  全局初始化，需要放在scan调用之前
    scanner_globals.yy_cursor = argv[1];    //将输入的第一个参数作为要解析的字符串

    yyparse();
    return 0;
}

在新的main函数中，我们新增加了yyparse函数的调用，此函数在执行过程中会自动调用yylex函数。

如果需要运行这个程序，则需要执行下面的命令：

re2c -o demo_scanner.c -c -t demo_scanner_def.h demo_scanner.l
bison -d demo.y
gcc -o t demo.tab.c demo_scanner.c
chmod +x t
./t "<?php tipi2011"

相关代码下载请移步TIPI项目

PHP的词法解析器：re2c

5条回复

re2c是一个扫描器制作工具，可以创建非常快速灵活的扫描器。它可以产生高效代码，基于C语言，可以支持C/C++代码。 与其它类似的扫描器不同，它偏重于为正则表达式产生高效代码（和他的名字一样）。因此，这比传统的词法分析器有更广泛的应用范围。 你可以在sourceforge.net获取源码。

PHP在最开始的词法解析器是使用的是flex，后来PHP的改为使用re2c。 在源码目录下的Zend/zend_language_scanner.l 文件是re2c的规则文件， 如果需要修改该规则文件需要安装re2c才能重新编译。

re2c调用方式：

re2c [-bdefFghisuvVw1] [-o output] [-c [-t header]] file

我们通过一个简单的例子来看下re2c。如下是一个简单的扫描器，它的作用是判断所给的字符串是数字/小写字母/大小字母。 当然，这里没有做一些输入错误判断等异常操作处理。示例如下：

#include <stdio.h>

char *scan(char *p){
#define YYCTYPE char
#define YYCURSOR p
#define YYLIMIT p
#define YYMARKER q
#define YYFILL(n)
    /*!re2c
      [0-9]+ {return "number";}
      [a-z]+ {return "lower";}
      [A-Z]+ {return "upper";}
      [^] {return "unkown";}
     */
}

int main(int argc, char* argv[])
{
    printf("%s\n", scan(argv[1]));

    return 0;
}

如果你是在ubuntu环境下，可以执行下面的命令生成可执行文件。

re2c -o a.c a.l
gcc a.c -o a
chmod +x a
./a 1000

此时程序会输出number。

我们解释一下我们用到的几个re2c约定的宏。

  • YYCTYPE 用于保存输入符号的类型，通常为char型和unsigned char型
  • YYCURSOR 指向当前输入标记， -当开始时，它指向当前标记的第一个字符，当结束时，它指向下一个标记的第一个字符
  • YYFILL(n) 当生成的代码需要重新加载缓存的标记时，则会调用YYFILL(n)。
  • YYLIMIT 缓存的最后一个字符，生成的代码会反复比较YYCURSOR和YYLIMIT，以确定是否需要重新填充缓冲区。

参照如上几个标识的说明，可以较清楚的理解生成的a.c文件，当然，re2c不会仅仅只有上面代码所显示的标记， 这只是一个简单示例，更多的标识说明和帮助信息请移步 re2c帮助文档：http://re2c.org/manual.html。

更多编译器相关算法: Compiler Algorithms