编译器（汇编器）开发工具Flex和Bison的使用方法之Flex

        编译器和汇编器在工作过程中，往往完成如下的任务：

       (1) 读取源代码并且获得程序的结构描述；

       (2) 分析程序结构，并且生成相应的目标代码。

       Flex和Bison就是为可以帮助完成以上任务。Flex将源代码文件分解为各种词汇(token)，Bison找到这些词汇的组成方式。下面通过例子讲述它们的使用方法，在Cygwin环境下调试。        

1. Flex

      Flex是一个生成扫描器(scanner)的工具，生成的扫描器能够识别文本中的词法模式(lexical pattern)。Flex接受文本格式的Flex文件（扩展名可以为.l，.flx、.lex或者.flex）作为输入，生成一个c源文件：lex.yy.c，其中定义了一个函数yylex()，该函数就是扫描器。它根据Flex文件中定义的模式(pattern)对输入的文本串进行分析，然后执行对应的动作(Action)，该模式和对应的动作叫做规则。例如，可以定义一个模式识别自定义标识符，并在对应的动作中规定，如果遇到自定义标识符，将该标识符写入某个数组。另外，lex.yy.c可以编译后执行，也可以被其他源文件中的函数调用。

    下面看一个简单的例子（example1.lex）：

int num_lines = 0, num_chars = 0;

%option noyywrap

%%

\n  num_lines; num_chars;
. num_chars;
%%
int main()
{
yylex();
printf( '# of lines = %d, # of chars = %d\n',num_lines, num_chars );

return 0;
}

在cygwin下，键入如下命令：

$flex example1.lex     //该命令生成lex.yy.c文件

$gcc -g -Wall -o scan.exe lex.yy.c  //该命令生成可执行文件scan.exe

$./scan 回车 

键入几行字符，以Ctrl D结束。扫描程序scan.exe扫描键入的字符串，识别的根据模式执行动作，不识别的直接输出。本例中遇到换行符'\n'变量num_lines和num_chars加1，遇到字符num_chars加1，最后输出结果：

# of lines = 2, # of chars = 15

如果Flex文件中没有定义main函数，gcc编译时，需用参数-lfl链接fl库（gcc -g -Wall -lfl -o scan.exe lex.yy.c），利用其中的main函数。

1.1 Flex文件的结构    

    Flex文件是词法规范定义文件，给出了单词的构成规则，以及在某个规则下应该执行的动作。它由定义段、规则段和用户代码段三个部分构成，中间用%%隔开。

定义段(definitions section)

%%

规则段(rulessection)

%%

用户代码段(user codesection)

1.1.1 定义段

    定义段包括一些简单名字定义和开始条件的声明。段中的定义不能有缩进。缩进的文本或用'%{'和'%}'括起来的文本会原封不动地拷贝到输出文件lex.yy.c中。'%{'和'%}'也必须在单独的行，并且不能缩进。另外，不缩进的注释（用'/*'和'*/'括起来）也拷贝到lex.yy.c中。

    1.简单名字定义

    格式为：name definition

    其中，name(名字)是一个以字母或'_'开始的word，后面可以是0个或多个字母、数字、'_'或'-'。definition(定义)从name后第一个非空白字符开始，一直到行末。对name的definition之后可以通过{name}引用。例如：

    Digit   [0-9]

    ID    [a-z][a-z0-9]*

    以上定义了两个name Digit和ID。Digit定义为一个正则表达式(regular expression)匹配一个字符，ID定义为一个正则表达式，第一个字符为a-z之间的字符，后面跟着零个或多个a-z之间的字符或0-9之间的数字。如果后面有个引用{DIGIT} '.'{DIGIT}*，等价于([0-9]) '.'([0-9])*。

    2.开始条件声明

    详见1.3。  

1.1.2 规则段

    规则段包括一系列如下所示的规则(rules)：

    pattern action

    1. Pattern(模式)

    pattern使用如下所示的一个正则表达式的扩展集表示。 

x          符合字符串'x'
.          除了换行以外的任何字符
[xyz]      一个字符类，在这个例子中，输入可以是'x'、'y'、'z'中的一个
[abj-oZ]   一个带范围的字符类，输入可以是'a', 'b', 从'j'到'o'还有'Z'中的字符
[^A-Z]     一个取反的字符类，任何字母除了大写字母。 
[^A-Z\n]   任何字符除了大写字母和换行符
r*         零个或更多r，r可以是任意正则表达式
r         一个或更多r
r?         零个或最多一个r
r{2,5}     任何2到5个r
r{2,}      2个或更多r
r{4}       正好4个r
{name}     对name的展开
'[xyz]\'foo'
           符合正则表达式 [xyz]'foo 的字符串
