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

标签: 我的代码 我的分享 | 发表时间:2011-10-24 14:35 | 作者:Xiaoxia zffl
出处:http://xiaoxia.org

以下内容仅为个人学习笔记,非正规教程,难免有疏漏之处,请指出!

目标要分析词法的对象是一种叫TINY+的计算机语言。下面是一个Example,

char str;
int x, fact;
str:= 'sample program in TINY+ language- computes factorial';
read x;
if x>0 and x<100 then {don’t compute if x<=0}
    fact:=1;
    while x>0 do
        fact:=fact*x;
        x:=x-1
    end;
    write fact
end

什么是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

apt-get install flex

入门

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

/* Definition */
%%
/* Rules */
%%
/* C Code */

用flex写一个查找读取文本所有整数的程序。
正则表达式里,[0-9]+表示正整数,[+-]?[0-9]+表示整数。定义下面的一个规则:

%%
[+-]?[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编译。

# flex find.l
# gcc lex.yy.c

编写一文本作输入样例如下,

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

运行结果,

root@xiaoxia-pc:~/study/Experiment/lex# ./a.out < test.in
12345
-1
123
555
+111
456

进阶

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

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

%{
/* 在这里面加入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

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

运行结果:

root@xiaoxia-pc:~/study/Experiment/lex# ./a.out < test.in
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
root@xiaoxia-pc:~/study/Experiment/lex#

最后

现在要对下面的代码进行词法分析,

char str;
int x, fact;
str:= 'sample program in TINY+ language- computes factorial';
read x;
if x>0 and x<100 then {don’t compute if x<=0}
    fact:=1;
    while x>0 do
        fact:=fact*x;
        x:=x-1
    end;
    write fact
end

这个是我的编译原理作业。交作业那晚才知道要做,自己从头写一个词法分析器就没那么多时间了,于是找flex帮忙。

任务要求:

1 The input of the scanner is a source code file and the output of the scanner is a stream of tokens.

2 Your scanner should go for longest possible match i.e. a string ‘:=’ is to be identified as ‘ass-symbol’ and not as ‘:’ and ‘=’.

3 Token is represented as (Kind, Value). We use the following symbols to denote different kinds of tokens
KEY denotes reserved words
SYM denotes special symbols
ID denotes identifiers
NUM denotes numeric constants
STR denotes string constants

4 Check lexical errors: giving meaning error messages and the lines where errors occur. The kinds of lexical errors are:
Illegal character, that is, scanner may recognize a character that is not in the alphabet of TINY+, such as $ is an illegal character
The right bracket of a STRING is lost, such as ' scanner
The right delimiter of a comment is lost, such as: {this is an example

flex文件:

/*
 *         File: tiny+.l
 *         Author: Xiaoxia([email protected])
 *         Usage:  lex tiny+.l
 *                 gcc lex.yy.c
 *                 ./a.out [testfile]
 */
%option yylineno
%%

if|then|else|end|repeat|until|read|write|or|and|int|bool|char|while|do {
    printf("Line %d: (KEY, %s)\n", yylineno, yytext); }  /* keyword */
":="|"="|"<"|"+"|"-"|"/"|"("|"*"|")"|";"|"<="|">="|">"|"," {
    printf("Line %d: (SYM, %s)\n", yylineno, yytext); }              /* symbol */
'[^'\n]*'       { printf("Line %d: (STR, %s)\n", yylineno, yytext); }       /* string */
"{"[^}]*"}"     {}                                                          /* comment */
[0-9]+          { printf("Line %d: (NUM, %s)\n", yylineno, yytext); }       /* number */
[A-Za-z]([A-Za-z]|[0-9])*    { printf("Line %d: (ID, %s)\n", yylineno, yytext); } /* identifier */
[ \t]+          {}                                                  /* whiltespace */
\n              {}                                                  /* newline */
.               { if(*yytext == '{' || *yytext == '\'')
                    printf("Line %d: missing the right part of %s\n", yylineno, yytext);
                  else
                    printf("Line %d: illegal character %s\n", yylineno, yytext);
                  yyterminate();
                }                                                           /* others */
%%

int yywrap() {
    return 1;
}

void main(int argc, char** argv) {
    if(argc > 1)
        yyin = fopen(argv[1], "r");
    else
        yyin = stdin;
    yylex();
}

测试输入如下的Tiny+代码。

