flex&bison完成C-语言编译器前端(一)

写在前面

因为自己在学习使用flex&bison编写编译器时,困难很大,网上的资料很老很陈旧,很多示例代码都无法运行。幸而自己最终找到一份07年的博客,所以想对其整理一下。一来加深自己的理解,为学弟学妹提供一份参考资料,二来也能防止原博客丢失。

flex是lex的加强版,同样bison也是yacc的加强版,lex和yacc的语法适用于flex和bison,之后的博客内容将不区分flexlexbison和yacc。

本文所有的代码都在kali2019运行测试过,没有linux基础的读者可以安装Ubuntu系列linux,推荐ubuntu16和ubuntu18。

原博客指路

文章代码示例

初识lex

在开始之前,你需要拥有一个装有flexbison的操作系统。

Lex(Lexical Analyzar 词法分析生成器),Yacc(Yet Another Compiler Compiler编译器代码生成器)是Unix下十分重要的词法分析,语法分析的工具。经常用于语言分析,公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单,就是跳跃太大,入门参考意义并不大。本文通过循序渐进的例子,从0开始了解掌握Lex和Yacc的用法。

lex初步示例

一个简单的lex文件: example1.l

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{%
#include "stdio.h"
%}

%%

[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);

%%

在命令行下执行命令

1
2
3
4
# flex解析,会自动生成lex.yy.c文件
flex example1.l
#进行编译生成parser可执行程序
cc -o parser lex.yy.cc -ll

如果不加-ll链结选项,cc编译时会出现以下错误,后面会进一步说明。
test

创建待解析的文件file.txt:

1
2
3
4
5
6
7
title

i=1+3.9;

a3=909/6

bcd=4%9-333

通过已生成的可执行程序,进行文件解析:
test

到此lex用法会有个直观的了解:
1.定义lex描述文件
2.通过lex,flex工具解析lex.yy.c文件
3.使用cc编译lex.yy.c生成可执行程序

再来看一个比较完整的lex描述文件exsec.l:

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
45
46
47
48
49
50
51
52
53
54
55
56
%{

#include "stdio.h"

int linenum;

void showtitle();
%}

%%

title showtitle();

[\n] linenum++;

[0-9]+ printf("Int : %s\n",yytext);

[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);

[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);

[\+\-\*\/\%] printf("Op : %s\n",yytext);

. printf("Unknown : %c\n",yytext[0]);

%%

void showtitle()

{

printf("----- Lex Example -----\n");

}

int main()

{

linenum=0;

yylex(); /* 进行分析 */

printf("\nLine Count: %d\n",linenum);

return 0;

}

int yywrap()

{

return 1;

}

进行解析编译:
test
这里就没有加-ll选项,但是可以编译通过。下面开始着重整理下Lex描述文件.l。

lex描述文件的结构介绍

Lex工具是一种词法分析程序生成器,它可以根据词法规则说明书的要求来生成单词识别程序,由该程序识别出输入文本中的各个单词。一般可以分为<定义部分><规则部分><用户子程序部分>。其中规则部分是必须的,定义和用户子程序部分是任选的。

(1)定义部分

定义部分起始于%{符号,终止于%}符号,其间可以是包括include语句、声明语句在内的C语句。这部分跟普通C程序开头没什么区别。

1
2
3
4
5
6
7
%{

#include "stdio.h"

int linenum;

%}

(2) 规则部分

规则部分起始于%%符号,终止于%%符号,其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成,动作部分是由C语言语句组成,这些语句用来对所匹配的模式进行相应处理。需要注意的是,lex将识别出来的单词存放在yytext[]字符数据中,因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多行执行语句,也可以用{}括起来。

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

title showtitle();

[\n] linenum++;

[0-9]+ printf("Int : %s\n",yytext);

[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);

[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);

[\+\-\*\/\%] printf("Op : %s\n",yytext);

. printf("Unknown : %c\n",yytext[0]);

%%

A.规则部分的正则表达式