\X         如果X是一个'a', 'b', 'f', 'n', 'r', 't', 或者'v',同标准C中\x的处理。否则，就是X，用于对某些符号转义
\0         NUL字符，ASCII码值为0

\123       ASCII码为八进制123的char型

\x2a             ASCII码为十六进制0x2a的char型
(r)              符合一个r，括号是用来越过优先级的
rs                   正则表达式r，紧跟着一个正则表达式s
r|s                  要么是正则表达式r，要么是正则表达式s

r/s     匹配模式r，但是要求其后紧跟着模式s。当需要判断本次匹配是否为“最长匹配（longest match）时，模式s匹配的文本也会被包括进来，但完成判断后开始执行对应的动作（action）之前，这些与模式s相配的文本会被返还给输入。所以动作（action）只能看到模式r匹配到的文本。这种模式类型叫做尾部上下文（trailing context）。（有些‘r/s’组合是flex不能识别的；请参看后面deficiencies/bugs一节中的dangerous trailing context的内容。）
^r                   一个r，但是必须是在一行的开始
r$                   一个r，但是必须是在行末
<s>r               一个r，但是之前字符串必须符合条件s
<s1,s2,s3>r  同上，但是必须之前字符串符合s1、s2、s3中的一个
<*>r               不考虑开始字符串类型，只符合r
<<EOF>>     文件末尾
<s1,s2><<EOF>>       前面符合s1或者s2的文件末尾

         除了以上正则表达式外，还有一些字符类表达式，它们括在分界符'[:'和':]'之间，使用时必须再用[]括起来。它们是：

   [:alnum:] [:alpha:] [:blank:]
  [:cntrl:] [:digit:] [:graph:]
  [:lower:] [:print:] [:punct:]
  [:space:] [:upper:] [:xdigit:]

        每一个表达式都指示了一个字符分类，而且其名称与标准C函数isXXXX的名字对应。例如，[:alnum:]就指示了那些经由函数isalnum()检查后返回true的字符，也就是任何的字母或者数字。注意，有些系统上没有给出C函数isblank()的定义，所以flex自己定义了[:blank:]为一个空格或者一个tab。

       下面所举的几个例子，都是等价的：

       [[:alnum:]] [[:alpha:][:digit:]] [[:alpha:]0-9][a-zA-Z0-9]

       如果扫描器是大小写不敏感的（执行flex命令时用了-i选项），则 [:upper:]和[:lower:]同[:alpha:]是等价的。

       2. 输入的文本如何匹配模式

       当生成的扫描器运行时，它分析输入的文本，寻找匹配规则段中定义的pattern。如果有多个pattern匹配，选择匹配最长字符串的pattern；如果有两个或多个相同长度的匹配，选择flex文件中最先列出的pattern。输入文本中能够匹配某个pattern的字符串叫做一个token。一旦匹配确定，全局字符指针yytext会指向这个token，可以通过该指针引用它，这个token的长度也可通过全局整型变量yyleng读取。同时，该pattern对应的action(动作)会执行，然后，剩余的输入文本会继续被分析匹配。如果没有匹配的pattern，会执行缺省的规则：剩余输入文本中的下一个字符被认为已经匹配，然后拷贝到标准输出中。因此，如果没有定义规则，输入文本会原样不动拷贝到标准输出中。

        这里提到一个非常重要的全局变量yytext，它可以定义为字符指针或字符数组。默认是指针型的。可以通过某种方式修改为数组型，这里不多说了。

       3. Action(动作)

        action(动作)跟在pattern的后面，可以是任意的C语言语句。一行中，pattern以第一个非转义的空白符作为结束标识，剩余部分就是action了。action有如下规则：

        (1) 如果某个pattern后的action为空，匹配的token直接舍弃。例如，如果只有一个pattern'zap me'，而后面action为空，会拷贝出zap me之外的字符到输出文件中。

        (2) 如果action中包括'{'，则必有一个对应的'}'，中间全部都是pattern对应的action。也可用'%{'和'%}'括起action中语句。

        (3) 如果一个action中只有一个'|'，表示执行的action同下一规则。

        (4) action中可包含return语句在内的任意c代码。如果有return语句，会返回一个值给yylex()。每次yylex()被调用，它会继续处理上一次没处理的token，直到文件末尾或遇到return。

        (5) action中可以包含以下特殊命令：

