简单理解Flex & bison 与词法解析应用

站长

2023年11月28日 15:06 · 阅读数 47

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 结束输入

简单理解Flex & bison 与词法解析应用

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

然后编译出语法分析器。

简单理解Flex & bison 与词法解析应用

PS.可以先不具体理解代码的含义，总而言之，词法分析器将输入分割成一个一个的token流，语法分析器将这个token流按照规则进行分析，获得token之间的联系和关系，做语法分析。

Flex 参考文章

Bison 参考文章

实际应用

这次突然了解到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))
   }

}

这段代码实现了一个简易版的词法解析器，提取出赋值表达式的左值和右值，同时保存下来的条件表达式以供进一步的分析。

我们对一开始给出的文件进行分析：

简单理解Flex & bison 与词法解析应用

可以看到成功提取出了条件和表达式，通过这种方式提取，比直接暴力匹配的准确性更高，后续的扩展性也会更好一点；

大佬们如果有其他更好的方式，也麻烦指点一下

转载自:https://juejin.cn/post/7304932252826435636

简单理解Flex & bison 与 词法解析应用

Background

Flex

Bison

实际应用

定义规则

词法提取流程

代码实现

简单理解Flex & bison 与词法解析应用