草木瓜----Lex和Yacc教程

Lex和Yacc应用方法(一).初识Lex

草木瓜 20070301

Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler

编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分

析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，

入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。

一.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

9+8/3

10+2-2/2-2*5

这里有两个文件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

-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

命令行输入编译编译器：

./yacclex b

进文件进行解释：

./parser < input

文中成功了使用了变量，并且操作符运算优先级也没有问题。

其实细看过《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

这也要求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:

[+]

|-----|

| |

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的强大功能。

Lex和Yacc应用方法(五).再识语法树

草木瓜 20070524

一、序

在《Lex和Yacc应用教程(四).语法树》一文已对语法树有了初步的概念，本文主要目的

是巩固语法树的概念，并做进一步的扩展分析。闲说少说，首先给出完整示例，本例在Redhat Linux 9

下调试通过，可放心使用。

另外系列文章的标题，有的叫“lex和yacc应用方法”，有的叫“lex和yacc应用教程”,

还有的叫“lex和yacc使用教程”等等，概念都是一样的。之所以起这么多名字是便于大家通

过搜索引擎能迅速查到。

<本站文章难免有错误疏漏之处。Lex,Yacc系列文章 http://blog.csdn.net/liwei_cmg/category/207528.aspx>

二、示例全代码

本示例包括四个文件

node.h(头文件),lexya_e.l(lex文件),lexya_e.y(yacc文件),parser.c(外部分析文件)

--------------------------------------

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 {

float content; /* 内容 */

int index; /* 索引 */

OpNode op; /* 操作符对象 */

};

} Node;

struct VarIndex

{

float val;

char mark[10];

};

struct VarDefine

{

int index;

char * name;

};

#define USER_DEF_NUM 259 /* Yacc编译的保留字开始索引 */

#define MAX_VARS 100 /* 最多变量数 */

#define MAX_DEFS 20 /* 最多保留字数 */

#define MAX_BUFF_COLS 40 /* 分析语句最多行数 */

#define MAX_BUFF_ROWS 40 /* 分析语句每行最多字符数 */

extern struct VarIndex G_Var[MAX_VARS]; /* 存储的变量数组 */

extern struct VarDefine G_Def[MAX_DEFS]; /* 系统保留字变量 */

extern int G_iVarMaxIndex; /* 变量目前总数 */

extern int G_iVarCurIndex; /* 当前操作变量索引 */

extern char G_sBuff[MAX_BUFF_ROWS][MAX_BUFF_COLS]; /* 存储分析语句 */

extern int G_iBuffRowCount; /* 当前语句行数 */

extern int G_iBuffColCount; /* 当前语句列数 */

/* 是否打印调试信息的开关 */

// #define PARSE_DEBUG

--------------------------------------

B.lexya_e.l lex文件

#include <stdlib.h>

#include "node.h"

#include "lexya_e.tab.h"

struct VarDefine G_Def[MAX_DEFS]; /* 存储的变量数组 */

char G_sBuff[MAX_BUFF_ROWS][MAX_BUFF_COLS]; /* 存储分析语句 */

int G_iBuffRowCount=0; /* 当前语句行数 */

int G_iBuffColCount=0; /* 当前语句列数 */

extern void add_var(char *); /* 在内存中添加变量 */

void add_buff(char *); /* 在内存中添加语句 */

void yyerror(char *);

/* 使用代变量表示任意字符 */

any .

#{any}*[\n] {

add_buff(yytext);

G_iBuffColCount=0;

G_iBuffRowCount++;

} /* 单行注释 */

[\n] {

G_iBuffColCount=0;

G_iBuffRowCount++;

} /* 回车 */

"for" {

yylval.index = FOR - USER_DEF_NUM;

G_Def[yylval.index].name="for";

add_buff(yytext);

return FOR;

}

"while" {

yylval.index = WHILE -USER_DEF_NUM;

G_Def[yylval.index].name="while";

add_buff(yytext);

return WHILE;

}

"if" {

yylval.index = IF - USER_DEF_NUM;

G_Def[yylval.index].name="if";

add_buff(yytext);

return IF;

}

"else" {

yylval.index = ELSE - USER_DEF_NUM;

G_Def[yylval.index].name="else";

add_buff(yytext);

return ELSE;

}

"print" {

yylval.index = PRINT -USER_DEF_NUM ;

G_Def[yylval.index].name="print";

add_buff(yytext);

return PRINT;

}

[a-zA-Z][a-zA-Z0-9]* {

add_var(yytext);

yylval.index = G_iVarCurIndex;

add_buff(yytext);

return VARIABLE;

}

[0-9]+ {

yylval.val = atof(yytext);

add_buff(yytext);

return NUMBER;

}

[0-9]*\.[0-9]+ {

yylval.val = atof(yytext);

add_buff(yytext);

return NUMBER;

}

"++" { yylval.index = ADD_T-USER_DEF_NUM; G_Def[yylval.index].name="++"; G_Def[yylval.index+1].name="++"; add_buff(yytext); return ADD_T; }

"--" { yylval.index = MUS_T-USER_DEF_NUM; G_Def[yylval.index].name="--"; G_Def[yylval.index+1].name="++"; add_buff(yytext); return MUS_T; }

">=" { yylval.index = GE - USER_DEF_NUM; G_Def[yylval.index].name=">="; add_buff(yytext); return GE;}

"<=" { yylval.index = LE - USER_DEF_NUM; G_Def[yylval.index].name="<="; add_buff(yytext); return LE;}

"==" { yylval.index = EQ - USER_DEF_NUM; G_Def[yylval.index].name="=="; add_buff(yytext); return EQ;}

"!=" { yylval.index = NE - USER_DEF_NUM; G_Def[yylval.index].name="!="; add_buff(yytext); return NE;}

"&&" { yylval.index = AND - USER_DEF_NUM; G_Def[yylval.index].name="&&"; add_buff(yytext); return AND;}

"||" { yylval.index = OR - USER_DEF_NUM; G_Def[yylval.index].name="||"; add_buff(yytext); return OR; }

[()<>=+\-*/;{}.] {

yylval.index = *yytext; /* 存储运算符 */

add_buff(yytext);

return *yytext;

}

[\t] { add_buff(yytext); } /* 去除TAB */

[ ] { add_buff(yytext); } /* 去除空格 */

{any} { printf("Ignore Unknow Symbol:[%s]\n",yytext); }

void add_buff(char * buff) {

strcat(G_sBuff[G_iBuffRowCount], buff);

G_iBuffColCount=G_iBuffColCount+strlen(buff);

}

int yywrap(void) {

return 1;

}

--------------------------------------

C.lexya_e.y yacc文件

