创建博客 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

涟漪

随缘顺性,不争不胜。

 
 
 

日志

 
 

Flex Bison 使用教程  

2011-06-10 10:33:15|  分类: make |  标签: |举报 |字号 订阅

参与编写者
Martin Tang (QQ275596197)
使用说明
本文需要读者对C语言有一定的了解作为基础
本文中所涉及的例子可以用本站提供的‘全自动化Makefile’一文中提供的Makefile进行编译
读者如果在Linux下,可以直接使用,Windows用户需要Cygwin(www.cygwin.com)环境
本文中的工具,需要用户安装flex和bison软件包
1.介绍
编译器是软件开发中的核心部件,其作用是其他任何软件所不能取代的。编译器在工作过程中,往往完成如下的任务:
读取源代码并且获得程序的结构描述
分析程序结构,并且生成相应的目标代码
在UNIX早期时代,编写一个编译器是一件非常耗时的工作。人们为了简化开发过程,开发了Lex和YACC程序来解决第一个任务,根据用户描述的语言,生成能够解决问题的C/C++语言代码,供开发者使用。
将源代码文件分解为各种词汇(Lex)
找到这些词汇的组成方式(YACC)
GNU软件协会开发了Flex和BISON,其功能与LEX和YACC基本兼容,并且在Lex和YACC提供的功能的基础上进行了各种扩展。
2.Flex入门
Lex能够用来编写那些输入数据流(字符串)能够用正则表达式描述的程序,它可以根据正则表达式的描述,将输入数据流分类为各类词汇,为后来的语法分析做准备。
2.1.正则表达式
正则表达式是通过对各种词组类型所包含的字符类型的归纳,描述所需词组组成格式的方法,比如下面的例子描述了所有数字类型的字符串,表明无论在何时起,只要有0-9字符出现,就进入该状态,说明是字符,直到非0-9字符结束:[0123456789]+
为了简化书写起见,也可以写成如下的格式:[0-9]+
对于任意单词,其中只能包含字母,所以单词的正则表达式为:[a-zA-Z]+
Flex支持如下类型的正则表达式: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',
             则按照ASCII码\x转义符进行处理,否则,其他的'X'将用来做取消处理符处理
\0         一个ASCII码空字符
\123       内容为八进制123的char型
\x2a       内容为十六进制0x2a的char型
(r)        符合一个r,括号是用来越过优先级的
rs         正则表达式r,紧跟着一个
r|s        要么是r要么是s
^r         一个r,但是必须是在一行的开始
r$         一个r,但是必须是在行末
<s>r       一个r,但是之前字符串必须符合条件s
<s1,s2,s3>r
           同上,但是必须之前字符串符合s1或者s2或者s3
<*>r       不考虑开始字符串类型,只符合r
<<EOF>>    文件末尾
<s1,s2><<EOF>>
           前面符合s1或者s2的文件末尾
2.2.第一个Lex代码
按照上一节我们讲述的正则表达式例子,我们尝试第一次使用Lex来产生我们所需要的程序,实践一遍Lex的使用以及gcc编译器如何编译和生成所需的二进制。 Flex甚至Bison代码都有如下的编写格式:/* 定义段 */
%%
/* Flex、Bison代码段(规则) */
%%
/* 辅助代码段,C语言 */
首先,使用vi编译器,输入以下代码(test.l):// 定义段代码
%{
// 这种括号说明内部的代码不许flex处理,直接进入.C文件
#include <stdio.h>
%}
%%
// 词法规则段代码
[0123456789]+    printf("NUMBER");
// 数字类型字符串
[a-zA-Z]+
{
                   printf("WO");
// 单词类型字符串(WORD)
                   printf("RD");
}
%%
// 辅助C语言函数代码(直接写C语言,无须括号,我们这里无内容)
下面我们首先使用lex程序生成所需的状态机代码:flex -otest.c test.l    # 从正则表达式声称对应的C语言代码,注意-o后不要有空格(flex bug?)
gcc test.c -o test -lfl # 从C语言代码生成二进制,从而运行,-lfl说明链接libfl.a库文件
./test                  # 运行刚刚生成的二进制
下面我们来对刚生成的二进制进行试验,以弄清楚flex到底是做什么的,在test程序中输入以下内容,按下Ctrl-D可以退出test程序:3505
hello
what is
3505
通过这些试验,相信您已经明白了Flex的用途,每当一个正则表达式符合时,flex生成的代码就会自动调用对应的函数,或者运行对应的程序。下面我们对这个例子进行一些深入研究,处理一个类似C语言的程序配置脚本代码。首先,一个演示脚本如下:logging {
    category lame-servers {
null;
};
    category cname {
null;
};
};
zone "."
{
    type hint;
    file "/etc/bind/db.root";
}
在这个脚本中,我们可以看到一系列的词汇类型:
单词(WORD),比如'zone', 'type'
文件名(FILENAME),比如'/etc/bind/db.root'
引号(QUOTE),比如文件名两边的
左花括号(OBRACE),'{'
右花括号(EBRACE),'}'
分号(SEMICOLON),';'
我们修改后的Lex代码如下:%{
#include <stdio.h>
%}
%%
[a-zA-Z][a-zA-Z0-9]*  printf("WORD ");
/* 字符串 */
[a-zA-Z0-9\/.-]+      printf("FILENAME ");
/* 文件名 */
\"                    printf("QUOTE ");      /* 引号"
*/
\{                    printf("OBRACE ");     /* 左花括号 */
\}                    printf("EBRACE ");     /* 右花括号 */
;                     printf("SEMICOLON ");  /* 分号 */
\n                    printf("\n");          /* 换行 */
[ \t]+                /* 忽略空白字符 */
%%
int yywrap(void)      /* 当词法分析器到了文件末尾做什么 */
{
        return 1;     /* 返回1,说明停止前进,0则继续 */
}