规则部分是Lex描述文件中最为复杂的一部分,下面列出一些模式部分的正则表达式字符含义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A-Z, 0-9, a-z         构成模式部分的字符和数字。
- 指定范围。例如:a-z 指从 a 到 z 之间的所有字符。
\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义,只取字符的本身。
[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C的任何一个。
^ 表示否定。
* 匹配0个或者多个上述模式。
+ 匹配1个或者多个上述模式。
? 匹配0个或1个上述模式。
$ 作为模式的最后一个字符时匹配一行的结尾。
{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。[a-z]{5} 表示长度为5的,由a-z组成的字符。此外,还可以表示预定义的变量。
. 匹配任意字符,除了 \n。
( ) 将一系列常规表达式分组。如:{Letter}({Letter}|{Digit})*
| 表达式间的逻辑或。
"一些符号" 字符的字面含义。元字符具有。如:"*" 相当于 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式,只匹配模版中"/"前面的部分。如:模式为 ABC/D 输入 ABCD,时ABC会匹配ABC/D,而D会匹配相应的模式。输入ABCE的话,ABCE就不会去匹配ABC/D。

B.规则部分的优先级

规则部分具有优先级的概念,先举个简单的例子example2.l

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

#include "stdio.h"

%}

%%

[\n] ;

A {printf("ONE\n");};

AA {printf("TWO\n");};

AAAA {printf("THREE\n");};

%%

此时,如果输入内容:

test

Lex分析词法时,是逐个字符进行读取,自上而下进行规则匹配的,读取到第一个A字符时,遍历后发现三个规则皆匹配成功,Lex会继续分析下去,读至第五个字符时,发现”AAAA”只有一个规则可用,即按行为进行处理,以此类推。可见Lex会选择最长的字符匹配规则。

如果将规则
AAAA {printf("THREE\n");};
改为
AAAAA {printf("THREE\n");};

则结果为

test

再来一个特殊的例子:

1
2
3
4
5
6
7
%%

title showtitle();

[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);

%%

并输入title,Lex解析完后发现,仍然存在两个规则,这时Lex只会选择第一个规则,下面的则被忽略的。这里就体现了Lex的顺序优先级。
把这个例子稍微改一下:

1
2
3
4
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%

Lex编译时会提示:warning, rule cannot be matched.这时处理title字符时,匹配到第一个规则后,第二个规则就无效了。再把刚才第一个例子修改下,加深下印象!
example3.l:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%{

#include "stdio.h"

%}

%%

[\n] ;
A {printf("ONE\n");}
AA {printf("TWO\n");}
AAAA {printf("THREE\n");}
AAAA {printf("Cannot be executed!");}

%%

./parser < file1.txt 显示效果是一样的,最后一项规则肯定是会忽略掉的。

test

C.规则部分的使用变量

且看下面示例example4.l:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
%{

#include "stdio.h"

int linenum;

%}

int [0-9]+

float [0-9]*\.[0-9]+

%%

{int} printf("Int : %s\n",yytext);

{float} printf("Float : %s\n",yytext);

. printf("Unknown : %c\n",yytext[0]);

%%

在%}和%%之间,加入了一些类似变量的东西,注意是没有;的,这表示int,float分别代指特定的含义,在两个%%之间,可以通过{int}{float}进行直接引用,简化模式定义。

(3) 用户子程序部分

最后一个%%后面的内容是用户子程序部分,可以包含用C语言编写的子程序,而这些子程序可以用在前面的动作中,这样就可以达到简化编程的目的。这里需要注意的是,当编译时不带-ll选项时,是必须加入main函数和yywrap(yywrap将下后面说明)。如:

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
...
%%

showtitle()

{

printf("----- Lex Example -----\n");

}

int main()

{

linenum=0;

yylex(); /* 进行Lex分析 */

printf("\nLine Count: %d\n",linenum);

return 0;

}

int yywrap()

{

return 1;

}

Lex一些的内部变量和函数

内部预定义变量:

1
2
3
4
5
yytext   char *  //当前匹配的字符串
yyleng int //当前匹配的字符串长度
yyin FILE * //lex当前的解析文件,默认为标准输出
yyout FILE * //lex解析后的输出文件,默认为标准输入
yylineno int //当前的行数信息

内部预定义宏:

1
2
3
#define ECHO fwrite(yytext, yyleng, 1, yyout)

//也是未匹配字符的默认动作

内部预定义的函数:

1
2
int yylex(void)   //调用Lex进行词法分析
int yywrap(void) //在文件(或输入)的末尾调用。如果函数的返回值是1,就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段,这样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的文件,直到所有的文件都被解析。最后,yywrap() 可以返回1来表示解析的结束。

lex和flex都是解析Lex文件的工具,用法相近,flex意为fast lexical analyzer generator,可以看成lex的升级版本。相关更多内容就需要参考flex的man手册了,十分详尽。

关于Lex的一些综述

Lex其实就是词法分析器,通过配置文件*.l,依据正则表达式逐字符去顺序解析文件,并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈,它不适合用于剖析外壳结构。而yacc增加了一个堆栈,并且能够轻易处理像括号这样的结构。Lex善长于模式匹配,如果有更多的运算要求就需要yacc了。