Lex 与 Yacc

Lex 与 Yacc

其实，在我看来lex和yacc就是一套文字识别及语法分析的编程软件，它们基于宿主语言(host languge)进行编程，例如常用的宿主语言有C、C++和basic。但是它们在自己的规则部分(也就是文件的第二部分)都有相应的语法规则，例如lex用正则表达式(regular expression)实现词法识别，词法识别实际上就是把输入文件中字符进行归类(例如关键字、变量、立即数等)，将其归类为不同的tokens。这里还涉及到一个概念那就是terminals。在这里terminals和tokens是同义词，表达的是一个含义，都是不能再分割的基本单元。这里不能再分割指的就是区别于yacc中可以再分割的nonterminals，因为yacc中规则部分实际上就是利用递归(recursion)来进行语法识别。yacc用nonterminals不断地递归下一层的nonterminals或者terminals，直到所有的最底层的语法都用terminals来表述，即不能再分割。terminals用大写字母表示，nonterminals用小写字母表示。这里先做简单介绍，后面会有详细的讲解。

1.如何编译和执行Lex与Yacc源代码？

例如有lex和yacc的源代码分别为example.l和example.y。如果宿主语言是C语言的话(以下未特殊说明，均指C语言)，由于lex和yacc的源代码规则部分都不是C语言，所以不能直接拿来用GCC编译，所以我们要先用lex和yacc指令来将源代码转换成完整的C语言文件。如下：

lex example.l

yacc -d example.y

第一条指令执行后生成lex.yy.c的C程序文件。第二条指令因为使用了option -d，所以该条指令生成两个文件，分别是y.tab.c和y.tab.h。这里y.tab.h里面包含的是各个token的宏定义，从257开始给每个token定义一个一个数字。所以通常该文件要使用#include<y.tab.h>包含在lex的源代码中，本例中，即example.l文件内，以便在后面的编译中使用。接下来就是编译生成的C文件，从而生成可执行文件。如下：

cc lex.yy.c y.tab.c -o example

执行可执行文件./example就可以实现编译器了。

总结：

编译lex、yacc源代码指令序列

lex xxx.l //生成lex.yy.c

yacc -d xxx.y //生成y.tab.c和y.tab.h

cc lex.yy.c y.tab.c -o xxx //生成可执行文件xxx

Lex&Yacc的结构图如图1所示：

图1 Lex&Yacc的结构图[1]

2. Lex的使用规则:

lex实际上就是一个文字识别软件，通过扫描一串输入字符来识别出你需要的部分，从而做出相应动作，即pattern/actions模式。简单的编译器完全使用lex就可以做到，但复杂的结构就不得不用yacc来作语法分析。

2.1 Lex源文件结构:

正如上面提到的，Lex的源代码分为三个部分：声明部分(头文件包含、C宏定义、lex声明)、Lex规则部分、以及C语言部分。三部分之间用%%符号来分隔，只有第二部分是必须的，其它部分可以省略。完整的Lex代码如下所示[1]：

C declarations and includes

Lex macro definitions and directives

Lex Specification

in the form of pattern/action statements like this:

keyword { my_c_code(yytext); }

C language program (the rest)

其实第一部分和第三部分可以合并成一个部分，对整个程序不会有什么影响。

2.2 Lex声明以及start conditions:

在lex的声明部分，%{与%}之间是头文件包含以及宏定义等用C语言描述的部分。%}之后则是lex声明，这里一般用来声明start conditions[2]。

这里我们重点讨论一下start conditions。我们可以在lex的声明部分声明一些start condition symbols，这些symbols用来控制在什么时候来匹配什么字符，或者不匹配什么字符。我们可以随时更改start condtion，只要在规则的action中使用指令BEGIN symbol;，如果想返回到原始的状态，可以使用指令BEGIN 0;或者BEGIN INITIAL;。在规则部分我们用<symbol>来标记处于某状态的 pattern/actions。Start conditions有两种模式一个是Inclusive condition，另一个是exclusive condition。

Inclusive condition用%s来声明，如果该时刻处于某个inclusive状态，则所有该inclusive状态的<symbol>及normal状态下的<symbol>指定的pattern/actions都会得到执行。

Exclusive condition用%x来声明。当遇到处于exclusive状态的<symbol>时，只有该symbol下的pattern/actions能得到执行，而normal状态<symbol>下的pattern/actions都不会执行。

举例如下[2]：

%s one

%x two

abc {printf("matched "); ECHO; BEGIN one;}

<one>def {printf("matched "); ECHO; BEGIN two;}

<two>ghi {printf("matched "); ECHO; BEGIN INITIAL;}

在这个例子中，如果处于one状态，则abc和def都会被检测匹配。然而处于two状态，则只有ghi会被检测匹配。

2.3 Lex的规则部分:

其实在这部分唱主角的应该是正则表达式，但是要想说清楚它，要另写一篇文章了。在这里主要是介绍Lex+Yacc，所以正则表达式就直接忽略。

简单地讲，这部分规则就是pattern/actions，如下：

regular_expression { C-program statements }

在{ C-program statements }部分你可以写任何C code。但是在与yacc合用的时候一般都是返回terminals和数值，例如{ yylval=atoi(yytext); return NUMBER; }

