好久没更了，现在公司边学习边做一个项目可能后面的写文章的时间也不会很多，今天想记录的这个知识点也是目前做的项目所需的一个简单框架，学的不是很深入简单记录一下。
词法&语法
词法即一个词一个词的检测，如我说“我想你”，如果拆分的话有“我”、“想、“你”，我们将其统计即为词法分析。语法分析则是在词法拆分后进行判断“我想你”很显然是对的，但如果是“我你想”那么就有问题。其中词法分析用的是flex实现，语法分析使用的是bison实现的。
Flex
flex用于生成词法程序（注意flex不能做词法分析，它生成的程序才能），它是一个自动化工具，可以按照定义好的规则自动生成一个C函数yylex()，也称为扫描器（Scanner）。这个C函数yylex()把文本串作为输入，按照定义好的规则分析文本串中的字符，找到符合规则的一些字符序列后，就执行在规则中定义好的动作。
也可以理解为这个函数其实是一个入口，当调用这个函数时我们会自动进入flex的布局中正则匹配从键盘上输入的字符串，如果成功就执行动作（说着可能有点懵，下面会用代码演示便于理解）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/*flex-wc.l*/ %option noyywrap %{ int chars = 0; int words = 0; int lines = 0; %} %% [a-zA-z]+ { words++; chars += strlen(yytext); } n { lines++; chars++; } . { chars++; } %% int main() { yylex(); printf("%8d %8d %8dn", lines, words, chars); return 0; }
1
2输入：hello world 输出：1 2 10
flex程序是用flex语法与C代码混合组成的，包括三部分：
①%option……%{……%} 包含第一行的选项 和 后面百分号+括号内的声明，其中括号内的声明是纯C语法。这里声明了一些全局变量来统计词、字和行。
②%%……%%包括模式和动作，可以看到模式其实就是一种匹配机制，上面用的是正则匹配，其实大部分用的也是正则匹配，后面的动作即要执行的代码。其中yytext是匹配到的数据（如果匹配到多次就执行动作多次）。
③后面的就是纯C代码，目的是用于生成一个flex的入口。
在Linux下编译的指令为：
1
2
3
4flex flex-wc.l gcc lex.yy.c -lfl ./a.out
继续温习flex的一个代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23%{ enum { NUMBER = 258, ADD = 259, }; int yylval = 0; %} %% "+" { return ADD; } [0-9]+ { yylval = atoi(yytext); return NUMBER; } %% int main() { int token; while((token = yylex()) != 0) { printf("%d", token); if (token == NUMBER) printf(" = %d", yylval); printf("n"); } return 0; }
1
2
3
4
5
6
7输入： 13 + 14 输出： 258=13 259 258=14
上面的代码为什么要用258、289？其他的0 1 2 3不行吗？这里要提一下在与bison联合使用时，标记编号的0值意味着文件结束；而为了防止与ASCII码和内定值冲突，其他的标记编号要从258开始定义。而且从输出结果中我们可以知道yylex()的返回值就是flex的return。
Bison
Bison用于生成语法分析器程序，在flex&bison中flex是作为辅助一方，主导核心位在bsion，bison要做的事也会是比较难的，如计算器中乘除法与加减法的优先级的设计，以及上下文无关的设计等等。而且也不太好理解。
bison的语法分析有两种：一种是LALR(1)，自左向右前看一个记号；另一种是GLR，通用的自左向右。大多数语法分析器使用LALR(1)，它不如GLR强大但被认为比GLR更块和更容易使用。bison程序包括与flex程序相同的三个部分结构：声明部分、规则部分、C代码部分，三个部分两两之用%%隔开，yyparse()可以理解为语法分析的入口。
直接看一串语法分析的代码（别的师傅那借用的，下面会附上链接）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/* simplest version of calculator */ %{ #include <stdio.h> int yyerror(const char *, ...); extern int yylex(); extern int yyparse(); %} /* declare tokens */ %token NUMBER %token ADD SUB MUL DIV ABS %token OP CP %token EOL %% calclist: /* nothing */ | calclist exp EOL { printf("= %dn> ", $2); } | calclist EOL { printf("> "); } /* blank line or a comment */ ; exp: factor | exp ADD exp { $$ = $1 + $3; } | exp SUB factor { $$ = $1 - $3; } | exp ABS factor { $$ = $1 | $3; } ; factor: term | factor MUL term { $$ = $1 * $3; } | factor DIV term { $$ = $1 / $3; } ; term: NUMBER | ABS term { $$ = $2 >= 0? $2 : - $2; } | OP exp CP { $$ = $2; } ; %% int main() { printf("> "); yyparse(); return 0; } int yyerror(const char *s, ...) { int ret; va_list va; va_start(va, s); ret = vfprintf(stderr, s, va); va_end(va); return ret; }
光有语法分析是不够的，语法分析是建立在词法分析的基础上，所以再附上师傅的词法分析，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/* recognize tokens for the calculator and print them out */ %{ # include "fb1-5.tab.h" extern int yyerror(const char *, ...); %} %% "+" { return ADD; } "-" { return SUB; } "*" { return MUL; } "/" { return DIV; } "|" { return ABS; } "(" { return OP; } ")" { return CP; } [-+]?[0-9]+ { yylval = atoi(yytext); return NUMBER; } n { return EOL; } "//".* [ t] { /* ignore white space */ } . { yyerror("Mystery character %cn", *yytext); } %%
直接过一遍语法分析，可以看到有一种写法
1
2term: NUMBER | ABS term { $$ = $2 >= 0? $2 : - $2; }
这个写法我个人觉得比较难理解。term为目标符号为后面动作$$的值，NUMBER是一个限制，一开始默认会$$=$1即将NUMBER赋给term，后面的操作得看NUMBER是否符合条件，当term有值过后在一步一步往后推进，其实说白了这就可以用递归的思想来理解。
①声明部分：
%{到%}部分会被拷贝到目标分析程序的开头。
%token后接一个大写的变量，可以理解为词法分析器得到的结果，用于传入语法分析器进行分析。
② 规则部分：
1、冒号 : 用于定义规则。分号 ; 表示一个规则的结束。
2、在每个规则之后，使用{}括起，表明如何处理。
3、规则按照语法树从上到下定义规则，第一条规则为语法起始符号，必须与输入匹配。
4、目标符号（冒号左边的语法符号）的值在动作中代码用$$代替，右边（准确来说是一个限制，后面才算）语法符号的语义值依次为$1,$2，直到这条规则的结束。
5、如果一个规则缺少现实的动作，语法分析器将把$1赋予$$，这是一个内部设定。
返回记号的时候，记号对应的值是存储在yylval变量中。
③纯 C部分：
主程序，负责调用yyparse()，并输出结果。
上面的代码有一段代码很有意思，就是如下
1
2
3
4
5exp: factor | exp ADD exp { $$ = $1 + $3; } | exp SUB factor { $$ = $1 - $3; } | exp ABS factor { $$ = $1 | $3; } ;
可以看到执行先后顺序相同的加减法一个是exp ADD exp 另一个是 exp SUB factor，这是为什么呢？这里需要提到一个二义性的问题，啥叫二义性？就是执行一个相同的东西会出现两种不同结果的可能。正如上述如果出现了
3 - 5 + 4 = ？
如果是exp SUB exp那么存在的二义性为
（3-5）+ 4 = 2
3-（5+4）=-6
相反如果是加法就不会出现这种二义性的情况，所以加法使用exp SUB exp。
而减法不行，因此用factor代替，为啥factor可以？看最低NUMBER那一条其中可以添加括号，所以用factor就可以避免这种二义性的结果产生。
参考：flex与bison_德阳凯子哥的博客-CSDN博客_flex和bison
二. 初识Bison：写一个简单计算器 - 简书
3.01 bison基本概念及语法介绍_ronnie88597的博客-CSDN博客_bison语法
最后
以上就是爱听歌苗条最近收集整理的关于词法分析flex & 语法分析bison词法&语法FlexBison的全部内容，更多相关词法分析flex内容请搜索靠谱客的其他文章。
发表评论 取消回复