orczhou.com

这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。这个系列，分成了几个部分，包括

• flex的基本用法
• 使用flex/bison实现一个简单的计算器
• 实现一个带有条件判断与循环的计算程序

了解这个系列需要一定的编译原理知识作为背景知识，了解程序如何从字符串先解析成Token，而后使用语法解析器生成解析树，最后执行该解析树。

概述

lex/flex可以按照“词法文件”的定义，将文本解析成单个的Token，然后通过执行“词法文件”中定义的Action来完成一些操作，一般，flex的输出会通过函数/变量将结果传递给yacc/bison进行进一步的语法解析。为了简化，本文将仅通过独立的“词法文件”完成一些操作，以了解flex的基础使用。

这里完成的程序是一个简单的“count”程序，输入是一个文件，程序输出文件中包含的字符数、词语数、以及行数。

安装flex并编写词法文件

1. 安装lex： yum/apt-get install flex

2. 编写如下词法文档：

%{                                       //
        int characters = 0;              //    %{ ... }% 之间的部分是"Declarations"
        int words = 0;                   //    Declarations 部分声明的变量，是可以在全局使用的
        int lines = 0;                   //    例如，在该示例的main程序中，就通过extern声明的方式
%}                                       //    使用了这些变量
%%                                       //
\n      {                                //    从这里开始是Translations阶段
                ++lines;                 //    这里定了Token，以及遇到了Token之后
                ++characters;            //    应该采取/执行什么，例如这里遇到了\n字符
        }                                //    则，将lines/characters变量都加1
[ \t]+          characters += yyleng;    //
[^ \t\n]+ {                              //    注释部分的文本需要删除，程序才能正常编译 
                ++words;                 //    删除注释的vim命令：1,$s/\/\/.*$//g 
                characters += yyleng;    //
        }                                //
                                         //
%%

直接使用如上代码的话，后面就会在gcc编译的时候遇到如下错误：

$ lex zzx.l
$ gcc lex.yy.c wc.c -o wc.out
/tmp/cc1SPYm2.o：In function yylex':
lex.yy.c:(.text+0x42f)：undefined reference toyywrap'
/tmp/cc1SPYm2.o：In function input':
lex.yy.c:(.text+0xf73)：undefined reference toyywrap'
collect2: ld returned 1 exit status

如果你也遇到了这个错误，不用担心，你并不孤单，在Stackoverflow上看到解决该失败的的答案一共有150点赞（up），就知道大家都一样了（参考@Stackoverflow）。因为默认的，lex生成的词法解析程序中，在最后是需要调用的yywrap函数的（关于yywrap），如果不打算提供该函数，则可以使用lex选项 %option noyywrap 禁用该调用。那么上面的代码就需要修改为：

$ cat zzx.l 
%{
        int characters = 0;
        int words = 0;
        int lines = 0;
%}
%option noyywrap
%%
\n      {
                ++lines;
                ++characters;
        }
[ \t]+          characters += yyleng;
[^ \t\n]+ {
                ++words;
                characters += yyleng;
        }

%%

编写入口函数并调用yylex

词法文件需要使用工具flex将其编译生成一个c语言文件，然后再使用gcc将其编译成一个可执行文件。编译前，我们需要先编写一个简单的main函数. 再编写一个程序的入口函数（main），并调用yylex()就可以了。具体如下：

$ cat wc.c
#include <stdio.h>

int yylex(void);

int main(void)
{
        extern int characters, words, lines;

        yylex();
        printf("%d characters, ", characters);
        printf("%d words, ", words);
        printf("%d lines\n", lines);
        return 0;
}

这里需要注意：在程序中，我们通过调用yylex()完成了实际的词法解析过程，并获得执行结果。这是一个非常简单的示例，实际过程比这要更加复杂，在词法文件中，每一次rule解析完成后，再起action部分，通常都会有return语句结束本次yylex调用，所以会是一个反复调用yylex的过程。

编译并执行

$ lex zzx.l    
$ gcc lex.yy.c wc.c -o wc.out
$ chmod +x wc.out
$ cat s.txt
this is a input file.
this is a input file.
$ ./wc.out < zzx.l
404 characters, 36 words, 18 lines
$ ./wc.out < s.txt
44 characters, 10 words, 2 lines

好了，至此，我们就完成一个词法解析的任务，因为这个任务不涉及任何语法（yyac）解析，所以比较适合初学者学习词法解析工具lex。

补充关于Definitions

为了再略微增强该示例的，这里对上面的示例又做了一个小调整，新增一行“Definitions”，有时候为了增强可读性，会对一些expression定义一个名称，如下，将\n定义为NL：

