「编译原理」flex入门

lex入门章

1 | Win flex-bison的安装

lex 就是词法分析器生成器, yacc 就是语法分析器

flex和bison分别是lex和yacc在GNU下的实现

Win flex-bison提供了 flex bison for Windows 的另外一种移植，将GNU m4宏处理器源代码集成进 win flex-bison ，不依赖Msys，Msys2，Cygwin 提供的模拟类 Unix 运行环境，不依赖GNU m4宏处理器便可生成 C 目标文件。

Win flex-bison的安装地址https://sourceforge.net/projects/winflexbison/

安装好后:

• 解压到指定目录
• 将该目录添加到环境变量

2 | lex的语法

from老师的ppt

简而言之:

{definitions}           // 定义部分
%%
{rules}                 // 规则部分
%%
{user subroutines}      // 用户自定义代码部分

2.1 | definitions - 辅助定义部分

辅助定义部分实际上就是给某些后面可能经常用到的正则表达式取一个别名, 从而简化词法规则的书写

该部分的格式一般为:

name definition

其中 name 是名字，definition 是任意的正则表达式

e.g.

…
digit [0-9]
letter [_a-zA-Z]
%%
{rules}
%%
{user subroutines}

值得一提的是，如果用户想要对这部分所用到的变量、函数或者头文件进行声明，可以定义部分之前使用%{和%}符号将要声明的内容添加进去。被%{和%}所包围的内容也会一并拷贝到生成的c语言文件的最前面^[4]。

在辅助定义部分同样包含了flex的控制选项%options, 下面是一些常用options的总结: ^[5]

1. %option reentrant: flex能够生成一个可重入的扫描器。通过定义%option reentrant（与-R选项等价）来实现可重入。所生成的扫描器在一个或多个控制线程中不仅可移植，而且安全性好。可重入扫描器通常应用于多线程应用程序。任何一个线程都可以在不考虑与其他线程同步的情况下创建并执行一个可重入的flex扫描器。默认情况下，flex生成一个不可重入的扫描器。本项目为了实现多线程，因而在定义段指定%option reentrant.
2. %option bison-bridge: flex和bison联合使用的选项，由于flex和bison部分内容声明不同，使用此选项后可以相互调用。
3. %option bison-locations: 此模式同上面参数同时使用，如果做了此声明，yylex 将被声明为int yylex (YYSTYPE lvalp, YYLTYPE llocp, yyscan_t scaninfo);加入了location参数.
4. %option 8bit: 识别其输入中8位字符的扫描器。
5. %option never-interactive: flex 生成的扫描器从不认为输入是交互的（不会调用isatty()
6. %option nodefault: 所有没有被匹配的输入都拷贝到yyoutflex允许在添加%option nodefault，使它不要添加默认的规则这样输入无法被给定的规则完全匹配时，词法分析器可以报告一个错误。
7. %option noinput:不使用默认的input函数
8. %option nounput: 添加Flex默认的C函数，比如yy_scan_buffer，yy_scan_bytes，yy_scan_string
9. %option noyywrap: 不使用yywrap()，当lex读取到文件末尾时，会调用yywrap(), 目的是，当有另外一个输入文件时，yywrap可以调整yyin的值并且返回0来重新开始词法分析。如果是真正的文件末尾，那么就返回1来完成分析。
10. %option noyyalloc，%option noyyrealloc，%option noyyfree：不使用flex自带的函数yyalloc，yyrealloc，yyfree（内存的申请，重申请以及释放）
11. %option warn: 开启所有警告
12. %option prefix=”core_yy”: 可以将原来的yylex等函数 变成core_yylex.这样可以在一个程序中建立多个词法分析器。

2.2 | rules - 规则部分

第二部分为规则部分，它由正则表达式和相应的响应函数组成，其格式为：

pattern {action}

其中 pattern 为正则表达式，其书写规则与前面的定义部分的正则表达式相同。而 action 则为将要进行的具体操作，这些操作可以用一段C代码表示。Flex 将按照这部分给出的内容依次尝试每一个规则，尽可能匹配最长的输入串。如果有些内容不匹配任何规则，Flex 默认只将其拷贝到标准输出，想要修改这个默认行为的话只需要在所有规则的最后加上一条 '.'（即匹配任何输入）规则，然后在其对应的 action 部分书写你想要的行为即可。

例如，下面这段Flex代码在遇到输入文件中包含一串数字时，会将该数字串转化为整数值 并打印到屏幕上：

…
digit [0-9]
%%
{digit}+ { printf("Integer value %d\n", atoi(yytext)); }
…
%%
{user subroutines}

其中变量 yytext 的类型为 char* ，它是 Flex 为我们提供的一个变量，里面保存了当前词法单元所对应的词素。函数 atoi() 的作用是把一个字符串表示的整数转化为 int 类型。^[4]

2.3 | user subroutines - 用户子程序部分

第三部分为用户子程序部分，这部分代码会被原封不动地拷贝到生成的c语言文件中，以方便用户自定义所需要执行的函数，main函数也可以写在这里。

3 | 例子

/* C声明 */
%option noyywrap
%{
#define ID 0
#define NUMBER 1
#define CREATE 2
#include <bits/stdc++.h>
using namespace std;
%}
/* 辅助定义正规式 */
char	[a-zA-Z]
digit	[0-9]
digits	{digit}+
optional_fraction	("."{digits})?
optional_exponent	(E[+-]?{digits})?
create create
/* 规则部分 */
%%
{create} { 
    printf("识别CREATE"); 
    return CREATE;
}
									
{char}({char}|{digit})*	{ 
    printf("识别标识符%s：长度为%d\n", yytext, yyleng);
    return ID;
}

{digits}{optional_fraction}{optional_exponent} {
    printf("识别数字%s：长度为%d\n", yytext, yyleng);
    return NUMBER;
}
%%
/* 用户自定义代码部分 */
int main(void)
{
	printf("词法分析成功，返回记号类别为%d\n", yylex());
	return 0;
}

vscode运行

为了简化编译运行过程, 我使用code-runner插件, 将win_flex的输出和g++的编译运行写在一起, settings.json配置如下:

"code-runner.executorMapByGlob": {
       "*.l": "cd $dir && win_flex --wincompat -o $fileName.cpp $fileName && g++ $fileName.cpp -o $fileNameWithoutExt && $dir$fileNameWithoutExt",
   },

也可以写一个简单的批处理bat脚本编译运行

cd %cd%
win_flex --wincompat -o mylexer.cpp mylexer.l && g++ mylexer.cpp -o mylexer && mylexer.exe
pause

addtion | 附录

1. 南京大学词法分析和语法分析课件: https://cs.nju.edu.cn/daixinyu/1006.pdf ↩
2. tutorial on lex/yacc: https://www.youtube.com/watch?v=54bo1qaHAfk ↩
3. bilibili- tutorial on lex/yacc: https://www.bilibili.com/video/BV1mE411h7oo?from=search&seid=10230721842328773717 ↩
4. 博客「编译原理-构造词法分析器」: https://www.xerrors.fun/lexical-analysis ↩
5. 博客「Flex介绍」: https://zhuanlan.zhihu.com/p/89473441 ↩