9.1　基础知识

数据包过滤机制在具体的实现上与数据包的协议类型并无多大关系，它只是简单地把数据包看成了1字节数组，实际过滤是根据具体的协议把谓词判断映射到数组特定位置的值上。例如判断ARP类型的数据包，只需要判断数组中第13、14个字节（以太网数据包头中的协议类型）是否为0X0806。从理论研究上看，数据包过滤机制是一个数学问题，或者说是一个算法问题，其中心任务是如何使用最少的判断操作、最少的时间完成过滤处理，从而提高过滤效率。下面将介绍理解WinPcap数据包过滤实现机制所必需的一些基础知识。

注意　本节难度较大，可先粗略地浏览一遍，看完本章其他小节后再回过头来仔细阅读本节。

9.1.1　flex和bison简介

一般语言的编译器在处理语言时，通常会分为词法分析和语法分析两个阶段。词法分析阶段识别低级对象，比如数、操作符及特殊符号等。语法分析阶段识别高级对象，如程序设计语言中的语句。无论是词法分析还是语法分析，用手工去编写程序都是十分烦琐的，因此在UNIX系统与类UNIX系统中，都提供了lex(lexical analyzer)和yacc(Yet another Compiler Compiler)等软件工具来实现该功能。使用这些工具，不仅可以显著地简化词法分析和语法分析程序的开发工作，还可以帮助用户完成许多其他的任务。

在GNU^[1]工程中，lex和yacc的对应工具为flex和bison，同时这两个工具也可以在Win32平台上与Microsoft Visual Studio C++结合使用。flex和bison的功能非常强大，非常适合开发词法和语法解析器，尤其是语言编译器和解释器。

1.flex和bison的程序格式

（1）flex

flex程序分为三个段，这些段以%%作为分界。第一段是C和flex的全局声明，第二段是规则，第三段是补充的C函数。flex的程序结构如下：

＜定义段＞、＜规则段＞和＜子程序段＞

＜定义段＞的内容主要是C语言说明，即括在“%{”和“%}”之间的内容。所有C语言的说明语句和预处理语句都可以放在这一部分中，flex将把“%{”和“%}”之间的内容不加改变地抄写到它所生成的词法分析程序中去。

＜规则段＞中的每一条规则都可分为正则表达式部分和C程序（或动作部分）。当输入流中出现与正则表达式相匹配的字符串时，就执行后面的动作。为了便于描述词法分析程序的动作，flex还提供了许多变量、子程序和宏供用户使用，详细可以参见用户手册。

＜子程序段＞可以定义词法分析程序所需的各类过程和函数，比如主程序main函数或yywrap函数。而子程序段里的内容会由flex原封不动地复制到它所生成的词法分析程序里面。

（2）bison

bison源程序结构也分为三个段：

＜说明段＞、＜规则段＞和＜子程序段＞

＜说明段＞中的说明包含两方面的内容：一个是C程序说明；另一个是bison说明。C程序说明必须用配对的“%{”和“%}”括在一起，它们将原封不动地复制到bison所生成的语法分析程序中去。bison说明有多种形式，关键字%token的作用是说明终结符，没有在%token语句中出现的标识符都被认为是非终结符，每个非终结符必须至少在产生式的左部出现一次。在所有的非终结符中，描述最一般结构的产生式左部的非终结符称为开始符。%right、%left和%nonassoc的作用是说明算符的结合性，以解决语法的二义性问题。

＜规则段＞由一条或多条规则组成，不包含任何规则的＜规则段＞是不合法的，每条规则以分号结尾。在逻辑上一条规则可分为两部分，一部分是一条巴科斯范式（BNF），另一部分是一段C程序（称为一个动作）。当从词法分析程序得来的单词序列可按某个BNF进行归类时，就可执行与该BNF相对应的动作了。

在＜子程序段＞里，用户可以定义自己所需的各种子程序，比如说错误处理程序yyerror。子程序中的内容都会被bison如实地复制到bison所生成的语法分析程序中去。

2.应用flex和bison编程的基本方法

在用flex和bison开发语言处理程序时，用户会先编写一个flex源程序和一个bison源程序。

注意　flex、bison和C/C++是强耦合的。

flex源程序经flex工具处理后，在文件lex.yy.c中生成一个用C语言描述的词法分析子程序yylex()，文件lex.yy.c再经C编译器编译，就可以得到能与其他模块链接的目标文件lex.yy.o或可直接运行的命令文件了。

bison源程序经bison工具处理后，可在文件y.tab.c中得到一个用C语言描述的语法分析子程序yyparse()。文件y.tab.c再经C编译器编译，则会得到能与其他模块链接的目标文件y.tab.o或可直接运行的命令文件。

flex和bison对源程序文件的名字没有特殊要求，但以.l作为flex源文件的扩展名（如frame.l），.y作为bison的扩展名（如frame.y），是一个良好的习惯。

flex编程可以分为三个步骤。

第一步：编写词法分析文件，以flex可以理解的格式指定与模式相关的动作。

第二步：运行flex工具，对该词法分析文件生成扫描器需要的C代码。

第三步：编译和链接该C代码，生成可执行的扫描器。

注意　如果扫描器是用bison开发的解析器的一部分，只需要进行第一步和第二步。

用bison创建一个编译器分为四个步骤。

第一步：编写一个扩展名为.y的语法文件，具体要求如下：

❑说明在这里要进行的动作；