%{                                        //
        int characters = 0;               //   %{ ... }% 之间的部分是"Declarations"
        int words = 0;                    //   Declarations 部分声明的变量，是可以在全局使用的
        int lines = 0;                    //   例如，在该示例的main程序中，就通过extern声明的方式
%}                                        //   使用了这些变量
                                          //
NL \n                                     //   这里新增了一行，这是一行 Definitions
                                          //   将\n用字母NL定义，所以下面的\n也就可以使用NL
                                          //   试想，如果表达式很复杂用这种方式，可读性会增强很多
%%                                        //
NL      {                                 //   从这里开始是Translations阶段
                ++lines;                  //   这里定了Token，以及遇到了Token之后
                ++characters;             //   应该采取/执行什么，例如这里遇到了\n字符
        }                                 //   则，将lines/characters变量都加1
[ \t]+          characters += yyleng;     //
[^ \t\n]+ {                               //   注释部分的文本需要删除，程序才能正常编译        
                ++words;                  //   删除注释的vim命令：1,$s/\/\/.*$//g 
                characters += yyleng;     //
        }                                 //
                                          //
%%           

自此，我们就了解一个词法解析文件的几个主要部分：Definitions、Declarations、rule（以及rule对应的Action）。

参考资料：

• Tutorial on using lex and yacc
• Lexical Analysis With Flex, for Flex 2.6.2
• How do Lex and YACC work internally
• yylval@bison manul

更多说明

• Flex / Lex程序通常与Yacc/Bison一起使用，flex负责词法解析，bison则负责语法解析
• flex与bison接口的函数，就是上面的调用 yylex()函数，该函数每次基于某个规则（rule）解析到一个新的Token的时候，则会执行对应的“Action”（也就是每个Token后面的代码）部分的代码。例如，上面的程序中会执行++lines或++words代码。
• 在rule action部分，我们看到使用了一个yyleng的“变量”用于获取当前被解析的原始字符串的长度。类似的“变量”有：yyleng、yytext、yyin等，完整的列表可以参考：Values Available To the User。另外，这些“变量”并不是真的变量，大部分都是一些“宏”，例如，yytext的真实定义可能是这样的：#define yytext (((struct yyguts_t*)yyscanner)->yytext_r)。了解这一点，有利于理解这些”变量”并不能在外部直接引用。
  • yyin yylex函数处理的字符串来源，默认情况是标准输入，在你的程序，例如可以定义为一个打开的文件描述符（在Posix中，一起都是文件）
  • yylength 用于记录，当前读取的Token的长度
  • yytext 用于记录当前读取的文本
• 一般的，flex的“Action部分”，会包含一个return,例如如果遇到一个整数，可能会看到类似这样的代码：return INTEGER; 这时候，yylex()遇到一个对应的字符就会返回INTEGER。
• 在实践中，则是按照如下方式实现：
  • 在 yacc/bison的语法文件中定义Token，例如整数为 INTEGER,语法为 %token INTEGER
  • 使用yacc/bison命令生成对应的头文件，头文件则会包含关于 INTEGER的预定义：#define INTEGER 257
  • 只需要在flex词法文件中包含该头文件，就可以使用这里的预定义 INTEGER了
  • 那么较为完整的代码看起来就是这样

cat cal.y
...
%token INTEGER
...

cat cal.tab.h //这是bison生成的文件
...
#define INTEGER 257
...

cat cal.l
...
[[:digit:]]+  { return INTEGER; }
...

• 我们在考虑另一个问题：在lex的rule action可以使用本地的“变量”（其实是“宏”），也会通过return语句给yyparse()中调用yylex时，返回当前Token的类型。如果一个Token是一个[:digit:]+的时候，我们除了需要知道这个Token是一个整数之外，至少yyparse()还需要知道这个是一个什么整数，具体数值是多少，当然并不是所有的token都需要，一般identifier都是需要的。而，前面的yytext都是yylex本地的“变量”。这时候，通常会使用yylval。yylval是一个由yacc/bison定义的变量（默认是int类型），用于存储词法解析需要传递给yyparse的数据，在yacc/bison的语句处理的Action阶段，可以使用变量，以获得词法解析阶段的一些值。例如，一个Token是一个整数、字符串（并非keyword）的时候，我们会将对应的值存储在yylval中。所以，yylval通常会被定义为一个联合体（union类型），用于存储不同类型的值。

关于这几个概念的更详细细致的解释可以参考最前面提到的“IBM的z/OS系统的文档中关于lex和yacc的介绍”（参考：Tutorial on using lex and yacc）。