技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> PHP --> PHP语法分析器:RE2C && BISON 总结

PHP语法分析器:RE2C && BISON 总结

浏览:2006次  出处信息

   在这之前,我曾经尝试过一个项目,就是将我们的PHP代码自动生成so扩展,

   编译到PHP中,我叫它 phptoc。

   但是由于各种原因,暂停了此项目。

   写这篇文章一是因为这方面资料太少,二是把自己的收获总结下来,以便以后参考,如果能明白PHP语法分析

   那对PHP源码的研究会更上一层楼地 ^.^…

   我尽可能写的通俗易懂些。

   这个项目思路源于facebook的开源项目 HipHop .

   其实我对这个项目的性能提高50%-60%持怀疑态度,从根本来讲,如果PHP用到APC缓存,它的性能是否低

   于HipHop,我还没有做测试,不敢断言。

   PHPtoc,我只是想把C程序员解放出来,希望能达到,让PHPer用PHP代码就可以写出接近于PHP扩展性能的一个扩展,

   它的流程如下,读取PHP文件,解析PHP代码,对其进行语法分析器,生成对应的ZendAPI,编译成扩展。

   

   进入正题

   

   这里最难的就是语法分析器了,大家应该都知道,PHP也有自己的语法分析器,现在版本用到的是re2c 和 Bison。

   所以,我自然也用到了这个组合。

   如果要用PHP的语法分析器就不太现实了,因为需要修改zend_language_parser.y和 zend_language_scanner.l 并重新编译,这难度大不说,还可能影响PHP自身。

   所以决定重新写一套自己的语法分析规则,这个功能就等于是重写了PHP的语法分析器,当然会舍弃一些不常用的。

   re2c && yacc/bison,通过引用自己的对应文件,然后将他们统一编译成一个*.c文件,最后再gcc编译就会生

   成我们自己的程序。所以说,他们从根本来讲不是语法分析程序,他们只是将我们的规则生成一个独立的c文

   件,这个c文件才是真正的我们需要的语法分析程序,我更愿意叫它 语法生成器。如下图:

   

   注:图中a.c是 扫描器生成的最终代码。。

   re2c扫描器,假如我们写的扫描规则文件叫scanner.l,它会将我们写的PHP文件内容,进行扫描,然后根据

   我们写的规则,生成不同的token传递给parse。

   我们写的(f)lex语法规则,比如我们叫他Parse.y

   会通过 yacc/bison编译成一个parse.tab.h,parse.tab.c的文件,parse根据不同的token进行不同的操作

   比如我们PHP代码是 “echo 1″;

   扫描其中有一个规则:

"echo" {
 
return T_ECHO;
 }

   扫描器函数scan会拿到”echo 1″字符串,它对这一段代码进行循环,如果发现有echo字符串,那么它就作为关键字返回token:T_ECHO,

   parse.y和scanner.l会分别生成两个c文件,scanner.c和parse.tab.c,用gcc编译到一起,就成了。

   下面会具体的说一说

   re2c,关于它的英文文档在 http://re2c.org/manual.html,感兴趣的可以去看看,我也翻译了一个中文版本,

   还么有结束,稍后我会放上来。

   re2c提供了一些宏接口,方面我们使用,我简单做了翻译,英语水平不好,可能有误,需要原文的可以去上面那个地址查看。

接口代码:
不像其他的扫描器程序,re2c 不会生成完整的扫描器:用户必须提供一些接口代码。用户必须定义下面的宏或者是其他相应的配置。
YYCONDTYPE
    用-c 模式你可以使用-to参数用来生成一个文件:使用包含枚举类型的作为条件。每个值都会在规则集合里面作为条件来使用。
YYCTYPE
    用来维持一个输入符号。通常是 char 或者unsigned char。
YYCTXMARKER
    *YYCTYPE类型的表达式,生成的代码回溯信息的上下文会保存在 YYCTXMARKER。如果扫描器规则需要使用上下文中的一个或多个正则表达式则用户需要定义这个宏。
YYCURSOR
    *YYCTYPE类型的表达式指针指向当前输入的符号,生成的代码作为符号相匹配,在开始的地方,YYCURSOR假定指向当前token的第一个字符。结束时,YYCURSOR将会指向下一个token的第一个字符。