• ECHO： 拷贝yytext到扫描器的输出
• BEGIN：跟在开始条件后，将扫描器放在对应的开始条件中
• REJECT：指示扫描器继续匹配第二好的规则
• yymore()：告诉扫描器下次匹配到一个规则时，对应的token加到yytext上。
• yyless()：
• unput(c)：
• input()：
• YY_FLUSH_BUFFER：
• yyterminate()：

1.1.3 用户代码段

        该段中的代码都被原样拷贝到lex.yy.c中。可以定义一些辅助函数或代码，供扫描器yylex()调用，或者调用扫描器（一般来说就是main()了）。这一部分是可选的。如果没有的话，Flex文件中第二个%%是可以省略的。

1.2 扫描器的生成

        前面提到，flex的输出是lex.yy.c，它包含扫描例程yylex()、一些用来存放匹配的token的table和一些附加的例程和宏。缺省情况下，yylex()声明如下：

        int yylex()
      {
      ... various definitions and the actions in here ...
      }

        如果要修改扫描例程的名字，可利用'YY_DECL'宏。例如，可以用#define YY_DECL float lexscan( a, b ) float a, b;将扫描例程名字定义为lexscan，返回值为float型，并有两个float型参数。

        yylex()被调用后，它从输入文件指针yyin(缺省情况下式stdin)扫描tokens，直到遇到EOF(这是return 0)或action执行了一个return语句。如果扫描器遇到EOF，接下来的调用时未定义的，除非yyin指向一个新的输入文件，或者调用yyrestart()。yyrestart()需要一个文件指针作为参数（如果该指针为nil，则必须设置YY_INPUT从一个源而不是yyin扫描），并使yyin指向那个文件。如果扫描器因为在action遇到return结束，可以重新从结束的地方开始扫描。

        缺省情况下，为了提高效率，扫描器通过yyin一次读一个数据块而不是用getc()读一个个字符。如何读可以通过YY_INPUT宏控制。YY_INPUT的调用方法是'YY_INPUT(buf,result,max_size)'。该宏是最多将max_size个字符放在字符数据缓冲区，返回一个整型变量，其值要么是读入的字符数，要么是常量YY_NULL(Unix下是0)指示EOF。YY_INPUT缺省下从yyin读入数据。下面是YY_INPUT的一个定义实例(在flex文件的定义段)：