说到这里，我要先介绍几个lex常用的内部变量，正如上面的yytext(yylval是Yacc中的内部变量)。如下表[6]:

yyin	FILE* 类型。它指向lexer正在解析的当前文件
yyout	FILE* 类型。它指向记录lexer输出的位置。缺省情况下，yyin和yyout都指向标准输入和输出。
yytext	匹配模式的文本存储在这一变量中(char*)。
yyleng	给出匹配模式的长度。
yylineno	提供当前的行数信息。(lexer不一定支持。)

2.4 Lex的C语言部分:

如果不用分析任何输入文件的话，直接从标准输入读取字符，则只需要在main函数中执行yylex()即可。但大多数情况下，需要我们从一个文件中读取字符。所以一个标准的读取文件C语言程序如下[5]:

%{
#include <stdio.h>
#include <errno.h>
int file_num;
int file_num_max;
char **files;
extern int errno;
%}
%%
(ftp|http):\/\/[^ \n<>"]* printf("%s\n",yytext); //打印输出网址
.|\n ; //消除任意单字符及换行符
%%
int main(int argc, char *argv[]) //这段代码就是常用来读取输入文件的，当执行yacc可执行文件的时候，可以附带多个参数在数组argv[]中
{
file_num=1;
file_num_max=argc;
files=argv; //这句代码很重要，把参数的首地址赋给files，以便后面的yywrap()函数使用。
if(argc>1)
{
if((yyin=fopen(argv[file_num],"r"))==0)
{
perror(argv[file_num]);
exit(1);
}
}
while(yylex()) ;
return 0;

}

int yywrap() //这个函数用来连续读取多个文件，当该函数返回1时，整个读取程序结束。所以需要我们手动给yywrap()函数返回1。

{

fclose(yyin);

if(++file_num<file_num_max)

{

if((yyin=fopen(files[file_num],"r"))==0)

{

perror(files[file_num]);

exit(1);

}

return 0;

}

else

{

return 1;

}

以上是一个通用的字符读取程序。如果再想进一步化简一下，当Yacc的可执行文件的参数只有一个的时候，yywrap()函数可以简化如下:

int yywrap()

{

return 1;

}

下面介绍几个常用的Lex函数[6]:

yylex()	从这一函数开始分析。它由Lex自动生成
yywrap()	这一函数在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解析。因此它可以用来解析多个文件。代码可以写在第三段，这样就能够解析多个文件。方法是使用yyin文件指针指向不同的文件，直到所有的文件都被解析。最后，yywrap()可以返回1来表示解析结束。
yyless(int n)	这一函数可以用来送回除了前n个字符外的所有读出标记。
yymore()	这一函数告诉Lexer将下一个标记附加到当前标记后。

yylex()函数是整个Lex源代码的精华，非C语言部分(包括lex声明部分，规则部分等)通过Lex自动编译成C代码的一个子函数yylex()。因此在主函数main()中调用yylex()就可以执行整个字符识别程序。

2.4 总结:

通过Lex我们可以将一串输入字符，分析出我们想要得到标识。然后再利用Yacc进行语法分析。

3. Yacc的使用规则:

Yacc使用“分析树”的原理来进行语法分析，这里我们通过递归的原则来实现分析树。

3.1 Yacc的文件结构:

Yacc的文件结构基本与Lex的源代码结构类似。同样是分成三个部分，只是第一部分通过关键字%token来定义所有的terminals (nonterminals不用定义，直接用symbol:的形式在规则部分使用即可)。

3.2 Yacc规则部分:

变量yylval通常用在lex规则中在变量yytext配合下来接受内容(可能是数字也可能是字符串等)。

而在Yacc规则部分，用$number来接收数值等。

在标记都是terminals的时候，我们直接用$number来获取数值即可。例如:

expression : NUMBER '+' NUMBER {printf("The result is %d\n", $1+$3); } //这里要重点注意的是，我们使用$1+$3，而不是$1+$2，因为'+'也是一个symbol。

如果标记是nonterminals，由于nonterminals不会出现在Lex的源代码中，所以我们要用另一种方法来给nonterminal symbol赋值，即用$$来给当前nonterminal symbol赋值。例如:

%token NAME NUMBER

statement: NAME '=' expression

| expression { printf("= %d\n", $1); }

;

expression: expression '+' NUMBER { $$=$1+$3; }

| expression '-' NUMBER { $$=$1-$3; }

| NUMBER { $$=$1; }

;

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

上面这段程序写成如下的递归形式更容易理解。从上面的代码可以看出，上面的规则不能用C语言的执行来理解，两者是完全不同的。从某种角度讲，上面的程序含义倒与verilog有几分相似。它们都表示一种，符号与符号之间的关系。没有什么执行顺序概念，理解这一点很重要，否则无法读懂其它程序，就算读懂，也不能写出自己的程序。所以一定要切记一点: 不要用C语言去思考所有的编程语言，很多时候它们的执行规则是完全不同的。

总之，上面这段代码就是描述下面这幅分析树，就像画画一样，没有执行次序与执行次数的概念，就是描述你如何画出这幅树形图的。所以我猜测，大概verilog等HDL也应该是这样儿理解吧。