YYDEBUG(state,current)
    这个只有指定-d标示符的时候才会需要。调用用户定义的函数时可以非常容易的调试生成的代码。
    这个函数应该有以下签名:void YYDEBUG(int state,char current)。第一个参数接受 state ,默认值为-1第二个参数接受输入的当前位置。
YYFILL(n)
    当缓冲器需要填充的时候,生成的代码将会调用YYFILL(n):至少提供n个字符。YYFILL(n)将会根据需要调整YYCURSOR,YYLIMIT,YYMARKER 和 YYCTXMARKER。注意在典型的程序语言当中,n等于最长的关键词的长度加一。用户可以在/*!max:re2c*/一次定义YYMAXFILL来指定最长长度。如果使用了-1,YYMAXFILL将会在/*!re2c*/之后调用一次阻塞。
YYGETCONDITION()
    如果使用了-c模式,这个定义将会在扫描器代码之前获取条件集。这个值,必须初始化为枚举YYCONDTYPE的类型。
YYGETSTATE()
    如果-f模式指定了,用户就需要定义这个宏。如果这样,扫描器在开始时为了获取保存的状态,生成的代码将会调用YYGETSTATE(),YYGETSTATE()必须返回一个带符号的整数,这个值如果是-1,告诉扫描器这是第一次执行,否则这个值等于以前YYSETSTATE(s) 保存的状态。否则,扫描器将会恢复操作之后立即调用YYFILL(n)。
YYLIMIT
    表达式的类型 *YYCTYPE 标记缓冲器的结尾(YYLIMIT(-1)是缓冲区的最后一个字符)。生成的代码将会不断的比较YYCORSUR 和 YYLIMIT 以决定 什么时候填充缓冲区。
YYSETCONDITION(c)
    这个宏用来在转换规则中设置条件,它只会在指定-c模式 和 使用转换规则时有用。
YYSETSTATE(s)
    用户只需要在指定-f模式时定义这个宏,如果是这样,生成的代码将会在YYFILL(n)之前调用YYSETSTATE(s),YYSETSTATE的参数是一个有符号整型,被称为唯一的标示特定的YYFILL(n)实例。
YYMARKER
    类型为*YYCTYPE的表达式,生成的代码保存回溯信息到YYMARKER。一些简单的扫描器可能用不到。

   扫描器,顾名思义,就是对文件扫描,找出关键代码来。

   扫描器文件结构:

/* #include 文件*/
/*宏定义*/
//扫描函数
int scan(char *p){
/*扫描器规则区*/
}
//执行scan扫描函数,返回token到yacc/bison中。
int yylex(){
        int token;
        char *p=YYCURSOR;//YYCURSOR是一个指针,指向我们的PHP文本内容
        while(token=scan(p)){//这里会移动指针p,一个一个判断是不是我们上面定义好的scanner...
                return token;
        }
}
int main(int argc,char**argv){
        BEGIN(INITIAL);//
        YYCURSOR=argv[1];//YYCURSOR是一个指针,指向我们的PHP文本内容,
        yyparse();
}

   BEGIN 是定义的宏

#define YYCTYPE char   //输入符号的类型
#define STATE(name)     yyc##name
#define BEGIN(n)        YYSETCONDITION(STATE(n))
#define LANG_SCNG(v)    (sc_globals.v)
#define SCNG    LANG_SCNG
#define YYGETCONDITION()        SCNG(yy_state)
#define YYSETCONDITION(s)       SCNG(yy_state)=s

   yyparse函数是在yacc 中定义的,

   里面有一个关键宏: YYLEX

   #define YYLEX yylex()

   它会执行scaner扫描器的yylex

   可能会有点绕,重新缕一缕:

   在scanner.l中,通过调用parse.y解析器函数yyparse,该函数调用scanner.l的yylex生成关键代码token,yylex

   将扫描器返回的

   token返回给parse.y,parse根据不同的token执行不同的代码.

   举例:

scanner.l
#include "scanner.h"
#include "parse.tab.h"
int scan(char *p){
/*!re2c
     <INITIAL>"<?php"([ \t]|{NEWLINE})? {
                BEGIN(ST_IN_SCRIPTING);
                return T_OPEN_TAG;
        }    
    "echo" {
 
                return T_ECHO;
        }
    [0-9]+ {
                return T_LNUMBER;
        }
*/
}
int yylex(){
          int c;
 
//       return T_STRING;
        int token;
        char *p=YYCURSOR;
        while(token=scan(p)){
                return token;
        }
}
 
int main (int argc,char ** argv){
        BEGIN(INITIAL);//初始化
        YYCURSOR=argv[1];//将用户输入的字符串放到YYCURSOR
        yyparse();//yyparse() -》yylex()-》yyparse()
        return 0;
}

   这样一个简单的扫描器就做成了,

   那解析器呢?

   解析器我用的是flex和bison。。。

   关于flex的文件结构:

%{
/*
  C代码段将逐字拷贝到lex编译后产生的C源文件中
  可以定义一些全局变量,数组,函数例程等...
*/
#include
#include "scanner.h"
extern int yylex();//它在scanner.l中定义的。。
void yyerror(char *);
# define YYPARSE_PARAM tsrm_ls
# define YYLEX_PARAM tsrm_ls
%}
{定义段,也就是token定义的地方}
//这就是关键  token程序是根据这是做switch的。
%token T_OPEN_TAG
%token T_ECHO
%token T_LNUMBER
%%
{规则段}
start:
         T_OPEN_TAG{printf("start\n"); }
        |start statement
;
statement:
T_ECHO expr {printf("echo :%s\n",$3)}
;
expr:
        T_LNUMBER {$$=$1;}
%%
{用户代码段}
void yyerror(char *msg){
        printf("error:%s\n",msg);
}

   在规则段中,start是开始的地方,如果 scan识别到PHP开始标签就会返回T_OPEN_TAG,然后执行括号的代码,输出start.

   在scanner.l中,调用scan的是个while循环,所以它会检查到php代码的末尾,

   yyparse会根据scan返回的标记做switch,然后goto到相应的代码,比如 yyparse.y发现当前的token是T_OPEN_TAG,

   它会通过宏 #line 映射到 parse.y所对应 21行,T_OPEN_TAG的位置,然后执行

   画个图来说明一下,

   

   那,TOKEN返回给yyparse之后做了什么呢?

   为了能直观一些,我用gdb跟踪:

   

   这个时候yychar是258,258是什么?

   

   258是bison自动生成的枚举类型数据。

   继续

   YYTRANSLATE宏接受yychar,然后返回所对应的值

#define YYTRANSLATE(YYX)                                                \
  ((unsigned int) (YYX) <= YYMAXUTOK ? yytranslate[YYX] : YYUNDEFTOK)
 
/* YYTRANSLATE[YYLEX] -- Bison symbol number corresponding to YYLEX.  */
static const yytype_uint8 yytranslate[] =
{
       0,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,    27,     2,   
      22,    23,     2,     2,    28,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,    21,  
       2,    26,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,    24,     2,    25,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     2,     2,     2,     2,   
       2,     2,     2,     2,     2,     2,     1,     2,     3,     4,   
       5,     6,     7,     8,     9,    10,    11,    12,    13,    14,  
      15,    16,    17,    18,    19,    20   
};

   yyparse拿到这个值,不断地translate,

   

   bison会生成很多用来映射的数组,将最终的translate保存到yyn,

   这样bison就能找到token所对应的代码

  switch (yyn)
    {    
        case 2:
 
/* Line 1455 of yacc.c  */
#line 30 "parse.y"
    {printf("start\n"); ;}
    break;

   循环,生成token逐条执行,然后解析成所对应的zend 函数等,生成对应的op保存在哈希表中,这些不是本文的重点,

   就不细说了。

   到这里,整体的流程就结束了。。剩下的就是细化的工作,如果有时间,我再继续phptoc :)

   我写的可能很乱,如果哪儿有不懂的话,就留言吧。。。 :)

   下面是一些相关资料:

   Yacc: http://dinosaur.compilertools.net/yacc/

   Yacc译文:http://blog.chinaunix.net/space.php?uid=20106293&do=blog&id=142118

   Bison:http://dinosaur.compilertools.net/bison/bison_6.html#SEC56

   Re2c:http://re2c.org/manual.html

   还有我翻译了一部分的re2c

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1