Flex and Bison

发表于 分类于

个人对Flex Bison的初次使用中遇到了许多的问题，亦花费了相当多的时间来浏览StackOverflow等论坛和官方手册。为了个人记忆，也为了后人少走弯路，特此记录。

Flex

Flex是一个词法分析器生成器，可以根据用户编写的源文件(.l文件)生成对应的C语言文件。

Flex格式

Flex源文件格式如下

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
--------
Prologue
--------
1. 前置代码
%{
    /*定义、声明相关*/    
}%

2. Flex声明

3. 正则定义
定义    (正则)

%%
------------
正则识别与动作
------------

{定义}  {动作}

%%

-------
后置代码
-------

Flex格式相对简单，主要由前言、动作、后置代码三个部分组成，顺序不限。

为便于讨论，后续称Flex的.l源文件为Flex.l、.c文件为Flex.c。

前言

  1. 前置代码: 用户自定义的C语言代码，将出现在Flex.c文件靠前位置(Flex自身相关的声明部分后、Flex的函数定义前)。书写时，以{}包围，以便Flex识别。
  2. flex声明：在此处通过部分语句，开启或关闭Flex的可选功能
  3. 正则定义：使用Flex规定的正则表达式，编写部分常见句型，并对其命名，便于后续使用。格式类似NAME REG。Flex的正则书写方法网上很多，在此不作赘述。

动作

动作部分相对简单，由正则句型及与之对应的动作组成。格式类似

1
2
{NAME}  {ACTION}
REG     {ACTION}

注意在使用前言中定义的NAME时，需要以{}包围。此处ACTION对应于Flex.c文件的函数yylex()中的行为。yylex()不停读取字符流，匹配，响应，再匹配，再响应，直至文件尾。用户可以在此处使用最终c文件中Flex上下文中的变量和函数来编写自己的代码。

后置代码

前言中的前置代码被迁移至Flex.c文件中Flex函数之前的位置，而后置代码则迁移至该文件的末端，其余基本一致。同样，在此处，用户可以在此处使用最终c文件中Flex上下文中的变量和函数来编写自己的代码。

进一步补充

在前面的概述中，提到了诸如Flex.c文件、Flex上下文这类的词语。对Flex不够熟悉的读者可能感到迷惑，此处给出详细解释。

Flex.c 文件

经过Flex文件的转换，.l源文件将被转换为Flex.c。

Flex.c文件包含了从Flex.l文件中的正则匹配规则与动作转换出的相关代码。其中，对外暴露的主要接口就是yylex()函数。

按照前述——yylex函数不停读取字符流，匹配，响应，再匹配，再响应，直至文件尾。这是yylex函数的一般行为，同时，前面也提及了，用户在匹配规则中，可以定义yylex函数在匹配到一个单词之后的行为，这个行为对于yylex的行为是有很大影响的。比如，改变一些变量——参考Flex上下文，又或直接Return，打断流程——参考Bison中的yylex的使用。

Flex.c的代码结构上，可以表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

----------------
Flex宏定义与声明
----------------

-----------
用户前置代码
-----------

-----------
Flex函数定义
-----------

-----------
用户后置代码
-----------

结合Flex.c的结构，就可以知道自己的代码的最终位置。进一步，按照C语言从前至后的编译顺序，也就能搞懂大部分Undefined问题了。

Flex 可选功能

Flex作为词法分析器生成器，其基本功能在于读入文件，分析出相应的token流。

但除此之外，Flex还可以在这个过程中完成一些附加操作，比如：

  1. 统计行号功能，即在分析的过程中维护一个yylineno变量，记录当前token的行号。
  2. ……

将以下格式的声明置于前言部分的Flex声明处，即可开启。

1
%option yylineno

Flex上下文

在Flex中书写代码，往往摸不着头脑。比如，在ACTION中书写对单词的响应代码，也不知道自己在哪儿，只能打印几个变量，匆匆作罢。

“要是知道自己写的代码在哪儿就好了。”——相信这是不少人的想法。在此，结合前述提及的Flex.c代码结构，说道说道编程上下文。

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

----------------
Flex宏定义与声明
/*宏类型等等*/
int yylineno;/*行号*/
char* yytext;/*当前token内容*/
----------------

-----------
用户前置代码
-----------

-----------
Flex函数定义

/*yylex外函数*/


yylex(){

    yylineno的更新代码
    yytext的更新代码
    Switch(Reg){
    case1:
        ACTION1
        break;
    case1：
        ACTION2
        break;
    ……
    }
}；
-----------

