[Flex&Bison]协同工作简介

1. 本节主要演示一个简单的模拟bc计算器的程序，主要功能就是解析整型数的四则运算，先给出bison程序：

%{

#include <stdlib.h>
#include <stdio.h>

%}

/* 定义两个记号，D_INT表示整型类型，EOL表示换行(End Of Line) */
%token	D_INT
%token	EOL

/* 以下4组BNF范式来定义构造语法树的规则 */
/* 每条规则都有一个对应的C语言动作，表示一旦bison使用该规则去构造语法树（的一部分），则执行相应的动作 */

%%

/* 由于这是第一组规则，因此cac将作为语法起始符号，cac:的第一行用空规则表示 */
cac : /* cac -> cac exp EOL */
	/* |表示从左边的cac推到到右边的表达式有多种不同的方式，即或的意思 */
	/* :可以理解为推导符号-> */
	/* :的左边为目标符号，其值用$$表示 */
	/* :右边的语法符号的值从左到右依次为$1、$2、$3…… */
	| cac exp EOL { printf( "ans = %dn",$2 ); }
	; /* ;表示一组规则的结束，同时也作为行分隔符美观代码 */

exp : fac /* exp -> fac|exp+fac|exp-fac */
	/* 虽然exp -> fac的这条规则没有定义动作，但是bison会默认处理成$$ = $1 */
	/* 这非常符合常理 */
	| exp '+' fac { $$ = $1 + $3; }
	| exp '-' fac { $$ = $1 - $3; }
	;

fac : trm /* fac -> trm|fac*trm|fac/trm */
	| fac '*' trm { $$ = $1 * $3; }
	| fac '/' trm {
		/* 判断除零错误 */
		if ( !$3 ) { perror( "Divide by zero!" ); exit( EXIT_SUCCESS ); }
		else $$ = $1 / $3;
	}
	;

trm : D_INT /* exp -> int||trm */
	| '|' trm { $$ = $2 < 0 ? -$2 : $2; }
	;

%%

int
main( int arc,char **argv ) {

	yyparse(); /* bison自己生成的语法分析例程 */

	return 0;
}

int
yyerror( char *s_err ) { /* 当分析产生错误时将自动调用该例程来解决错误 */

	fprintf( stderr,"error: %sn",s_err );

	return 0;
}

经过bison编译后得到的.h文件：

/* Tokens.  */
#ifndef YYTOKENTYPE
# define YYTOKENTYPE
   /* Put the tokens into the symbol table,so that GDB and other debuggers
      know about them.  */
   enum yytokentype {
     D_INT = 258,EOL = 259
   };
#endif
/* Tokens.  */
#define D_INT 258
#define EOL 259




#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
typedef int YYSTYPE;
# define yystype YYSTYPE /* obsolescent; will be withdrawn */
# define YYSTYPE_IS_DECLARED 1
# define YYSTYPE_IS_TRIVIAL 1
#endif

extern YYSTYPE yylval;

可以看到在.l文件和.y文件中都可以定义标记，只不过.l文件中定义标记必须通过enum yytokentype的方式定义（但前提是.y文件中必须定义！）并且需要定义YYTOKENTYPE宏，同时可以看到.y中定义的标记的编号是从258开始的，因此不会和ASCII字符的值相冲突；

在这就是yylval是一个外部链接过来的全局变量，该变量是在flex的库中定义（和yylex()一样），因此最后cc编译时要链接lex库才行！

2. Bison的语法分析基本原理以及对上述程序的补充说明：

? ? 1) 语法分析的主要任务就是用flex解析出来的所有标记构造出一棵语法树；

? ? 2) 而bison最主要的任务就是确定一种将标记转化为语法树的规则；

? ? 3) bison就是使用上下文无关文法来确定这组规则的，而描述该文法的标准书写格式就是BNF范式；

? ? 4) bison程序的结构和flex相同，也分为三段，第一段和第三段和flex的意义相同，而第二段则是规则段，用来确定构造语法树的规则；

? ? 5) 规则段使用BNF来描述，其实就是一组组产生式规则，规则中包含终结符和非终结符，其中%token声明的记号都属于终结符，而在规则段中出现的未在%token中声明过的符号都是非终结符，它们一定能从终结符推导出来，任何没有声明为%token的符号必须至少出现在:左边一次，否则就意味着像C语言中的变量声明了但未使用的情形，可能会导致错误！

? ? 6) 规则段中的第一组规则是最高级别的规则，其左部就是该语法的起始符号，最终推导一定要归结到该符号，否则就意味着原文本语法错误！

? ? 7) 以上使用左递归的方式描述了四则运算的法则，其中将加减和乘除分开，使得乘除优先级高于加减，同时定义了用|模拟取绝对值运算符，并且其优先级最高！

? ? 8) 在每条规则中，每个终结符和非终结符都是由具体值的，:左边的非终结符的值默认已经从其它推导获得（计算而得），可以直接用$n的方式访问，而左边的目标符号的值确实未知的，需要通过动作来决定它，例如$$ = $1 + $3，这也就是定义语法意义的本质！

3. 再看flex程序：

%{
	
/* 由bc.y通过bison编译而得 */
/* 里面定义了记号D_INT和EOL */
#include "bc.tab.h"

%}

/* 为整型数的正则表达式定义一个宏名 */
INT				[-+]?[0-9]+

/* 由于char类型所表示字符处于ASCII范围 */
/* 而bison程序中定义的标记的编号是从258开始的 */
/* 因此直接返回字符和返回编号两者之间不会冲突 */

/* flex和bison之间的关系就是bison利用flex的yylex()去解析 */
/* 原文中的各个记号，解析出来一个记号，yylex()就将该记号的编号返回给bison供它分析 */
/* 同时flex会将解析出来的记号值存放在yytext中，并且可以将记号值所表示的数值解析到yylval中保存 */
/* 而这两个变量的值都会自动传给bison，因此在bison程序中也可以访问这两个值 */
/* 这样bison就可以充分利用flex的词法分析了 */
%%

"+"		{ return '+'; }
"-"		{ return '-'; }
"*"		{ return '*'; }
"/"		{ return '/'; }
"|"		{ return '|'; }

{INT}	{ yylval = atoi( yytext ); return D_INT; }

n		{ return EOL; }
[ t]	{ }

.		{ fprintf( stderr,"Illegal character %cn",*yytext ); }

%%

lex.bc.y是由bison -d bc.y得来的！

4. Makefile：

bc.out: bc.l bc.y
	bison -o bc.tab.c -d bc.y
	flex -o lex.bc.c bc.l
	cc -o $@ -ll bc.tab.c lex.bc.c

5. 运行结果：

$ ./bc.out
2 +  	832 * |-3
ans = 2498

6.?