lex，yacc学习笔记

lex和yacc是什么

lex是一个生成词法分析器的程序，flex是其开源版本。

所谓生成词法分析器，就是按照你的意愿，遇到某个词法时执行某个动作

yacc时生成编译器的编译器，生成的主要是编译器的词法解析器。配合yacc使用，当解析到某种语法时执行一定的动作。

lex的开源版本为flex，yacc对应gnu的bison

kali安装

1
sudo apt install flex bison

lex使用简单介绍

lex文件格式为*.l，例子：

1
2
3
4
5
6
7
%{
#include <stdio.h>
%}
%%
stop printf("Stop command received\n");
start printf("Start command received\n");
%%

保存，然后执行

1
lex 文件名.l

会在同目录下生成lex.yy.c

执行命令

1
cc lex.yy.c -ll -o a # -ll代表使用lex库，提供了main函数，-o a代表输出到

运行a程序，发现输入stop和start时会打印对应的东西，其他情况回显

lex使用正则表达式

yacc使用

yacc语法分析器解析一个标识流符，这里就需要lex配合了。因为yacc并不知道输入流中的字符是什么东西。

假定有一个温度计，使用如下语言控制它

1
2
3
4
5
heat on
Heater on!
heat off
Header off!
target temperature set!

lex的tokenizer为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%{
#include <stdio.h>
#include "y.tab.h"
%}

%%
[0-9]+ return NUMBER;
heat return TOKHEAT;
on|off return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* ignore end of line */;
[ \t]+ /* ignore whitespace */
%%ure set\n");
};

y.tab.h中定义了NUMBER，TOKHEAT这些常量，这个文件由yacc根据我们编写的语法规则生成

yacc的文件后缀名为*.y

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
48
49
%{
#include <stdio.h>
#include <string.h>

//在lex.yy.c里定义，会被yyparse()调用。在此声明消除编译和链接错误。
extern int yylex(void); 

// 在此声明，消除yacc生成代码时的告警
extern int yyparse(void); 

int yywrap()
{
	return 1;
}

// 该函数在y.tab.c里会被调用，需要在此定义
void yyerror(const char *s)
{
	printf("[error] %s\n", s);
}

int main()
{
	yyparse();
	return 0;
}
%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%
commands: /* empty */
| commands command
;

command: heat_switch | target_set ;

heat_switch:
TOKHEAT STATE
{
	printf("\tHeat turned on or off\n");
};

target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
	printf("\tTemperature set\n");
};
%%

编译运行这个程序

1
2
3
lex a.l
yacc -d a.y # 增加-d选项以生成y.tab.h
cc lex.yy.c y.tab.c -o a

现在为止，已经具备一个编译器的基本单元。但是考虑这个问题：lex识别了一个标识符，但是C语言中不同的标识符有不同的含义，所以还需要为它生成一个ID，为语义分析做准备。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%{
#include <stdio.h>
#include "y.tab.h"
%}
// yytext指识别到的语句，yyval用来向yacc传递值
%%
[0-9]+ yylval = atoi(yytext); return NUMBER;
heat return TOKHEAT;
on|off yylval = !strcmp(yytext, "on"); return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* ignore end of line */
[ \t]+ /* ignore whitespace */
%%

yacc规则中也需要做出一些更改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
    printf("\tTemperature set to %d\n", $3);
};
// $3表示这个语法的第三个单元中的参数
heat_switch:
TOKHEAT STATE
{
    if ($2)
        printf("\tHeat turned on\n");
    else
        printf("\tHeat turned off\n");
}
// $2表示这个语法中第二个单元的参数

参考资料

[1] Lex与YACC详解 - Deepliu的文章 - 知乎