- 浏览: 11686 次
最新评论
在编译过程中,词法分析和语法分析是两个重要阶段。lex和yacc是Unix环境下非常著名的两个工具,可以生成分别完成词法分析和语法分析功能 的C代码。在学习编译原理过程中,可以善加利用这两个工具,加深对两个阶段的理解。在平时的工作中,这两个工具也会起到重要的作用。 Lex是LEXical compiler的缩写,主要功能是生成一个词法分析器(scanner)的C源码。描述词法分析器的文件,经过lex编译后,生成一个lex.yy.c 的文件,然后由C编译器编译生成一个词法分析器。词法分析器,简单来说,其任务就是将输入的各种符号,转化成相应的标识符(token),转化后的标识符 很容被后续阶段处理。
先让我们来看一个简单的例子:
int num_lines = 0, num_chars = 0;
%%
\n {++num_lines; ++num_chars;}
. {++num_chars;}
%%
main()
{
yylex();
printf("# of lines = %d, # of chars = %d\n", num_lines, num_chars);
}
然后编译,输入一个文本试试:
$ flex sample1.l$ mv lex.yy.c sample1.c$ gcc sample1.c -o sample1 -ll$ ./sample1 正则表达式声明。希望出现在目标C源码中的代码,用%{…%}扩在一起。比如:
%
{#include
#include "y.tab.h"
typedef char * YYSTYPE;
char * yylval;
%
}
正则表达式声明如下
/* regular definitions */
delim [ \t\n]
ws {delim}+
letter [A-Za-z]
digit [0-9]
id {letter}({letter}{digit})*
number {digit}+(\.{digit}+)?(E[+\-]?{digit}+}?
这段正则表达式描述识别数(number)、标识符(id)的"规则"。过一会我们再细说正则表达式。
规则段是由正则表达式和相应的动作组成的。
p1 {action1}
p2 {action2}
……
pn {actionn}
值得注意的是,lex 依次尝试每一个规则,尽可能地匹配最长的输入流。如果有一些内容根本不匹配任何规则,那么 lex 将只是把它拷贝到标准输出。比如
%%
A {printf("you");}
AA {printf("love ");}
AAAA {printf("I ");}
%% 编译后运行一下,
$ ./sample3
AAAAAAA
I love you
可以看出lex的确按照最长的规则匹配。
程序段部分放一些扫描器的其它模块,比如一些动作执行时需要的模块。也可以在另一个程序文件中编写,最后再链接到一起。 生成C代码后,需用C的编译器编译。连接时需要指定链接库。gcc的连接参数为 -ll。
[编辑]正则表达式
正则表达式(regular expression)可以描述有穷状态自动机(finite automata)接受的语言,也就是定义一个可以接受的串的集合。限于篇幅,我们就不展开关于这方面的话题了。有兴趣的请参考[4]。 这里只介绍一下lex中用到的正则表达式的一些规则。
转义字符(也称操作符):
" \ [ ] ^ - ? . * + | ( ) $ / { } % 这些符号有特殊含义,不能用来匹配自身。如果需要匹配的话,可以通过引号(")或者转义符号(\)来指示。比如
C"++" C\+\+都可以匹配C++。
非转义字符:所有除了转义字符之外的字符都是非转义字符。一个非转义字符可以匹配自身。比如
integer匹配文本中出现的integer。
通配符:通配符就是.(dot),可以匹配任何一个字符。
字符集:用一对[]指定的字符构成一个字符集。比如[abc]表示一个字符集,可以匹配a、b、c中的任意一个字符。使用 可以指定范围。比如[a-z]表示可以匹配所有小写字母的字符集。
重复:
* 任意次重复+ 至少一次的重复,相当于xx*? 零次或者一次选择和分组:|符号表示选择,二者则一;括号表示分组,括号内的组合被看作是一个原子。比如(ab|cd)匹配ab或者cd。
简单来说,yacc(Yet Another Compiler-Compiler)就是编译器的编译器。Yacc是一个通用的工具,能够根据用户指定的规则,生成一个词法分析程序。yacc能识别 LALR(1)且无歧义的文法,它的输入是词法分析器的输出。我们知道,生成词法分析器是lex分内的事,因此lex和yacc常常珠联璧合。
先让我们看一下yacc文件的格式。和前面介绍的lex的格式类似:
declarations(声明)
%%rules(规则)%%
programs(代码)
其中声明段声明一些符号常量,可以为空。同lex一样,声明段中可以有出现在目标C程序中的代码,放在%{…%}中;还有一些yacc关键词可以指示出token的结合顺序: %left 左结合 %right 右结合 %nonassoc 不结合 %token 声明token
俗话说"没有规矩,不成方圆"。 规则段描述规则,自然是重中之重了。规则段的结构是如下,
A : BODY ;
A表示非终结符名,BODY表示产生式和动作。产生式包括非终结符和终结符,终结符用''引用。一些转义字符,比如'\r','\n'等,和C里面 的表示是一样的。动作(action)则是在输入被当前规则识别出来时而执行的。动作实际上就是C的代码,写在{ }中。为了沟通词法分析器和动作,yacc引入了形式变量,以$开头。如果希望获得词法分析器和前面的动作返回的值,我们可以使用$1,$2,…。$i表 示一条规则右侧第i个单元的值。比如有这样的一条规则,
A : B C D ;C的返回值为$2,D为$3。依此类推。
程序段放一些其它的程序,也可以省略,连%%都可以不要。
连接时需要指定连接库,gcc的参数为-ly。
[编辑]举例
让我们看一个典型的例子,它实现一个简单的计算器:
%
{
# include
# include
int regs[26];
int base;%
}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /* supplies precedence for unary minus */
%%
/* beginning of rules section
*/list :
/* empty */
| list stat '\n'
| list error '\n'
{
yyerrok;
} ;
stat : expr
{ printf( "=%d\n", $1 ); }
| LETTER '=' expr
{ regs[$1] = $3; } ;
expr : '(' expr ')'
{ $ = $2; }
| expr '+' expr
{ $ = $1 + $3; }
| expr '-' expr
{ $ = $1 - $3; }
| expr '*' expr
{ $ = $1 * $3; }
| expr '/' expr
{ $ = $1 / $3; }
| expr '%' expr
{ $ = $1 % $3; }
| expr '&' expr
{ $ = $1 & $3; }
| expr '|' expr
{ $ = $1 | $3; }
| '-' expr %prec UMINUS
{ $ = - $2; }
| LETTER
{ $ = regs[$1]; }
| number ; number : DIGIT { $ = $1; base = ($1==0) ? 8 : 10; } | number DIGIT { $ = base * $1 + $2; } ; %% /* start of programs */ yylex() { /* lexical analysis routine */ /* returns LETTER for a lower case letter, yylval = 0 through 25 */ /* return DIGIT for a digit, yylval = 0 through 9 */ /* all other characters are returned immediately */ int c; while( (c=getchar()) == ' ' ) { /* skip blanks */ } /* c is now nonblank */ if( islower( c ) ) { yylval = c - 'a'; return ( LETTER ); } if( isdigit( c ) ) { yylval = c - '0'; return( DIGIT ); } return( c ); } 编译、执行:
$bison example.y
$gcc example.tab.c ly -o example
$./example
20+30*50=1520
小结
lex是词法分析器的生成工具,yacc是文法分析器的生成工具。lex的描述规则采用正则表达式,关于正则表达式的详细讨论,参见文献[1]; yacc的描述规则采用无歧异文法。在GNU中有相应lex和yacc工具:flex和bison,与lex和 yacc兼容。
发表评论
-
string(字符串)类常用成员----增+,append,insert 删erase 改replace 查find 遍历 截取子串 字符串比较
2012-07-06 09:52 1050头文件及命名空间: ... -
Ext 对象编程-单页面组件销毁
2012-07-03 13:44 819单页面组件销毁 为了贯彻OO设计, 在使用单页面Ext ... -
打包swf flash应用为PlayBook AIR应用
2012-07-02 13:04 642命令行打包swf flash应用为PlayBook AIR ... -
flex4 datagrid里点击链接打开图片的方法
2012-07-02 13:03 6111. 在datagrid里面 加入链接 链接新窗口显 ... -
flex 显示pdf文档
2012-07-02 13:03 646FlexPager下载地址 http://code.goo ... -
[酷东东] 在Flex里嵌入网页:IFrame 开源类库
2012-07-02 13:03 713项目 地址:http://code.google .com ... -
第5课 Spark组件、Halo组件和Flex命名空间
2012-07-02 13:03 576flex/spark" xmln ... -
Flex 文件上传导入组件
2012-07-01 10:37 580上文讲到Flex利用Blazeds来上传文件,本文则封装了 ... -
flex中给图片(或任意组件)着色的方法
2012-07-01 10:37 517作者:屈剑峰 2011年4月3日 在fl ... -
Flex 数据易犯错误: 常见误用和错误
2012-07-01 10:37 728在某些情形下,绑定操作似乎不能正常工作,此时你可能非常懊恼 ... -
flex 中GML转换
2012-07-01 10:37 686package org.openscales.core.f ... -
Flex学习笔记
2012-07-01 10:37 600类成员有四种修饰符: public internal ... -
在Eclipse下使用Ant编译Flex程序
2012-06-30 17:01 577在Eclipse下使用Ant编译Fle ... -
Flex4+Spring3+Hibernate3+BlazeDS整合笔记
2012-06-30 17:01 606Flex4+Spring3+Hibernate3+BlazeD ... -
Flex是咋回事之二 前世今生
2012-06-30 17:01 564Flex是咋回事之二 前世 ... -
Flex 应用内存泄露的分析与诊断
2012-06-30 17:01 551Flex 应用内存泄露的分析与诊断 2010年11月01日 ... -
探究 Flex 组件的生命周期
2012-06-30 17:01 515探究 Flex 组件的生命周期 2011年01月05日 ...
相关推荐
Lex和Yacc工具使用方法,介绍了编译原理课程中的工具lex和yacc的基础使用方法
完整介绍Lex和Yacc Windows 上的使用 及工具的按装, 及环境变量的设置, GNU Bison实际上是使用最广泛的Yacc-like分析器生成器,使用它可以生成解释器,编译器,协议实现等多种程序. 它不但与Yacc兼容还具有许多Yacc不...
lex 和yacc 是两个用来生成词汇分析器和剖析器的工具,
LEX和YACC第二版中文版。LEX是词法分析工具,YACC是语法分析工具,使用这两个工具可以编写编译器等。
使用Lex, Yacc开发的算术表达式解析器,以及算术表达式的计算器。压缩文件包括代码,工程文件,文档。
lex&yacc是两个用来生成词汇分析器和剖析器的工具。我假设你能够运用C 语言编程,并且理解数据结构的含义,例如“链表”和“树”。导言部分描写了构建编译器所需的基本部分,以及lex&yacc 之间的互动关系。后面两章...
C语言的lex和yacc工具说明.doc
本系列文档就是专门用来由浅入深的介绍两 个有名的Unix 工 具Lex 和Yacc,并会一步一步的详细解释如何用这两个工具 来实现我们想要的任何 功能的解析程序
我找了N久,才找到的资源,拿出来和大家一同分享,里面有flex.exe和bison.exe以及相关的文件。觉得好的话,请大家顶一下。
详细实用的lex工具书:lex_yacc工具说明
简单介绍unix下的工具lex 和 yacc的语法与应用,很不错的资料
lex 与yacc 构成编译器的绝佳工具
很多人都知道lex&yacc,特别是计算机科班毕业的。因为在unix上自带的bshell就有这些功能。 cygwin里面也有这些。 可是,这种基本的功能,在win32平台下,微软似乎忘了。 有个外国人写了个软件Parser Generator (bum...
lex 和 yacc使用的简要中文说明。 是我见到得比较好的一本!
找了很久才找到一个下载的连接地址,下载了拿到这里供大家学习使用,连接如下:http://www.bumblebeesoftware.com/downloads.htm
c语言编译器,用lex和yacc工具完成词法分析与语法分析并生成语法树
都是做作业时在维普上下载的,崭新的没怎么看过的,谁要就拿去吧。 利用LEX和YACC实现对SQL查询语句的语法分析.pdf 应用YACC实现MicroC编译器.pdf 对语法分析程序自动生成器...语言开发工具Lex和Yacc的分析与应用.pdf
lex与yacc 构成编译器的绝佳工具 共五部分
lex和yacc是进行编译原理实验的常用工具,提供一份lex和yacc的资料。
lex 与yacc 构成编译器的绝佳工具