加载中…
flex与bison的基础知识整理
(2016-02-15 10:25:53)
标签：
杂谈 |
flex与bison的教程看得一头雾水，于是用自己理解整理一下相关知识
flex和bison是用于语法解析的玩意，使用平台是window
使用的原理就是通过“规则文件”来生成一份语法解析的代码，嵌入到程序内/直接编译
我将用这个来写SaraScript的语法解析部分
1、flex
flex用于分词，它比较好理解
flex的规则文件以.l为后缀名，生成的文件为lex.yy.c
规则文件分为3个部分，每个部分之间用%%分割
1.1、声明部分
声明部分可以进行声明和选项设置（还没看到相关介绍）
另外，如果有被%{和%}包围的部分，里面的内容会被完整地复制到lex.yy.c
的开头，通常会用来放置include、define的信息
例如：
%{
#include <stdio.h>
%}
1.2、规则部分
第二个部分被两个%%包围（需换行），这部分主要描述规则，格式是：
正则表达式 {匹配到之后执行的C代码}
例如：
[0-9] {printf("NUMBER %s\n",yytext);}
行首不可留白
1.3、C代码部分
这部分是C代码，它们会被复制到lex.yy.c的最末
通常用于一些未定义接口的定义，例如
int yywrap()
{
return 1;
}
2、bison
bison是语法树的解析，我主要卡在这个上
语法树的内容可以去网络上搜索，这里就不再介绍了
bison的规则文件以.y为后缀，生成的文件为 xxx.tab.c和xxx.tab.h
（我发文为止尚未成功生成这俩文件，这里只是根据教程推测的）
规则文件也分为3个部分
1.1、声明部分和C代码部分
和flex一样，可以进行声明和选项设置（还没看到相关介绍），C代码则是拷贝到文件末
声明部分同时也可以写%{%}
在这之后，一般还要进行token设置
token用于标记语法解析中用到的基本语素，教程里称之为“记号”，应该是一个类似枚举那样的东西，语法是：
%token 记号
例如
%token NUMBER
一行可以声明多个记号，例如
%token ADD SUB MUL DIV
记号这玩意大概就是每个语法树的节点，比如一个变量、一个数字/字符串常量、一个运算符
这些记号将被用于规则部分
通常是：flex中匹配到某个词，然后{return
NUMBER;}返回一个记号，然后在bison的规则中查找应该进行的动作
1.3、规则部分
我主要是卡在这里
这里把教程上的内容贴出来，一行行解释
%%
calclist:
| calclist exp EOL { printf("= %d\n",$2);}
;
exp: factor default $$ = $1
| exp ADD factor { $$ = $1 $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term default $$ = $1
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term: NUMBER default $$ = $1
| ABS term { $$ = $2 >= 0? $2 : - $2; }
;
%%
首先是
calclist:
| calclist exp EOL { printf("= %d\n",$2);}
;
分号;是代表一组规则的结束
calclist:
calclist在教程里被称作语法符号，我认为可以把它视作规则索引，同时我也认为是一个语法树的节点类型
:是“是”xxx的意思，在第一行，:之后没有跟任何东西，表示calclist没有任何东西
|是“或”的意思
calclist exp EOL是一段规则，表示匹配
calclist后有一个exp，exp之后跟一个EOL记号的语法
在解析时，会先找calclist这条规则（这也是我认为它是规则索引的原因），这个过程是递归的
举例说明大概更好理解：
exp EOL可以匹配这条规则，exp EOL exp EOL也可以匹配这个规则，exp EOL exp EOL exp
EOL也可以匹配这个规则、等等。
然后再去找exp规则，是另一段
exp: factor default $$ = $1
| exp ADD factor { $$ = $1 $3; }
| exp SUB factor { $$ = $1 - $3; }
;
看看是否匹配这三者之一
第一条exp: factor default $$ = $1
翻译过来即是 把exp当作factor看待
default $$ = $1的意思是，如何把exp和factor等价起来，在案例中，是直接等同
在这些规则中，$$是:左边的值，这里是指exp，$1、$2等是:或|右边的值依次排序
例如exp ADD
factor，$1就是exp，$2就是ADD，$3就是factor。。。这里需要注意的是$1的exp不等同于$$的exp，exp只是规则名称，就好像类名相同但对象不同
一般而言，我们把同优先级的符号放在一组
剩下的应该没啥问题了，以后有问题再继续
喜欢
0
赠金笔