- 浏览: 18743 次
最新评论
在编译过程中,词法分析和语法分析是两个重要阶段。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
#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兼容。
发表评论
-
(转载)C++中枚举与字符串相互转换
2012-07-06 09:52 4133有的时候我们喜欢使用一些外部的文件保存管理一些配置信息,这 ... -
awk教程
2012-07-06 09:45 603一个年轻的程序员问一个老程序员(一个比较牛逼的公司的CTO ... -
正则表达式中附加参数的用法
2012-07-06 09:38 614附件参数g的用法: 1)对于表达式对象的exec方法, ... -
asp.net gridview美化
2012-07-06 09:30 1273i am now in university(HIT@We ... -
javascript js 删除表格的行、单元列
2012-07-05 20:45 649大发现,大家在贴代码的时候。系统会自动加上一些代码或注释之 ... -
具有可过滤功能的JList组件【Swing】
2012-07-03 13:44 778【场景】:在一个列表中,可以通过输入某个字符,而动态过滤列 ... -
Flex应用程序背景颜色渐变
2012-07-02 12:29 617今天突然看见CSDN一个美女高手写的小东西,发现Flex背 ... -
Flex操作Json数据示例
2012-07-02 12:29 679Flex操作Json数据示例 本示例中需要用到JSO ... -
FLEX4中 获取JSON数据的一个例子
2012-07-02 12:29 789公司要求使用JSON格式来获取服务器端的数据 通过 ... -
Flex获取操作XML示例
2012-07-02 12:28 532/****** ".",&qu ... -
Flex 4 Canvas backgroundImage 问题
2012-07-02 12:28 742倾听,慎言,勇行,自省... ... -
GNU Make 中文手册v3.8 学习 ( 3/3 )
2012-07-01 10:05 1018GNU Make 中文手册v3.8 学习 ( 3/3 ) ... -
Web前端开发之“常见模块你真的很了解吗?”
2012-07-01 10:05 746标题和内容模 ... -
谈谈我对未来的想法吧
2012-07-01 10:05 682来总行珠海研发中 ... -
终于搞清楚了Flex到底是收费还是免费
2012-06-30 16:30 1616终于搞清楚了Flex到底是收费还是免费 2010年06月29 ... -
结合实际项目谈谈Extjs、Flex、Jquery等富因特网时代框架的用武之处
2012-06-30 16:30 672结合实际项目谈谈Extjs ... -
全面认识Flex安全沙箱
2012-06-30 16:30 604全面认识Flex安全沙箱 2 ... -
为Flex应用添加实时组件
2012-06-30 16:30 459为Flex应用添加实时组件 2011年06月30日 在很 ... -
Flex socket通信实践学习笔记(2)-1
2012-06-30 16:30 622Flex socket通信实践学习 ...
相关推荐
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 构成编译器的绝佳工具