-----------
用户后置代码
-----------

上述Flex.c结构更为详尽地解析了用户编程的上下文。可以看出，用户定义的ACTION，将在yylex中被调用，同时，yylex还将维护之前定义的yytext与yylineno等变量。这些变量以及用户在前置代码中定义的变量，在ACTION中都是可以使用的——这也就意味着用户可以在ACTION中改变这些参数，这可能极大地影响yylex的行为，故对Flex内置变量的使用要小心，而对于自定义变量，就可以随意使用了。

PS:关于yytext，虽然yytext保留的是指向当前token的字符串指针，但在实际操作时，其内容将串行排列，从而第一个token的指向内容在解析到后期时，已然成了一整个文件。

1
2
3
4
开始时              后来
|最初指针           |最初指针    |现在的指针  
a \0                a b c d e f g \0
最初指针打印结果“a”  最初指针打印结果“abcdefg”

所以，若是想打印对应内容，应当在ACTION中，即词法分析该token时就进行深拷贝。

其他

yywrap(0)

在yylex执行时需要yywrap函数辅助。在读完一份文件后，yywarp函数负责返回int值来表示任务是否结束（1 结束 0 未结束）。若结束，则停止程序；否则，继续读取另一份文件。这个函数需要用户自己定义。

Bison

Bison是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。

Bison格式

Bison源文件格式如下

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
--------
prologue
--------

1. 前置代码
%{
        
}%

2. Bison声明

3. 语法相关声明


%%

-----------
生成式与动作
-----------

生成式  {ACTION}


%%

--------
后置代码
--------

Bison源文件格式结构为与Flex类似的三段式，由前言、生成式与动作、后置代码构成。
为了后续讨论方便，将Bison的.y文件称为Bison.y；Bison生成的.c文件称为Bison.c文件，而.h文件称为Bison.h。

前言

Bison中的前言亦由三个部分组成：

  1. 前置代码：用户自定义代码，出现在Bison.c文件的开头
  2. Bison声明：用来开启一些可选功能、定义符号（非终结符/终结符）类型
  3. 语法相关声明：用于定义生成式移入/规约时解决冲突时使用的计算优先级——优先级按规则从上至下递减，声明包括%left %right %nunonassoc三种，对应左结合、右结合、不结合。

生成式与动作

生成式——动作的格式如下：

1
2
3
4
5
6

A:B         {ACTION}
 |C         {ACTION}
 |D         {ACTION}
 |/*empty*/ {ACTION}
 ;

Bison.c文件中的yyparse()，对输入的token流执行LALR(1)语法解析，即移入规约分析。

当yyparse执行对应于规则的规约时,将附带执行ACTION内容，同样ACTION内动作的编写也需考虑Bison上下文

这一部分的规则还定义了错误分析功能，待后续分析。

后置代码

Bison.y后置代码同Flex.l的后置代码被移入Flex.c末尾一致，被移动到Bison.c末尾。

进一步补充

此处对上述简要提及但未详述的内容做出补充。

Bison.c文件与Bison上下文

Bison.y 文件经Bison程序处理后生成 Bison.c 文件。其中，最为主要的对外暴露接口为yyparse()用于对文件（没错，不是token流，而是文件。这部分在后续联合编译中将涉及）进行语法解析。

其结构如下

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
Bison.c

---------------------
Bison版本信息与运行设置
---------------------

-----------
用户前置代码
-----------

--------------------
Bison宏与状态转移矩阵
--------------------

-----------
Bison内部变量、函数与运行设置

yylval定义
yylloc定义
……

int yyparse(){

    yylval更新
    yylloc更新
    ……

    yylex()使用
    Switch(Reduction){
    case1:
        ACTION
        break;
    case2:
        ACTION
        break;
    ……
}
}
-----------

-----------
用户后置代码
-----------

认识清楚自身代码的位置、代码上下文，有利于用户在ACTION、前后置代码中的编程。

值得一提的是yylval与yylloc两个变量的定义，yylval用于记录目前分析的词素的值、yylloc则记录位置，而语法栈中不同符号的信息会被另外保存，故在ACTION是对yylval与yylloc进行访问往往得不到想要的结果，而是应该使用@$ @1 ……@n访问位置信息；$$ $1 …… $n访问词素值信息。

可选功能

