简介

以前学编译原理的时候，老师推荐过LEX /YACC来写编译器，其实这是古老的UNIX软件。 LINUX上有他们的GNU版本 FLEX、BISON。
这两个东西一个是词法分析器，一个是语法分析器。词法分析器的作用是把字符解析成单词。一般的把单词称为token, 而语法分析器则是把单词解析成语法树。

词法分析

语法分析是使用flex工具。flex的使用简单来说分为两步：

  1. 先定义一个flex的输入文件，描述词法。
  2. 用flex程序处理这个文件，生成对应的C语言源代码文件。

一般flex的输入文件以.l文件结尾。以下是一个示例文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
%{

#define YYSTYPE _EasyTData*
#include <iostream>
#include "stdio.h"
#include "easytdata.h"
#include "json.y.hpp"

%}

int [+-]*[0-9]+ 
num [+-]*([0-9]|\.)* 
string \"(\\.|[^\\"])*\"
ignore_char [ \t\r\n]
identifier [a-zA-Z_][a-zA-Z0-9_]*

%%
{identifier} {
        if(strcmp(yytext,"true")==0)
        {
            json2tdata_lval=ed_factory_bool(true);
            return TRUE;
        }
        else if(strcmp(yytext,"false")==0)
        {
            json2tdata_lval=ed_factory_bool(false);
            return FALSE;
        }
        else if(strcmp(yytext,"null")==0)
        {
            json2tdata_lval=ed_factory_none();
            return NIL;
        }
        else
        {
            json2tdata_lval=ed_factory_string(yytext);
            return IDENTIFIER;
        }
}

{num}  {
        json2tdata_lval=ed_factory_int(atoi(yytext));
        return NUM;
    }/*要区分浮点数*/


{string}  {
    /*去掉前后引号的处理，存到TData里面不需要引号*/
    /**/
    json2tdata_pre_process_string(yytext);
    json2tdata_lval=ed_factory_string(yytext);
    return STRING;
}
"{" {return L_BRACE;}
"}" {return R_BRACE;}
"[" {return L_BRACKET;}
"]" {return R_BRACKET;}
":" {return COLON;}
";" {return SEMICOLON;}
"," {return COMMA;}
{ignore_char}
%%

文件分成三个部分。
第一部分:
是从 %{ 到 }% 标记的部分。 这个部分会原封不动的复制到flex的生成代码中。
文件开头定义了一个YYSTYPE宏。每个TOKEN可以有一个lval值属性，YYSTYPE定义类型就是token的lval的类型。_EasyTData是我们的web服务层和web页面层公用的通用数据结构。然后就是一些要include的头文件，第一部分就完了。

第二部分:
是从 %} 到 %% 之间的部分。这部分用正则表达式定义了一些数据类型。
比如int num string ignore_char identifier等。int型的定义就是(±号)后面跟着一些重复的数字。注意这里使用的正则表达式的形式是ERE而不是BRE。 ERE与BRE比较明显的区别就是，ERE使用+表示字符重复一次以上，*表示字符重复0次以上。BRE使用{1,}这种方式表示字符重复1次以上。

第三部分:
是 %% 到 %% 的部分。这里定义了词法分析器在解析的处理动作。
yytext是一个flex内部的标识符，表示匹配到的字符串。上文介绍了，lval也是一个内部标识符，表示TOKEN的值。json2tdata_是标识符的前缀, 在执行flex的时候，用-P指定。

flex输入文件写完之后，使用下面这条命令，就可以把flex的输入文件转换为C语言的源代码了。

1
flex -P"json2tdata_" -o json.l.cpp json.l

语法分析

语法分析是使用bison工具。使用bison工具也是分为两步：

  1. 第一步写bison的输入文件
  2. 第二步用bison程序生成C语言源码