❑编写一个词法分析器来处理输入，并将标记传递给解析器，这通常可以使用flex来完成；

❑编写一个函数，通过调用yyparse函数开始解析；

❑编写错误处理例程(如yyerror函数)。

第二步：运行bison工具为该语法文件生成一个解析器。

第三步：编译bison生成的代码以及其他相关的源文件。

第四步：将目标文件链接到适当的可执行解析器中。

3.flex和bison之间的接口

如果要用flex所生成的词法分析程序和bison生成的语法分析程序共同组成一个完整的语言处理系统，那么，就需要使它们的函数名、参数和返回值一致。恰巧bison所生成的语法分析程序yyparse()调用的词法分析程序与flex所生成的程序都叫yylex()，所以它们在函数名上是相吻合的，不存在矛盾。而且因为yylex()是无参函数，也不存在参数传递问题，语法分析程序yyparse()会要求词法分析程序为它返回单词的编码。

在flex源程序中，同一个单词在词法分析程序和语法分析程序中必须代表相同的值。在bison所生成的文件y.tab.c中，每一个终结符、标识符都会用#define语句定义为一个整数，这个整数的值就是该终结符的编码。第一个出现在bison源程序%token说明中的终结符的编码为257，其余终结符的编码按照它们在%token说明中出现的顺序依次增加。文字型终结符以它们的ASCII码值(0～255)作为自身的单词编码。yylval是一个由bison负责定义的变量，不必在源程序中进行说明。但如果需要重新定义，就需要在.y文件的说明段指出。

4.使用flex与bison的实例

下面介绍使用flex与bison的实例，下面的实例将会在两种操作系统环境中进行演示。该实例用于实现一个简单的四则运算计算器。

第一种环境为Redhat Enterprise Advance server 5(2.6.18内核)操作系统，开发环境使用操作系统自带的gcc编译器，flex的版本为2.5.4，bison的版本为2.3。

词法文件frame.l的内容如下：

%{

include＜stdlib.h＞

include"frame.tab.h"

void yyerror(char*);

%}

%%

[0-9]+{yylval=atoi(yytext);

return INTEGER;}

[-+/\n]{returnyytext;}

[\t];

.yyerror("invalid character");

%%

int yywrap(void)

{

return 1;

}

语法文件frame.y的内容如下：

%{

include＜stdio.h＞

int yylex(void);

void yyerror(char*);

%}

%token INTEGER

%%

program:

program expr'\n'{printf("%d\n",$2);}

|

;

expr:INTEGER{$$=$1;}

|expr'+'expr{$$=$1+$3;}

|expr'-'expr{$$=$1-$3;}

|expr''expr{$$=$1$3;}

|expr'/'expr{$$=$1/$3;}

;

%%

void yyerror(char*s){

printf("%s\n",s);

return;

}

int main(void){

yyparse();

return 0;

}

编译过程如下：

$fex frame.l

$bison-d frame.y

$g++-o cal frame.tab.c lex.yy.c

$ls

cal frame.l frame.tab.c frame.tab.h frame.y lex.yy.c

运行结果如下：

$./cal

7=8

invalid character

syntax error

$./cal

7+8

15

8*6

48

9/4

2

7*8

56

第二种环境为Windows XP操作系统，开发环境为Visual Studio 2005，flex的版本为2.5.4，bison的版本为1.28^[2]。

词法文件frame.l的内容如下：

%{

include＜stdlib.h＞

include＜io.h＞

include"frame.tab.h"

void yyerror(char*);

%}

%%

[0-9]+{yylval=atoi(yytext);

return INTEGER;}

[-+/\n]{returnyytext;}

[\t];

.yyerror("invalid character");

%%

int yywrap(void)

{

return 1;

}

语法文件frame.y的内容如下：

%{

include＜stdlib.h＞

include＜stdio.h＞

int yylex(void);

void yyerror(char*);

%}

%token INTEGER

%%

program:

program expr'\n'{printf("%d\n",$2);}

|

;

expr:INTEGER{$$=$1;}

|expr'+'expr{$$=$1+$3;}

|expr'-'expr{$$=$1-$3;}

|expr''expr{$$=$1$3;}

|expr'/'expr{$$=$1/$3;}

;

%%

void yyerror(char*s){

printf("%s\n",s);

return;

}

int main(void){

yyparse();

return 0;

}

编译过程如下：

＞fex frame.l

＞bison-d frame.y

在Visual Studio 2005中创建cal_vc2005工程，把生成的frame.tab.c、frame.tab.h与lex.yy.c文件添加到该工程中。

注意，应把lex.yy.c文件的第25行代码（如下所示）屏蔽掉，否则编译会出错，因为这是UNIX系统或类UNIX系统的头文件。

//#include＜unistd.h＞

至此，构建成功。

注意　如果源文件中使用了C++的特性，则需要进行文件改名，否则编译器会依据扩展名把这些源文件当作C文件处理，编译将会出错。

把C语言的文件改名为C++语言的文件名的操作如下：

＞mv frame.tab.c frame.tab.cpp

＞mv lex.yy.c lex.yy.cpp

Windows XP环境下开发的这个计算器程序的运行结果如图9-1所示。

图　9-1　计算器的运行结果

[1]GNU(Gnu's Not UNIX)项目由Stallman于1983年创建，这是自由软件基金会的工程，主要工作是创建开放源代码的类UNIX操作系统及其相应的应用软件。

[2]可从因特网上获得UnxUtils工具套件，其中包含flex与bison工具。