上面提到的yylloc在默认状况下是不开启的，此时使用将导致无定义——YYLTYPE未定义。需要使用一定的声明才能启动这个选项，即将下述代码置于Bison声明区。

1
%locations

还存在许多其他可选功能，如%union{}重新定义yylval的类型（默认为char*）。

错误分析功能

Bison的错误分析基于恐慌模式，即在发生错误——读入符号后无对应动作的情况下：

  1. 生成一个error token
  2. 然后不停弹出栈顶符号与对应状态，直至按照给定的生成式中有一个能够移入error的状况为止,移入error
  3. 此后，仅接受该生成式中能够跟在error token后的符号,直至完成该生成式
  4. 同时，在成功移入三个符号后，解除error

举例：

1
2
3
4
5
6
7
8

Exp:……
    |Exp LB Exp RB
    |……
    |Exp LB Exp error RB
    ；
按照规则，对语句中“a[3,5]”将在读入“,”时引发错误。
Bison将弹出","，按照最后个生成式移入"error"，丢弃“5”，读入“]”，并在再读入两个符号后结束错误模式。（亦可用宏yyerrok立即结束）；

故错误分析往往是对给定例子进行，并在较低层给出生成式。在高层定义的生成式，接受绝大多数错误，难以识别具体错误类型。

联合编译

Flex与Bison往往是组合工作的，为此，我们需要理清楚期间的关系。

  • Flex从文件读入字符流，匹配token，响应，再匹配，直至结束。

  • Bison从文件读入字符流，分析语法，自底向上规约出初始符号。

可以看出，二者间的工作有一定的重复性，所以通过联合编译，可以减少重复劳作。

yylex

在Bison的工作中，其实也需要获取token，为语法分析作准备。Bison在Bison.h文件中为Bison.y中出现的所有终结符——以%token声明，与所有非终结符——生成式左侧的所有符号，定义了一系列宏，用以区分词素类型。对于非终结符，往往由终结符规约生成，而终结符呢？则依靠Bison中使用的yylex函数给出，这个yylex其实是需要用户自己实现的。

注意：Bison.yylex函数的功能为匹配文件中下一个token（Bison中是一遍匹配token，一遍语法分析的），返回其类型；而Flex中的yylex则不停匹配，并不返回。

为了复用Flex的yylex，我们需要改造Flex.yylex的行为，以适配Bison需要。

  1. Flex.l文件前置代码#include Bison.h文件，获取Bison中对不同类型Token的编码
  2. 在ACTION中改变yylex函数的走向，返回token类型，然后return结束单次调用。

位置信息

Bison在开启%locations可选功能后将提供yylloc变量，但由于高层词素信息往往来自底层的位置信息的组合，故在yylex中亦需要手动填写token的位置信息。该部分可由以下代码实现。

1
2
3
4
5
6
7
#define YY_USER_ACTION \
    yylloc.first_line = yylloc.last_line = yylineno;\
    yylloc.first_column = yycolumn;\
    yylloc.last_column = yycolumn + yyleng - 1;\
    yycolumn += yyleng;

\n|\r       {yycolumn=1;}

其中YY_USER_ACTION是Flex.c中匹配成功后将进行的动作。

这样一来，在Flex.c中修改Bison.c上下文中的变量yylloc即可提供对应的位置信息。

同理，token的词素信息也来自ACTION中的赋值

词素信息

与位置信息类型，Bison.c中高层词素的语义来自低层语义的组合，而底层token的语义就得靠yylex来实现了。

我们可以在ACTION中使用yylval来为token赋值。

其他

有时，我们在语法解析时还希望从Flex中获取一些别的相关信息，如规约错误时的位置什么的。

这时可以依据C语言的extern关键字，将Flex中的变量对外开放访问。

1
2
extern int yylineno;
extern int yytext;

上述语句就允许Bison.c（包括用户代码）直接访问Flex中的变量。

依赖与编译

我们再整理一次文件的依赖关系

1
2
3
4
5

Flex.c include Bison.h for token编号 yylloc yylval do 解析token编号、给token赋值、给token位置信息。

Bison.c include Flex.c for yylex定义 yylineno等成分 do yyparse() for US

故可编写如下makefile

1
2
3
4
5
6
7
8
9
10
11
parser: bison.c flex.c
	gcc -o parser bison.c

bison.c: bison.y
	bison -o bison.c -dvt bison.y
bison.h: bison.y
	bison -o bison.c -dvt bison.y

flex.c: flex.l bison.h
	flex -o flex.c flex.l