#include <stdio.h>

#include <stdlib.h>

#include <stdarg.h>

#include "node.h"

/* 属性操作类型 */

Node *opr(int name, int num, ...);

Node *set_index(int value);

Node *set_content(float value);

/* 树结点操作 */

void NodeFree(Node *p);

float NodeExecute(Node *p);

typedef union {

float val; /* 变量值 */

int index; /* 用于存放变量数组索引或一元操作符值或多元操作符索引 */

Node *node; /* 结点地址 */

}yystype;

#define YYSTYPE yystype

/* 打印分析调试信息 */

void debug_vsp(YYSTYPE , char * ,YYSTYPE *, char * );

void print_stmt();

/* 在内存中添加变量 */

void add_var(char *);

int G_iVarMaxIndex = 0; /* 变量最大个数 */

int G_iVarCurIndex = -1; /* 变量当前索引 */

struct VarIndex G_Var[MAX_VARS]; /* 变量内存数组 */

void yyerror(char *s);

%union {

float val; /* 变量值 */

int index; /* 变量数组索引 */

Node *node; /* 结点地址 */

};

%token <val> NUMBER

%token <index> VARIABLE

%token PRINT

%token FOR WHILE

%nonassoc IF

%nonassoc ELSE

%left AND OR

%left GE LE EQ NE '>' '<'

%left '+' '-'

%left '*' '/'

%left ADD_T ADD_TT MUS_T MUS_TT

%nonassoc UMINUS

%type <node> stmt stmt_list expr_set expr_setself expr_comp expr

program:

function { exit(0); }

;

function:

function stmt { NodeExecute($2); NodeFree($2); }

| /* NULL */

;

stmt:

';' { $$ = opr(';', 2, NULL, NULL); debug_vsp(yyval,";",yyvsp,"0"); }

| expr_set ';' { $$ = $1; debug_vsp(yyval,"es;",yyvsp,"01"); }

| PRINT expr ';' { $$ = opr(PRINT, 1, $2); debug_vsp(yyval,"p(e);",yyvsp,"401"); }

| PRINT expr_set ';' { $$ = opr(PRINT, 1, $2); debug_vsp(yyval,"p(es);",yyvsp,"401"); }

| FOR '(' expr_set ';' expr_comp ';' expr_set ')' stmt { $$ = opr(FOR, 4, $3, $5, $7, $9); debug_vsp(yyval,"for(es;ec;es) st",yyvsp,"410101010"); }

| WHILE '(' expr_comp ')' stmt { $$ = opr(WHILE, 2, $3, $5); debug_vsp(yyval,"while(ec) st",yyvsp,"41010"); }

| IF '(' expr_comp ')' stmt %prec IF { $$ = opr(IF, 2, $3, $5); debug_vsp(yyval,"if(ec) st",yyvsp,"41010"); }

| IF '(' expr_comp ')' stmt ELSE stmt %prec ELSE { $$ = opr(IF, 3, $3, $5, $7); debug_vsp(yyval,"if(ec)else st",yyvsp,"4101040"); }

| '{' stmt_list '}' { $$ = $2; debug_vsp(yyval,"{stl}",yyvsp,"101"); }

;

stmt_list:

stmt { $$ = $1; debug_vsp(yyval,"st",yyvsp,"0"); }

| stmt_list stmt { $$ = opr(';', 2, $1, $2); debug_vsp(yyval,"stl st",yyvsp,"00"); }

;

expr_set:

VARIABLE '=' expr { $$ = opr('=', 2, set_index($1), $3); debug_vsp(yyval,"v=e",yyvsp,"210"); }

| VARIABLE '=' expr_setself { $$ = opr('=', 2, set_index($1), $3); debug_vsp(yyval,"v=ess",yyvsp,"210"); }

| expr_setself

;

expr_setself:

ADD_T VARIABLE { $$ = opr(ADD_T, 1, set_index($2)); debug_vsp(yyval,"++v",yyvsp,"42"); }

| MUS_T VARIABLE { $$ = opr(MUS_T, 1, set_index($2)); debug_vsp(yyval,"--v",yyvsp,"42"); }

| VARIABLE ADD_T { $$ = opr(ADD_TT, 1, set_index($1)); debug_vsp(yyval,"v++",yyvsp,"24"); }

| VARIABLE MUS_T { $$ = opr(MUS_TT, 1, set_index($1)); debug_vsp(yyval,"v--",yyvsp,"24"); }

| '(' expr_setself ')' { $$ = $2; debug_vsp(yyval,"(ess)",yyvsp,"101"); }

;

expr_comp:

expr '<' expr { $$ = opr('<', 2, $1, $3); debug_vsp(yyval,"e<e",yyvsp,"010"); }

| expr '>' expr { $$ = opr('>', 2, $1, $3); debug_vsp(yyval,"e>e",yyvsp,"010"); }

| expr GE expr { $$ = opr(GE, 2, $1, $3); debug_vsp(yyval,"e>=e",yyvsp,"040"); }

| expr LE expr { $$ = opr(LE, 2, $1, $3); debug_vsp(yyval,"e<=e",yyvsp,"040"); }

| expr NE expr { $$ = opr(NE, 2, $1, $3); debug_vsp(yyval,"e!=e",yyvsp,"040"); }

| expr EQ expr { $$ = opr(EQ, 2, $1, $3); debug_vsp(yyval,"e==e",yyvsp,"040"); }

| expr_comp AND expr_comp { $$ = opr(AND, 2, $1, $3); debug_vsp(yyval,"ec&&ec",yyvsp,"040"); }

| expr_comp OR expr_comp { $$ = opr(OR, 2, $1, $3); debug_vsp(yyval,"ec||ec",yyvsp,"040"); }

| '(' expr_comp ')' { $$ = $2; debug_vsp(yyval,"(ec)",yyvsp,"101"); }

;

expr:

NUMBER { $$ = set_content($1); debug_vsp(yyval,"f",yyvsp,"3"); }

| VARIABLE { $$ = set_index($1); debug_vsp(yyval,"v",yyvsp,"2"); }

| '-' NUMBER %prec UMINUS { $$ = set_content(-$2); debug_vsp(yyval,"-e", yyvsp,"13"); }

| expr '+' expr { $$ = opr('+', 2, $1, $3); debug_vsp(yyval,"e+e",yyvsp,"010"); }

| expr '-' expr { $$ = opr('-', 2, $1, $3); debug_vsp(yyval,"e-e",yyvsp,"010"); }

| expr '*' expr { $$ = opr('*', 2, $1, $3); debug_vsp(yyval,"e*e",yyvsp,"010"); }

