woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

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

LexYacc应用方法().初识Lex

草木瓜  20070301

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

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

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

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

 

.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.通过lexflex工具解析成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);

%%

并输入titleLex解析完后发现,仍然存在两个规则,这时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]);

%%

%}%%之间,加入了一些类似变量的东西,注意是没有;的,这表示intfloat

别代指特定的含义,在两个%%之间,可以通过{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

来表示解析的结束。

 

 

lexflex都是解析Lex文件的工具,用法相近,flex意为fast lexical analyzer generator

可以看成lex的升级版本。

 

相关更多内容就需要参考flexman手册了,十分详尽。

 

.关于Lex的一些综述

Lex其实就是词法分析器,通过配置文件*.l,依据正则表达式逐字符去顺序解析文件,

并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈,

它不适合用于剖析外壳结构。而yacc增加了一个堆栈,并且能够轻易处理像括号这样的

结构。Lex善长于模式匹配,如果有更多的运算要求就需要yacc了。

 

LexYacc应用方法().再识LexYacc

 

草木瓜  20070314

 

早在二十世记七十年代之前,编写编译器一直是一个非常费时的工作。但到了1975

一年这一切却发生了重大转变,首先Stephen C. Johnson Lesk在贝尔实验室完成了

Yacc开发,为了配合yacc更好的协作, Mike LeskEric Schmidt又完成了lex。从

Lexyacc成为计算机编译领域的重要理论,而这些工具也极大地简化了编写编译

器的工作。

 

后来Robert CorbettRichard Stallman在此基础上又完成了bisonJef Poskanzer,

Vern Paxson 也对lex作了大量改进,称为flex

 

<本系列文章的地址:http://blog.csdn.net/liwei_cmg/category/207528.aspx>

 

一、Lex理论

 

Lex使用正则表达式从输入代码中扫描和匹配字符串。每一个字符串会对应一个动作。

通常动作返回一个标记给后面的剖析器使用,代表被匹配的字符串。每一个正则表达

式代表一个有限状态自动机(FSA)。我们可以用状态和状态间的转换来代表一个(FSA)

其中包括一个开始状态以及一个或多个结束状态或接受状态。

 

我们以上文《LexYacc应用方法().初识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算法肯定是更为复杂的理论体系,这个没有

接触过,有兴趣可以参看相关资料。

 

 

二、yaccBNF文件

 

    个人认为lex理论比较容易理解的,yacc要复杂一些。

    我们先从yacc的文法说起。yacc文法采用BNF(Backus-Naur Form)的变量规则描

述。BNF文法最初由John BackusPeter 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。这

个内容会在后面的实例做进一步深化。

 

 

三、十分典型的利用lexyacc模拟的简单+-*/计算器。

 

    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.ylexya_a.llexya_a.yyacc文件,bison -d lexya_a.y

编译后会产生 lexya_a.tab.c  lexya_a.tab.hlex文件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

会调用yylexyylex的返回值类型是整型,可以用于返回标记。而在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+zy

应先与“-”号结合, 执行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的递归解析方式。

 

  programexpr是规则标记,但是作为一个整体描述表达式。

 

  先看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的值,完成字符运算。

 

.后记

     如果到这里能完全理解所述内容,对于lexyacc就有些感觉了。后面文章会做进一步

的深入。

 

 

LexYacc应用教程().使用变量

 

草木瓜  20070512

 

一、序

 

早在两个月前就想对LexYacc作系列的阐述,然而工作的事情实在太多,很难抽出空

静下心去总结学习。不觉感慨国内工作环境恶劣,加班是家常便饭,整天基本都是在做

一些简单大量的重复,甚至徒劳无用。

 

在《初识Lex》一文中主要从入门角度总结了Lex,《再识LexYacc》一文在可以简单

使用Lex情况基础,介绍了LexYacc的算法理论,并说明如何将LexYacc结合起来使

用。

 

这里我们需要对LexYacc使用方法做进一步研究,以备能理解后面会引入的语法树。

 

<本系列文章的地址: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

 

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

 

    其实细看过《LexYacc应用方法().再识Yacc》一文后,理解上面的例子就很轻

松了。

 

    这里只是做了一些扩充变化:

    1.增加了全局数组sMem来存放变量,不过变量名有限制,只支持单字符。

    2.增加了全局数组sBuff存放分析过的语句

    3.增加debuginfo打印堆栈信息

    4.增加printinfo打印目前的分析语句

 

    要进行内部分析,就需要剖析生成的c文件,对程序(parser)进行跟踪调试。

(注:Lex编译时加上d参数,会在程序解释时输出详细的调试信息。如:lex -d lexya_$1.l)

    通过本示例再加上实际对lexya_b.tab.c的分析理解,会对lexyacc理论有更进一步的

理解。

 

 

四、增加支持的变量字符数

 

    上面的例子只支持单字符的变量,想支持多字符,需要定义一全局变量如:

   

  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;

  }

 

五、最后

 

    本文说明文字较少,主要是前两篇说得已经够多了,对照代码应该比较容易理解,

下一篇将着重介绍语法树的构建,也才是真正应用的开始。

 

 

 

LexYacc应用方法().语法树的应用

 

草木瓜  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对应IFX055对应ELSE055高于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语法,不过也只是

一小部分,在后续的文章中将逐步扩展本例的功能,从而发掘yacclex的强大功能。

 

 

LexYacc应用方法().再识语法树

 

草木瓜  20070524

 

一、序

 

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

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

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

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

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

过搜索引擎能迅速查到。

   

    <本站文章难免有错误疏漏之处。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;

 

}

 

 

 

三、示例功能说明

 

 

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

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

  2

  3

  9

  11

 

四、思路分析

 

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

 

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

 

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

  NUMBERVARIABLE。然后划分一元运算符,多元运算符和保留字。一元运算符可以用

  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_liststmt用了一个循环递归,但不是死循环,因为BNF范式本身就是有序的,

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

    不存在死循环的问题。

       

   

   2.构造内存中的语法树

   

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

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

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

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

   

   

   3.调试分析信息的打印

   

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

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

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

        调试信息需要lexyacc配合起来实现,需要提出的是yystypeindex是一值多用,

    可以通过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开始。

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

 

 

 

LexYacc应用方法().语法树打印

 

草木瓜  20070525

 

一、序

 

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

LexYacc应用教程().语法树的应用》) 其实语法树显示程序在Tom Niemann

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

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

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

 

    <注:本站文章难免有错误疏漏之处。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  }

     

 

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

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

 

 

三、总体思路说明

 

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

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

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

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

这一非常有趣的事情。

 

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

打印内存树四个部分。

 

  A.构造内存树

 

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

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

两者是很类似的。

 

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

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

   

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

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

   

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

   

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

   

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

    可复制到记事本观看)

    

      5

      |

    |---| 

    4   6

    |   |

    | |---|

    4 5   7

   

        第一结点如x5,第一个子节点便是-1,后面的子节点就是+1,依此类推,主要

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

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

   

       5

       |

     |---| 

     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),发现printc(2)严重重合,通过比较两者xoffset,算出调整

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

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

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

   

   

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

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

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

   

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