%{ #define YY_INPUT(buf,result,max_size) { int c = getchar(); \ 定义为每次读入一个字符 result = (c == EOF) ? YY_NULL : (buf[0] = c, 1); } %}

        当扫描器从YY_INPUT收到EOF，它会检查yywrap()函数。如果该函数返回false(即0)，则假定该函数已经执行并设置了yyin指向另一个输入文件，扫描继续进行；如果该函数返回true(非0)，扫描器终止，返回0给它的调用者。无论哪种情况，开始条件保持不变，没有变回INITIAL。

        如果没有提供自己的yywrap()，则要么使用%option noyywrap(相当于返回1)，要么使用-lfl链接选项获取例程的缺省版本，该版本下总是return 1。

        扫描器将ECHO输出写到yyout中(缺省是stdout)，可以通过设置yyout为某个文件指针重新定义。

        如下例所示，扫描器扫描a.txt文件，并将ECHO输出和不能识别的内容写到b.txt文件中。

int main(){
yyin=fopen('a.txt','r');
yyout = fopen('b.txt', 'w');
yylex();
fclose(yyin);
fclose(yyout);
return 0;
}

1.3 开始条件

        flex提供了机制有条件地激活规则。如果规则的pattern有前缀'<sc>'，表示扫描器在名为'sc'的开始条件下该规则才是活动的。例如，<STRING>[^']*下，pattern [^']*只有在STRING条件下是active的。

        开始条件在定义段声明。该行必须不能缩进，并使用%s或%x开始，跟着一个名字列表。%s表示inclusive(包含的)开始条件，%x表示exclusive(排它的)开始条件。开始条件使用BEGIN动作激活。直到下一个BEGIN动作执行，给定开始条件的规则才被激活，其他开始条件变得inactive。如果开始条件是inclusive，没有开始条件的规则都是active的；如果是exclusive的，只有符合开始条件的规则才是active的。如果flex文件中定义了一系列的依赖相同exclusive开始条件的规则，相当于描述了一个独立于其他规则的扫描器。下面通过例子说明inclusive和exclusive的区别。

%s example

 %%
 <example>foo  do_something();
bar  something_else();
相当于
 %x example
 %%
<example>foo do_something();
 <INITIAL,example>bar  something_else();

第二个例子中，如果没有<INITIAL,example>修饰，bar模式在开始条件满足时将不是active的；如果仅用<example>修饰，则只在条件满足时是active的。但第一个例子中bar是一直active的，因为条件是inclusive。

另外，<*>匹配所有的开始条件。所以，上例还可以写为：

%x example
 %%
<example>foo do_something();
 <*>bar  something_else();

         BEGIN(0)返回原始状态，这时只有无开始条件的规则是活动的。这个状态也被叫做开始条件“INITIAL”，所以BEGIN(INITIAL)等价于BEGIN(0)。BEGIN动作也可以在规则段的开始被指定为缩进代码。如下例所示，当yylex()被调用，并且enter_special为真，扫描器会进入'SPECIAL'开始条件。

int enter_special; %x SPECIAL %% if ( enter_special ) BEGIN(SPECIAL); <SPECIAL>blahblahblah ...more rules follow...

        为了阐明开始条件的用法，下面给出一个例子。扫描器对像'123.456'这样的字符有两种不同的解释。缺省情况下它被当做3个token，整数123、一个字符'.'和一个整数456。但如果它在的行中前面有字符串'expect-floats'，它会被识别为单个token，浮点数123.456。

%{ #include <math.h> %} %s expect %% expect-floats BEGIN(expect); <expect>[0-9] '.'[0-9] { printf( 'found a float, = %f\n',atof( yytext ) ); } <expect>\n { /* that's the end of the line, so we need another 'expect-number' before we'll recognize any more numbers */ BEGIN(INITIAL); } [0-9] { printf( 'found an integer, = %d\n',atoi( yytext ) ); } '.' printf( 'found a dot\n' );

        下面这个扫描器识别并舍弃C语言的注释，并保留当前的输入行。

%x comment %% int line_num = 1; '/*' BEGIN(comment); <comment>[^*\n]* /* eat anything that's not a '*' */ <comment>'*' [^*/\n]* /* eat up '*'s not followed by '/'s */ <comment>\n line_num; <comment>'*' '/' BEGIN(INITIAL);

        开始条件名字是整数值，可以当做整数值存储。因此，以上的例子可以扩展如下：

%x comment foo %% int line_num = 1; int comment_caller; '/*' { comment_caller = INITIAL; BEGIN(comment); } ... <foo>'/*' { comment_caller = foo; BEGIN(comment); } <comment>[^*\n]* /* eat anything that's not a '*' */ <comment>'*' [^*/\n]* /* eat up '*'s not followed by '/'s */ <comment>\n line_num; <comment>'*' '/' BEGIN(comment_caller);

        而且，当前的开始状态可以通过整型值的YY_START宏访问。例如，上述的对comment_caller的赋值可以写为：comment_caller = YY_START。Flex还为YY_START提供了一个别名：YYSTATE。

        如果多个pattern使用相同的开始条件，可以用如下方式描述：

<ESC>{ '\\n' return '\n'; '\\r' return '\r'; '\\f' return '\f'; '\\0' return '\0'; }

1.4 文件尾规则

          特殊规则'<<EOF>>'指示当遇到end-of-file并且yywrap()返回非零值时该执行的action。action必须通过做下面四件事情之一结束。

• 为yyin分配一个新的文件指针
• 执行一个返回语句
• 执行yyterminate()动作
• 用yy_switch_to_buffer()转向一个新的缓冲区

1.5 用户可用的values

        下面给出规则段中用户可用的values。

• char *yytext。指向当前的token文本。可以被修改，但不能加入字符，即在后面append字符。如果定义段中使用了 %array选项，则定义为char  yytext[YYLMAX]，YYLMAX是一个缺省值为8KB的宏，可以在定义段中重新设置大小。   
• int yyleng。存储当前token的长度。
• FILE  *yyin。缺省情况下flex从这里读取要分析的文本。它可以被重新定义，但只能在扫描开始前或遇到EOF后。在扫描过程中修改它会引起预料不到的结果，因为flex缓存输入。但在中间可以使用yyrestart()。一点扫描器遇到EOF，可以为yyin分配新的输入文件，并继续扫描。
• void  yyrestart( FILE *new_file ) 。在扫描中间修改要扫描的文件。
• FILE  *yyout。ECHO操作的输出文件。
• YY_CURRENT_BUFFER。返回一个YY_BUFFER_STATE句柄给当前缓冲区。
• YY_START。返回一个对应当前开始条件的整数值。可以接下来用BEGIN重新返回到该开始条件。  

参考资料

1. The flex manual page. http://dinosaur.compilertools.net/flex/manpage.html

2. Bison-Flex 笔记. http://www.cppblog.com/woaidongmao/archive/2008/11/23/67635.html

3. 基于MSYS的 Flex & Bison （编译器开发工具）使用教程. https://code.google.com/p/msys-cn/wiki/ChapterFour