- 论坛徽章:
- 0
|
在编译过程中,词法分析和语法分析是两个重要阶段。lex和yacc是Unix环境下非常著名的两个工具,可以生成分别完成词法分析和语法分析功能的C代码。在学习编译原理过程中,可以善加利用这两个工具,加深对两个阶段的理解。在平时的工作中,这两个工具也会起到重要的作用。
词法分词器生成工具lex
Lex是LEXical compiler的缩写,主要功能是生成一个词法分析器(scanner)的C源码。描述词法分析器的文件,经过lex编译后,生成一个lex.yy.c的文件,然后由C编译器编译生成一个词法分析器。词法分析器,简单来说,其任务就是将输入的各种符号,转化成相应的标识符(token),转化后的标识符很容被后续阶段处理。过程如图 1。
先让我们来看一个简单的例子:
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
没多少代码就可以实现一个行数统计程序。让我们再加点功能。
int num_lines = 0, num_chars = 0, num_words = 0;
%%
\n {++num_lines; }
[A-Za-z]* {++num_words; }
. {++num_chars; }
%%
main()
{
yylex();
printf("lines:%d \tchars:%d\twords:%d\n", num_lines, num_chars, num_words);
}
现在这个lex文件可以用来生成一个统计行数、字符个数和单词个数的工具。
让我们来仔细研究一下这个奇妙的工具吧。先看看Lex文件的结构。 Lex文件结构简单,分为三个部分:
declarations
%%
translation rules
%%
auxiliary procedures
分别是声明,转换规则和其它函数。
声明段包括变量的声明、符号常量的声明和正则表达式声明。希望出现在目标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。
本文来自ChinaUnix博客,如果查看原文请点:http://blog.chinaunix.net/u/8649/showart_342641.html |
|