图中while12[<=]8idx(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

   

<Graph 0>

                    if

                    |

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

            |               |                   |

           [||]           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查看。

 

 

LexYacc应用方法().企业方面的实际应用

 

20070527

 

草木瓜

 

一、前言

 

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

少能使用到。

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

().再识语法树》

 

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

 

二、企业应用综述

 

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

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

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

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

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

 

  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"

 

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

 

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

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

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

 

 

  %}

 

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

  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;

  }

 

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

  <tree.y>

 

  %{

  #include <stdio.h>

  #include <stdlib.h>

  #include <stdarg.h>

 

  #include "parser.h"

  #include "compile.h"

 

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

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

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

 

  char G_sFormula[MAX_FORMULA_LEN];  /* 全局变量,存储公式内容 */

  int  G_iFormulaPos = 0;                /* 全局变量,存储公式当前的处理位置 */

 

  void (* G_LoadVar)(char *, float *);

 

  %}

 

  %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 {}

  ;

  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"); }

  ;

 

  %%

  #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;

    if(G_LoadVar!=0)

      G_LoadVar(mark,&G_Var[0].val);

    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;

   if(G_LoadVar!=0)

     G_LoadVar(mark,&G_Var[G_iVarCurIndex].val);

   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);

  }

 

 

  int GetParserInput(char *buf, int maxlen) {

   int i;

   if(G_iFormulaPos>=strlen(G_sFormula))

    return 0;

    for(i=0; i<maxlen && G_sFormula[G_iFormulaPos]!='\0'; i++)

      buf[i] = G_sFormula[G_iFormulaPos++];

    return i;

  }

 

  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]);

  }

 

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

  <parser.h>

 

  #include "compile.h"

  //------------------------------------------------------------

  //lex yacc 定义的结构体

 

  /* 定义树结点的权举类型 */

  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;

  };

 

  //------------------------------------------------------------

  //lex yacc 宏定义

 

  #undef YY_INPUT

  #define YY_INPUT(buf, ret, maxlen) (ret = GetParserInput(buf, maxlen))

 

  /* yystype */

  typedef union {

  float val;  /* 变量值 */

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

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

  }yystype;

 

  #define YYSTYPE yystype

 

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

 

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

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

 

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

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

 

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

  // #define PARSE_DEBUG 

 

  //------------------------------------------------------------

  //lex yacc 全局变量

 

  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;  /* 当前语句列数 */

 

  extern char G_sFormula[MAX_FORMULA_LEN];  /* 全局变量,存储公式内容 */

  extern int  G_iFormulaPos;                /* 全局变量,存储公式当前的处理位置 */

 

  extern void (* G_LoadVar)(char *, float *); /* 函数指针 */

 

  //------------------------------------------------------------

  //lex yacc 函数定义

 

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

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

 

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

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

  void print_stmt();

 

  /* 属性操作类型 */

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

  Node *set_index(int value);

  Node *set_content(float value);

 

  /* 树结点操作 */

  void NodeFree(Node *p);

  float NodeExecute(Node *p);

 

  void yyerror(char *);

 

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

  <parser.c>

 

  #include <stdio.h>

  #include "parser.h"

  #include "tree.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;

  

  }

 

  int FormulaVarGet(char * mark, float * val) {

 

   int i;

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

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

     *val = G_Var[i].val;

     return 0;

    }

   return 1;

  }

 

  int FormulaParser(char * cmd,void (* loadvar)(char *, float *)) {

 

   G_iFormulaPos=0;

   G_LoadVar=loadvar;

   strcpy(G_sFormula,cmd);

   return yyparse();

 

  }

 

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

  <compile.h>

 

  #define MAX_FORMULA_LEN 350

   

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

  <main.c>

 

  #include <stdio.h>

  #include "compile.h"

 

  void loadvar(char * mark, float * val) {

   if(strcmp(mark,"xxxx")==0) {

    *val=6;

    return;

   }

   if(strcmp(mark,"xxxx")==0) {

    *val=6.99789;

    return;

   }

  }

 

  int main(int argc, char *argv[]) {

    int iRet;

  

    /**/

   char sFile[MAX_FORMULA_LEN]={0};

   FILE * fp;

 

   if(argc!=2) {

    printf("Error: command filename\n");

    exit(-1);

   }

 

   fp = fopen(argv[1], "r");

   if(fp==NULL) {

    printf("Error: Cannot open file\n");

    exit(-1);

   }

   fread(sFile,sizeof(char),MAX_FORMULA_LEN,fp);

    fclose(fp);

   

   iRet=FormulaParser(sFile, loadvar);

   printf("\nRet:%d\n",iRet );

  

   float fVal;

   iRet=FormulaVarGet("i", &fVal);

   if(iRet==0)

    printf("i:%g\n",fVal );

  

  }

 

  

四、一些修改说明

 

 

  1.将内部使用变量,函数,结构体和宏定义集中到parser.h

  2.yyparser的输入进行重定义,见#undef YY_INPUT部分

  3.提供一个回调函数接口 extern void (* G_LoadVar)(char *, float *); /* 函数指针 */

    4.内部创建可供外部调用的函数接口,FormulaParser FormulaVarGet

    5.提供一个内外部交互的定义文件compile.h,暂时的内容只是保持数组大小一致性。

    6.外部程序通过输入文件进行编译处理

   

    这样在外部程序main.c,直接可以实现公式编译和变量访问控制。

   

    生成静态库文件:

   

    bison -d tree.y

  lex tree.l

  gcc -g -c lex.yy.c tree.tab.c parser.c

  ar -rl compile.a *.o

 

  使用静态库文件编译外部程序:

 

  gcc -g  -o lw main.c compile.a

  

  

    运行编译显示结果:

   

    ./lw input

   

    1

 

  Ret:0

  i:1

 

  input内容:

  i=i+1;print(i);

 

 

五、一些总结

 

    在企业的应用中,本示例提供的功能还略显浅薄,主要有如下一些缺点:

   

    1.目前仅支持浮点整型,不支持字符型

    2.不支持switch分支结构

    3.不支持return,break,goto,continue等跳转语句

   

    这些用目前的语法树也不是不能实现,不过语法树需要做大量的递归操作,在效率上存在

一些问题。

  后面的系列文章中会逐渐引入堆栈来处理语法编译的问题,也可能会对现有的语法树做些

优化。LexYacc系列到现在都是在Linux下面说事,我们也不能忽略Windows下的情况。诸如

此类,只有花时间慢慢琢磨了。

 

 

 

LexYacc应用方法().使用堆栈编译语法

 

草木瓜  20070604

 

一、序

 

    前面一些系列文章着重介绍了递归语法树在编译理论方面的应用。本文则会介绍另一种

实现方式----堆栈。 

    堆栈在底层系统有十分广泛的应用,同样也十分擅长处理语法结构,这里通过实际示例

探讨如何构造堆栈完成语法分析。

 

    重要补充:下面是本系列文章全示例代码统一的调试测试环境,另对于lex,yacc文件需

要存储为Unix格式,这一点和LinuxUnixshell很类似,DOS格式的Shell是不能够被执行

的,同样bison,lex编译DOS格式文件会出错误提示:

   

    Red Hat Linux release 9 (Shrike)

    Linux 2.4.20-8

    gcc version 3.2.2 20030222

    bison (GNU Bison) 1.35

    lex version 2.5.4

    flex version 2.5.4

 

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

 

 

