如何用flex+bison写语法分析器
发布时间：2020-12-15 04:26:32 所属栏目：百科 来源：网络整理
导读：http://my.oschina.net/costaxu/blog/107714? 背景 这个星期，项目中要使用C++或C语言解析JSON格式的数据，把解析的结果放到一个通用的数据结构。这个通用的数据结构，实际上是作为web服务层（这一层大家可以认为是类似于PHP服务器或webpy的服务器容器）到we
|
http://my.oschina.net/costaxu/blog/107714?
背景
这个星期，项目中要使用C++或C语言解析JSON格式的数据，把解析的结果放到一个通用的数据结构。这个通用的数据结构，实际上是作为web服务层（这一层大家可以认为是类似于PHP服务器或webpy的服务器容器）到web页面层(这一层是语法类似PHP脚本或者tornardo模板)的数据传输的协议。 之所以要这样处理， 主要是因为这个web类的项目(一般的web类项目也是如此)需求变化较快，而web的服务层使用是采用C++进行开发的，为了使当web服务层的数据格式变化不影响web页面层，所以双方使用统一的通用的数据结构。而之所以交代这么多的背景是， 为了让大家了解为什么我们不使用类似rapidjson或jsoncpp来实现json的解析而需要手写解析器。 因为使用类似rapidJson或者是jsoncpp之类的Json解析器，相当于我们要做:
?JSON文档 -> json DOM -> 通用数据结构。?
而如果手写解析器，只需要做:
JSON文档 -> 通用数据结构。
少一层转换能换来很多效率的提升。
说了这么多，下面开始进入正题。 ? 以前学编译原理的时候，老师推荐过LEX /YACC来写编译器，其实这是古老的UNIX软件。 LINUX上有他们的GNU版本 FLEX、BISON。 这两个东西一个是词法分析器，一个是语法分析器。词法分析器的作用是把字符解析成单词。一般的把单词称为token,?而语法分析器则是把单词解析成语法树。
词法分析
首先来看flex的使用：简单来说分为两步： 1 先定义一个flex的输入文件，描述词法。2 用flex程序处理这个文件，生成对应的C语言源代码文件。
?一般flex的输入文件以.l文件结尾， 比如这个文件json.l。?
|
? |
03
#define YYSTYPE _EasyTData*
|
04
#include <iostream>
|
05
#include "stdio.h"
|
06
#include "easytdata.h"
|
07
#include "json.y.hpp"
|
08
09
|
? |
10
%}
|
11
12
|
int?[+-]*[0-9]+
|
13
num [+-]*([0-9]|.)*
|
14
string "(.|[^"])*"
|
15
ignore_char [ trn]
|
16
identifier [a-zA-Z_][a-zA-Z0-9_]*
|
17
18
|
%%
|
19
{identifier} {
|
20
????????if(strcmp(yytext,"true")==0)
|
21
????????{
|
22
????????????json2tdata_lval=ed_factory_bool(true);
|
23
????????????return?TRUE;
|
24
}
|
25
else?"false")==0)
|
26
{
|
27
false);
|
28
FALSE;
|
29
}
|
30
"null"31
|
32
|
json2tdata_lval=ed_factory_none();
|
33
NIL;
|
34
35
|
else
|
36
37
|
json2tdata_lval=ed_factory_string(yytext);
|
38
IDENTIFIER;
|
39
40
|
41
|
42
|
{num}? {
|
43
json2tdata_lval=ed_factory_int(atoi(yytext));
|
44
NUM;
|
45
????}
|
46
47
|
48
|
{string}? {
|
49
????
|
50
/**/
|
51
json2tdata_pre_process_string(yytext);
|
52
json2tdata_lval=ed_factory_string(yytext);
|
53
????STRING;
|
54
55
|
"{"?{L_BRACE;}
|
56
"}"?R_BRACE;}
|
57
"["?L_BRACKET;}
|
58
"]"?R_BRACKET;}
|
59
":"?COLON;}
|
60
";"?SEMICOLON;}
|
61
","?COMMA;}
|
62
{ignore_char}
|
63
%%
|
文件分成三个部分。第一部分是从%{到 }%标记的部分。 这个部分会原封不动的复制到flex的生成代码中。文件开头定义了一个YYSTYPE宏。每个TOKEN可以有一个lval值属性，YYSTYPE定义类型就是token的lval的类型。_EasyTData是我们的web服务层和web页面层公用的通用数据结构。然后就是一些要include的头文件，第一部分就完了。
flex的输入文件的第二部分，是从%}到%%之间的部分，这部分用正则表达式定义了一些数据类型。 比如int num string ignore_char identifier等。 int型的定义就是(+-号)后面跟着一些重复的数字。注意这里使用的正则表达式的形式是ERE而不是BRE。 ERE与BRE比较明显的区别就是，ERE使用+表示字符重复一次以上，*表示字符重复0次以上。BRE使用{1,}这种方式表示字符重复1次以上。
flex的输入文件的第三部分，是%%到%%的部分。这里定义了词法分析器在解析的处理动作。yytext是一个flex内部的标识符，表示匹配到的字符串。上文介绍了，lval也是一个内部标识符，表示TOKEN的值。json2tdata_是标识符的前缀,在执行flex的时候，用-P指定。
flex输入文件写完之后，使用下面这条命令，就可以把flex的输入文件转换为C语言的源代码了。
1
flex -P"json2tdata_"?-o json.l.cpp json.l
|