| expr '/' expr { $$ = opr('/', 2, $1, $3); debug_vsp(yyval,"e/e",yyvsp,"010"); }

| '(' expr ')' { $$ = $2; debug_vsp(yyval,"(e)",yyvsp,"101"); }

;

//| '(' expr error { $$ = $2; printf("ERROR"); exit(0); }

#define SIZE_OF_NODE ((char *)&p->content - (char *)p)

Node *set_content(float value) {

Node *p;

size_t sizeNode;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(float);

if ((p = malloc(sizeNode)) == NULL)

yyerror("out of memory");

/* 复制内容 */

p->type = TYPE_CONTENT;

p->content = value;

return p;

}

Node *set_index(int value) {

Node *p;

size_t sizeNode;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(int);

if ((p = malloc(sizeNode)) == NULL)

yyerror("out of memory");

/* 复制内容 */

p->type = TYPE_INDEX;

p->index = value;

return p;

}

Node *opr(int name, int num, ...) {

va_list valist;

Node *p;

size_t sizeNode;

int i;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(OpNode) + (num - 1) * sizeof(Node*);

if ((p = malloc(sizeNode)) == NULL)

yyerror("out of memory");

/* 复制内容 */

p->type = TYPE_OP;

p->op.name = name;

p->op.num = num;

va_start(valist, num);

for (i = 0; i < num; i++)

p->op.node[i] = va_arg(valist, Node*);

va_end(valist);

return p;

}

/**/

