使用lex和yacc组建你的分析器

1.前言

[源码精读系列]先从PHP开始写起,下一篇PHP2的版本中,新增了PHP解释器的雏形。这是基于bison的解析器,所以有必要写一篇前置文章,来介绍下bison。bison是yacc的替代品,所以再往上追朔,我们就需要了解下lex和yacc的应用。

2.介绍

关于编译原理的相关细节问题,不在本文的讨论范围之内

2.1 什么是lex

lex是由美国的贝尔实验室用C语言开发的一个词法分析器自动生成工具,通过配置lex规定的语法格式的配置文件,来生成C语言版本的翻译器。

2.2 什么是yacc

yacc也是由美国的贝尔实验室用C语言开发的一个语法解析器,它的解析输入源需要是标识符,所以一般会和lex配合使用,把lex生成的标识符交给yacc去处理。yacc的语法规则会因为歧义性而导致归约冲突。

3.配置文件结构

3.1 lex配置文件结构

...定义段...
%%
...规则段...
%%
...用户程序段...

3.2 yacc配置文件结构

...定义段...
%%
...规则段...
%%
...用户程序段...

定义段中,引入C语言的部分需要包含在%{}%之间

4.常见C语言API接口

4.1 lex

yylex():开始或者重启lex扫描程序

yyleng:当扫描程序匹配标记识符时,匹配的内容以空字符为终止符存储在yytext中,长度为yyleng 即 strlen(yytext)

yyless(n):返回除标记开头的n个字符以外的所有字符,和yymore(n)相对应

yytext:存储了扫描程序匹配的标识符内容

yywrap():当词法分析器遇到文件结尾时,扫描程序的行为,通过返回值确定:1表示结束、0表示继续

4.2 yacc

yyparse():开始语法分析程序

yyerrok():错误回退到最后一个正常状态

yyerror():语法错误时的回调函数

5.小试牛刀

5.1 lex的示例

%{
#include <stdio.h>
%}
%%
a |
b |
c   {printf("%s: found\n", yytext);}
[0-9]+ {printf("%s is number\n", yytext);}
%%

int yywrap()
{
	return 1;
}

int main()
{
	yylex();
}
通过对上述lex文件的编译生成最后的可执行词法分析程序

5.2 yacc的示例

yacc需要配合lex一起使用,先看下面的示例代码

%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0-9]+ {
yylval = strdup(yytext);
return YEAR;
};
[a-zA-Z]+ {
yylval = strdup(yytext);
return NAME;
}
%%
int yywrap()
{
return 1;
}
%{
#include <stdio.h>
typedef char* string;
#define YYSTYPE string
%}
%token YEAR
%token NAME
%%
file : date name
;
date: YEAR
{
printf("date: %s\n", $1); 
}
;
name: NAME
{
printf("name: %s\n", $1); 
};
%%
int main()
{
yyparse();
return 0;
}
int yyerror(char *msg)
{
printf("Error formated! Please Input YYYY MM DD!: %s \n", msg);
}

编译操作

lex name.l && bison -y name.y -d

cc lex.yy.c y.tab.c -o name

最后运行结果:

yacc和lex的组合使用

6.结语

lex和yacc就写到这里,只是两个很简单的例子,不过可以让我们理解它们的运行原理,便于后面写PHP2源码阅读系列的时候,容易去精读PHP解析器的实现细节。如果需要深入了解,建议查阅官方文档。

7.参考

《Lex与Yacc第二版》

https://baike.baidu.com/item/lex%E4%B8%8Eyacc/12110521?fr=aladdin

网络资料

https://www.ibm.com/developerworks/cn/linux/sdk/lex/index.html
如无特殊说明,文章均为本站原创,转载请注明出处。如发现有什么不对的地方,希望得到您的指点。

发表评论

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