void yyerror(char *s) /* 错误信息打印函数 */
{
        fprintf(stderr, "%s\n", s);
        return 0;
}

int main(int argc, char *argv[])
{
        FILE *fp;
        fp = fopen(argv[1], "r"); /* 首先打开要被处理的文件(参数1)
*/

        yyin = fp;                /* yyin是lex默认的文件输入指针,则不处理控制台输入 */

        yylex();                  /* 调用lex的工作函数,从这里开始,lex的词法分析器开始工作 */

        fclose(fp);
        return 0;
}到这里,我们已经完全可以对一个包含各种类型词组的源代码文件进行分析,得出其中各类型词组的排列顺序。在一个规范的基于语法的源代码中,词组的顺序从一定意义上来说,就是语法。对于源代码,lex的处理能力也就到这里为止,但是我们并没有完全展示lex的所有功能,读者如果有兴趣,可以继续深入阅读本文提供的参考文献。如何进行语法分析?我们在下面的章节中讲开始讲述Bison的基本使用方法,以及如何使用Bison进行语法分析。
3.Bison入门3.1.基础理论
Bison采用与YACC相同的描述语言,这种语言是BNF语法(Backus Naur Form)的一种,最早被John Backus和PeterNaur用于ALGOL60语言的开发工作。BNF语法可以用来表达与内容无关的,基于语法的语言,几乎所有的现代编程语言都可以用BNF进行描述。作为一个例子,一个进行加法和乘法的数学表达式语法可以如下表达:E : E '+' E
E : E '*' E
E : id
在这三句中,E在Bison语言中代表表达式,一个表达式可以是一个数字,也可以是一个变量名称,也可以是几个变量名称的组合,比如:1
1+2
a
a+b*c
而以上三句Bison语言就能够表达这些语法结构。
3.2.Bison初探
我们在下面作一个计算器,通过这个实例让大家明白Flex和Bison的相互关系和如何共同工作。首先,建立test2ll.l文件,并输入以下内容:/* 计算器的词法分析器描述,Flex语言 */
%{
/* 直接翻译为C语言 */
#include <stdlib.h>       /* 包含标准库文件 */
void yyerror(char
*);
/* 这是我们上面用到的错误报告函数 */
#include "test2yy.h"      /* 这个头文件由Bison自动生成 */
%}
%%
[0-9]+
{
              yylval = atoi(yytext);
/* yytext是flex内部用于指向当前词汇的字符串指针 */
return INTEGER;
/* INTEGER是从test2yy.h中包含过来的,在Bison中定义 */
}
[-+\n]
return
*yytext;
[
\t]
;
/* 跳过空白字符 */
.         yyerror("invalid character");
/* 产生一个错误,说明是无效字符 */
%%
int yywrap(void)
{
return
1;
/* 文件结束时退出 */
}
以上就是计算器使用的Flex语言,描述了我们将会遇到的各种词汇的格式,比如[0-9]+说明了,只有连续的从'0'到'9'的字符串,才被分析为INTEGER类型,如果遇到制表符、空格等,直接忽略,遇到加减符号则返回字符指针,其它的则报告语法错误。下面是我们的Bison语法文件test2yy.y:/* 注:您先抄写,注解见下文 */
%{
#include <stdio.h>
int yylex(void);
void yyerror(char
*);
%}
%token INTEGER                          /* Flex语言中INTEGER定义在此 */
%%
program:
        program expr '\n'
{ printf("%d\n", $2);
}
|
;
expr:
        INTEGER              { $$ = $1;
}
| expr '+' expr      { $$ = $1 + $3;
}
/* (1) */
| expr '-' expr      { $$ = $1 - $3;
}
/* (2) */
;
%%
void yyerror(char
*s)
{
    fprintf(stderr,
"%s\n", s);
}
int main(void)
{
    yyparse();
return
0;
}
编译过程:flex -otest2ll.c test2ll.l
bison -otest2yy.c test2yy.y -d      # 注意-d,用于产生对应的头文件
gcc test2yy.c test2ll.c -o test2
在这个例子中,我们遇到了许多没有见过的用法,Bison的书写格式基本与Flex的相同,只是规则的定义语法不同。其中,$N(N为数字)代表语法描述中,第N个词汇的内容,比如(1)中的$1代表'+'左边的expr,$3代表右边expr的内容,其中的N是指当前语法的词汇顺序,从1开始计数。而$$则代表这一段语法处理完后的结果,每一个语法对应的处理都有输入$N和输出$$。该例子中还有一个特殊的地方,就是第归调用,在Bison中,语法规则可以是第归的,这也是Bison之处(或者说是YACC的强大之处)。举个例子:program:
        program expr '\n'
{ printf("%d\n", $2);
}
|
;
这里,program的定义就是任何符合program的表达式后面紧接着expr和'\n',扫描到该表达式后,将expr处理的结果打印到屏幕。最后的|是“或者”的意思,也就是说program也可以是空的,什么都不写,分号代表该语义定义结束。 有了第归之后,Bison才可以说是一个能够应对任何状况的语法分析器,当然,这里还需要读者对以上所提供代码进行深入的研究和分析,考虑清楚后,会发现无论是C语言,还是Bison,第归永远是一个神奇的解决方案。
3.3.计算器程序的深入研究
以上我们设计的计算器只能进行加减计算,并且里面还有一些软件缺陷,对于一个实用的计算器来说,我们必须能够支持:
变量定义
变量赋值
变量与数字立即处理
于是我们假想设计出来的计算器能有如下的操作过程(输入和输出):输入:3
*
(4
+
5)
结果:27
输入:x =
3
*
(4
+
5)
输入:y =
5
输入:x
结果:27
输入:y
结果:5
输入:x +
2
* y
结果:37
这样看,这个计算器的功能已经相当强大了,下面我们着手实现,首先修改上面例子的Flex文件为如下:%{
#include <stdlib.h>
void yyerror(char
*);
#include "test2yy.h"
%}
%%
[a-z]
{
/* 变量类型词汇,限制:变量只能用一个字符 */
                 yylval =
*yytext -
'a';
return VARIABLE;
}
[0-9]+
{
/* 整数 */
                 yylval = atoi(yytext);
return INTEGER;
}
[+-()=/*\n]  { return *yytext; }          /* 数学计算符号 */
[
\t]
;
/* 跳过空白符号 */
%%
int yywrap(void)
{
return
1;
}
下面是我们新的Bison文件:%token INTEGER VARIABLE
%left '+'
'-'
%left '*'
'/'
%{
void yyerror(char
*);
int yylex(void);
int sym[26];
%}
%%
program:
    program statement '\n'
|
;
statement:
    expr                       { printf("%d\n", $1);
}
| VARIABLE '=' expr        { sym[$1]
= $3;
}
;
expr:
    INTEGER
    | VARIABLE                 { $$ = sym[$1];
}
| expr '+' expr            { $$ = $1 + $3;
}
| expr '-' expr            { $$ = $1 - $3;
}
| expr '*' expr            { $$ = $1 * $3;
}
| expr '/' expr            { $$ = $1 / $3;
}
|
'(' expr ')'
{ $$ = $2;
}
;
%%
void yyerror(char
*s)
{
    fprintf(stderr,
"%s\n", s);
return
0;
}
int main(void)
{
    yyparse();
return
0;
}
现在我们对该例子中引入的新功能介绍,%left,%right,%token都是用来声明词汇的,区别在于,%token声明的词汇与左右优先级无关,而%left的处理时,先处理左边的,%right先处理右边的,例如遇到字符串"1 - 2 - 5",到底是处理为"(1 - 2) -5",还是处理为"1 - (2 -5)"?%left处理为前者,而%right处理为后者(注:第一个计算器代码中就有这个缺陷,比如执行1-2+3,得到的结果就是-4,作为一个练习,读者可以使用这里讲解的%left自行更正)。
  评论这张
 
阅读(3638)| 评论(0)
推荐 转载

历史上的今天

最近读者

热度

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2014