二、具体示例

 

    本示例主要完成功能:

   

    1  支持整型,浮点型和字符串型

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

    3  支持整型,浮点型的+-*/()=运算法则

    4  支持字符串型赋值

    5  支持print打印整型,浮点型和字符串型

    6  支持打印变量值

    7  支持while if else switch四种控制结构,并支持控制结构的嵌套

    8  支持> >= < <= != == 六种比较运算,同时也支持字符串的比较

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

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

    11 支持#的单行注释

    12 支持{}多重组合

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

    14 支持外部变量值传入(整型,浮点型和字符型)

    15 支持外部变量获取(整型,浮点型和字符型)

    16 完整的企业应用模式

   

三、示例全代码

 

 

A.stack.l

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

 

%{

#include <stdlib.h>

#include "stack.tab.h"

#include "stack.h"

%}

 

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

any  .

 

%%

 

#{any}*[\n]  {

 AddBuff(yytext);

 G_iBuffColCount=0;

 G_iBuffRowCount++;

} /* 单行注释 */

 

 

[\n]    {

 G_iBuffColCount=0;

 G_iBuffRowCount++;

}

 

"if"  {

 AddBuff(yytext);

 return IF;

}

 

"else"  {

 AddBuff(yytext);

 return ELSE;

}

 

"switch" {

 AddBuff(yytext);

 return SWITCH;

}

 

"case" {

 AddBuff(yytext);

 return CASE;

}

 

"print" {

 AddBuff(yytext);

 return PRINT;

}

 

"while" {

 AddBuff(yytext);

 return WHILE;

}

 

">=" {

 AddBuff(yytext);

 return GE;

}

 

 

"<=" {

 AddBuff(yytext);

 return LE;

}

 

"==" {

 AddBuff(yytext);

 return EQ;

}

 

"!=" {

 AddBuff(yytext);

 return NE;

}

 

"&&" {

 AddBuff(yytext);

 return AND;

}

 

"||" {

 AddBuff(yytext);

 return OR;

}

 

[a-zA-Z_][a-zA-Z0-9_]* {

 return GetVar();

}

 

\"[^\"]*\" {

 return GetString();

}

 

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

 return GetFloat();

}

 

[0-9]+  {

 return GetFloat();

}

 

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

 return GetOperator();

}

 

[\t]    { AddBuff(yytext); }  

[ ]     { AddBuff(yytext); }  

.       { printf("Unknown: %s\n", yytext); }

%%

 

int GetFloat(void) {

 yylval.fVal=atof(yytext);

 AddBuff(yytext);

 return FLOAT;

}

int GetOperator(void) {

 yylval.cVal=*yytext;

 AddBuff(yytext);

 return *yytext;

}

int GetVar(void) {

 AddVar(yytext);

 yylval.iVal = G_iVarCurIndex;

 AddBuff(yytext);

 return VAR;

}

int GetString(void) {

 AddString(yytext);

 yylval.iVal = G_iStrCurIndex;

 AddBuff(yytext);

 return STRING;

}

 

int yywrap(void) {

 return 1;

}

 

 

B.stack.y

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

 

%{

#include <stdlib.h>

#include "stack.h"

 

typedef union {

float fVal;

int   iVal;

char  cVal;

} yystype;

 

#define YYSTYPE yystype

void AddCommand(int, int, YYSTYPE *);

 

 

%}

%union {

float fVal;

int   iVal;

char  cVal;

};

%token <fVal> FLOAT

%token <iVal> VAR STRING

%token PRINT WHILE

%nonassoc IF

%nonassoc ELSE

%token SWITCH CASE

%left AND OR

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

%left '+' '-'

%left '*' '/'

%%

program:

function

;

 

function:

function stmt

|

;

 

stmt:

exprset ';'

| PRINT expr ';'  { AddCommand(D_ACT_PRINT, D_VAR_NULL, 0); }

| PRINT '(' STRING ')' ';'  { AddCommand(D_ACT_PUSHVALUE, D_VAR_STRING, &yyvsp[-2]); AddCommand(D_ACT_PRINT, D_VAR_NULL, 0); }

| IF '(' exprcmp ')' ifx stmt  %prec IF { AddCommand(D_ACT_ENDIF, D_VAR_NULL, 0); }

| IF '(' exprcmp ')' ifx stmt ELSE elsex stmt %prec ELSE { AddCommand(D_ACT_ENDIF, D_VAR_NULL, 0); }

| SWITCH '(' expr ')' switchx '{' stmtcaselist '}' { AddCommand(D_ACT_ENDSWITCH, D_VAR_NULL, 0); }

| WHILE whileb '(' exprcmp ')' whilex stmt { AddCommand(D_ACT_ENDWHILE, D_VAR_NULL, 0); }

| '{' stmtlist  '}'

;

 

stmtcaselist:

stmtcase

| stmtcaselist stmtcase

;

 

stmtcase:

CASE number casex ':' stmt

;

 

ifx:     { AddCommand(D_ACT_IF, D_VAR_NULL, 0);     }

;

elsex:   { AddCommand(D_ACT_ELSE, D_VAR_NULL, 0);   }

;

switchx: { AddCommand(D_ACT_SWITCH, D_VAR_NULL, 0); }

;

casex:   { AddCommand(D_ACT_CASE, D_VAR_NULL, 0);   }

;

whilex:  { AddCommand(D_ACT_WHILE, D_VAR_NULL, 0);   }

;

whileb:  { AddCommand(D_ACT_BEGINWHILE, D_VAR_NULL, 0);   }

;

 

stmtlist:

stmt 

| stmtlist stmt

;

 

exprcmp:

  exprx '>' exprx  { AddCommand(D_ACT_G, D_VAR_CHAR, 0); }

| exprx GE  exprx  { AddCommand(D_ACT_GE, D_VAR_NULL, 0); }

| exprx '<' exprx  { AddCommand(D_ACT_L, D_VAR_CHAR, 0); }

| exprx LE  exprx  { AddCommand(D_ACT_LE, D_VAR_NULL, 0); }

| exprx EQ  exprx  { AddCommand(D_ACT_EQ, D_VAR_NULL, 0); }

| exprx NE  exprx  { AddCommand(D_ACT_NE, D_VAR_NULL, 0); }

| exprcmp AND exprcmp { AddCommand(D_ACT_AND, D_VAR_NULL, 0); }

| exprcmp OR  exprcmp { AddCommand(D_ACT_OR, D_VAR_NULL, 0); }

| '(' exprcmp ')'

;

 

exprx:

expr

| STRING  { AddCommand(D_ACT_PUSHVALUE, D_VAR_STRING, &yyvsp[0]); }

;

 

exprset:

VAR '=' expr { AddCommand(D_ACT_PUSHVAR, D_VAR_INT, &yyvsp[-2]); AddCommand(D_ACT_ASSIGN, D_VAR_CHAR, &yyvsp[-1]); }

| VAR '=' STRING { AddCommand(D_ACT_PUSHVALUE, D_VAR_STRING, &yyvsp[0]); AddCommand(D_ACT_PUSHVAR, D_VAR_INT, &yyvsp[-2]); AddCommand(D_ACT_ASSIGN, D_VAR_CHAR, &yyvsp[-1]); }

;

 

expr:

number

| VAR { AddCommand(D_ACT_PUSHVAR,   D_VAR_INT,   &yyvsp[0]); }

| expr '+' expr { AddCommand(D_ACT_ADD, D_VAR_CHAR, &yyvsp[-1]);  }

| expr '-' expr { AddCommand(D_ACT_MINUS, D_VAR_CHAR, &yyvsp[-1]);}