{this is an example}
int A,B;
bool C1, C2, C3;
char D;
D:= 'scanner;
while A<=B do
A:=A*2
end

运行结果,

相关 [编译器 学习 gnu] 推荐:

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

- zffl - Xiaoxia[PG]
以下内容仅为个人学习笔记,非正规教程,难免有疏漏之处,请指出. 目标要分析词法的对象是一种叫TINY+的计算机语言. char str; int x, fact; str:= 'sample program in TINY+ language- computes factorial'; read x; if x>0 and x<100 then {don’t compute if x<=0}.

GNU/Linux 中到底有多 GNU ?

- walker - LinuxTOY
按照 Free Software Foundation 的说法,Linux 的全称应该是 GNU/Linux. 那么一个常见的 Linux 发行版究竟有多 GNU 呢. Pedro Côrte-Real 在他的博客中发表了一份以代码行为单位对于 Ubuntu 11.04 中 main 仓库包含软件 GNU 比例(仅限由 Ubuntu 打包的部分,不包括从 Debian 继承的)的分析,参见下图:.

GNU Mediagoblin Project启动

- aviot - Solidot
自由的图片共享项目GNU Mediagoblin于本月初正式启动,旨在解决现有图片共享服务如Flickr、DeviantArt、Picasa和Facebook没有很好解决的问题:诸如隐私、数据所有权,可靠性和软件自由. GNU Mediagoblin一开始是针对照片/艺术图,未来将扩大到所有媒体. GNU Mediagoblin的设想很简单:它没有采用需要注册的中心化服务,而是允许任何人搭建一个实例,然后在朋友之间共享媒体.

生日快乐,GNU!(1983~)

- 欧剃 - 笨兔兔
1983年的9月27日,Richard Stallman 公开发布惊天动地的《GNU宣言》. RMS 的目标,在于创建一套完全自由的操作系统. 自1983《GNU 宣言》发布以来,取得了巨大成绩:. Linux 目前运行在世界82%左右的超级计算机平台上,支持耗费$100亿的亚原子大型强子对撞机研究.

GNU黑客大会2011

- Tairan Wang - Solidot
Shawn the R0ck 写道 "2011年8月25日至28日,GNU各大社区的黑客在巴黎召开了GNU的年度会议GHM(GNU Hackers Meeting) 2011,来自emacs、gcc、gdb、GNU/Hurd、debian、GNU R等重要GNU自由软件项目的开发者都参与了此次会议.

了解 GNU GPL/GNU LGPL/BSD/MIT/Apache协议

- aoao - IFLONELY
越来越多的开发者与设计者希望将自己的产品开源,以便其他人可以在他们的代码基础上做更多事,开源社区也因此充满生机. 在我们所能想到的应用领域,都有开源软件存在(象 WordPress,Drupal 这些开源CMS). 然而很多人对开源许可并不了解,本文介绍开源领域常用的几种许可协议以及它们之间的区别.

为什么每个程序员都应该学习代码编译器知识

- - 外刊IT评论
所有优秀的计算机科学学院都提供了编译器课程,但是相对比较少的学校把它作为本科课程的必修部分. 这篇文章回答了这个问题:为什么需要学习编译器知识. 我写这篇文章的其中一个原因是,尽管我在读本科时很喜欢编译器课程,但是我几乎看不到它的实际作用. 大多数资料看起来要么简单易懂,要么很深奥(事实上,我找到的大部分编译器资料都是很枯燥的.

开始加入gnu toolchain的开发

- netcasper - HelloGcc Working Group
作者: qiyao@hellogcc. 很多刚刚加入gnu toolchain开发的工程师,都会被各种各样的规定,缩写还有交流方式搞得晕头转向. 本文就是为了让刚刚进入gnu toolchain的开发的工程师简单介绍一下在这个圈子里边工作的一些特别之处. checkout就不用说了,绝大多数人都知道怎样check out代码.

好文: 為什麼 GNU grep 這麼快

- chuang - Tsung&#39;s Blog
Linux shell 常常會用到 grep, 為何 grep 可以那麼快的找到我們要的資料?. 這篇文章有清楚的說明: 為什麼 GNU grep 這麼快 (下述摘錄自此文), 詳細討論原文: why GNU grep is fast. 為什麼 GNU grep 這麼快. GNU grep 有使用下述技巧:.