简单理解Flex & bison 与 词法解析应用
Background
开始之前，先介绍两个概念：Flex和Bison
Flex和Bison 是Linux下用来生成词法分析器和语法分析器代码的工具，编译器的两个重要功能就是他们：
- Flex 可以用来生成词法分析器代码
- 词法分析(lexical analysis 或 Scanning):我的理解就是一个tokenizer，对输入数据，按照我们写好的规则，进行匹配和分词,形成一个个有意义的词块。
- Bison 则是用来生成语法分析器代码的工具
- 语法分析(syntax analysis 或prsing): 将词法分析的输出，按照我们定义的规则，分析每个token之间的关系以及是如何彼此关联的。
Flex
用一个单词统计的例子来简单理解一下Flex
下面这段代码(flex.l)是生成词法分析器的源文件，定义了词法规则以及相应的动作。
/* 统计输入字符串*/
%{
int chars = 0;
int words = 0;
int lines =0;
%}
%%
[a-zA-Z]+ {
words++;
chars += strlen(yytext);
}
\n { chars++; lines++;}
. { chars++; }
%%
int main(int args, char **argv)
{
yylex();
printf("lines=%6d words=%6d chars=%6d\n", lines, words, chars);
return 0;
}
这个源文件主要分为三个部分:
- %...%: 第一部分定义了一些变量和头文件
- %%...%%:第二部分使用正则表达式定义了词法解析规则
- 最后部分为C代码，会被拷贝到生成的词法分析器
- yylex是Flex提供的一个函数，yylex每次被调用都会去解析输入的字符流，直到找到一个token才会返回。
- 上面例子的动作部分没有return，所以yylex每次匹配到一个规则后都判定没有发现token，会继续解析后续的字符流，直到发现一个token或者到达了字符流末尾(最长和最早匹配规则)
利用工具生成词法解析代码和词法解析器(mac 版)
lex flex.l
gcc -ll lex.yy.c -o flex
./flex
# 输入文本，mac使用 crt+D 结束输入
Bison
Bison 主要用于处理 Flex 输出的Token流，分析语法；它的语法规则和Flex一样分为3个部分，
- 第一部分是C语言声明、token声明、类型声明。由”%{“和”}%“围住的C语言部分会被直接拷贝到生成的语法分析器代码前面。
- 第二部分是使用BNF语法编写的语法规则，为了编写方便，Bison对BNF做了一定的简化。
- 第三部分是要执行的main函数(yyparse是Bison生成的语法分析器入口，yyparse会不断地调用yylex获取token流去解析，和语法规则去做匹配，直到token流结束或者发现语法错误。)。
举一个简单的计算器的例子(bison会调用词法分析器，所以要改改词法分析源码)
%{
#include<stdlib.h>
void yyerror(char*);
#include "cal.tab.h"
%}
%%
[0-9]+ {yylval=atoi(yytext); return NUMBER;}
[-+*/\n] {return *yytext;}
[ \t] ;
. yyerror("Error");
%%
int yywrap(void)
{
return 1;
}
语法分析器代码
%token NUMBER
%left '+' '-' '*' '/'
%{
#include <stdio.h>
#include <math.h>
void yyerror(char *s);
int yylex();
%}
%%
prog:
| prog expr '\n' { printf("= %d\n", $2); };
expr:
NUMBER {{ printf("read number %d\n", $$); }};
| expr '+' expr {{ $$ = $1 + $3; }}
| expr '-' expr {{ $$ = $1 - $3; }}
| expr '*' expr {{ $$ = $1 * $3; }}
| expr '/' expr {{ $$ = $1 / $3; }}
;
%%
void yyerror(char *s) {
fprintf(stderr, "%s\n", s);
}
int main() {
yyparse();
return 0;
}
执行命令生成词法解析代码和语法分析代码，编译语法解析器
bison -d cal.y
flex cal.l
gcc -std=c99 -o cl cal.tab.c lex.yy.c -ll (mac版)
bison -d cal.y
这个命令会生成 cal.tab.c 和 cal.tab.h 文件。添加 -d 选项会生成头文件 cal.tab.h，它包含由Bison生成的符号（tokens）的定义。
flex cal.l 生成词法分析器，代码里使用了cal.tab.h
然后编译出语法分析器。
PS.可以先不具体理解代码的含义，总而言之，词法分析器将输入分割成一个一个的token流，语法分析器将这个token流按照规则进行分析，获得token之间的联系和关系，做语法分析。
实际应用
这次突然了解到Flex & Bison源于一个比较麻烦的需求
策略团队那边给了一个策略文件(简单来说就是各种IF，然后命中了什么规则，就输出什么task ID)，需要提取出里面的所有需要的变量和值。
看到这个需求的时候，第一反应就是遍历策略文件每一行，做字符串匹配，匹配到xxx="xxx"后，提取出这个xxx。
但又第一时间否定了这个方案，感觉这个方案太暴力了，而且不容易后续扩展以及错误率感觉挺高的。
了解了词法分析器的原理后，感觉可以做一个简单的词法分析(实际也还是正则匹配)，对策略进行简单的分析。
策略文件类似这种格式
a =1
b = 2
IF (condition1) THEN
IF ((condition2) AND condition3) THEN
IF condition4 = 0 THEN //comment
'targeta' = "A"
'targetb' = "B"
ENDIF
IF condition5 THEN //comment targert_test=1
'targetc' = "c"
'targetd' = ""
ENDIF
IF condition6 THEN //comment
'tartgetf'[2] = 1
'tartgetf'[1] = "5"
ENDIF
ENDIF
ENDIF
定义规则
通过分析策略文件，我们可以大致观察出来，策略文件包含
-
关键字 : IF,ENDIF,THEN 等
-
运算符 : + - * / =
-
注释 : //
-
条件表达式： IF xxx THEN 中间的 xxx
-
赋值表达式: THEN xxx ENDIF 中间的 xxx
词法提取流程
那么我们要提取出赋值表达式的左值和右值，可以按照以下流程进行处理
-
去除注释 ：
//.*|/\*[\s\S]*?\*/- 这段正则表达式表示匹配 所有 // 后的字符 或者 /* */ 中间的字符
-
提取并去除条件式：
\bIF\s+(.*?)\s+THEN-
这段正则表达式表示匹配 IF 和THEN 中间的所有字符， \s+ 为匹配一个或多个空格 ，\b 为匹配一个单词边界，避免IF 为其他关键字的子串
-
(.*?) 即提取 IF xxx THEN 中间的xxx，带括号这种方式为匹配组，通过
-
提取出来的条件式可以进一步的处理
-
去除条件式后的文本只剩下 IF THEN xxx=xx ENDIF
-
-
去除关键字：
(?i)\b(IF|ENDIF|THEN|ELSE|ELIF)\b-
这段正则表达式表示识别关键字并去除, (?i) 忽略大小写
-
我们目前并不知道所有关键字；但分析文件，通过步骤二后剩下的关键字只有IF THEN ENDIF这些
-
去除关键字后就只剩下 'xxx' = "xx"这类表达式，我们希望处理的就是这些赋值表达式了
-
-
去除数组索引：
\[[^\]]*\]– — 识别[]和中间的内容- 表达式中有的变量是 'xxx'[1]，'xxx'[2]，这段正则表达式表示匹配将索引下标
-
提取左值和右值:
([^=\s]*)\s*=\s*([^=\s]*)-
这段正则表达式表示匹配所有 xxx = xxx的字符串，两个括号为两个匹配组分别提取左值和右值
-
[^=\s]* 非等号和非空格的组成的字符串
-
去除全部单引号双引号
-
过滤空字符串
-
通过这种方式把变量名和值提取出来，保存成 map[string][]string的形式
-
利用正则来提取也可以避免数据没有格式化的问题
- 合理的格式是 a=1 \n b=2 ；没有格式化的是 a=1 b=2; 通过这个解析流程，我们可以获得我们想要的赋值表达式的左值和右值，进一步进行我们的业务处理
-
代码实现
// Lexer 分析器
type Lexer struct {
Input string // 输入字符串
Condition []Token
VariableMap map[string][]string
}
// NewLexer 创建一个新的词法分析器
func NewLexer(input string) *Lexer {
return &Lexer{
Input: input,
Condition: []string{},
OutputVariableMap: make(map[string][]string),
}
}
// Lex 开始词法分析
func (l *Lexer) Lex() {
commentPattern := "//.*|/\*[\s\S]*?\*/"
keywordPattern := "(?i)\b(IF|ENDIF|THEN|ELSE|ELIF)\b"
conditionPattern := "\bIF\s+(.*?)\s+THEN"
varPattern := "([^=\s]*)\s*=\s*([^=\s]*)"
l.RemoveComments(commentPattern)
l.RemoveCondition(conditionPattern)
l.RemoveKeyword(keywordPattern)
l.ExtractOutputVars( varPattern)
}
func (l *Lexer) RemoveComments(pattern string) {
re := regexp.MustCompile(pattern)
l.Input = re.ReplaceAllString(l.Input, "")
}
func (l *Lexer) RemoveCondition(pattern string) {
re := regexp.MustCompile(pattern)
matches := re.FindAllStringSubmatch(l.Input, -1)
for _, match := range matches {
values := strings.TrimSpace(match[1])
if values != "" {
l.Condition = append(l.Condition, values)
}
}
l.Input = re.ReplaceAllString(l.Input, "")
}
func (l *Lexer) RemoveKeyword(ctx context.Context, pattern string) {
re := regexp.MustCompile(pattern)
l.Input = re.ReplaceAllString(l.Input, "")
}
func (l *Lexer) ExtractOutputVars( pattern string) {
re := regexp.MustCompile(`[[^]]*]`)
l.Input = re.ReplaceAllString(l.Input, "")
re = regexp.MustCompile(pattern)
matches := re.FindAllStringSubmatch(l.Input, -1)
for _, match := range matches {
if len(match) < 3 {
log.Warn(ctx, "pattern not match = %v,", match)
continue
}
key := strings.ReplaceAll(match[1], "'", "")
key = strings.ReplaceAll(key, """, "")
value := strings.ReplaceAll(match[2], "'", "")
value = strings.ReplaceAll(value, """, "")
if key == "" || value == "" {
log.Warn(ctx, fmt.Sprintf("empty var/value,var name=%v,value = %v", key, value))
continue
}
l.VariableMap[strings.TrimSpace(key)] = append(l.OutputVariableMap[strings.TrimSpace(key)], strings.TrimSpace(value))
}
}
这段代码实现了一个简易版的词法解析器，提取出赋值表达式的左值和右值，同时保存下来的条件表达式以供进一步的分析。
我们对一开始给出的文件进行分析：
可以看到成功提取出了条件和表达式，通过这种方式提取，比直接暴力匹配的准确性更高，后续的扩展性也会更好一点；
大佬们如果有其他更好的方式，也麻烦指点一下