| expr '*' expr { AddCommand(D_ACT_MUL, D_VAR_CHAR, &yyvsp[-1]);  }

| expr '/' expr { AddCommand(D_ACT_DIV, D_VAR_CHAR, &yyvsp[-1]);  }

| '(' expr ')'

;

 

number:

FLOAT { AddCommand(D_ACT_PUSHVALUE, D_VAR_FLOAT, &yyvsp[0]); }

;

 

%%

 

void AddCommand(int typeact, int typeval, YYSTYPE * val) {

 

 G_iCommandCount++;

 G_Command[G_iCommandCount].iTypeAction = typeact;

 G_Command[G_iCommandCount].iTypeVal = typeval;

 

 G_Command[G_iCommandCount].iVar=0;

 G_Command[G_iCommandCount].fVal=0;

 G_Command[G_iCommandCount].iControl=0;

 G_Command[G_iCommandCount].iString=-1;

 

 switch(typeval) {

  case D_VAR_INT:

   G_Command[G_iCommandCount].iVar=(*val).iVal;

   break;

  case D_VAR_FLOAT:

   G_Command[G_iCommandCount].fVal=(*val).fVal;

   break;

  case D_VAR_STRING:

   G_Command[G_iCommandCount].iString=(*val).iVal;

   break; 

  case D_VAR_NULL:

   break;

 }

 

}

 

void yyerror(char *s) {

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

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

}

 

 

C.stack.h

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

 

#include "public.h"

 

//#define DEBUG_PRINT

 

#undef YY_INPUT

#define YY_INPUT(buf, ret, maxlen) (ret = FormulaParserInput(buf, maxlen))

 

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

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

 

#define MAX_VAR_LEN 10   /* 分析语句中变量名长度 */

#define MAX_VAR_NUM 100  /* 分析语句中变量最大个数 */

 

#define MAX_COMMAND_NUM 100  /* 命令集最大长度 */

#define MAX_CONTROL_NUM 100  /* 控制集最大长度 */

 

#define MAX_STACK_LEN   100  /* 堆栈长度     */

 

#define MAX_STRING_NUM 10 /* 字符变量最多个数 */

        

#define  D_ACT_NULL         0        

#define  D_ACT_PUSHVAR      1        

#define  D_ACT_PUSHVALUE    2        

#define  D_ACT_PRINT        3        

#define  D_ACT_ADD          4        

#define  D_ACT_MINUS        5        

#define  D_ACT_MUL          6        

#define  D_ACT_DIV          7        

#define  D_ACT_ASSIGN       8        

#define  D_ACT_G            9        

#define  D_ACT_GE           10       

#define  D_ACT_L            11       

#define  D_ACT_LE           12       

#define  D_ACT_EQ           13       

#define  D_ACT_NE           14

#define  D_ACT_AND          15      

#define  D_ACT_OR           16

#define  D_ACT_IF           17    

#define  D_ACT_ELSE         18    

#define  D_ACT_ENDIF        19       

#define  D_ACT_SWITCH       20    

#define  D_ACT_CASE         21    

#define  D_ACT_ENDSWITCH    22 

#define  D_ACT_BEGINWHILE   23 

#define  D_ACT_WHILE        24 

#define  D_ACT_ENDWHILE     25 

 

/* 内存字符结构 */

typedef struct {

 

 char content[MAX_STRING_LEN];

 

} TString;

 

/* 内存指令集结构 */

typedef struct {

 

  int iTypeAction;

  int iTypeVal;

 float fVal;

 int iVar;

 int iString;

 int iControl;

 

} TCommand;

 

/* 堆栈控制结构 */

typedef struct {

 

  int iTypeAction;

  int iControl;

  int iVal;

 

} TControl;

 

/* 内存变量结构 */

typedef struct {

 

 float val;

 int str;

 char  name[MAX_VAR_LEN];

 

} TVar;

 

typedef struct {

 int iTypeAction;

 int  (* Execute)(int val);

 char * sText;

} TCommandRelation;

 

 

int Act_PushValue(int);

int Act_PushVar(int);

int Act_Print(int);

 

int Act_Add(int);

int Act_Minus(int);

int Act_Mul(int);

int Act_Div(int);

int Act_Assign(int);

 

int Act_G(int);

int Act_Ge(int);

int Act_L(int);

int Act_Le(int);

int Act_Eq(int);

int Act_Ne(int);

 

int Act_And(int);

int Act_Or(int);

 

int Act_If(int);

int Act_Else(int);

int Act_EndIf(int);

 

int Act_Switch(int);

int Act_Case(int);

int Act_EndSwitch(int);

 

int Act_BeginWhile(int);

int Act_While(int);

int Act_EndWhile(int);

 

static TCommandRelation G_CommandRelation[] = {

 {D_ACT_NULL,      0,               "null"},

 {D_ACT_PUSHVAR,    Act_PushVar,     "pushvar"},

 {D_ACT_PUSHVALUE,  Act_PushValue,   "pushvalue"},

 {D_ACT_PRINT,       Act_Print,        "print"},

 {D_ACT_ADD,        Act_Add,         "add"},

 {D_ACT_MINUS,       Act_Minus,       "minus"},

 {D_ACT_MUL,        Act_Mul,         "mul"},

 {D_ACT_DIV,        Act_Div,         "div"},

 {D_ACT_ASSIGN,      Act_Assign,       "assign"},

 {D_ACT_G,          Act_G,           ">"},

 {D_ACT_GE,          Act_Ge,         ">="},

 {D_ACT_L,           Act_L,            "<"},

 {D_ACT_LE,          Act_Le,           "<="},

 {D_ACT_EQ,          Act_Eq,           "=="},

 {D_ACT_NE,          Act_Ne,           "!="},

 {D_ACT_AND,         Act_And,          "and"},

 {D_ACT_OR,          Act_Or,           "or"},

 {D_ACT_IF,          Act_If,           "if"},

 {D_ACT_ELSE,        Act_Else,         "else"},

 {D_ACT_ENDIF,      Act_EndIf,       "endif"},

 {D_ACT_SWITCH,      Act_Switch,       "switch"}, 

 {D_ACT_CASE,        Act_Case,         "case"},

 {D_ACT_ENDSWITCH,   Act_EndSwitch,    "endswitch"},

 {D_ACT_WHILE,       Act_BeginWhile,   "beginwhile"},

 {D_ACT_WHILE,       Act_While,        "while"},

 {D_ACT_ENDWHILE,    Act_EndWhile,     "endwhile"}

};

 

typedef struct {

 int val[MAX_STACK_LEN];

 int pos;

} TStack;

 

 

extern char       G_sFormula[MAX_FORMULA_LEN];  /* 全局变量,存储公式内容 */

extern int        G_iFormulaPos;                /* 全局变量,存储公式当前的处理位置 */

                 

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

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

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

 

extern TCommand   G_Command[MAX_COMMAND_NUM];   /* 命令集 */

extern int        G_iCommandCount;              /* 命令集个数 */

 

extern void    (* G_LoadVar)(char *, void **, int *);  /* 函数指针 */

 

extern TVar       G_Var[MAX_VAR_NUM];           /* 变量集 */

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

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

 

extern TString    G_String[MAX_STRING_NUM];     /* 控制集 */

extern int        G_iStrMaxIndex;

extern int        G_iStrCurIndex;

 

extern TStack     G_StackStmtAddress;

 

void yyerror(char *);

int  yylex  (void);

 

 

