#关于flex&bison(lex&yacc)解析JSON的探索
**目录**
[TOC]
##前言
关于lua，有句话很出名：
>它使我们很脸红……
像`Lua`、`TCC`这种，又小又好用的东西，然而我们却写不出来这样的东西，确实是很可惜的……
其实我还是研究过`Lua`的源码一段时间的……比如说`Lua1.0`版本比较简单，里面就是用`lex&yacc`工具辅助进行解析的……
此外我还对`wxBasic`的实现也比较感兴趣（好歹我也是自称`BASIC`出身的程序媛啊……惭愧惭愧），它也是用`lex&yacc`工具辅助进行解析的……
编译原理这门课我还真没学过，然而自学了三年，还是停留在第一章，只能说意志不坚啊……
话说直到前几天，在群里有个同事问，`JSON`的解析需要什么算法么？我说与其说需要算法，不如说需要编译原理吧……可惜我对编译原理也是略通啊……
但是这也并不能阻止我用`lex&yacc`去写一个`JSON`解析器啊……当然，我们的目标不在于实现，而在于弄清楚其原理……
同事的求问激起了我的强烈兴趣，我写一个`JSON`解析器尝试一下……以此来打开我进入新世界的大门~
先说说工具和环境，工具用的是`UnxUtils`中的`flex&bison`工具，环境用的还是万年不变的`MinGW`……关于`JSON`的说明资料……
##词法解析器（lex/flex）
说干就干，先是用`flex`工具，写一个词法解析器，这一步还是相对简单的……
当然我们的目标不是写一个相对完整的`JSON`，所以，在对`Number`的正则上也是随便意思一下……
但是对于`String`类型的词法解析还是比较复杂的，我凑了半天没凑出正则了，后来我就参考了这篇文章《[Lex识别C风格字符串和注释](http://blog.csdn.net/xfxyy_sxfancy/article/details/45024573 "Lex识别C风格字符串和注释")》……
总体来说还是没有什么难点的……我们先写一些测试输出看看拼凑的正则对不对，感受一下lex神器带来的优越感~
当然，在这儿我们用的工具是`flex`……到词法解析这一步，整体还是挺顺风顺水的……
`testjson.l`文件:
```lex
%{
#include <string.h>
char* yylval;
%}
def [_a-zA-Z][_a-zA-Z0-9]*
str \"(\\\"|[^\"])*\"
num [0-9]+(\.[0-9]+)?
arrs \[
arre \]
objs \{
obje \}
split ,
desc :
%%
{str} { yylval = strdup(yytext);
printf("[STR:%s]",yylval);
free(yylval);}
{def} { yylval = strdup(yytext);
printf("[DEF:%s]",yylval);
free(yylval);}
{num} { yylval = strdup(yytext);
printf("[NUM:%s]",yylval);
free(yylval);}
{arrs} {printf("[ARRS]");}
{arre} {printf("[ARRE]");}
{objs} { printf("[OBJS]"); }
{obje} { printf("[OBJE]"); }
{desc} { printf("[DESC]"); }
{split} { printf("[SPLIT]");}
%%
```
然后用flex工具生成C文件，用gcc编译一下，相关命令：
```Shell
flex -o testjson.c testjson.l
gcc -o testjson.exe testjson.c -lfl
```
当然，我写了个批处理来编译运行它，内容如下：
```Shell
@echo off
color 1E
echo 当前目录:%~dp0
cd "%~dp0"
echo flex编译testjson.l生成testjson.c...
flex -o testjson.c testjson.l
echo gcc编译testjson.c链接libfl.a输出testjson.exe...
gcc -o testjson.exe testjson.c -L. -lfl
echo 运行testjson.exe输入json.txt作为测试文件...
echo 输出结果:
testjson.exe<json.txt
pause
```
其中的示例`json.txt`内容如下（后面再不声明的情况下，都是用的这个串）：
```json
{
a:[1,2,3],
b:["a\tbc","12 3","4,5\"6",{
x:1,
y:"cc\ncc"
},4.56],
"text":"I'm OK~",
"1-2":234
}
```
运行批处理生成结果如下：
```
当前目录:C:\jsonParse\lexTest\
flex编译testjson.l生成testjson.c...
gcc编译testjson.c链接libfl.a输出testjson.exe...
运行testjson.exe输入json.txt作为测试文件...
输出结果:
[OBJS]
[DEF:a][DESC][ARRS][NUM:1][SPLIT][NUM:2][SPLIT][NUM:3][ARRE][SPLIT]
[DEF:b][DESC][ARRS][STR:"a\tbc"][SPLIT][STR:"12 3"][SPLIT][STR:"4,5\"6"
][SPLIT][OBJS]
[DEF:x][DESC][NUM:1][SPLIT]
[DEF:y][DESC][STR:"cc\ncc"]
[OBJE][SPLIT][NUM:4.56][ARRE][SPLIT]
[STR:"text"][DESC][STR:"I'm OK~"][SPLIT]
[STR:"1-2"][DESC][NUM:234]
[OBJE]
请按任意键继续. . .
```
输出的结果感觉还是挺优雅的~
特别是给批处理配上颜色之后，大家感受一下效果图：
##语法解析器（yacc/bison）
然后，就是语法解析了……轮到`yacc`神器出场了，当然，我们在这儿用的工具是`bison`……
对于`yacc`来说，最关键的东西就是语法生成树了……语法生成树的构造还是挺学问的……
我尝试了一些写法……总之，终于凑出一个写法来结果是对的……
因为编译原理自学的不好，所以搞出一些奇怪的异常来……
在此要提醒的有这些：`yacc`源文件中的`#define YYSTYPE char*`放得高点比较好，还有就是那三个函数的定义，不写上会报`warnning`，尽管没什么影响……
好了，先要改写`json.l`文件，使其的词法解析结果`token`作为`json.y`的输入：
```lex
%{
#include <string.h>
#include "json.tab.h"
extern char* yylval;
%}
space [ \t\n]+
def [_a-zA-Z][_a-zA-Z0-9]*
str \"(\\\"|[^\"])*\"
num [0-9]+(\.[0-9]+)?
arrs \[
arre \]
objs \{
obje \}
split ,
desc :
%%
{str} { yylval = strdup(yytext);
return STR; }
{def} {
if(strcmp(yytext,"true")==0){
return TRUE;
}else if(strcmp(yytext,"false")==0){
return FALSE;
}else if(strcmp(yytext,"null")==0){
return NIL;
}else{
yylval = strdup(yytext);
return STR;
}
}
{num} { yylval = strdup(yytext);
return NUM; }
{arrs} { return ARRS; }
{arre} { return ARRE; }
{objs} { return OBJS; }
{obje} { return OBJE; }
{desc} { return DESC; }
{split} { return SPLIT; }
{space} {}
%%
```
然后是`json.y`的语法树解析，输出一下对于解析结果的一些初步规划，比如说`push`和`add`之类的，这样可以查看结果跟预想的是不是一样：
```yacc
%{
#define YYSTYPE char*
#include <stdio.h>
#include "lex.yy.c"
int yyparse(void);
int yyerror(const char* msg);
int yywrap();
%}
%token STR NUM DESC SPLIT ARRS OBJS ARRE OBJE FALSE TRUE NIL
%%
command : value {printf("end\n");}
value: STR {printf("value:[string]%s\n",$1);free($1);}
|NUM {printf("value:[number]%s\n",$1);free($1);}
|FALSE {printf("value:FALSE\n");}
|TRUE {printf("value:TRUE\n");}
|NIL {printf("value:NULL\n");}
|object {printf("value:OBJECT\n");}
|array {printf("value:ARRAY\n");}
;
arrs: ARRS {printf("array_start\n");};
array : arrs ARRE {printf("[empty]\n"); }
| arrs values ARRE {printf("[...]\n"); }
;
objs: OBJS {printf("object_start\n");};
object : objs OBJE {printf("{empty}\n");}
| objs pairs OBJE {printf("{...}\n");}
;
values : values SPLIT value {printf("add %s\n",$3);}
|value {printf("add %s\n",$1);}
|values SPLIT
;
pairs : pairs SPLIT pair {printf("put\n");}
|pair {printf("put\n");}
|pairs SPLIT
;
pair : STR DESC value {printf("key %s\n",$1);}
;
%%
int main()
{
return yyparse();
}
int yyerror( const char* msg)
{
fprintf (stderr,"%s\n",msg);
return 0;
}
int yywrap()
{
return 1;
}
```
同样，写个脚本运行一下，同样的测试字符串：
```Shell
@echo off
color 1E
echo 当前目录:%~dp0
cd "%~dp0"
echo flex编译json.l生成lex.yy.c...
flex json.l
echo bison编译json.y生成json.tab.h、json.tab.c...
bison -d json.y
echo gcc编译json.tab.c输出json.exe...
gcc json.tab.c -o json.exe
echo 运行json.exe输入json.txt作为测试文件...
echo 输出结果:
json.exe<json.txt
pause
```
输出的结果是这个样子的：
还是挺有感觉的……配合堆栈以及`Map`和`List`的复式结构，就可以把这个`json`中表现的内容存起来了~
##配套堆栈处理
语法解析是第一道坎，而相关的堆栈操作和处理便是第二道坎……
每一步执行什么操作都是要有所设计，做到心中有数的……
刚才已经看到了语法解析的处理结果，必须要配合堆栈才能把数据处理好……
可惜，`C语言`里要写个`Stack`或者是`Map`是挺麻烦的……我并不准备这么干……
因为我们的目标是弄清楚编译原理，而不是要实现各什么东西……
于是我选择了语法解析之后，将结果转为`JS`语句，将`JSON`输出形成一个返回`JS对象`的函数……
听上去还是挺酷的~相关的`json.l`文件不用变动，其中的`json.y`文件变成了这样：
```yacc
%{
#define YYSTYPE char*
#include <stdio.h>
#include "lex.yy.c"
int yyparse(void);
int yyerror(const char* msg);
int yywrap();
%}
%token STR NUM DESC SPLIT ARRS OBJS ARRE OBJE FALSE TRUE NIL
%%
command : value {printf("\treturn curValue;\n");}
value: STR {printf("\tcurValue=\"%s\"\n",$1);free($1);}
|NUM {printf("\tcurValue=%s\n",$1);free($1);}
|FALSE {printf("\tcurValue=false;\n");}
|TRUE {printf("\tcurValue=true;\n");}
|NIL {printf("\tcurValue=null;\n");}
|object {printf("\tcurValue=curObj;\n\tcurObj=stack[stack.length-1];\n\n");}
|array {printf("\tcurValue=curObj;\n\tcurObj=stack[stack.length-1];\n\n");}
;
arrs: ARRS {printf("\tcurObj=[];\n\tstack.push(curObj);\n");};
array : arrs ARRE {printf("\tcurObj=stack.pop();\n"); }
| arrs values ARRE {printf("\tcurObj=stack.pop();\n"); }
;
objs: OBJS {printf("\tcurObj={};\n\tstack.push(curObj);\n");};
object : objs OBJE {printf("\tcurObj=stack.pop();\n");}
| objs pairs OBJE {printf("\tcurObj=stack.pop();\n");}
;
values : values SPLIT value {printf("\tcurObj.push(curValue);\n");}
|value {printf("\tcurObj.push(curValue);\n");}
|values SPLIT
;
pairs : pairs SPLIT STR DESC value {printf("\tcurObj[\"%s\"]=curValue;\n",$3);}
|STR DESC value {printf("\tcurObj[\"%s\"]=curValue;\n",$1);}
|pairs SPLIT
;
;
%%
int main()
{
printf("(function(){\n\tvar stack = [];\n\tvar curObj = null;\n\tvar curValue=null;\n\n");
int r = yyparse();
printf("})()");
return r;
}
int yyerror( const char* msg)
{
fprintf (stderr,"%s\n",msg);
return 0;
}
int yywrap()
{
return 1;
}
```
相应的测试批处理文件内容：
```Shell
@echo off
color 1E
echo 当前目录:%~dp0
cd "%~dp0"
echo flex编译json.l生成lex.yy.c...
flex json.l
echo bison编译json.y生成json.tab.h、json.tab.c...
bison -d json.y
echo gcc编译json.tab.c输出json.exe...
gcc json.tab.c -o json.exe
echo 运行json.exe输入json.txt输出“生成结果.txt”...
json.exe<json.txt>生成结果.txt
pause
```
生成的结果：
```JavaScript
(function(){
var stack = [];
var curObj = null;
var curValue=null;
curObj={};
stack.push(curObj);
curObj=[];
stack.push(curObj);
curValue=1
curObj.push(curValue);
curValue=2
curObj.push(curValue);
curValue=3
curObj.push(curValue);
curObj=stack.pop();
curValue=curObj;
curObj=stack[stack.length-1];
curObj["a"]=curValue;
curObj=[];
stack.push(curObj);
curValue="a\tbc"
curObj.push(curValue);
curValue="12 3"
curObj.push(curValue);
curValue="4,5\"6"
curObj.push(curValue);
curObj={};
stack.push(curObj);
curValue=1
curObj["x"]=curValue;
curValue="cc\ncc"
curObj["y"]=curValue;
curObj=stack.pop();
curValue=curObj;
curObj=stack[stack.length-1];
curObj.push(curValue);
curValue=4.56
curObj.push(curValue);
curObj=stack.pop();
curValue=curObj;
curObj=stack[stack.length-1];
curObj["b"]=curValue;
curValue="I'm OK~"
curObj["text"]=curValue;
curValue=234
curObj["1-2"]=curValue;
curValue=false;
curObj["mybool"]=curValue;
curValue=null;
curObj["mynull"]=curValue;
curValue=true;
curObj["myreal"]=curValue;
curObj=stack.pop();
curValue=curObj;
curObj=stack[stack.length-1];
return curValue;
})()
```
既然生成了`js`，就可以在浏览器里执行一下看看效果有什么不同：
从效果图上来看，结果还是挺棒的~~~~~
这里，来讲解一下这段代码跟上面那段代码不同的地方。
刚才说了，`C`里面写堆栈、`List`和`Map`啰里啰嗦的，还是`js`方便……`js`中用变量`stack`作为`json`解析的处理堆栈……
注意，在语法解析时，`yacc`里面其实是有堆栈的，一个是运行堆栈，一个是值堆栈，这是语法解析用的堆栈……
而`js`中这个`stack`是真正的运行时堆栈……传说中的`runtime`对象……只是听上去高大上而已……
`stack`的出栈入栈就这么被体现出来了~
还有一个是`curValue`、`curObj`，是保存当前值的变量……这两个变量赋值来赋值去的，看上去挺烦的……
但是我觉得虽然很繁琐，但是这么写很好用啊~
然后就这么出栈入栈，赋值来赋值去，一个生成`js对象`的函数就这么生成了……是不是很神奇？
##后话
我就这么通宵一晚上用`flex&bison`工具完成了`JSON`解析的大致原理性的实现……
然后第二天去群里向那个求问的同事显摆，然而那个同事连看都不看一眼，表示，要用`java`写才行……还要用原生`JDK`方法，不能引入第三方包……
我苦逼的问为啥，他说写完`java`版的`json`解析，就可以去阿里工作了！
我哈哈一笑，去阿里这么简单？我既然能写个`flex&bison`版的，我肯定就能写个`java`版的呀……
你看，我这看了1/10本的编译原理的人都能写出来，这阿里的门槛不早被踏破了？
我说你等着，我很快就给你出个`java`版本的……于是我又通宵一晚上写了个`java`版本的……
至于这个`java`版本的，留到下一篇博客中再说吧……
鲁公网安备 37010202001027号