void debug_vsp(YYSTYPE yval, char * info, YYSTYPE * vsp, char * mark) {

#ifdef PARSE_DEBUG

printf("\n -RULE 0x%x %s \n ", yval.node, info );

int i;

int ilen=strlen(mark);

for(i=1-ilen;i<=0;i++) {

switch(mark[ilen+i-1]){

case '0':

printf(" [ 0x%x ",vsp[i].node);//「」

switch(vsp[i].node->type) {

case TYPE_CONTENT:

printf("%g ] ",vsp[i].node->content);

break;

case TYPE_INDEX:

printf("%s ] ",G_Var[vsp[i].node->index].mark);

break;

case TYPE_OP:

if(vsp[i].node->op.name<USER_DEF_NUM)

printf("%c ] ",vsp[i].node->op.name);

else

printf("%s ] ",G_Def[vsp[i].node->op.name-USER_DEF_NUM].name);

break;

}

break;

case '1':

printf(" %c ",vsp[i].index); /* 打印运算符 */

break;

case '2':

printf(" %s ",G_Var[vsp[i].index].mark);

break;

case '3':

printf(" %g ",vsp[i].val);

break;

case '4':

printf(" %s ",G_Def[vsp[i].index].name);

break;

}

printf("\n");

print_stmt();

#endif

}

void add_var(char *mark) {

if(G_iVarMaxIndex==0){

strcpy(G_Var[0].mark,mark);

G_iVarMaxIndex++;

G_iVarCurIndex=0;

return;

}

int i;

for(i=0;i<=G_iVarMaxIndex-1;i++) {

if(strcmp(G_Var[i].mark,mark)==0) {

G_iVarCurIndex=i;

return;

}

strcpy(G_Var[G_iVarMaxIndex].mark,mark);

G_iVarCurIndex=G_iVarMaxIndex;

G_iVarMaxIndex++;

}

void print_stmt() {

printf(" -STMT: \n");

int i;

for(i=0;i<=G_iBuffRowCount;i++)

printf("%s \n",G_sBuff[i]);

if(G_iBuffColCount==0)

printf(" %s \n",G_sBuff[G_iBuffRowCount-1]);

else

printf(" %s \n",G_sBuff[G_iBuffRowCount]);

printf("\n");

}

void NodeFree(Node *p) {

int i;

if (!p) return;

if (p->type == TYPE_OP) {

for (i = 0; i < p->op.num; i++)

NodeFree(p->op.node[i]);

}

free (p);

}

void yyerror(char *s) {

//fprintf(stdout, "%s\n", s);

printf("<Parser Error> Line %d ,Col %d \n",G_iBuffRowCount+1,G_iBuffColCount+1);

printf(" %s\n",G_sBuff[G_iBuffRowCount]);

}

int main(void) {

yyparse();

return 0;

}

--------------------------------------

D. parser.c(外部分析文件)

#include <stdio.h>

#include "node.h"

#include "lexya_e.tab.h"

float NodeExecute(Node *p) {

if (!p) return 0;

switch(p->type) {

case TYPE_CONTENT: return p->content;

case TYPE_INDEX: return G_Var[p->index].val;

case TYPE_OP:

switch(p->op.name) {

case WHILE: while(NodeExecute(p->op.node[0]))NodeExecute(p->op.node[1]);

return 0;

case FOR: NodeExecute(p->op.node[0]);

while(NodeExecute(p->op.node[1])) {

NodeExecute(p->op.node[3]);

NodeExecute(p->op.node[2]);

}

return 0;

case IF: if (NodeExecute(p->op.node[0]))

NodeExecute(p->op.node[1]);

else

if (p->op.num>2)

NodeExecute(p->op.node[2]);

return 0;

case PRINT: printf("%g\n", NodeExecute(p->op.node[0]));

return 0;

case ';': NodeExecute(p->op.node[0]);

return NodeExecute(p->op.node[1]);

case '=': return G_Var[p->op.node[0]->index].val = NodeExecute(p->op.node[1]);

case UMINUS: return NodeExecute(p->op.node[0]);

case '+': return NodeExecute(p->op.node[0]) + NodeExecute(p->op.node[1]);

case '-': return NodeExecute(p->op.node[0]) - NodeExecute(p->op.node[1]);

case '*': return NodeExecute(p->op.node[0]) * NodeExecute(p->op.node[1]);

case '/': return NodeExecute(p->op.node[0]) / NodeExecute(p->op.node[1]);

case '<': return NodeExecute(p->op.node[0]) < NodeExecute(p->op.node[1]);

case '>': return NodeExecute(p->op.node[0]) > NodeExecute(p->op.node[1]);

case GE: return NodeExecute(p->op.node[0]) >= NodeExecute(p->op.node[1]);

case LE: return NodeExecute(p->op.node[0]) <= NodeExecute(p->op.node[1]);

case NE: return NodeExecute(p->op.node[0]) != NodeExecute(p->op.node[1]);

case EQ: return NodeExecute(p->op.node[0]) == NodeExecute(p->op.node[1]);

case AND: return NodeExecute(p->op.node[0]) && NodeExecute(p->op.node[1]);

case OR: return NodeExecute(p->op.node[0]) || NodeExecute(p->op.node[1]);

case ADD_T: return ++G_Var[p->op.node[0]->index].val;

case MUS_T: return --G_Var[p->op.node[0]->index].val;

case ADD_TT: return G_Var[p->op.node[0]->index].val++;

case MUS_TT: return G_Var[p->op.node[0]->index].val--;

}

return 0;

}

三、示例功能说明

以上示例显然是根据《Lex和Yacc应用教程(四).语法树》文中的示例扩展而来。主要演示

C语言类似的语法编译方法。支持的功能如下：

1. 支持整型和浮点型

2. 支持变量存储，变量名可为多个字符

3. 支持+-*/()=运算法则

4. 支持负数及负数运算

5. 支持变量的自加(++)和自减运算(--)，区分前自加减和后自加减

6. 支持print打印值和变量

7. 支持for while if else控制结构，并支持控制结构的嵌套

8. 支持>= <= != ==四种比较运算

9. 支持&& ||的复合比较运算

10. 支持对空格和TAB的忽略处理

11. 支持#的单行注释

12. 支持{}多重组合

13. 支持编译错误的具体显示

14. 支持编译过程的变量堆栈信息打印，便于调试分析

15. 支持保留字的存储显示。

16. 支持语法树打印(将在下一篇文章着重说明)

示例文件:

k=9;

if((1>1)||(-9>-1))

for(i=0;i<=9;i=i+1)

print(i);

else

if(3>1&&2>1) {

for(j=-1.1;j<=3;j++)

print(j);

for(jdd=1;jdd<=3;++jdd)

print(jdd);

while(k<=9) {

print(k++);

print(++k);

}

#test

关闭调试信息的输出：

-1.1

-0.1

0.9

1.9

2.9

四、思路分析

示例已经包括了一些注释，这里只对一些难点做些说明。

1.定义的规则和递归的语法树

我们第一步需要划分数值(1,2.2,99 ...)和变量(ab,d)的概念。即lex文件中的

NUMBER和VARIABLE。然后划分一元运算符，多元运算符和保留字。一元运算符可以用

int来表示，多元必须依靠token去标记。

这里要注意的是，使用了代变量any，为得是成功描述#{any}*[\n]这个规则，否

则是拼不出合法规则符的。

Lex的规则划分难度在于逻辑优先级，这个也在于自已把握，总的依据是复杂规则

在前，简单规则在后。

有了Lex的规则定义，就可以进行语法的递归划分。如下图：

program #未做定义表示整个文件的内容

function #未做定义表示整个文件的内容可有多个stmt组成

stmt #包含赋值，打印，分支的组合语句，须以;或者{}结尾

expr_set #赋值句句

| stmt_list #多个stmt

| | ... #其他打印分支语句

expr_setself stmt |

| |

expr expr_set expr_comp expr

| |

expr_setself expr

expr

想用简单图描述出复杂的递归思路，还是比较难。下面逐一进行补充说明。

expr设计用于基本的数值运算，并可以无限扩展递归，表示了“普通运算表达式”的

所有可能。

expr_comp设计用于“普通运算表达式”的比较，对于&& ||支持无限扩展递归，包括

了大部分的比较运算可能。

expr_setself设计用于“变量自身加减”，只支持()形式的递归

expr_set设计用于“赋值运算”，即两种可能，一是将“普通运算表达式”结果赋值

给变量，另一是将“变量自身加减”结果赋值。

stmt其实就是大杂烩，融合了多种保留字的运算法则。stmt将随着功能扩展不断细分。

stmt_list和stmt用了一个循环递归，但不是死循环，因为BNF范式本身就是有序的，

归并顺序自顶而上，自复杂至简单，归并后的规则会越来越少。递归的方向是有序的，就

不存在死循环的问题。

2.构造内存中的语法树

这部分内容在上文已有些许说明。即定义一个Union保存三种类型的树结点，对每种类

型的树结点提供可递归的规则。yacc文件中定义的各类动作便是为了构造内存的语法树。

总体概念是利用lex,yacc解析文件，同时构造了一棵完整的语法树，在归并到stmt时，

进行遍历处理。至于每步的操作细节可结合打印信息和语法树进行全面分析。

3.调试分析信息的打印

系统定义了G_sBuff存储已分析的字符，G_Var存储所有变量，G_Def存储所有保留字。

在yacc的每步归并规则中，通过debug_vsp和预定义的文法规则打印vsp的堆栈信息。对于

特殊信息，须查找全局内存变量。

调试信息需要lex和yacc配合起来实现，需要提出的是yystype的index是一值多用，

可以通过gdb跟踪调试，加深理解。

4.前自加减和后自加减

这个例子其实对++做了两个token，并在实现操作中直接使用C的规则。

五、重要提示

1.写C的时候，要严防内存越界。本例大多通过宏定义，定义了一些有界的数组，一旦出现

字符越界会造成奇怪的错误，而且很难调试发现。换句话说，一旦遇到奇怪的问题，首先

想到得是内存越界。写本例的自加自减功能时，忽略了MAX_DEFS(当初为10)，遇到ADD_T

MUS_T，数值运算总是出错，在打印信息中也发现乱码，G_Var无缘无故被写，逐步跟踪调

试半天，也没有发现具体问题，后来最终发现是G_Def越界，写脏了G_Var。将MAX_DEFS改

为20即可。

2.对于不能理解的概念，必须单步跟踪调试，这是最为快捷的解决方法。本例需要重点理解

opr的内存构造和NodeExecute执行过程。

六、结束

这篇文章的示例已是初步成形了，具备了一定的应用价值，但是与C语言的编译体系相比仍

有相当大的距离，更不用说编译优化了。

随着对lex yacc的研究深入，会逐渐发现这套理论的强大和精妙所在。lex,yacc比较原始，

也只有原始才是真实的。研究计算机就需要从0开始。

在下篇文章中将详细介绍语法树的打印。

Lex和Yacc应用方法(六).语法树打印

草木瓜 20070525

一、序

没有直观的语法树显示界面，理解前面两篇文章会比较难一些。(语法树的示例见

《Lex和Yacc应用教程(四).语法树的应用》) 其实语法树显示程序在Tom Niemann的

《A Compact Guide to Lex & Yacc》文中已有完整的示例，不过我很不喜欢，也许

是无法适应别人的代码习惯吧，这里针对《Lex和Yacc应用方法(五).再识语法树》，

完全重写了打印语法树的程序代码。我不敢说算法有多高明，起码十分便于理解和掌握。

<注：本站文章难免有错误疏漏之处。Lex,Yacc系列文章 http://blog.csdn.net/liwei_cmg/category/207528.aspx>

二、示例代码

老方法，先给出测试通过的完整代码。

liwei.c

001 #include <stdio.h>

002 #include <string.h>

003 #include "node.h"

004 #include "lexya_e.tab.h"

005

006 /* 节点最大文本宽度 */

007 #define MAX_NODE_TEXT_LEN 10

008 /* 节点最大子节点个数 */

009 #define MAX_SUBNODE_COUNT 5

010

011 /* 节点宽度 */

012 #define NODE_WIDTH 4

013

014 #define MAX_NODE_COUNT 100

015

016 /* 排序后树结点 */

017 #define MAX_TREE_WIDTH 20

018 #define MAX_TREE_DEEP 10

019

020

021 /* 树结点图信息 */

022 struct NodePoint {

023

024 int x; /* 标准坐标X */

025 int y; /* 标准坐标Y */

026

027 char text[MAX_NODE_TEXT_LEN]; /* 显示内容 */

028 int textoffset1;

029 int textoffset2;

030

031 int parent; /* 父结点索引 */

032 int idx; /* 当前结点索引 */

033

034 Node * node; /* 实际内存树节点 */

035

036 int oppx; /* 相对坐标 */

037 int oppx_mid;/* 相对坐标中值 */

038

039 int childnum; /* 子结点个数 */

040 int child[MAX_SUBNODE_COUNT]; /* 子结点索引 */

041

042 };

043

044 struct NodePoint G_TreeNodePoint[MAX_NODE_COUNT]; /* 树结点全局全量 */

045

046 int G_iNodeCount; //存储树结点个数

047 int G_iNodeParent;//存储树的父结点

048

049 struct NodePoint * G_pTreeNodeOrder[MAX_TREE_DEEP][MAX_TREE_WIDTH]; /* 树结点按层次的排序数组 */

050 int G_iTreeNodeOrderCount[MAX_TREE_DEEP]; /* 每层树结点个数 */

051

052 int G_iDeepCount; /* 层次深度 */

053 int G_iMinNodeXValue; /* 树结点最小x值 */

054 int G_iGraphNum=-1; /* 图个数 */

055

056 /* 函数定义 */

057

058 void GraphNode(Node *, int, int, int);

059 void GraphNode_Set(int, int, int, char *, Node *);

060 void GraphNode_PrintVars();

061

062 void GraphNode_Order();

063 void GraphNode_Adjust();

064 void GraphNode_FillPos();

065

066 void GraphNode_Print();

067

068 struct NodePoint * NodeFind(struct NodePoint *, struct NodePoint *);

069 void NodeAdjust(struct NodePoint *, int tmp);

070

071 void PrintInfo(int, char *);

072 void InitVars();

073

074 int GetOffset(int, int, int);

075

076 char * itoa(int,char*);

077

078 /* 供内部调用函数 */

079 int NodeExecute(Node *p) {

080

081 G_iNodeCount=-1;

082 G_iNodeParent=-1;

083 G_iMinNodeXValue=0;

084

085 InitVars();

086

087 GraphNode(p, 0, 0, G_iNodeParent);

088

089 GraphNode_Order();

090 GraphNode_PrintVars();

091 GraphNode_Adjust();

092 GraphNode_FillPos();

093 GraphNode_PrintVars();

094

095 GraphNode_Print();

096

097 return 0;

098 }

099

100 /* 主递归函数，用于填充全局变量值 */

101 void GraphNode(Node *p, int xoffset, int yoffset, int parent) {

102

103 char sWord[MAX_NODE_TEXT_LEN];

104 char *sNodeText;

105 int i;

106

107 G_iNodeCount++;

108

109 if(parent!=-1) {

110 G_TreeNodePoint[parent].child[G_TreeNodePoint[parent].childnum]=G_iNodeCount;

111 G_TreeNodePoint[parent].childnum++;

112 }

113

114 switch(p->type) {

115

116 case TYPE_CONTENT:

117 sprintf (sWord, "c(%g)", p->content);

118 sNodeText = sWord;

119 GraphNode_Set (xoffset, yoffset, parent, sNodeText, p);

120 break;

121

122 case TYPE_INDEX:

123 sprintf (sWord, "idx(%s)",G_Var[p->index].mark);

124 sNodeText = sWord;

125 GraphNode_Set (xoffset, yoffset, parent, sNodeText, p);

126 break;

127

128 case TYPE_OP:

129 switch(p->op.name){

130 case WHILE: sNodeText = "while"; break;

131 case IF: sNodeText = "if"; break;

132 case FOR: sNodeText = "for"; break;

133 case PRINT: sNodeText = "print"; break;

134 case ';': sNodeText = "[;]"; break;

135 case '=': sNodeText = "[=]"; break;

136 case UMINUS: sNodeText = "[_]"; break;

137 case '+': sNodeText = "[+]"; break;

138 case '-': sNodeText = "[-]"; break;

139 case '*': sNodeText = "[*]"; break;

140 case '/': sNodeText = "[/]"; break;

141 case '<': sNodeText = "[<]"; break;

142 case '>': sNodeText = "[>]"; break;

143 case GE: sNodeText = "[>=]"; break;

144 case LE: sNodeText = "[<=]"; break;

145 case NE: sNodeText = "[!=]"; break;

146 case EQ: sNodeText = "[==]"; break;

147 case AND: sNodeText = "[&&]"; break;

148 case OR: sNodeText = "[||]"; break;

149 case ADD_T: sNodeText = "[++v]"; break;

150 case MUS_T: sNodeText = "[--v]"; break;

151 case ADD_TT: sNodeText = "[v++]"; break;

152 case MUS_TT: sNodeText = "[v--]"; break;

153

154 }

155 GraphNode_Set (xoffset, yoffset, parent, sNodeText, p);

156

157 for (i=0; i<p->op.num; i++) {

158 GraphNode(p->op.node[i], GetOffset(p->op.num,i+1,2), yoffset+1, GetNodeIndex(p));

159 }

160 break;

161 }

162

163 }

164

165 /* 树结点赋值函数 */

166 void GraphNode_Set(int xoffset, int yoffset, int parent, char * text, Node * p ) {

167

168 int iBaseValue;

169

170 if(parent<=-1)

171 iBaseValue=0;

172 else

173 iBaseValue=G_TreeNodePoint[parent].x;

174

175 G_TreeNodePoint[G_iNodeCount].x = (iBaseValue + xoffset) ;

176 G_TreeNodePoint[G_iNodeCount].y = yoffset;

177

178 strcpy(G_TreeNodePoint[G_iNodeCount].text, text);

179

180 iBaseValue = strlen(text);

181 if(iBaseValue&1) {

182 G_TreeNodePoint[G_iNodeCount].textoffset1 = strlen(text)/2 ;

183 G_TreeNodePoint[G_iNodeCount].textoffset2 = strlen(text) - G_TreeNodePoint[G_iNodeCount].textoffset1 ;

184 }

185 else {

186 G_TreeNodePoint[G_iNodeCount].textoffset1 = strlen(text)/2 - 1;

187 G_TreeNodePoint[G_iNodeCount].textoffset2 = strlen(text) - G_TreeNodePoint[G_iNodeCount].textoffset1 ;

188 }

189

190 G_TreeNodePoint[G_iNodeCount].parent = parent;

191 G_TreeNodePoint[G_iNodeCount].idx = G_iNodeCount;

192 G_TreeNodePoint[G_iNodeCount].node = p;

193

194 G_TreeNodePoint[G_iNodeCount].oppx = 0;

195 G_TreeNodePoint[G_iNodeCount].oppx_mid = 0;

196

197 G_TreeNodePoint[G_iNodeCount].child[0] = 0;

198 G_TreeNodePoint[G_iNodeCount].childnum = 0;

199

200 /* 记录最小值 */

201 if(G_TreeNodePoint[G_iNodeCount].x<G_iMinNodeXValue)G_iMinNodeXValue=G_TreeNodePoint[G_iNodeCount].x;

202

203

204 }

205

206 /* 根据树结点层次排序 */

207 void GraphNode_Order() {

208

209 int i;

210 int iDeep;

211

212 G_iDeepCount=-1;

213

214 for(i=0;i<=G_iNodeCount;i++) {

215 G_TreeNodePoint[i].x = G_TreeNodePoint[i].x - G_iMinNodeXValue + 1;

216 iDeep=G_TreeNodePoint[i].y;

217 G_iTreeNodeOrderCount[iDeep]++;

218 G_pTreeNodeOrder[iDeep][G_iTreeNodeOrderCount[iDeep]]=&G_TreeNodePoint[i];

219 if(iDeep>G_iDeepCount)G_iDeepCount=iDeep;

220 }

221

222 }

223

224 /* 填充树结点真实坐标，相对坐标 */

225 void GraphNode_FillPos() {

226

227 int iInt;

228 int iBlank;

229 int idx;

230 int i,j;

231

232 for(j=0;j<=G_iDeepCount;j++) {

233 iBlank = 0;

234 for(i=0;i<=G_iTreeNodeOrderCount[j];i++) {

235 idx=G_pTreeNodeOrder[j][i]->idx;

236 if(i!=0) {

237 iInt = (G_TreeNodePoint[idx].x - G_TreeNodePoint[G_pTreeNodeOrder[j][i-1]->idx].x) * NODE_WIDTH ;

238 iBlank = iInt - G_TreeNodePoint[idx].textoffset1 - G_TreeNodePoint[G_pTreeNodeOrder[j][i-1]->idx].textoffset2;

239 }

240 else {

241 iInt = (G_TreeNodePoint[idx].x) * NODE_WIDTH ;

242 iBlank = iInt - G_TreeNodePoint[idx].textoffset1;

243 }

244 G_TreeNodePoint[idx].oppx = iInt ;

245 G_TreeNodePoint[idx].oppx_mid = iBlank ;

246 }

247 }

248

249 }

250

251 /* 调整树结点位置 */

252 void GraphNode_Adjust() {

253

254 int i,j;

255 int tmp;

256

257 for(i=G_iDeepCount;i>=0;i--)

258

259 for(j=0;j<=G_iTreeNodeOrderCount[i];j++)

260

261 if(j!=G_iTreeNodeOrderCount[i]) {

262

263 if(j==0) {

264 tmp = G_pTreeNodeOrder[i][j]->textoffset1 / NODE_WIDTH ;

265 if(tmp>=1)

266 NodeAdjust(NodeFind(G_pTreeNodeOrder[i][j], G_pTreeNodeOrder[i][j+1]), tmp);

267 }

268

269 tmp = G_pTreeNodeOrder[i][j]->x - G_pTreeNodeOrder[i][j+1]->x + ( G_pTreeNodeOrder[i][j]->textoffset2 + G_pTreeNodeOrder[i][j+1]->textoffset1 ) / NODE_WIDTH + 1;

270 if(tmp>=1)

271 NodeAdjust(NodeFind(G_pTreeNodeOrder[i][j], G_pTreeNodeOrder[i][j+1]), tmp);

272

273 }

274

275 }

276

277 /* 查找需要调整的子树的根结点

278 struct NodePoint * NodeFind(struct NodePoint * p) {

279

280 while(p->parent!=-1 && G_TreeNodePoint[p->parent].child[0]==p->idx) {

281 p=&G_TreeNodePoint[p->parent];

282 }

283 return p;

284

285 }

286 */

287

288 /* 查找需要调整的子树的根结点 */

289 struct NodePoint * NodeFind(struct NodePoint * p1, struct NodePoint * p2) {

290

291 while(p2->parent!=-1 && p1->parent!=p2->parent) {

292 p1=&G_TreeNodePoint[p1->parent];

293 p2=&G_TreeNodePoint[p2->parent];

294 }

295 return p2;

296

297 }

298

299 /* 递归调整坐标 */

300 void NodeAdjust(struct NodePoint * p, int tmp) {

301

302 int i;

303 if(p->childnum==0)

304 p->x=p->x+tmp;

305 else {

306 p->x=p->x+tmp;

307 for(i=0;i<=p->childnum-1;i++)

308 NodeAdjust(&G_TreeNodePoint[p->child[i]], tmp);

309 }

310

311 }

312

313 /* 打印内存变量 */

314 void GraphNode_PrintVars() {

315

316 printf("\n");

317 int i,j;

318 for(i=0;i<=G_iNodeCount;i++) {

319 printf("ID:%2d x:%2d y:%2d txt:%6s ofs:%d/%d rx:%2d b:%2d pa:%2d num:%2d child:",

320 i,

321 G_TreeNodePoint[i].x,

322 G_TreeNodePoint[i].y,

323 G_TreeNodePoint[i].text,

324 G_TreeNodePoint[i].textoffset1,

325 G_TreeNodePoint[i].textoffset2,

326 G_TreeNodePoint[i].oppx,

327 G_TreeNodePoint[i].oppx_mid,

328 G_TreeNodePoint[i].parent,

329 G_TreeNodePoint[i].childnum

330 );

331 for(j=0;j<=G_TreeNodePoint[i].childnum-1;j++)

332 printf("%d ",G_TreeNodePoint[i].child[j]);

333 printf("\n");

334 }

335 printf("\n");

336 }

337

338 /* 打印语法树 */

339 void GraphNode_Print() {

340

341 G_iGraphNum++;

342 printf("<Graph %d>\n", G_iGraphNum);

343

344 int idx;

345 int i,j;

346

347 for(j=0;j<=G_iDeepCount;j++) {

348

349 /* 打印首行结点 [] */

350 for(i=0;i<=G_iTreeNodeOrderCount[j];i++) {

351 idx=G_pTreeNodeOrder[j][i]->idx;

352 PrintInfo( G_TreeNodePoint[idx].oppx_mid , G_TreeNodePoint[idx].text);

353 }

354 printf("\n");

355

356 if(j==G_iDeepCount)return; /* 结束 */

357

358 /* 打印第二行分隔线 | */

359 int iHave=0;

360 for(i=0;i<=G_iTreeNodeOrderCount[j];i++) {

361 idx=G_pTreeNodeOrder[j][i]->idx;

362 if(G_pTreeNodeOrder[j][i]->childnum) {

363 if(iHave==0)

364 PrintInfo( G_TreeNodePoint[idx].oppx , "|");

365 else

366 PrintInfo( G_TreeNodePoint[idx].oppx - 1 , "|");

367 iHave=1;

368 }

369 else

370 PrintInfo( G_TreeNodePoint[idx].oppx , "");

371 }

372 printf("\n");

373

374 /* 打印第三行连接线 ------ */

375 for(i=0;i<=G_iTreeNodeOrderCount[j+1];i++) {

376 idx=G_pTreeNodeOrder[j+1][i]->idx;

377 int k;

378 if(i!=0 && G_pTreeNodeOrder[j+1][i]->parent==G_pTreeNodeOrder[j+1][i-1]->parent) {

379 for(k=0;k<=G_pTreeNodeOrder[j+1][i]->oppx - 2; k++)

380 printf("-");

381 printf("|");

382 }

383 else if(i==0) {

384 PrintInfo( G_TreeNodePoint[idx].oppx , "|");

385 }

386 else {

387 PrintInfo( G_TreeNodePoint[idx].oppx - 1 , "|");

388 }

389 }

390 printf("\n");

391

392 /* 打印第四行分割连接线 | */

393 for(i=0;i<=G_iTreeNodeOrderCount[j+1];i++) {

394 idx=G_pTreeNodeOrder[j+1][i]->idx;

395 if(i==0)

396 PrintInfo( G_TreeNodePoint[idx].oppx , "|");

397 else

398 PrintInfo( G_TreeNodePoint[idx].oppx - 1 , "|");

399 }

400 printf("\n");

401

402 }

403

404

405 }

406

407 /* 获取节点位移 */

408 int GetOffset(int count, int idx, int base) {

409

410 if(count&1)

411 return (idx-(count+1)/2)*base;

412 else

413 return idx*base-(count+1)*base/2;

414

415 }

416

417 /* 根据节点地址获取内存索引 */

418 int GetNodeIndex(Node * p) {

419

420 int i;

421 for(i=G_iNodeCount;i>=0;i--) {

422 if(p==G_TreeNodePoint[i].node)return G_TreeNodePoint[i].idx;

423 }

424

425 }

426

427 /* 初始化变量 */

428 void InitVars() {

429

430 /*

431 int i,j;

432 for(j=0;j<=MAX_TREE_DEEP-1;j++)

433 for(i=0;i<=MAX_TREE_WIDTH-1;i++)

434 G_pTreeNodeOrder[j][i]=0;

435 */

436

437 int i;

438 for(i=0;i<=MAX_TREE_DEEP-1;i++)

439 G_iTreeNodeOrderCount[i]=-1;

440 }

441

442 /* 打印固定信息 */

443 void PrintInfo(int val, char * str) {

444

445 char sInt[10];

446 char sPrint[20];

447 itoa( val , sInt);

448 strcpy(sPrint, "%");

449 strcat(sPrint, sInt);

450 strcat(sPrint,"s");

451 printf(sPrint,"");

452 printf(str);

453

454 }

455

456 /* int 转 char */

457 char * itoa(int n, char *buffer) {

458

459 int i=0,j=0;

460 int iTemp; /* 临时int */

461 char cTemp; /* 临时char */

462

463 do

464 {

465 iTemp=n%10;

466 buffer[j++]=iTemp+'0';

467 n=n/10;

468 }while(n>0);

469

470 for(i=0;i<j/2;i++)

471 {

472 cTemp=buffer[i];

473 buffer[i]=buffer[j-i-1];

474 buffer[j-i-1]=cTemp;

475 }

476 buffer[j]='\0';

477 return buffer;

478

479 }

这个文件需要与《Lex和Yacc应用方法(五).再识语法树》中提到的node.h,lexya_e.l,lexya_e.y

一起编译，生成可执行文件。我这里编译的可执行文件名是graph，下文皆使用这个名称。

三、总体思路说明

打印语法树的难点在于，要通过十分原始的printf来打印，而且操作对象是任意的

递归树。对齐和空白是十分令人头痛的事情，比较遗憾的是，没能读懂Tom Niemann的算

法思想(也许根本就不想去花时间读)，这里姑且凭空想象，从0开始。

本示例代码没有进行什么优化，个人感觉重点不在于此，主要是描述整体思路，实现

这一非常有趣的事情。

示例的执行过程可大致划分为四大部分：构造内存树，排序内存树，调整内存树和

打印内存树四个部分。

A.构造内存树

顾名思义，就是在内存中再次构造一棵树，这个树不同于《Lex和Yacc应用方法(五).再识语法树》

中的语法树。我们这里的树记录的都是打印显示信息，确切是叫显示树。不过在结构上，

两者是很类似的。

行<22-42>是内存结点的结构定义。

行<44>是全局内存变量，存储所有的内存结点。

行<100> GraphNode 是构造内存树的主函数，构造方法与语法树相同。主要调用

GraphNode_Set进行赋值。这里有个细节，构造过程会记录最小的x。

下面对结点里相对难以理解的内容含义进行说明。

结构里除了oppx,oppx_mid之外，均需要在GraphNode_Set赋值。

x 表述的原始坐标值，跟据本结点和子结点的位置确定。如下图(图中可能显示不对齐，

可复制到记事本观看)，

|---|

4 6

| |

| |---|

4 5 7

第一结点如x为5，第一个子节点便是-1，后面的子节点就是+1，依此类推，主要

保证树的对称性。GetOffset这个函数就是用来取节点的位移值。当然用这些值打印

是很可出现交叉现象的，这个问题我们将在后面讨论。交叉图如下：

|---|

4 6

| |

|---|---|

3 55 7

y 表述的是节点深度

textoffset1 文本前位移

textoffset2 文本后位移

[=]

|-------|

| |

idx(b) c(-1)

这两个offset表述了“|”的位置。“|”前为offset1，“|”后包括“|”为offset2

[=] offset1 为 1 offset2 为 2

idx(b) offset1 为2 offset2 为4

c(-1) offset1 为2 offset2 为3

offset会在调整内存树和打印内存树时使用。

B.排序内存树

这个过程比较简单，是将构造完的所有内存结点，按深度依此排序到G_pTreeNodeOrder中，

代码见行<207>。

在构造内存树时，我们传递的基本位移值是0，整个树中肯定会有负值，显然负值是不能

打印出来的，而且在GraphNode_Set中已经存储了整个树的最小值。在排序的过程，对所有树

结点也进行了坐标平移。

C.调整内存树

在介绍“构造内存树”时提及，会存在树结点交叉的现象，这里采用的算法是从最深层，最

左边节点依此遍历处理。(当然也可从最高层，最左边节点依此遍历）

处理的方法是找出要调整的结点的最大子树，此子树不能包括参考结点，对最大子树所有节

点进行向右平移。

举个例子，如下图：

while

|---------------|

| |

[<=] [;]

| |

|-------| |-----------|

| | | |

idx(i) c(2) print [=]

| |

| |-------|

| | |

idx(i) idx(i) [+]

|-------|

| |

idx(i) c(1)

现在若处理到c(2)，发现print和c(2)严重重合，通过比较两者x和offset，算出调整

值(具体算法可查看详细代码<261-273>)。要调整print的结点，需要向上追溯，真至找出

最大子树，这个子树不能包括参考节点c(2)。具体算法可参见行<289>的NodeFind函数。

查找最大子树的根结点后，调用<299>递归函数NodeAdjust，进行平移。

保证无交叉后，还需要根据x,textoffset1,textoffset2和#define NODE_WIDTH，算

出绝对坐标值和树结点间相对值，即oppx,oppx_mid。具体算法见<225>GraphNode_FillPos。

这些细节需要结合“打印内存树”理解。

这里需要明确一十分重要的规则，每个“|”前面的字符都是NODE_WIDTH的整数倍，如上

图中while是12，[<=]是8，idx(i)是4 等等。

没有这个规则，是很难打印出标准，对称且美观的语法图。

D.打印内存树

行<339>GraphNode_Print，负责将内存变量绘制到屏幕上。由于采用printf这么

原始的命令行方式，需要从顶部开始绘图。具体可参考上述重要规则进行理解。

四、结束

本示例也提供了内存变量的打印函数(GraphNode_PrintVars)，用于调试分析。

输入文件：

if(1>1||2>2)print(1);

else

if(3>1&&2>2)print(2);

else

print(3);

编译运行：

./graph < input

|---------------|-------------------|

| | |

[||] print if

| | |

|---------------| | |---------------|-------|

| | | | | |

[>] [>] c(1) [&&] print print

| | | | |

|-------| |-------| |---------------| | |

| | | | | | | |

c(1) c(1) c(2) c(2) [>] [>] c(2) c(3)

| |

|-------| |-------|

| | | |

c(3) c(1) c(2) c(2)

此外也测试过更复杂的输入：

k=9;

if((1>1)||(-9>-1))

for(i=0;i<=9;i=i+1)

print(i);

else

if(3>1&&2>1) {

for(j=-1.1;j<=3;j++)

print(j);

for(jdd=1;jdd<=3;++jdd)

print(jdd);

while(k<=9) {

print(k++);

print(++k);

}

if(1==1) {

d=9;

d=d--;

print(d);

#dd

}

输出内容太多，不再列出，用户可自行尝试。页面显示的常有错位，最好复制到记

事本或UltraEdit查看。

Lex和Yacc应用方法(七).企业方面的实际应用

20070527

草木瓜

一、前言

说到这里，也许有人觉得要把这些东西实际应用起来，还没谱，或许很多人觉得工作中很

少能使用到。

本文的主要目的就是为了详细说明下实际的企业应用示例。示例基于《Lex和Yacc应用方

法(五).再识语法树》

<注：本站文章难免有错误疏漏之处。Lex,Yacc系列文章 http://blog.csdn.net/liwei_cmg/category/207528.aspx>

二、企业应用综述

Lex和Yacc的编译理论体系十分适用于处理相对复杂的逻辑判断。在中国这个特殊环境下，

有个十分典型的例子就是计算费用，俗话说就是算钱。实在不是一般的麻烦，接触的一些行业

如集装箱物流行业，电信行业皆如事，恐怕中国人的心眼全用在玩花样算钱了罢。

越复杂的逻辑环境，Lex和Yacc的优势越明显。如工业控制，成本核算，人员评估，费用

计算等等方面。下面举些实际的例子说明。

A.集装箱的滞箱费

超期使用集装箱，一般会产生滞箱费。滞箱费与进出口，提箱单位，承运人，使用天数，

箱属，箱型和箱尺寸都可能有关系，此外还存在人为协议上的调整。

我们假设：fee表示费用返回值，rate表示基本费率，size表示箱尺寸，type表示箱型，

days表示天数。

计算公式：

(注：实际费用并非如此，仅供示例)

#普通箱，10天免费

if((size==20 || size=40) && type==1)

if(days<=10)

fee=0;

else

fee=(days-10)*feerate;

#冷箱，4天免费

if(size==40 && type==2)

if(days<=4)

fee=0;

else

fee=(days-4)*feerate;

#开顶箱和超高箱,7天免费

if(type==3 || type==4)

if(days<=7)

fee=0;

else

fee=(days-4)*feerate;

B.电信套餐计费

各运营商，品牌，套餐的计费方法是层出不穷，不使用公式计费，复杂度可想而知。

拿亲情电话组为例，A,B,C,D是一个电话组，5元包300分钟，超出按市话3毛一分算。正

常资费为5毛一分。

我们假设：FEE表示费用返回值，G_CALL*表示主被叫所在组，W_CALL*表示主被叫

套餐内累计时长, T_CALL*表示正常累计时长。0主叫，1被叫

计算公式：

(注：实际电信计费公式远复杂与此，仅做示例)

if(G_CALL0==G_CALL1)

if(T_CALL0<=300)

FEE=0

else

FEE=30

else

FEE=50

三、修改后的实际应用全代码

复杂的逻辑判断简化成程序判断语句，可便于应用的扩展和维护，也极大增强了代码的

可读性。

我们对整体文件划分如下：

tree.l

tree.y

parser.h #内部编译使用的头文件

parser.c #内部编译的主函数

compile.h #内外部交互的头文件

main.c #外部程序

----------------------------------------------------------------------

<tree.l>

#include <stdlib.h>

#include "parser.h"

#include "tree.tab.h"