bison的输入文件一般用.y作为后缀名。以下是一个示例文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
%{
  	
  	#include "stdio.h"
  	#include "easytdata.h"
//	#define YYDEBUG 1
	#define YYSTYPE _EasyTData*
	  	
	extern int json2tdata_lex();
	void json2tdata_error(const char*msg);
	
	_EasyTdata *g_oJsonData; //结果存放点  %}
%token INT NUM STRING IGNORE_CHAR L_BRACE R_BRACE L_BRACKET R_BRACKET COLON SEMICOLON COMMA IDENTIFIER TRUE FALSE NIL
%%

Json	: Value {g_oJsonData=$1;/*printf("=========\nResult ToJson():%s",g_oJsonData.ToJson().c_str());*/}

Object	: L_BRACE Pairs R_BRACE {$$=$2;}
		| L_BRACE R_BRACE {$$=ed_factory_map();}

Array	: L_BRACKET Elements R_BRACKET {$$=$2;}
		| L_BRACKET R_BRACKET {$$=ed_factory_vector();}

ID		: NUM {$$=$1;}
		| STRING {$$=$1;}
		| IDENTIFIER{$$=$1;}

Pair	: ID COLON Value 
     {
        
        $$ = ed_factory_pair($1, $3);  
    }

Pairs	: Pairs COMMA Pair {
            ed_map_add_pair($1,$3);
            $$ = $1;
        }
		| Pair {
                  
            $$=ed_factory_map();
            ed_map_add_pair($$, $1);
        }


Value	: NUM {
            $$=$1;
        }
		| STRING {
            $$=$1;

        }
		| Object {$$=$1;}
		| Array {$$=$1;}
		| FALSE {
            $$=$1;
            }
		| TRUE {
            $$=$1;
            }
		| NIL {
            $$=$1;
       
        }

Elements	: Elements COMMA Value {
            ed_vector_add($1,$3);
            $$ = $1;

        }
		| Value {
            $$ = ed_factory_vector();
            ed_vector_add($$,$1);
        }

%%

和flex的词法分析输入文件类似，bison的输入文件也是分成3部分。

第一部分:
%{ 和 %} 之间，是原封不动拷贝到输出的C语言源文件中的。 json2tdata_lex这个函数是flex生成的。json2tdata_error是用来处理错误信息的函数。通过定义和实现这个函数你可以把错误信息写到任何地方。与flex类似，json2tdata也是自定义的前缀。

第二部分:
是
%token INT NUM STRING IGNORE_CHAR L_BRACE R_BRACE L_BRACKET R_BRACKET COLON SEMICOLON COMMA IDENTIFIER TRUE FALSE NIL
这一行，这一行的作用就是声明在flex中定义的那些TOKEN。

第三部分:
是 %% %% 包围的部分。这部分就是语法的推导过程。可以比较轻松的看出，这部分主要就是采用BNF对语法进行描述。比如Array，它有两种形式，表示一个空的Array：

  • 第一种是 `L_BRACKET ELEMENTS R_BRACKET
  • 第二种则是L_BRACKET R_BRACKET`

Bison能够完全支持LR(1)文法。这种文法的特点是只要多向前看一个TOKEN，就能够决定如何解析。因此如果bison告诉你语法ambiguous的时候，可以想一想如何把自己的文法改成LR(1)型文法。另外，每一条规则的后面可以用{}来定义解析的动作。bison用$$表示规则左边的对象，用$1 $2 $3 等依次表示规则右边的对象。

比如：

1
2
3
4
5
6
Elements	: Elements COMMA Value {
            
            ed_vector_add($1,$3);
            $$ = $1;

        }

在执行这条规则的时候，就会用ed_vector_add函数将 Value加入到 Elements中去，然后把$1赋值给$$。

bison的输入文件可以用下面这样的命令转换成C语言的源文件：

1
bison -d -o json.y.cpp json.l -p"json2tdata_"

-p "json2tdata_"是给语法分析器加一个前缀。 有这个选项，就会生成json2tdata_parse等以json2tdata开头的函数。