逍遥游

编译原理:利用lex,写一个词法分析器

原文:写编译器:学习GNU Flex,写一个词法分析器

什么是Flex

“Flex is a tool for generating scanners: programs which recognized lexical patterns in text. flex reads the given input files, or its standard input if no file names are given, for a description of a scanner to generate. The description is in the form of pairs of regular expressions and C code, called rules. flex generates as output a C source file, lex.yy.c’, which defines a routine yylex()’. This file is compiled and linked with the -lfl’ library to produce an executable. When the executable is run, it analyzes its input for occurrences of the regular expressions. Whenever it finds one, it executes the corresponding C code.” — Vern Paxson

安装Flex

1
apt-get install flex

入门

flex通过读取一个*.l或者*.lex文件里的单词匹配规则生成C语言的实现代码。
一个*.l的文件里的结构大概如下,用%%分隔开来。

1
2
3
4
5
/* Definition */
%%
/* Rules */
%%
/* C Code */

用flex写一个查找读取文本所有整数的程序。

正则表达式里,[0-9]+表示正整数,[+-]?[0-9]+表示整数。定义下面的一个规则:

1
2
3
4
5
6
7
8
9
10
11
12
13
%%
[+-]?[0-9]+ { printf("%s\n", yytext); } /* Print integers */
\n {} /* newline */
. {} /* For others, do nothing */
%%
void main(){
yylex();
}
int yywrap(){
return 1;
}

保存为find.l,使用flex和gcc编译。

1
2
flex find.l
gcc  lex.yy.c

编写一文本(test.in)作为输入

样例如下:

1
2
3
test 12345 -1
test kkk lll abc123 555
+111 < 456

运行结果,

1
./a.out > test.in

输出

1
2
3
4
5
6
12345
-1
123
555
+111
456

进阶

统计一段C语言代码里符合要求的标识符名称。
一个符号要求的标识符名称,满足以下几点:
1、标识符只能包含数字,字母,下划线
2、不能以数字打头
3、不能是C语言关键字

因为关键字太多,不想写,这里只考虑(unsigned, int, return)

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
%{
/* 在这里面加入C代码 */
int count = 0;
%}
/* definition */
digit    [0-9]
number   {digit}+
letter   [A-Za-z]
identifier   (_|{letter})({letter}|{digit}|_)*
%%
[ \t]+ {}
\n {} /* 忽略换行 */
{number} {} /* number */
unsigned|int|return {} /* 关键字 */
{number}({letter}|{digit}|_)* {} /* 不能以数字开头 */
{identifier} { ++count; printf("Good identifier: %s\n", yytext); }
. {}
%%
int yywrap(){return 1;}
void main(){
yylex();
printf("Total number proper identifier is %d\n", count);
}

测试输入find.l

1
2
3
4
unsigned int rand_code(unsigned int* rand_seed, unsigned int generator)
{
return *rand_seed = ((*_rand_seed * 234generator + 1)>>16)&65535;
}

运行结果:

1
./a.out < test.in
1
2
3
4
5
6
Good identifier: rand_code
Good identifier: rand_seed
Good identifier: generator
Good identifier: rand_seed
Good identifier: _rand_seed
Total number proper identifier is 5

后面不copy了。。。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com