[心得]应用编译原理知识解决问题

时间:2021-08-22 13:28:24

背景
项目中要使用C++或C语言解析JSON格式的数据,把解析的结果放到一个通用的数据结构。作为web服务层(这一层大家可以认为是类似于PHP服务器或webpy的服务器容器)到web页面层(这一层是语法类似PHP脚本或者tornardo模板)的数据传输的协议。如果使用类似rapidJson或者是jsoncpp之类的Json解析器,相当于我们要做:
JSON文档 -> json DOM -> 通用数据结构。

而如果手写解析器,只需要做:
JSON文档 -> 通用数据结构。

少一层转换能换来很多效率的提升。

解释一下什么是DOM,这是Data Object Model的缩写。
注意Lex/Yacc已经被flex和bison取代了。

词法分析器flex:把字符解析成token;
语法分析器bison:把token解析成语法树。

甜点
先看看flex+bison组合如何处理4则计算。
此例子来自flex和bison的入门教程,写得很好。

flex一般用.l作后缀。例如calc.l。它标准格式是3段。第1段写注释以及包含预处理头文件,第2段描述解析token的规则,第3段实现具体处理代码;

%{
#define YYSTYPE double
#include "calc.tab.h"
#ifdef CALC_LEX
YYSTYPE yylval;
#endif
%}


%%
"+" { return ADD;}
"-" { return SUB;}
"*" { return MUL;}
"/" { return DIV;}
"(" { return OP;}
")" { return CP;}
"|" { return ABS;}
\n { return EOL;}
[ t] { /* ignore*/}
([0-9]*\.?[0-9]+|[0-9]+\.[0-9]*) { yylval = atof(yytext); return NUMBER;}
%%


#ifdef CALC_LEX
int main(int argc, char** argv){
int token;

while(token = yylex()){
printf("%d", token);

if(token == NUMBER){
printf(" = %f\n", yylval);
}else{
printf("\n");
}
}

return 0;
}
#endif

calc.y格式也是类似的3段:

%{
#include <stdio.h>
#define YYSTYPE double
%}

/* decalre tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS OP CP
%token EOL

%%
calclist: /* nothing */
| calclist exp EOL {printf("=%f\n", $2);}
;
exp: factor
| exp ADD factor { $$ = $1 + $3;}
| exp SUB factor { $$ = $1 - $3;}
;
factor: term
| factor MUL term { $$ = $1 * $3;}
| factor DIV term { $$ = $1 / $3;}
;
term: NUMBER
| ABS exp ABS { $$ = $2 >= 0? $2: -$2;}
| OP exp CP { $$ = $2;}
;
%%

main(int argc, char **argv){
yyparse();
}

yyerror(char *s){
fprintf(stderr, "error: %s\n",s);
}

编译的时候需要注意:
先编bison,并且必须加上-d选项,这样才会生出.h头文件。该头文件作为flex文件的一个include输入。
次编flex,这个时候生成输出.c文件
最后用g++编译目标程序,注意链接flex静态库: -lfl

关于编译原理和词法库,我还有2笔欠账:
1. http://www.cnblogs.com/itech/archive/2012/03/04/2375746.html
动手捣鼓一个自己的编译器:http://blog.csdn.net/haoel/article/details/4789364
2. 龙书编译原理的学习和心得总结。

这两笔账,今年年内找个周末补上。

到时候再来更新此博客。