http://www.linuxdiyf.com/viewarticle.php?id=91568
作者：绚丽也尘埃
最近看《GCC-the-Complete-Reference-fly》才知道有lex和yacc这两个有趣的工具，并且fedora core 8也默认安装有这两个工具，所以趁此机会学习一下，以前学编译原理时，知道有yacc这个名词，但是从来没有考虑过它是个什么东东，要学习的东西实在是太多了，真是学海无涯。
先从lex讲起吧。Lex又称Lexical Analyzar是对源程序进行词法分析的。如果学过《编译原理》便会知道一份源代码从文本文件变成可执行的二进制文件的过程。最开始的两个步骤便是词法分析和语法分析。lex按照指定的模式来匹配输入，当匹配到一条规则时，便执行相应的动作。
一个 Lex 程序分为三个段：第一段是 C 和 Lex 的全局声明，第二段包括模式（C 代码），第三段是补充的 C 函数。 例如, 第三段中一般都有 main() 函数。这些段以%%来分界。
下面是一个统计字数的lex程序。
| QUOTE: |
| %{ int wordCount = 0; %} chars [A-za-z\_\'\.\"] /*类似shell使用的正则表达式*/ numbers ([0-9])+ delim [" "\n\t] whitespace {delim}+ words {chars}+ %% {words} { wordCount++; /*increase the word count by one*/ } {whitespace} { /* do nothing*/ } {numbers} { /* one may want to add some processing here*/ } %% void main() { yylex(); /* start the analysis*/ /*此函数由lex自动生成*/ printf(" No of words: %d\n", wordCount); } int yywrap() { return 1; } |
将文件保存为wordCount.lex。接下来就是编译它生成可执行程序了，步骤如下：
| QUOTE: |
| [ecy@localhost ~]$ flex wordCount.lex [ecy@localhost ~]$ gcc lex.yy.c -lfl -o wordCount [ecy@localhost ~]$ cat word fuzhijie dandan 1234567 ecy_fu@163.com fuzhijie1985 annie [ecy@localhost ~]$ cat word | ./wordCount @ No of words: 6 |
生成的可执行程序为wordCount，它对输入的文件按照指定的模式进行匹配，当一个词语中出现了字母，这个词语便同words匹配，匹配促发的动作是将变量wordCount加1。这个lex文件是比较完备的，在《GCC-the-Complete-Reference-fly》有个例子，它的代码只有中间一段，起代码如下：
| QUOTE: |
| %% switch printf("SWITCH "); case printf("CASE "); [a-zA-Z][_a-zA-Z0-9]* printf("WORD(%s) ",yytext); [0-9]+ printf("INTEGER(%s) ",yytext); 375 Chapter 19: Implementing a Language \{ printf("LEFTBRACE "); \} printf("RIGHTBRACE "); %% [ecy@localhost ~]$ flex kwords.lex [ecy@localhost ~]$ gcc lex.yy.c -lfl -o kwords [ecy@localhost ~]$ cat kwtry.text blatz { switch big_time_do case HamFram case 889 } dend [ecy@localhost ~]$ cat kwtry.text | ./kwords WORD(blatz) LEFTBRACE SWITCH WORD(big_time_do) CASE WORD(HamFram) CASE INTEGER(889) RIGHTBRACE WORD(dend) |
这个程序编译后也能正常工作，这说明相关的函数都有lex自动生成了。
http://xingxinwang.blog.163.com/blog/static/19929240200762211239458/
Lex和Yacc应用方法(一).初识Lex
草木瓜 20070301
Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。
<本系列文章的地址：http://blog.csdn.net/liwei_cmg/category/207528.aspx>
一.Lex(Lexical Analyzar) 初步示例
先看简单的例子(注：本文所有实例皆在RetHat Linux下完成):
一个简单的Lex文件 exfirst.l 内容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下执行命令flex解析，会自动生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
进行编译生成parser可执行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll链结选项，cc编译时会出现以下错误，后面会进一步说明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status
创建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通过已生成的可执行程序，进行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法会有个直观的了解：
1.定义Lex描述文件
2.通过lex，flex工具解析成lex.yy.c文件
3.使用cc编译lex.yy.c生成可执行程序
再来看一个比较完整的Lex描述文件 exsec.l ：
%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
进行解析编译：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
这里就没有加-ll选项，但是可以编译通过。下面开始着重整理下Lex描述文件.l。
二.Lex(Lexical Analyzar) 描述文件的结构介绍
Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识别程序，由该程序识别出输入文本中的各个单词。 一般可以分为<定义部分><规则部分><用户子程序部分>。其中规则部分是必须的，定义和用户子程序部分是任选的。
(1)定义部分
定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括include语句、声明语句在内的C语句。这部分跟普通C程序开头没什么区别。
%{
#include "stdio.h"
int linenum;
%}
(2) 规则部分
规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多行执行语句，也可以用{}括起来。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.规则部分的正则表达式
规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字
符含义：
A-Z, 0-9, a-z 构成模式部分的字符和数字。
- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。
\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义，只取字符的本身。
[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C的任何一个。
^ 表示否定。
* 匹配0个或者多个上述模式。
+ 匹配1个或者多个上述模式。
? 匹配0个或1个上述模式。
$ 作为模式的最后一个字符时匹配一行的结尾。
{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。[a-z]{5} 表示长度为5的，由a-z组成的字符。此外，还可以表示预定义的变量。
. 匹配任意字符，除了 \n。
( ) 将一系列常规表达式分组。如：{Letter}({Letter}|{Digit})*
| 表达式间的逻辑或。
"一些符号" 字符的字面含义。元字符具有。如："*" 相当于 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式，只匹配模版中"/"前面的部分。如：模式为 ABC/D 输入 ABCD，时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话，ABCE就不会去匹配ABC/D。
B.规则部分的优先级
规则部分具有优先级的概念，先举个简单的例子：
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此时，如果输入内容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现"AAAA"只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符匹配规则。
如果将规则
AAAA {printf("THREE\n");};
改为
AAAAA {printf("THREE\n");};
./parser < file1.txt 输出结果为：
THREE
TWO
再来一个特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
并输入title，Lex解析完后发现，仍然存在两个规则，这时Lex只会选择第一个规则，下面的则被忽略的。这里就体现了Lex的顺序优先级。把这个例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex编译时会提示：warning, rule cannot be matched.这时处理title字符时，匹配到第一个规则后，第二个规则就无效了。
再把刚才第一个例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 显示效果是一样的，最后一项规则肯定是会忽略掉的。
C.规则部分的使用变量
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分别代指特定的含义，在两个%%之间，可以通过{int}{float}进行直接引用，简化模式定义。
(3) 用户子程序部分
最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
三.Lex(Lexical Analyzar) 一些的内部变量和函数
内部预定义变量：
yytext char * 当前匹配的字符串
yyleng int 当前匹配的字符串长度
yyin FILE * lex当前的解析文件，默认为标准输出
yyout FILE * lex解析后的输出文件，默认为标准输入
yylineno int 当前的行数信息
内部预定义宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的默认动作
内部预定义的函数：
int yylex(void) 调用Lex进行词法分析
int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段，这样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回1来表示解析的结束。
lex和flex都是解析Lex文件的工具，用法相近，flex意为fast lexical analyzer generator。可以看成lex的升级版本。
相关更多内容就需要参考flex的man手册了，十分详尽。
四.关于Lex的一些综述
Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了。
Lex和Yacc应用方法(二).再识Lex与Yacc
草木瓜 20070314
早在二十世记七十年代之前，编写编译器一直是一个非常费时的工作。但到了1975这一年这一切却发生了重大转变，首先Stephen C. Johnson Lesk在贝尔实验室完成了Yacc开发，为了配合yacc更好的协作, Mike Lesk和Eric Schmidt又完成了lex。从而Lex和yacc成为计算机编译领域的重要理论，而这些工具也极大地简化了编写编译器的工作。
后来Robert Corbett和Richard Stallman在此基础上又完成了bison。Jef Poskanzer,Vern Paxson也对lex作了大量改进，称为flex。
<本系列文章的地址：http://blog.csdn.net/liwei_cmg/category/207528.aspx>
一、Lex理论
Lex使用正则表达式从输入代码中扫描和匹配字符串。每一个字符串会对应一个动作。通常动作返回一个标记给后面的剖析器使用，代表被匹配的字符串。每一个正则表达式代表一个有限状态自动机(FSA)。我们可以用状态和状态间的转换来代表一个(FSA)。其中包括一个开始状态以及一个或多个结束状态或接受状态。
我们以上文《Lex和Yacc应用方法(一).初识Lex》第一个例子详细说明：
exfirst.l
%{
#include "stdio.h"
%}
%%
[\n] ; A
[0-9]+ printf("Int : %s\n",yytext); B
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext); C
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext); D
[\+\-\*\/\%] printf("Op : %s\n",yytext); E
. printf("Unknown : %c\n",yytext[0]); F
%%
这里使用一相对简单的输入文件 file.txt
i=1.344+39;
bcd=4%9-333
我们假定，
Lex 系统创建一动态列表：内容+规则+状态
Lex 状态：1 接受 2 结束
接受表示该元素可以做为模式匹配
结束表示该元素已完成模式匹配
读入“i”
[查找元素]查找相邻且状态为1的元素，无元素，
[匹配规则]D，
[新增列表<元素1>并置数据](存在则覆盖)状态为1，规则为D，内容为"i"。
[操作顺序符] 1
读入“=”
[查找元素]查找相邻且状态为1的元素，“i=”寻找匹配规则，无规则
[置上一元素]<元素1>状态为2
[匹配规则]F，
[新增列表<元素2>并置数据](存在则覆盖)状态为1，规则为F，内容为"="
[操作顺序符] 2
读入“1”，
[查找元素]查找相邻且状态为1的元素，“=1”寻找匹配规则，无规则
[置上一元素]<元素2>状态为2
[匹配规则]B,
[新增列表<元素3>并置数据](存在则覆盖)状态为1，规则为B，内容为"1"
[操作顺序符] 3
读入“.”
[查找元素]查找相邻且状态为1的元素，“1.”寻找匹配规则，无规则，但有潜在规则C
[匹配规则]F,
[新增列表<元素4>并置数据](存在则覆盖)状态为1，规则为F，内容为"."
[置上一元素]<元素3>状态为1
[操作顺序符] 4
读入“3”
[查找元素]查找相邻且状态为1的元素，“1.3”寻找匹配规则，有规则
[置起始元素]状态为1，规则为C，内容为"1.3"
[操作顺序符] 3 组合元素的起始操作符
读入“4”
[查找元素]查找相邻且状态为1的元素，“1.34”寻找匹配规则，有规则
[置起始元素]状态为1，规则为C，内容为"1.34"
[操作顺序符] 3 组合元素的起始操作符
读入“4”
[查找元素]查找相邻且状态为1的元素，“1.344”寻找匹配规则，有规则
[置起始元素]状态为1，规则为C，内容为"1.344"
[操作顺序符] 3 组合元素的起始操作符
读入“+”
[查找元素]查找相邻且状态为1的元素，“1.344+”寻找匹配规则，无规则
[匹配规则]E,
[新增列表<元素4>并置数据](存在则覆盖)状态为1，规则为E，内容为"+"
[置上一元素]<元素3>状态为2
[操作顺序符] 4
...
最后解析结果为
内容 规则 状态
<元素1> i D 2
<元素2> = F 2
<元素3> 1.344 C 2
<元素4> + E 2
...
上面列出的算法是仅属于个人的分析，是相对直观且便于理解的，也可以参照这个算法用C语言模拟出lex的效果。不过真正的Lex算法肯定是更为复杂的理论体系，这个没有接触过，有兴趣可以参看相关资料。
二、yacc的BNF文件
个人认为lex理论比较容易理解的，yacc要复杂一些。
我们先从yacc的文法说起。yacc文法采用BNF(Backus-Naur Form)的变量规则描述。BNF文法最初由John Backus和Peter Naur发明，并且用于描述Algol60语言。BNF能够用于表达上下文无关的语言。现代程序语言大多数结构能够用BNF来描述。
举个加减乘除例子来说明：
1+2/3+4*6-3
BNF文法：
优先级
E = num 规约a 0
E = E / E 规约b 1
E = E * E 规约c 1
E = E + E 规约d 2
E = E - E 规约e 2
这里像（E表达式）这样出现在左边的结构叫做非终结符(nonterminal)。像（num标识符）这样的结构叫终结符（terminal，读了后面内容就会发现，其实是由lex返回的标记），它们只出现在右边。
我们将 “1+2/3+4*6-3-2”逐个字符移进堆栈，如下所示：
.1+2/3+4*6-3
1 1.+2/3+4*6-3 移进
2 E.+2/3+4*6-3 规约a
3 E+.2/3+4*6-3 移进
4 E+2./3+4*6-3 移进
5 E+E./3+4*6-3 规约a
6 E+E/.3+4*6-3 移进
7 E+E/3.+4*6-3 移进
8 E+E/E.+4*6-3 规约a
9 E+E/E+.4*6-3 移进
10 E+E/E+4.*6-3 移进
11 E+E/E+E.*6-3 规约a
12 E+E/E+E*.6-3 移进
13 E+E/E+E*6.-3 移进
14 E+E/E+E*E.-3 规约a
15 E+E/E+E*E-.3 移进
16 E+E/E+E*E-3. 移进
17 E+E/E+E*E-E. 规约a
18 E+E+E*E-E. 规约b
19 E+E+E-E. 规约c
20 E+E-E. 规约d
21 E-E. 规约d
22 E. 规约e
我们在实际运算操作中是把一个表达式逐步简化成一个非终结符。称之为“自底向上”或者“移进归约”的分析法。
点左面的结构在堆栈中，而点右面的是剩余的输入信息。我们以把标记移入堆栈开始。当堆栈顶部和右式要求的记号匹配时，我们就用左式取代所匹配的标记。概念上，匹配右式的标记被弹出堆栈，而左式被压入堆栈。我们把所匹配的标记认为是一个句柄，而我们所做的就是把句柄向左式归约。这个过程一直持续到把所有输入都压入堆栈中，而最终堆栈中只剩下最初的非终结符。
在第1步中我们把1压入堆栈中。第2步对应规则a，把1转换成E。然后继续压入和归约，直到第5步。此时堆栈中剩下E+E，按照规则d，可以进行E=E+E的合并，然而输入信息并没有结束，这就产生了“移进-归约”冲突(shift-reduce conflict)。在yacc中产生这种冲突时，会继续移进。
在第17步，E+E/E，即可以采用E+E规则d，也可以采用E/E规则b，如果使用E=E+E规约，显然从算法角度是错误的，这就有了运算符的优先级概念。这种情况称为“归约-归约”冲突(reduce-reduce conflict)。此时yacc会采用第一条规则，即E=E/E。这个内容会在后面的实例做进一步深化。
三、十分典型的利用lex和yacc模拟的简单+-*/计算器。
A.示例
最有效的方法是示例学习，这样首先给出全部示例文件。
lex文件：lexya_a.l
%{
#include <stdlib.h>
void yyerror(char *);
#include "lexya_a.tab.h"
%}
%%
[0-9]+ { yylval = atoi(yytext); return INTEGER; }
[-+*/\n] return *yytext;
[\t] ;/* 去除空格 */
. yyerror("无效字符");
%%
int yywrap(void) {
return 1;
}
yacc文件：lexya_a.y
%{
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
%}
%token INTEGER
%left '+' '-'
%left '*' '/'
%%
program:
program expr '\n' { printf("%d\n", $2); }
|
;
expr:
INTEGER { $$ = $1; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;
%%
void yyerror(char *s) {
printf("%s\n", s);
}
int main(void) {
yyparse();
return 0;
}
进行编译：
bison -d lexya_a.y
lex lexya_a.l
cc -o parser *.c
运行：
./parser
输入计算式，回车会显示运算结果
如：
1+2*5+10/5
13
9+8/3
11
10+2-2/2-2*5
1
这里有两个文件lexya_a.y和lexya_a.l。lexya_a.y是yacc文件，bison -d lexya_a.y 编译后会产生lexya_a.tab.c lexya_a.tab.h。lex文件lexya_a.l中头声明已包括了lexya_a.tab.h。这两个文件是典型的互相协作的示例。
B.分析
(1)定义段和预定义标记部分
yacc文件定义与lex十分相似，分别以%{ }% %% %%分界。
%{
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
%}
这一段十分容易理解，只是头文件一些引用说明。称为“定义”段。
%}
%token INTEGER
%left '+' '-'
%left '*' '/'
%%
%}和%%这一段可以看作预定义标记部分。%token INTEGER 定义声明了一个标记。当我们编译后，它会在lexya_a.tab.c中生成一个剖析器，同时会在lexya_a.tab.h
产生包含信息：
# define INTEGER 257
其中0-255的之间的标记值约定为字符值，是系统保留的后定义的token。
lexya_a.tab.h其它部分是默认生成的，与token INTEGER无关。
# ifndef YYSTYPE
# define YYSTYPE int
# define YYSTYPE_IS_TRIVIAL 1
# endif
extern YYSTYPE yylval;
lex文件需要包含这个头文件，并且使用其中对标记值的定义。为了获得标记，yacc会调用yylex。yylex的返回值类型是整型，可以用于返回标记。而在yylval变量中保存着与返回的标记相对应的值。
yacc在内部维护着两个堆栈，一个分析栈和一个内容栈。分析栈中保存着终结符和非终结符，并且记录了当前剖析状态。而内容栈是一个YYSTYPE类型的元素数组，对于分析栈中的每一个元素都保存着一个对应的值。例如，当yylex返回一个INTEGER标记时，把这个标记移入分析栈。同时，相应的yacc值将会被移入内容栈中。分析栈和内容栈的内容总是同步的，因此从栈中找到对应的标记值是很容易的。
比如lex文件中下面这一段：
[0-9]+ { yylval = atoi(yytext); return INTEGER; }
这是将把整数的值保存在yylval中，同时向yacc返回标记INTEGER。即内容栈存在了整数的值，对应的分析栈就为INTEGER标记了。yylval类型由YYSTYPE决定，由于它的默认类型是整型，所以在这个例子中程序运行正常。
lex文件还有一段：
[-+*/\n] return *yytext;
这里显然只是向yacc的分析栈返回运算符标记，系统保留的0-255此时便有了作用，
内容栈为空。把“-”放在第一位是防止正则表达式发现类似a-z的歧义。
再看下面的：
%left '+' '-'
%left '*' '/'
%left 表示左结合，%right 表示右结合。最后列出的定义拥有最高的优先权。因此乘法和除法拥有比加法和减法更高的优先权。+ - * / 所有这四个算术符都是左结合的。运用这个简单的技术，我们可以消除文法的歧义。
注：关于结合性，各运算符的结合性分为两种，即左结合性(自左至右)和右结合性(自右至左)。例如算术运算符的结合性是自左至右，即先左后右。如有表达式x-y+z则y应先与“-”号结合， 执行x-y运算，然后再执行+z的运算。这种自左至右的结合方向就称为“左结合性”。而自右至左的结合方向称为“右结合性”。 最典型的右结合性运算符是赋值运算符。如x=y=z,由于“=”的右结合性，应先执行y=z再执行x=(y=z)运算。
(2)规则部分
%%
program:
program expr '\n' { printf("%d\n", $2); }
|
;
expr:
INTEGER { $$ = $1; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;
%%
这个规则乍看起来的确有点晕，关键一点就是要理解yacc的递归解析方式。
program和expr是规则标记，但是作为一个整体描述表达式。
先看expr，可以由单个INTEGER值组成，也可以有多个INTERGER和运算符组合组成。
以表达式“1+4/2*3-0”为例，1 4 2 3 都是expr，就是expr+expr/expr*expr-expr
说到底最后还是个expr。递归思想正好与之相反，逆推下去会发现expr这个规则标记能表示所有的数值运算表达式。
了解了expr后，再看program，首先program可以为空，也可以用单单的expr加下“\n”回车符组成，结合起来看program定义的就是多个表达式组成的文件内容。
回过头，创建如下文件input：
[root@localhost yacc]# cat input
1+5/5+4*5
3+9+2*10-9
2/2
3-9
运行则结果如下：
[root@localhost yacc]# ./parser < input
22
23
1
-6
粗略有了概念之后，再看lex如何执行相应的行为。
以 expr: expr '+' expr { $$ = $1 + $3; }为例：
在分析栈中我们其实用左式替代了右式。在本例中，我们弹出“ expr '+' expr ”然后压入“expr”。我们通过弹出三个成员，压入一个成员来缩小堆栈。在我们的代码中可以看到用相对地址访问内容栈中的值。如$1，$2，这样都是yacc预定义可以直接使用的标记。“$1”代表右式中的第一个成员，“$2”代表第二个，后面的以此类推。“$$”表示缩小后的堆栈顶部。在上面的动作中，把对应两个表达式的值相加，弹出内容栈中的三个成员，然后把得到的和压入堆栈中。这样，保持分析栈和内容栈中的内容依然同步。
而
program:
program expr '\n' { printf("%d\n", $2); }
说明每当一行表达式结束时，打印出第二个栈值，即expr的值，完成字符运算。
四.后记
如果到这里能完全理解所述内容，对于lex和yacc就有些感觉了。后面文章会做进一步的深入。
Lex和Yacc应用教程(三).使用变量
草木瓜 20070512
一、序
早在两个月前就想对Lex和Yacc作系列的阐述，然而工作的事情实在太多，很难抽出空静下心去总结学习。不觉感慨国内工作环境恶劣，加班是家常便饭，整天基本都是在做一些简单大量的重复，甚至徒劳无用。
在《初识Lex》一文中主要从入门角度总结了Lex，《再识Lex和Yacc》一文在可以简单使用Lex情况基础，介绍了Lex和Yacc的算法理论，并说明如何将Lex和Yacc结合起来使用。
这里我们需要对Lex和Yacc使用方法做进一步研究，以备能理解后面会引入的语法树。
<本系列文章的地址：http://blog.csdn.net/liwei_cmg/category/207528.aspx>
本系列所有示例均在RedHat Linux 8测试通过。
二、示例
我们在以前的基础上，深入一步，设计一个简单的计算器，包含+,-,*,/四项操作，且支持()运算符，其中对值可以进行变量保存，并打印出内部的分析信息。
Lex文件全内容(lexya_b.l)：
---------------------------------------------
%{
#include <stdlib.h>
#include "lexya_b.tab.h"
void yyerror(char *);
void add_buff(char *);
extern char sBuff[10][20];
extern int iX;
extern int iY;
%}
%%
[a-z] { yylval = *yytext; add_buff(yytext); return VAR; }
[0-9]+ { yylval = atoi(yytext); add_buff(yytext); return INT; }
[-+()=*/] { yylval = *yytext; add_buff(yytext); return *yytext; }
[\n] { yylval = *yytext; iY=0;iX++; return *yytext; }
[\t] ;/* 去除空格 */
. yyerror("无效字符");
%%
void add_buff(char * buff) {
sBuff[iX][iY]=*buff; iY++;
}
int yywrap(void) {
return 1;
}
Yacc文件全内容(lexya_b.y)：
---------------------------------------------
%{
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
void debuginfo(char *, int *, char *);
void printinfo();
int sMem[256];
char sBuff[10][20]={0};
int iX=0;
int iY=0;
%}
%token INT VAR
%left '+' '-'
%left '*' '/'
%%
program:
program statement
|
;
statement:
expr { printf("%d\n",$1); }
| VAR '=' expr { debuginfo("=",yyvsp,"110"); sMem[$1]=$3; }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debuginfo("INT",yyvsp,"0"); $$ = $1; }
| VAR { debuginfo("VAR",yyvsp,"1"); $$ = sMem[$1]; }
| expr '*' expr { debuginfo("*",yyvsp,"010"); $$ = $1 * $3; }
| expr '/' expr { debuginfo("/",yyvsp,"010"); $$ = $1 / $3; }
| expr '+' expr { debuginfo("+",yyvsp,"010"); $$ = $1 + $3; }
| expr '-' expr { debuginfo("-",yyvsp,"010"); $$ = $1 - $3; }
| '(' expr ')' { debuginfo("()",yyvsp,"101"); $$ = $2; }
;
%%
void debuginfo(char * info,int * vsp, char * mark) {
/* */
printf("--RULE: %s \n", info);
int i=0;
int ilen=strlen(mark);
for(i=0;i>=1-ilen;i--) {
if(mark[ilen+i-1]=='1')
printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
else
printf("$%d %d \n", i+ilen, vsp[i]);
}
printinfo();
}
void printinfo() {
int i=0;
printf("--STATEMENT: \n");
/*
for(i=0;i<=iX;i++)
printf("%s \n",sBuff[i]);
*/
if(iY==0)
printf("%s \n",sBuff[iX-1]);
else
printf("%s \n",sBuff[iX]);
printf("\n");
}
void yyerror(char *s) {
printf("%s\n", s);
}
int main(void) {
yyparse();
return 0;
}
编译文件脚本(yacclex)全内容：
---------------------------------------------
rm lexya_$1.tab.c
rm lexya_$1.tab.h
rm lex.yy.c
bison -d lexya_$1.y
lex lexya_$1.l
gcc -g -o parser lex.yy.c lexya_$1.tab.c
待解释编译文本(input)全内容：
---------------------------------------------
a=4+2*(3-2-1)+6
b=1-10/(6+4)+8
c=a-b
a
b
c
命令行输入编译编译器：
./yacclex b
进文件进行解释：
./parser < input
10
8
2
文中成功了使用了变量，并且操作符运算优先级也没有问题。
其实细看过《Lex和Yacc应用方法(二).再识Yacc》一文后，理解上面的例子就很轻松了。
这里只是做了一些扩充变化：
1.增加了全局数组sMem来存放变量，不过变量名有限制，只支持单字符。
2.增加了全局数组sBuff存放分析过的语句
3.增加debuginfo打印堆栈信息
4.增加printinfo打印目前的分析语句
要进行内部分析，就需要剖析生成的c文件，对程序(parser)进行跟踪调试。
(注：Lex编译时加上d参数，会在程序解释时输出详细的调试信息。如：lex -d lexya_$1.l)
通过本示例再加上实际对lexya_b.tab.c的分析理解，会对lex，yacc理论有更进一步的理解。
四、增加支持的变量字符数
上面的例子只支持单字符的变量，想支持多字符，需要定义一全局变量如：
struct varIndex
{
int iValue;
char sMark[10];
};
同时打印信息加入对变量的显示，下面列出全部文件内容，比较简单，不再
附加说明。
头文件(userdef.h)
typedef struct {
int iValue;
char sMark[10];
} varIndex;
varIndex strMem[256];
Lex文件：
%{
#include <stdlib.h>
#include "userdef.h"
#include "lexya_c.tab.h"
void yyerror(char *);
void add_buff(char *);
void add_var(char *);
extern char sBuff[10][20];
extern int iBuffX;
extern int iBuffY;
extern varIndex strMem[256];
extern int iMaxIndex;
extern int iCurIndex;
%}
%%
[a-zA-Z][a-zA-Z0-9]* { add_var(yytext); yylval = iCurIndex; add_buff(yytext); return VAR; }
[0-9]+ { yylval = atoi(yytext); add_buff(yytext); return INT; }
[-+()=*/] { yylval = *yytext; add_buff(yytext); return *yytext; }
[\n] { yylval = *yytext; iBuffY=0;iBuffX++; return *yytext; }
[\t] ;/* 去除空格 */
. yyerror("无效字符");
%%
void add_buff(char * buff) {
strcat(sBuff[iBuffX],buff);
iBuffY+=strlen(buff);
}
void add_var(char *mark) {
if(iMaxIndex==0){
strcpy(strMem[0].sMark,mark);
iMaxIndex++;
iCurIndex=0;
return;
}
int i;
for(i=0;i<=iMaxIndex-1;i++) {
if(strcmp(strMem[i].sMark,mark)==0) {
iCurIndex=i;
return;
}
}
strcpy(strMem[iMaxIndex].sMark,mark);
iCurIndex=iMaxIndex;
iMaxIndex++;
}
int yywrap(void) {
return 1;
}
Yacc文件:
%{
#include <stdlib.h>
#include "userdef.h"
int yylex(void);
void yyerror(char *);
void debug_info(char *, int *, char *);
void stm_info();
extern varIndex strMem[256];
int iMaxIndex=0;
int iCurIndex=0;
char sBuff[10][20]={0};
int iBuffX=0;
int iBuffY=0;
%}
%token INT VAR
%left '+' '-'
%left '*' '/'
%%
program:
program statement
|
;
statement:
expr { printf("%d\n",$1); }
| VAR '=' expr { debug_info("=",yyvsp,"210"); strMem[$1].iValue=$3; }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debug_info("INT",yyvsp,"0"); $$ = $1; }
| VAR { debug_info("VAR",yyvsp,"2"); $$ = strMem[$1].iValue; }
| expr '*' expr { debug_info("*",yyvsp,"010"); $$ = $1 * $3; }
| expr '/' expr { debug_info("/",yyvsp,"010"); $$ = $1 / $3; }
| expr '+' expr { debug_info("+",yyvsp,"010"); $$ = $1 + $3; }
| expr '-' expr { debug_info("-",yyvsp,"010"); $$ = $1 - $3; }
| '(' expr ')' { debug_info("()",yyvsp,"101"); $$ = $2; }
;
%%
void debug_info(char * info,int * vsp, char * mark) {
/* */
printf("--RULE: %s \n", info);
int i=0;
int ilen=strlen(mark);
for(i=0;i>=1-ilen;i--) {
switch(mark[ilen+i-1]){
case '1':
printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
break;
case '0':
printf("$%d %d \n", i+ilen, vsp[i]);
break;
case '2':
printf("$%d %s %d\n", i+ilen, strMem[vsp[i]].sMark, strMem[vsp[i]].iValue);
break;
}
}
stm_info();
}
void stm_info() {
int i=0;
printf("--STATEMENT: \n");
/*
for(i=0;i<=iBuffX;i++)
printf("%s \n",sBuff[i]);
*/
if(iBuffY==0)
printf("%s \n",sBuff[iBuffX-1]);
else
printf("%s \n",sBuff[iBuffX]);
printf("\n");
}
void yyerror(char *s) {
printf("%s\n", s);
}
int main(void) {
yyparse();
return 0;
}
五、最后
本文说明文字较少，主要是前两篇说得已经够多了，对照代码应该比较容易理解，下一篇将着重介绍语法树的构建，也才是真正应用的开始。
Lex和Yacc应用方法(四).语法树的应用
草木瓜 20070515
一、序
不论什么语言，语法结构总是那几种，可以想象任何程序体都可以解释成一棵语法树，语法树的本质是递归，很显然Yacc文法的核心思想也是递归。本文就通过具体实例，使用Yacc构建递归的语法树来解决实际问题。
比较遗憾的是，在总结的过程中想表达清楚并不容易，估且三分言传，七分会意吧。关键在于个人去思考。
二、递归的一些思想
我们先看一个简化的C语言示例段：
i=0;
while(i<=10) {
print(i);
i=i+1;
}
print(i+i);
首先，我们将()+/* print while之类的组合称为expr(expression)，仅表示基本的表达式，可以理解通过递归可以进行任意的运算符组合。如下面每一行都可称为expr:
i=0
while(i<=10)
print(i)
i=i+1
print(i+i)
再把expr + ;的语句行称为stmt(statement)，表示一条语句的结束。把{}引起来的多个stmt
称为stmt_list。如此，原示例段可表示为：
stmt
expr stmt_list
stmt
这样显然不符合递归法则，倘若stmt也可由expr stmt_list组合，程序则可以递归到最顶级
stmt
stmt
stmt
这也要求yacc文法定义必须可以递归到最顶级，即如上所示。
三、内存结构
编译过程必须在内存中形成一定规则且可递归的树形结构，比较容易理解对每一语句stmt
需要构建一棵语法树。
以下是我们准备采用的语法树实际示例：
Graph 0:
[=]
|
|----|
| |
idx(i) c(0)
Graph 1:
while
|
|----------------|
| |
[<=] [;]
| |
|-----| |----------|
| | | |
idx(i) c(10) print [=]
| |
| |-------|
| | |
idx(i) idx(i) [+]
|
|----|
| |
idx(i) c(1)
Graph 2:
print
|
|
|
[+]
|
|-----|
| |
idx(i) idx(i)
细心查看以上三张图，会发现每个stmt即对应一张树形图，树结点包含三种类型：操作符
(如 + = ; )，变量索引(如 idx(i))和值(如 c(10) c(1) )。对于每个操作符，需要保证一
个可递归的规则。
四、具体实例
A. node.h <树结点的定义头文件>
/* 定义树结点的权举类型 */
typedef enum { TYPE_CONTENT, TYPE_INDEX, TYPE_OP } NodeEnum;
/* 操作符 */
typedef struct {
int name; /* 操作符名称 */
int num; /* 操作元个数 */
struct NodeTag * node[1]; /* 操作元地址 可扩展 */
} OpNode;
typedef struct NodeTag {
NodeEnum type; /* 树结点类型 */
/* Union 必须是最后一个成员 */
union {
int content; /* 内容 */
int index; /* 索引 */
OpNode op; /* 操作符对象 */
};
} Node;
extern int Var[26];
[说明] Node即为定义的树形结点，结点可以是三种类型(CONTENT,INDEX,OP)。结点
如果是操作符对象(OpNode)的话，结点可继续递归结点。操作符结点包括了名称，个
数和子结点三个要素，其中子结点可以为多个。
B.lexya_e.l <lex文件>
%{
#include <stdlib.h>
#include "node.h"
#include "lexya_e.tab.h"
void yyerror(char *);
%}
%%
[a-z] {
yylval.sIndex = *yytext -'a';
return VARIABLE;
}
[0-9]+ {
yylval.iValue = atoi(yytext);
return INTEGER;
}
[()<>=+*/;{}.] {
return *yytext;
}
">=" return GE;
"<=" return LE;
"==" return EQ;
"!=" return NE;
"&&" return AND;
"||" return OR;
"while" return WHILE;
"if" return IF;
"else" return ELSE;
"print" return PRINT;
[\t\n]+ ; /* 去除空格，回车 */
. printf("unknow symbol:[%s]\n",yytext);
%%
int yywrap(void) {
return 1;
}
[说明] 这里的Lex文件比较简单，没啥好说的。
C.lexya_e.y <yacc文件>
001 %{
002
003 #include <stdio.h>
004 #include <stdlib.h>
005 #include <stdarg.h>
006 #include "node.h"
007
008 /* 属性操作类型 */
009 Node *opr(int name, int num, ...);
010
011 Node *set_index(int value);
012 Node *set_content(int value);
013
014 void freeNode(Node *p);
015 int exeNode(Node *p);
016
017 int yylexeNode(void);
018 void yyerror(char *s);
019
020 int Var[26]; /* 变量数组 */
021
022 %}
023
024 %union {
025 int iValue; /* 变量值 */
026 char sIndex; /* 变量数组索引 */
027 Node *nPtr; /* 结点地址 */
028 };
029
030 %token <iValue> VARIABLE
031 %token <sIndex> INTEGER
032 %token WHILE IF PRINT
033 %nonassoc IFX
034 %nonassoc ELSE
035 %left AND OR GE LE EQ NE '>' '<'
036 %left '+' '-'
037 %left '*' '/'
038 %nonassoc UMINUS
039 %type <nPtr> stmt expr stmt_list
040 %%
041 program:
042 function { exit(0); }
043 ;
044 function:
045 function stmt { exeNode($2); freeNode($2); }
046 | /* NULL */
047 ;
048 stmt:
049 ';' { $$ = opr(';', 2, NULL, NULL); }
050 | expr ';' { $$ = $1; }
051 | PRINT expr ';' { $$ = opr(PRINT, 1, $2); }
052 | VARIABLE '=' expr ';' { $$ = opr('=', 2, set_index($1), $3); }
053 | WHILE '(' expr ')' stmt { $$ = opr(WHILE, 2, $3, $5); }
054 | IF '(' expr ')' stmt %prec IFX { $$ = opr(IF, 2, $3, $5); }
055 | IF '(' expr ')' stmt ELSE stmt %prec ELSE { $$ = opr(IF, 3, $3, $5, $7); }
056 | '{' stmt_list '}' { $$ = $2; }
057 ;
058 stmt_list:
059 stmt { $$ = $1; }
060 | stmt_list stmt { $$ = opr(';', 2, $1, $2); }
061 ;
062 expr:
063 INTEGER { $$ = set_content($1); }
064 | VARIABLE { $$ = set_index($1); }
065 | '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); }
066 | expr '+' expr { $$ = opr('+', 2, $1, $3); }
067 | expr '-' expr { $$ = opr('-', 2, $1, $3); }
068 | expr '*' expr { $$ = opr('*', 2, $1, $3); }
069 | expr '/' expr { $$ = opr('/', 2, $1, $3); }
070 | expr '<' expr { $$ = opr('<', 2, $1, $3); }
071 | expr '>' expr { $$ = opr('>', 2, $1, $3); }
072 | expr GE expr { $$ = opr(GE, 2, $1, $3); }
073 | expr LE expr { $$ = opr(LE, 2, $1, $3); }
074 | expr NE expr { $$ = opr(NE, 2, $1, $3); }
075 | expr EQ expr { $$ = opr(EQ, 2, $1, $3); }
076 | expr AND expr { $$ = opr(AND, 2, $1, $3); }
077 | expr OR expr { $$ = opr(OR, 2, $1, $3); }
078 | '(' expr ')' { $$ = $2; }
079 ;
080 %%
081 #define SIZE_OF_NODE ((char *)&p->content - (char *)p)
082
083 Node *set_content(int value) {
084
085 Node *p;
086
087 size_t sizeNode;
088 /* 分配结点空间 */
089 sizeNode = SIZE_OF_NODE + sizeof(int);
090
091 if ((p = malloc(sizeNode)) == NULL)
092 yyerror("out of memory");
093
094 /* 复制内容 */
095 p->type = TYPE_CONTENT;
096 p->content = value;
097
098 return p;
099
100 }
101
102 Node *set_index(int value) {
103
104 Node *p;
105 size_t sizeNode;
106 /* 分配结点空间 */
107 sizeNode = SIZE_OF_NODE + sizeof(int);
108
109 if ((p = malloc(sizeNode)) == NULL)
110 yyerror("out of memory");
111
112 /* 复制内容 */
113 p->type = TYPE_INDEX;
114 p->index = value;
115
116 return p;
117 }
118
119 Node *opr(int name, int num, ...) {
120
121 va_list valist;
122 Node *p;
123 size_t sizeNode;
124 int i;
125 /* 分配结点空间 */
126 sizeNode = SIZE_OF_NODE + sizeof(OpNode) + (num - 1) * sizeof(Node*);
127
128 if ((p = malloc(sizeNode)) == NULL)
129 yyerror("out of memory");
130
131 /* 复制内容 */
132
133 p->type = TYPE_OP;
134 p->op.name = name;
135 p->op.num = num;
136
137 va_start(valist, num);
138
139 for (i = 0; i < num; i++)
140 p->op.node[i] = va_arg(valist, Node*);
141
142 va_end(valist);
143 return p;
144 }
145 void freeNode(Node *p) {
146 int i;
147 if (!p) return;
148 if (p->type == TYPE_OP) {
149 for (i = 0; i < p->op.num; i++)
150 freeNode(p->op.node[i]);
151 }
152 free (p);
153 }
154 void yyerror(char *s) {
155 fprintf(stdout, "%s\n", s);
156 }
157 int main(void) {
158 yyparse();
159 return 0;
160 }
[说明] 这个文件是核心所在，大体分为Yacc预定义文法，BNF递归文法和扩展实现函数
三个部分。
Yacc预定义文法的解释：
(1).(024-031)(039)
%union {
int iValue; /* 变量值 */
char sIndex; /* 变量数组索引 */
Node *nPtr; /* 结点地址 */
};
%token <iValue> INTEGER
%token <sIndex> VARIABLE
(024-031)这一段扩充了yystype的内容，默认yystype只是int类型，编译之后会
生成如下代码：
#ifndef YYSTYPE
typedef union {
int iValue; /* 变量值 */
char sIndex; /* 变量数组索引 */
Node *nPtr; /* 结点地址 */
} yystype;
# define YYSTYPE yystype
# define YYSTYPE_IS_TRIVIAL 1
#endif
并将<iValue>与INTEGER，<sIndex>与VARIABLE绑定，表示对lex返回的值自动
进行类型转换。
(039)将<nPtr>与Union的指针类型绑定。
即在剖析器的内容栈中，常量、变量和节点都可以由yylval表示。yylval既可以是int,
char，也可以是Node *。具体可以查看lexya_e.tab.c生成文件部分，可有更深刻的
理解。(switch (yyn) 下面)
(2).(032-039)
这段方法主要定义了操作符的优先级。nonassoc，意味着没有依赖关系。它经常在连接
词中和 %prec一起使用，用于指定一个规则的优先级。如下面的规则存在IF ELSE的二义
性，需要使用nonassoc指定规则。054对应IFX，055对应ELSE，055高于054。
054 | IF '(' expr ')' stmt %prec IFX { $$ = opr(IF, 2, $3, $5); }
055 | IF '(' expr ')' stmt ELSE stmt %prec ELSE { $$ = opr(IF, 3, $3, $5, $7); }
(039)type的关键字语句，表示后面的返回值是<ptr>类型。
BNF递归文法(040-080)：
这个递归文法看起来容易，自个设计起来还是有点难度的，相关的递归思想可以参见本文
最前面的“递归的一些思想”。可以考虑一下(056)-(060)的语法定义。
扩展实现函数：
本例扩展了set_index,set_value两个赋值语句，其操作实质是在内存空间分配index
和value的两种树结点。opr这个扩展函数很重要，而且使用了动态参数，主要考虑操作
符的操作元个数是可变的，这个也与头文件“struct NodeTag * node[1];”的定义思
想一致。opr主要在内存空间中分配操作符相关的树结点。
set_index,set_value,opr从概念上是完全一致，目的就是在内存中构造一棵可递归的
语法树。
D.parser.c
#include <stdio.h>
#include "node.h"
#include "lexya_e.tab.h"
int exeNode(Node *p) {
if (!p) return 0;
switch(p->type) {
case TYPE_CONTENT: return p->content;
case TYPE_INDEX: return Var[p->index];
case TYPE_OP:
switch(p->op.name) {
case WHILE: while(exeNode(p->op.node[0]))exeNode(p->op.node[1]);
return 0;
case IF: if (exeNode(p->op.node[0]))
exeNode(p->op.node[1]);
else
if (p->op.num>2)
exeNode(p->op.node[2]);
return 0;
case PRINT: printf("%d\n", exeNode(p->op.node[0]));
return 0;
case ';': exeNode(p->op.node[0]);
return exeNode(p->op.node[1]);
case '=': return Var[p->op.node[0]->index] = exeNode(p->op.node[1]);
case UMINUS: return exeNode(p->op.node[0]);
case '+': return exeNode(p->op.node[0]) + exeNode(p->op.node[1]);
case '-': return exeNode(p->op.node[0]) - exeNode(p->op.node[1]);
case '*': return exeNode(p->op.node[0]) * exeNode(p->op.node[1]);
case '/': return exeNode(p->op.node[0]) / exeNode(p->op.node[1]);
case '<': return exeNode(p->op.node[0]) < exeNode(p->op.node[1]);
case '>': return exeNode(p->op.node[0]) > exeNode(p->op.node[1]);
case GE: return exeNode(p->op.node[0]) >= exeNode(p->op.node[1]);
case LE: return exeNode(p->op.node[0]) <= exeNode(p->op.node[1]);
case NE: return exeNode(p->op.node[0]) != exeNode(p->op.node[1]);
case EQ: return exeNode(p->op.node[0]) == exeNode(p->op.node[1]);
case AND: return exeNode(p->op.node[0]) && exeNode(p->op.node[1]);
case OR: return exeNode(p->op.node[0]) || exeNode(p->op.node[1]);
}
}
return 0;
}
这个文件是对语法树的解释分析。只包含一个递归函数exeNode。首先分树结点类型，
再根据操作符一一判定动作。
五、结束
bison -d lexya_e.y
lex lexya_e.l
gcc -g -o parser lex.yy.c lexya_e.tab.c parser.c
编译即可测试执行。
多说无益，个人感觉自已领会的东西才是最要的。本示例包含了一些C语法，不过也只是
一小部分，在后续的文章中将逐步扩展本例的功能，从而发掘yacc和lex的强大功能。
<注：本文示例参考Tom Niemann的《A Compact Guide to Lex & Yacc》
http://epaperpress.com/lexandyacc/index.html>