D.stackparser.c

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

 

#include "stack.h"

 

char     G_sFormula[MAX_FORMULA_LEN];  /* 全局变量,存储公式内容 */

int      G_iFormulaPos=0;              /* 全局变量,存储公式当前的处理位置 */

 

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

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

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

 

TCommand G_Command[MAX_COMMAND_NUM];   /* 命令集 */

TControl G_Control[MAX_CONTROL_NUM];   /* 控制集 */

 

int      G_iCommandCount=-1;            /* 命令集个数 */

int      G_iControlCount=-1;            /* 控制集个数 */

 

TVar     G_Var[MAX_VAR_NUM];

int      G_iVarMaxIndex=-1;

int      G_iVarCurIndex=-1;

 

void  (* G_LoadVar)(char *, void **, int *);

 

TStack   G_StackValue;

TStack   G_StackControl;

 

TString  G_String[MAX_STRING_NUM];   /* 控制集 */

int      G_iStrMaxIndex=-1;

int      G_iStrCurIndex=-1;

 

void AddBuff(char * buff) {

 strcat(G_sBuff[G_iBuffRowCount], buff);

 G_iBuffColCount=G_iBuffColCount+strlen(buff);

}

 

void AddString(char * str) {

 

 char * sTmp=str;

 

 if(sTmp[0]=='"') {

  str[strlen(str)-1]=0;

  sTmp++;

 }

 

 if(G_iStrMaxIndex<0){   

  strcpy(G_String[0].content, sTmp);

  G_iStrMaxIndex=0;

  G_iStrCurIndex=0;

  return;

 }

 

 int i;

 for(i=0;i<=G_iStrMaxIndex;i++) {

  if(strcmp(G_String[i].content, sTmp)==0) {

   G_iStrCurIndex=i;

   return;

  }

 }

 

 G_iStrMaxIndex++;

 strcpy(G_String[G_iStrMaxIndex].content, sTmp);

 G_iStrCurIndex=G_iStrMaxIndex;

 

}

 

void AddVar(char * name) {

 

 int iType;

 void * pRet;

 

 if(G_iVarMaxIndex<0){

   

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

  G_Var[0].val = 0;

  G_Var[0].str = -1;

 

  G_iVarMaxIndex = 0;

  G_iVarCurIndex = 0;

 

  if(G_LoadVar!=0) {

   

    G_LoadVar(name, &pRet, &iType);

   

    switch(iType) {

     case D_VAR_FLOAT:

       G_Var[0].val = *(float *)pRet;

       break;

     case D_VAR_STRING:

       AddString((char *)pRet);

       G_Var[0].str=G_iStrCurIndex;

       break;

   }

  

  }

  return;

 

 }

 

 

 int i;

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

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

   G_iVarCurIndex=i;

   return;

  }

 }

 

 G_iVarMaxIndex++;

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

 G_Var[G_iVarMaxIndex].val = 0;

 G_Var[G_iVarMaxIndex].str = -1;

 

 G_iVarCurIndex=G_iVarMaxIndex;

 

 

 

 if(G_LoadVar!=0) {

  

   G_LoadVar(name, &pRet, &iType);

  

   switch(iType) {

    case D_VAR_FLOAT:

      G_Var[G_iVarCurIndex].val = *(float *)pRet;

      break;

    case D_VAR_STRING:

      AddString((char *)pRet);

      G_Var[G_iVarCurIndex].str=G_iStrCurIndex;

      break;

  }

 

 }

 

}

 

void AddControl(int typeact, int val, int control) {

 

 G_iControlCount++;

 G_Control[G_iControlCount].iTypeAction = typeact;

 G_Control[G_iControlCount].iVal = val;

 G_Control[G_iControlCount].iControl = control;

 

}

 

 

void StackFree(TStack * s) {

 s->pos=-1;

 int i;

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

  s->val[i]=-1;

}

 

int StackPush(TStack * s, int val) {

 if(s->pos==MAX_STACK_LEN)

  return -1;

 s->val[++s->pos]=val;

 return 0;

}

 

int StackPop(TStack * s, int * val) {

 if(s->pos==-1)

  return -1;

 *val=s->val[s->pos];

 s->val[s->pos--]=-1;

 return 0;

}

 

void StackGetTop(TStack * s, int * val) {

 if(s->pos<=-1) {

  *val=-1;

  return;

 }

 *val=s->val[s->pos];

}

 

void StackGetTopA(TStack * s, int * val) {

 if(s->pos<=0) {

  *val=-1;

  return;

 }

 *val=s->val[s->pos-1];

}

 

int Act_PushValue(int idx) {

 

 StackPush(&G_StackValue, idx);

 return idx;

 

}

 

int Act_PushVar(int idx) {

 

 G_Command[idx].fVal = G_Var[G_Command[idx].iVar].val;

 G_Command[idx].iString = G_Var[G_Command[idx].iVar].str;

 StackPush(&G_StackValue, idx);

 return idx;

 

}

 

 

