PHP语法分析器:RE2C BISON 总结

澳门新葡亰网址 2

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

写在前面的几句废话

编译到PHP中,我叫它 phptoc。

最近在项目的过程中接触了lex 和
yacc,他们可以帮助我们来实现自己的领域语言。最典型的应用就是可以帮助我们来实现自定义测试脚本的执行器。但是,这里也有一个限制,就是测试脚本要做的基本事情必须有现成的C语言库来实现,否则就做不到了;如果基本的操作是用java来做的,那么还可以用Antlr,这里不对Antlr做详细介绍。

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

lex是什么?

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

教科书上把lex的作用的作用叫做“词法分析 lexical analysis
”,这个中文叫法非常让人看不明白(叫做“符号提取”更合适),其实从它的英文单词lexical上来看他的意思其实是非常清楚的。

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

澳门新葡亰网址,lexical,在webster上的解释是:of or relating to words or the vocabulary
of a language as distinguished from its grammar and construction。

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

指的是: 一种语言中关于词汇、单词的,与之相对的是这种语言的语法和组织

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

这么来看的话 lexical analysis
的作用就应该是语言中的词汇和单词分析。事实上他的作用就是从语言中提取单词。放到编程语言中来说,他要做的事情其实就是提取编程语言占用的各种保留字、操作符等等语言的元素

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

所以他的另外一个名字scanner其实更形象一些,就是扫描一个文本中的单词。

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

lex把每个扫面出来的单词叫统统叫做token,token可以有很多类。对比自然语言的话,英语中的每个单词都是token,token有很多类,比如non(名词)就是一个类token,apple就是属于这个类型的一个具体token。对于某个编程语言来说,token的个数是很有限的,不像英语这种自然语言中有几十万个单词。

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

lex工具会帮我们生成一个yylex函数,yacc通过调用这个函数来得知拿到的token是什么类型的,但是token的类型是在yacc中定义的。

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

lex的输入文件一般会被命名成 .l文件,通过lex XX.l
我们得到输出的文件是lex.yy.c

澳门新葡亰网址 1

yacc是什么呢?

进入正题

刚才说完lex了,那么yacc呢,教科书上把yacc做的工作叫做syntactic
analysis。这次我们翻译没有直译做句法分析,而是叫语法分析,这个翻译能好一点,意思也基本上比较清楚。
其实我们最开始学习英语的时候老师都会告诉我们英语其实就是“单词+语法”,这个观点放到编程语言中很合适,lex提取了单词,那么是剩下的部分就是如何表达语法。那么yacc做的事情就是这一部分(实际应该说是BNF来做的)。

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

yacc会帮我们生成一个yyparse函数,这个函数会不断调用上面的yylex函数来得到token的类型。

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

yacc的输入文件一般会被命名成 .y文件,通过yacc -d
XX.y我们得到的输出文件是y.tab.h
y.tab.c,前者包含了lex需要的token类型定义,需要被include进 .l文件中

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

lex和yacc的输入文件格式

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

Definition section
%%
Rules section

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

%%
C code section

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

.l和.y的文件格式都是分成三段,用%%来分割,三个section的含义是:

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

  • Definition Section

澳门新葡亰网址 2

这块可以放C语言的各种各种include,define等声明语句,但是要用%{
%}括起来。

如果是.l文件,可以放预定义的正则表达式:minus “-”
还要放token的定义,方法是:代号 正则表达式。然后到了,Rules
Section就可以通过{符号} 来引用正则表达式

如果是.y文件,可以放token的定义,如:%token INTEGER PLUS
,这里的定一个的每个token都可以在y.tab.h中看到

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

  • Rules section

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

.l文件在这里放置的rules就是每个正则表达式要对应的动作,一般是返回一个token

.y文件在这里放置的rules就是满足一个语法描述时要执行的动作

不论是.l文件还是.y文件这里的动作都是用{}扩起来的,用C语言来描述,这些代码可以做你任何想要做的事情

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

  • C code Section

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

main函数,yyerror函数等的定义

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

lex和yacc能帮我们做什么?

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

一句话:解释执行自定义语言。有几点要注意:

扫描其中有一个规则:

  1. 自定义语言的要做的事情必须可以能通过C语言来实现。其实任何计算机能做的事情都可以用C语言来实现,lex和yacc存在的意义在于简化语言,让使用者能够以一种用比较简单的语言来实现复杂的操作。比如:对于数据库的查询肯定有现成的库可以来完成,但是使用起来比较麻烦,要自己写成语调用API,编译才行。如果我们想实自定义一个简单的语言(比如SQL)来实现操作,这个时候就可以用lex和yacc。
  2. lex和yacc
    做的事情只是:用C语言来实现另外一种语言。所以,他没办法实现C语言自己,但是可以实现java、python等。当然你可以通过Antlr来实现C语言的解析和执行,如果你这么做的话,C语言程序首先是通过java来执行,然后java又变成了本地语言(C语言)来执行,谁叫我们的操作系统都是C语言实现的呢。
"echo" {

return T_ECHO;
 }

使用lex和yacc我们要做那几件事情?

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

  1. 定义各种token类型。他们在.y中定义,这些token既会被lex使用到,也会被.y文件中的BNF使用到。
  2. 写词汇分析代码。这部分代码在.l文件(就是lex的输入文件)中。这块的定义方式是:正则表达式–>对应操作。如果和yacc一起来使用的话,对应的操作通常是返回一个token类型,这个token的类型要在yacc中提前定义好。
  3. 写BNF。这些东西定义了语言的规约方式。

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

关于BNF

下面会具体的说一说

是一种context-free
grammars,请参考:
摘录:

re2c,关于它的英文文档在

<symbol> ::= __expression__

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

  1. <symbol> is a
    nonterminal
  2. __expression__)
    consists of one or more sequences of symbols
  3. more sequences are separated by the vertical
    bar, ‘|’
  4. Symbols that never appear on a left side are
    terminals. On
    the other hand
  5. symbols that appear on a left side are
    non-terminals
    and are always enclosed between the pair <>.

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

在yacc中定义的方式其实是:

接口代码:

<symbol> : __expression__ {operation}

不像其他的扫描器程序,re2c
不会生成完整的扫描器:用户必须提供一些接口代码。用户必须定义下面的宏或者是其他相应的配置。

| __expression__ {operation}

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。一些简单的扫描器可能用不到。

operation 是
满足语法时要执行的C语言代码,这里的C语言代码可以使用一些变量,他们是:$$
$1
$2等等。$$代表规约的结果,就是表达式__expression__的值,$1代表的是前面
__expression__ 中出现的各个word。举个例子:

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

expr2:
expr3 { $$ == $1; }
| expr2 PLUS expr3 { $$ = plus($1, $3); }
| expr2 MINUS expr3 { $$ = minus($1, $3); }
;

扫描器文件结构:

来自:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图