int Act_Add(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 /*

 if(G_Command[val1].iTypeAction==D_VAR_STRING || G_Command[val2].iTypeAction==D_VAR_STRING) {

  StackPush(&G_StackValue, val1);

  StackPush(&G_StackValue, val2); 

  return idx;

 }

 */

 

 /* 运算 */

 G_Command[val1].fVal=G_Command[val1].fVal+G_Command[val2].fVal;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

int Act_Minus(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 /* 运算 */

 G_Command[val1].fVal=G_Command[val1].fVal-G_Command[val2].fVal;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Mul(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 G_Command[val1].fVal=G_Command[val1].fVal * G_Command[val2].fVal;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Div(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

  if(G_Command[val2].fVal==0)

   G_Command[val1].fVal=0;

  else

  G_Command[val1].fVal=G_Command[val1].fVal / G_Command[val2].fVal;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Assign(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 if(G_Command[val1].iString>=0) {

  G_Var[G_Command[val2].iVar].str = G_Command[val1].iString;

  G_Command[val2].iString = G_Command[val1].iString;

 }

 else {

  G_Var[G_Command[val2].iVar].val = G_Command[val1].fVal;

  G_Command[val2].fVal = G_Command[val1].fVal;

 }

 StackPush(&G_StackValue, val2);

 return idx;

 

}

 

int Act_G(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)>0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else {

  if(G_Command[val1].fVal>G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Ge(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)>=0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else {

  if(G_Command[val1].fVal>=G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_L(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)<0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else {

  if(G_Command[val1].fVal<G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Le(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)<=0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else {

  if(G_Command[val1].fVal<=G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Eq(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)==0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else {

  if(G_Command[val1].fVal==G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Ne(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>-1 && G_Command[val2].iString>-1)

  if(strcmp(G_String[G_Command[val1].iString].content,G_String[G_Command[val2].iString].content)!=0)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 else { 

  if(G_Command[val1].fVal!=G_Command[val2].fVal)

   G_Command[val1].iControl=1;

  else

   G_Command[val1].iControl=0;

 }

 

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_And(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 if(G_Command[val1].iControl && G_Command[val2].iControl)

  G_Command[val1].iControl=1;

 else

  G_Command[val1].iControl=0;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_Or(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val2);

 StackPop(&G_StackValue, &val1);

 if(G_Command[val1].iControl || G_Command[val2].iControl)

  G_Command[val1].iControl=1;

 else

  G_Command[val1].iControl=0;

 StackPush(&G_StackValue, val1);

 return idx;

 

}

 

int Act_If(int idx) {

 

 

 int val;

 StackPop(&G_StackValue, &val);

 AddControl(D_ACT_IF, val, G_Command[val].iControl);

 StackGetTop(&G_StackControl, &val);

 

 if(val==-1)

  StackPush(&G_StackControl, G_iControlCount);

 else {

  G_Control[G_iControlCount].iControl=G_Control[val].iControl & G_Control[G_iControlCount].iControl;

  StackPush(&G_StackControl, G_iControlCount);

 }

 return idx;

 

}

 

int Act_Else(int idx) {

 

 int val1,val2;

 StackPop(&G_StackControl, &val1);

 StackGetTop(&G_StackControl, &val2);

 if(val2==-1 || G_Control[val2].iControl==1)

  G_Control[val1].iControl=!G_Control[val1].iControl;

 StackPush(&G_StackControl, val1);

 return idx;

 

}

 

int Act_EndIf(int idx) {

 

 int val;

 StackPop(&G_StackControl, &val);

 return idx;

 

}

 

int Act_Switch(int idx) {

 

 int val;

 StackPop(&G_StackValue, &val);

 AddControl(D_ACT_SWITCH, val, G_Command[val].iControl);

 StackGetTop(&G_StackControl, &val);

 

 if(val==-1)

  StackPush(&G_StackControl, G_iControlCount);

 else {

  G_Control[G_iControlCount].iControl=G_Control[val].iControl & G_Control[G_iControlCount].iControl;

  StackPush(&G_StackControl, G_iControlCount);

 }

 return idx;

 

}

 

int Act_Case(int idx) {

 

 

 int val1,val2,val3;

 StackPop(&G_StackControl, &val1);

 StackGetTop(&G_StackControl, &val2);

 if(val2==-1 || G_Control[val2].iControl==1) {

  StackPop(&G_StackValue, &val3);

  if(G_Command[val3].fVal==G_Command[G_Control[val1].iVal].fVal)

   G_Control[val1].iControl=1;

  else

   G_Control[val1].iControl=0;

 }

 StackPush(&G_StackControl, val1);

 return idx;

 

}

 

int Act_EndSwitch(int idx) {

 

 int val;

 StackPop(&G_StackControl, &val);

 return idx;

 

}

 

int Act_BeginWhile(int idx) {

 

 int val;

 AddControl(D_ACT_BEGINWHILE, idx, 1);

 StackGetTop(&G_StackControl, &val);

 

 if(val==-1)

  StackPush(&G_StackControl, G_iControlCount);

 else {

  G_Control[G_iControlCount].iControl=G_Control[val].iControl & G_Control[G_iControlCount].iControl;

  StackPush(&G_StackControl, G_iControlCount);

 }

 return idx;

 

}

 

int Act_While(int idx) {

 

 int val1,val2;

 StackPop(&G_StackValue, &val1);

 StackPop(&G_StackControl, &val2);

 

 G_Control[val2].iControl=G_Control[val2].iControl & G_Command[val1].iControl;

 StackPush(&G_StackControl, val2);

 return idx;

 

}

 

int Act_EndWhile(int idx) {

 

 int val;

 StackGetTop(&G_StackControl, &val);

 if(G_Control[val].iControl)

  return G_Control[val].iVal;

 else {

  StackPop(&G_StackControl, &val);

  return idx;

 }

}

 

int Act_Print(int idx) {

 

 int val1;

 StackGetTop(&G_StackValue, &val1);

 

 if(G_Command[val1].iString>=0)

  printf("%s\n",G_String[G_Command[val1].iString].content);

 else

  printf("%g\n",G_Command[val1].fVal);

 

 return idx; 

 

}

 

int FormulaParserInput(char * buf, int maxlen) {

 

 int i;

 if(G_iFormulaPos>=strlen(G_sFormula))

  return 0;

  for(i=0; i<maxlen && G_sFormula[G_iFormulaPos]!='\0'; i++)

    buf[i] = G_sFormula[G_iFormulaPos++];

  return i;

 

}

 

int FormulaGetVar(char * name, void ** val, int * type) {

 

 int i;

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

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

   if(G_Var[i].str>-1) {

    *val = &G_String[G_Var[i].str].content;

    *type = D_VAR_STRING;

   }

   else {

    *val = &G_Var[i].val;

    *type = D_VAR_FLOAT;

   }

   return 0;

  }

 return 1;

 

}

 

 

void FormulaPrint() {

 

#ifdef DEBUG_PRINT

 

 printf("<Print>\n");

 int i;

 for(i=0;i<=G_iCommandCount;i++)  {

  printf("id: %2d act: %10s iv: %d fv:%g ",

  i,

  G_CommandRelation[G_Command[i].iTypeAction].sText,

  G_Command[i].iVar,

  G_Command[i].fVal

  );

  if(G_Command[i].iString>=0)

   printf("is:%s\n", G_String[G_Command[i].iString].content);

  else

   printf("is:%d\n", G_Command[i].iString);

 }

 

#endif

 

}

 

int FormulaParser(char * str, void (* loadvar)(char *, void **, int *)) {

 

 G_iFormulaPos=0;

 G_LoadVar=loadvar;

 

 StackFree(&G_StackControl);

 StackFree(&G_StackValue);

 

 strcpy(G_sFormula, str);

 yyparse();

 

 FormulaPrint();

 

 int i;

 for(i=0;i<=G_iCommandCount;i++)  {

 

  if(G_Command[i].iTypeAction>=D_ACT_IF || G_Command[i+1].iTypeAction==D_ACT_CASE)

   i=G_CommandRelation[G_Command[i].iTypeAction].Execute(i);

  else { 

  

   int val;

   StackGetTop(&G_StackControl, &val);

  

   if(val==-1)

    i=G_CommandRelation[G_Command[i].iTypeAction].Execute(i);

   else {

    if(G_Control[val].iControl)

     i=G_CommandRelation[G_Command[i].iTypeAction].Execute(i);

   }

   

  }

 

 }

 

 FormulaPrint();

 return 0;

 

}

 

 

E.public.h

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

 

#define MAX_FORMULA_LEN 500

 

#define MAX_STRING_LEN 10   /* 字符最大长度 */

 

#define  D_VAR_NULL    0

#define  D_VAR_INT     1

#define  D_VAR_FLOAT   2

#define  D_VAR_CHAR    3

#define  D_VAR_STRING  4

 

extern float LoadFloat;

extern char  LoadString[MAX_STRING_LEN];

 

 

F.main.c

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

 

#include <stdio.h>

#include "public.h"

 

float LoadFloat;

char  LoadString[MAX_STRING_LEN];

 

void loadvar(char * mark, void ** val, int * type) {

 

 if(strcmp(mark,"DEF_NAME")==0) {

  strcpy(LoadString,"liwei");

  *val=&LoadString[0];

  *type=D_VAR_STRING;

  return;

 }

 if(strcmp(mark,"DEF_RATE")==0) {

  LoadFloat=9.5;

  *val=&LoadFloat;

  *type=D_VAR_FLOAT;

  return;

 }

 if(strcmp(mark,"DEF_TYPE")==0) {

  strcpy(LoadString,"GP");

  *val=&LoadString[0];

  *type=D_VAR_STRING;

  return;

 }

 

 *type==D_VAR_NULL;

}

 

int main(int argc, char *argv[]) {

 

  int iRet;

 

 char sFile[MAX_FORMULA_LEN]={0};

 FILE * fp;

 

 if(argc!=2) {

  printf("<Error> Missing file name.\n");

  exit(-1);

 }

 

 fp = fopen(argv[1], "r");

 if(fp==NULL) {

  printf("<Error> Cannot open file.\n");

  exit(-1);

 }

 fread(sFile,sizeof(char),MAX_FORMULA_LEN,fp);

  fclose(fp);

 

 iRet=FormulaParser(sFile, loadvar);

 printf("ParserRet:%d\n",iRet );

 

 

 void * pRet;

 int iType;

 iRet=FormulaGetVar("i", &pRet, &iType);

 if(iRet==0)

  if(iType==D_VAR_STRING)

   printf("i:%s\n",(char *)pRet );

  if(iType==D_VAR_FLOAT)

   printf("i:%g\n",*(float *)pRet );

 

 return iRet;

}

 

 

G.mk 编译shell文件

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

 

bison -d stack.y

lex stack.l

gcc -g -c lex.yy.c stack.tab.c stackparser.c

ar -rl stack.a *.o

gcc -g -o lw main.c stack.a

 

 

H.mkclean shell文件

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

 

rm stack.tab.c

rm stack.tab.h

rm lex.yy.c

rm *.o

rm *.a

rm lw

 

 

四、思路说明

 

    上面列出的代码是目前最长的。

    可见写一个堆栈编译器并不是一簇而就的事情,即使对于目前的实例,也需要有很多完

善的地方。设计一个堆栈编译器,我们往往需要从最简单最容易的语句开始。

 

    A.简单的堆栈分析思想

   

    我们先举一个简单的例子,a=1+2。要完成这个公式的计算,我们首先需要将12,压

入堆栈,然后分析到+运算,此时又需要将12出栈,执行+法后将3压入。继续分析,需要

压入a,在最后的=运算时,将3a出栈进行赋值运算后,将a入栈。运作序列如下:

 

  id:  0 act:  pushvalue                  

  id:  1 act:  pushvalue                  

  id:  2 act:        add                  

  id:  3 act:    pushvar                  

  id:  4 act:     assign

 

  使用堆栈进行编译的难点在于,将无比复杂的语法结构抽象到简单的入栈出栈操作。单

从这个角度讲,是很难一步倒位的。一般地,我们需要先将指令字符串根据设定的语法归并

规则编译成有序的指令序列。然后对指令序列制定堆栈动作执行函数,依次执行指令并调用

相应函数。

 

    值得欣慰的是,早在N年前,外国人就形成了一套十分强大的编译理论体系(lex,yacc)

去完成归并语法的工作。我们只需实现外部的规则动作。

 

    B.lexyacc的归并语法设计

   

    与前面例子相似的是,使用G_Var存储编译时的变量信息,G_sBuff存储编译语句,这里

又增加了G_String统一存储编译语句中的所有字符串。至于lexyacc设计方法也是相近的,

只是冗余了一些语句标志,如ifx,elsex,switchx等。这些标志是为了生成顺序正确的指令

序列。

 

    lexyacc会把编译后的所有结果指令存于G_Command中。见AddCommand

   

  /* 内存指令集结构 */

  typedef struct {

   

    int iTypeAction;

    int iTypeVal;

   float fVal;

   int iVar;

   int iString;

   int iControl;

 

  } TCommand;

 

  这个指令集的设计是关键所在,iTypeAction说明这个指令的类型,iTypeVal表示指令

的值类型。fVal存储整型浮点型数值,iVar存储变量索引,iString如果不是-1,则表示字

符串的索引,iControl表示指令返回的控制信息。

 

 

    C.堆栈编译

   

    lexyacc编译后会把指令生成到G_Command中,随后对G_Command进行遍历处理,并调

用相关动作函数进行出入栈操作。(Act系列函数) 这里出入栈操作的是G_Command索引,处

理的结果皆存于G_Command中,这是外人比较难以理解的一点。

    TCommand结构体元素是相对独立的,fVal,iString互斥,iVar标志变量索引,iControl

只用于控制堆栈的值。

 

    在刚开始时需要对各种语法结构做统筹分析。比如拿分支和循环这类语句来说,if分支

就需要维护一个控制状态,由于嵌套语句的存在,这个控制状态需要具有堆栈的特点。每次压

入新if语句要进行现有堆栈的判断,如果前一iffalse,这个if即使为true也还是false,另

else也要做相似处理。之后对于endif做出栈操作,标志这对if/else已处理。switchif

稍微复杂一些,还要记录原始值,每次case要做比较。while不仅需要条件还要进行跳转,这是

Act动作函数有返回值的重要原因。

    以上这个分析要进行比较体系化的考虑,这些也便于以后的功能扩展,如goto等。

    这里我引入了StackValueStackControl两个堆栈。Value用于普通的顺序计算,Control

用于if else switch while等控制结构。关于控制堆栈,可以参见Act_If,Act_Else等控制

动作函数,在编译指令序列时,会读取控制信息来判断是否执行该指令。值的注意的是,Act

动作函数还返回了下一指令的索引,这主要用于对循环,跳转等方面的处理,默认是顺序执行。

    总得来说,TCommand的元素含义要独立,并严格保证处理指令时G_Command的指令数据的

合法性。

 

 

    D.变量传值和获取

   

    还是回调函数的思想,只是由于字符串的存在制造了一些小麻烦,所以使用了二级指针,

并通过返回值类型,来进行外部判断处理。不过Linux Unix下的gcc不支持引用传值,这里使

用的都是指针传递。

   

 

五、一些注意事项

 

 

    A.stack.l,stack.y 文件要求为Unix格式,这一点和LinuxUnixshell很类似,DOS

格式的Shell是不能够被执行的,同样bison,lex编译DOS格式文件会出错误提示。

 

    B.SegmentFault多半产生于内存越界(前面已经着重说明过),除此以为还经常出现这类

情况,产生这类错误的位置的代码并无错误,但是内存值已出现乱码,这一般是指针使用不当。

 

    C.避免一切的warning项,比如在stack.y中,将函数的预说明去除,会提示warning,但

是在执行中,函数传值就会发生根本性的错误。

 

    D.还在在编译C/C++出现的堆栈溢出错误,当然可以用ulimit查看参数,但多半也由内存

越界有关,遇到莫名其妙的错误第一点就要想到内存问题。

 

    E.stack.l,stack.y 注意 规则应用顺序,shift-reduce的顺序

   

    F.耐心才是最重要的,尽量多打印一些调试信息,对于复杂的语法结构调试起来并不是很

轻松的事。

 

 

六、总结

 

    lexyacc应用目前是在Unix/Linux平台下,生成的是C代码,固然C++使用这些接口没有

问题,但不能满足Windows平台的使用需求。从下文起会开始介绍Windows下这类工具的使用,

以及C/C++/Java代码的生成。

 

 

 

LexYacc应用方法().Windows下使用LexYacc

 

草木瓜  20070904

 

一、序

 

    不想LexYacc系列的最后一篇文章竟如此“难产”,已时隔三个月之久。不由慨叹自由可支

配时间是如此之少,如此岂不谓新时代的“奴隶”~

    罢罢罢,闲话少叙,回归正题,本文主要介绍在Windows下如何去使用LexYacc,以作为

本系列文章的终结。

   

二、方法介绍

 

    Windows下使用LexYacc多种多样,简单罗列如下:

   

    a.Cygwin

   

    CygwinWindows平台上运行的unix/linux模拟环境,由Cygnus Solutions开发。

    Cygnus起初把gccgdbgas等开发工具进行了改进,使他们能够生成并解释win32的目标

文件。然后再把这些工具移植到windows平台上去。

    移值方案有多种,一是基于win32 api对这些工具的源代码进行大幅修改。但工作量太大,他

们采取了另一种方法,即开发一个共享库(cygwin.dll),把win32 api中没有的unix风格的调用(如

fork,spawn,signals,select,sockets等)封装在里面,也就是说,他们基于win32 api写了一个unix

系统库的模拟层。这样,只要把这些工具的源代码和这个共享库连接到一起,就可以使用unix

机上的交叉编译器来生成可以在windows平台上运行的工具集。

 

    以这些移植到windows平台上的开发工具为基础,Cygnus又逐步把其他的工具(几乎不需要

对源代码进行修改,只需要一些配置脚本)软件移植到windows上来。这样,就在windows平台

模拟出一个unix环境。

 

    Cygwin是一个功能强大的工具集,借助它不需要一台 Unix 机器也可以编译运行 Unix 程序,

这可以帮助程序开发人员把应用程序从 UNIX/Linux 移植到 Windows 平台,或者在 Window 平台

开发 UNIX/Linux 应用程序。Cygwin目标在于兼容性,而不是执行效率。

 

    b.MinGW + MSYS

   

    MinGW (Minimalist GNU for Windows) 原来是CygwinGNU开发工具的一个分支,实质是一

些头文件和函数库的集合,该集合允许在没有第三方动态链接库的情况下使用GCCGNU Compiler C

开发Win32程序。MinGW主要由GNU binary utilitiesGCCGDB组成。同时还包括一些重要的

库:libcC Runtime),专用于Win32环境的API接口库。MinGW开发的程序与MS Visual Studio

程序可以彼此互相通用。

    MinGW允许控制台模式的程序使用微软的标准C运行库(MSVCRT.DLL),所以你既可以用

GCC写控制台模式的ANSI程序,也可以用微软提供的 C 运行库。该功能是 Windows32 API

不具备的。

    Cygwin+gccMinGW,都是gccwindows下的编译环境。Cygwin+gcc编译的程序,在windows

执行时必须依赖cygwin.dllMinGW则不需要。相比 Cygwin 执行效率是 MinGW 的重点。

 

    MinGW只是开发环境,其实就是GCCWindows下的一个实现,没有包括Linux/Unix一些其他

的工具(如bashsh等),而MSYS弥补了这一点。MinGW常于MSYS配合使用。

 

    MSYS (Minimal GNUPOSIXsystem on Windows) ,是一个小型的GNU环境,包括基本的

bashmake等等,其提供了Bourne shell的类似环境。

 

    c.下载flexbisonWin32源码或版本

   

    其实上面两种方法本质也是这个。推荐网址: http://gnuwin32.sourceforge.net

   

    d.Dev-C++ 编译由 bison flex 编译生成代码

   

    其实是使用 Dev C++ 代替了MinGW gcc 或者 Cygwin gcc

    Dev-C++是一个C&C++开发工具,是一款自由软件,遵守GPL协议。它集合了GCCMinGW32

等众多自由软件,并且可以从devpak.org上取得最新版本的各种工具支持,而这一切工作都是来自

全球的爱好者所做的工作。 Dev-C++ IDE采用Delphi开发。

 不过要注意的是,变量声明位置问题的会导致编译不通过,即使用前面文章的例子在Dev-C++

认设置下是不能编译通过的。解决起来也简单,手工移到函数体开始就行了。

 

    e.使用Parser Generator

 

    Parser Generator可以生成Windows平台下的C/C++/Java LexYacc代码。支持Borland C++ Builder

Visual C++多种编译环境。这里我使用的是Visual C++.Net Eclipse 测试生成的LexYacc代码。

 

 (本机测试环境 Visual C++.Net / Eclipse 3.1 + Parser Generator 2.07 )

 

    在使用Parser Generator前,须要Build相关Lib。打开Parser Generator IDEProject -> LibBuilder

-> 选中Visual C++ (32-Bit) -> Properties -> 在弹出的对话框中依次设置 Options,示例如下:

   

    Compile Version : Version 7 (.Net)

    Unicode : True

    Treat w_char as Build-in Type :  True

    Compiler Bin Directory : E:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\bin

    Compiler Bin Directory (2) : E:\Program Files\Microsoft Visual Studio .NET 2003\Common7\IDE

    Compiler Include Directory : E:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include

    Compiler Include Directory (2) : E:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\PlatformSDK\Include

    Compiler Library Directory : E:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\lib

    Compiler Library Directory (2) : E:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\PlatformSDK\Lib

   

 注:注意根据自已情况调整Directory目录位置。

 

 设置完成之后确认并返回LibBuilder。点击Build就可以编译Visual C++须使用的lexyacclib库。生成库

文件在软件安装目录下的E:\Program Files\Parser\Cpp\Lib\msvc32下。

 然后可以在Visual C++环境下设置添加

  头文件目录

  E:\Program Files\Parser\Cpp\Include

  库文件目录

  E:\Program Files\Parser\Cpp\Lib\msvc32

  依赖项

  yl.lib yld.lib ylmt.lib ylmtd.lib ylmtr.lib ylmtrd.lib ylmtri.lib ylmtrid.lib

 

 (Visual C++ 环境设置方法可见 《Oracle数据库开发().Windows下配置使用ProChttp://blog.csdn.net/liwei_cmg/archive/2007/06/06/1641330.aspx 一文,有详尽的描述,这里不在赘述 )

 

 Java的代码生成也十分相似,将自带示例E:\Program Files\Parser\Java\Examples\Calc代码,添加到Eclipse项目

并把E:\Program Files\Parser\Java\Lib\yl.jar添加到项目中,启动Java Application即可。

 

    项目文件列表:

   

    calc_lexer.java

    calc_parser.java

    Symbol.java

    SymbolTable.java

   

    yl.jar

   

    Run As -> Java Application ,控制台Console即可进行输入测试。

 

    更多Parser Generator使用方法,见联机手册。

   

   

三、后记

 

    本文所提到的方法大多一带而过,至于具体的内容,每个人自可亲自尝试,此也不属于本系列

的范围。文中提到的交叉编译的问题,这个概念在《手机应用与开发》一栏已有比较整体的描述,

在未来系列《Linux平台开发浅谈》中会有更详细的说明。

 

posted on 2008-09-20 02:30 肥仔 阅读(16529) 评论(3)  编辑 收藏 引用 所属分类: LEX & YACC

评论

# re: 草木瓜----Lex和Yacc教程[未登录]  回复  更多评论   

我表示光看例子完全看不懂,还是回去啃那破英文的好了。
2012-06-15 20:01 | Michael

# re: 草木瓜----Lex和Yacc教程  回复  更多评论   

是原创的文章么? 怎么缩进那么差,严重影响阅读啊,有没有好点的版本?
2012-10-21 13:14 | TNTDoctor

# re: 草木瓜----Lex和Yacc教程  回复  更多评论   

这么长的文章。。
http://www.seanyxie.com/c的rtti(typeid和dynamic_cast)/
2014-09-20 21:14 | xie

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理