flex/bison使用

1 基本介绍

• Flex（词法分析器）
  像“文本拆分器”，负责将原始文本拆解成有意义的单词（称为 Token）。
  例如：从代码 price = 100+20 中识别出 price、=、100、+、20。

• Bison（语法分析器）
  像“语法检查器”，负责验证这些单词是否符合预定规则，并构建结构。
  例如：检查 100+20 是否符合数学表达式规则，并解释其计算逻辑。

典型应用场景

• 写编程语言的编译器/解释器（比如实现一个简易的 Python 或 JSON 解析器）
• 读取配置文件（比如解析 Nginx 的配置规则）
• 开发专用小语言（比如一些脚本指令）

2 安装配置

• Linux (Ubuntu)

  sudo apt-get install flex bison

• macOS

  brew install flex bison

• Windows

1. 使用Cygwin或WSL环境
2. 或使用预编译包：https://winflexbison.sourceforge.net/

验证安装：

flex --version
bison --version

3 编写flex文件

以下代码均用C++编写，第一种使用方式为flex/bsion在C语言中的使用风格（在这两节中介绍），第二种为在C++中面向对象的使用风格（在后文中介绍）。

flex文件一般在C语言中后缀用.l，在C++中用.ll。

// 禁用旧式yyloop，其他option查手册
%option noyywrap yylineno

%{
// C头文件和声明（会直接复制到输出）
#include "parser_tab.h" // Bison生成的头文件，名称可自定义

// 可定义函数/变量
void yyerror（char *s，..）｛ 
    va_list ap；
    va_start（ap,s）；
    fprintf（stderr，"Error： "）；
    vfprintf（stderr,s,ap）；
    fprintf（stderr，"\n"）；
｝
int brace_count = 0； // 记录大括号的嵌套层级
%}

// 状态声明，默认状态为INITIAL，用户可定义不同状态，以及特定状态下的规则
%× COMMENT

%%

/* 规则段，注意规则会从前往后查找 */

"VALUE"                       { return VALUE;}
"ARRAY"                       { return ARRAY;}
"SIZE"                        { return SIZE;}

">"  { yylval.comptok = 1; return COMPARISON; }
"<"  { yylval.comptok = 2; return COMPARISON; }
">=" { yylval.comptok = 3; return COMPARISON; }
"<=" { yylval.comptok = 4; return COMPARISON; }
"!=" { yylval.comptok = 5; return COMPARISON; }
"==" { yylval.comptok = 6; return COMPARISON; }

\"([^"\\]|\\.)*\"                  {
                                    yylval.str = strdup(yytext);
                                    return STRING;
                                }

[-+]?[0-9]+                        {
                                    yylval.num = atoi(yytext);
                                    return NUMBER;
                                }


[a-zA-Z0-9_/!][a-zA-Z0-9_/\-+\.]*     {
                                    yylval.id = strdup(yytext);
                                    return IDENTIFIER;
                                }

[-+]?[0-9]+"."[0-9]* |
[-+]?"."[0-9]+ |
[-+]?[0-9]+[eE][-+]?[0-9]+ |
[-+]?[0-9]+"."[0-9]*[eE][-+]?[0-9]+ |
[-+]?"."[0-9]*[eE][-+]?[0-9]+      {
                                    yylval.floatval = atof(yytext) ;
                                    return FLOAT; 
                                }


[ \t\r\n]+                      /* 忽略空白字符 */
"//".*\n                        /* 忽略 C/C++ 风格注释 */
"/*"           { BEGIN(COMMENT) ; }
<COMMENT>"*/"  { BEGIN(INITIAL); }
<COMMENT>([^*]|\n)+|.

.               { yyerror("未知字符 '%c'", *yytext); }

%%

• %%分割符号
• yytext包含匹配的文本
• yylval向Bison传递token值
• 返回值对应Bison的token类型

# 生成命令，根据.l生成.c
flex -o xxx_lex.c  xxx_flex.l 

4 编写bison文件

bison文件一般在C语言中后缀用.y，在C++中用.yy。

%{
//头文件及全局变量声明段
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define xxx 1000

extern void yyerror(const char *s);
int hier_stack_top = -1;
void xxxfunc() {
}

%}

/*! * * * * * * * * * * * * * * *  * * * * * * * * * * * * * */
/* 定义令牌，必须在flex中定义过，这里列出的不需要通过yylval传参 */
%token VALUE ARRAY SIZE

/* 定义类型(yylval) */
%union {
    char *id;
    char *str;
    int num;
    double floatval;
    int comptok;
    Expr* expr;  // 用户定义结构体
}

/* 为非终结符指定类型 */
%type <expr> expression;
%type <expr> expressions;

/* 为令牌指定类型 */
%token <id> IDENTIFIER
%token <str> STRING
%token <num> NUMBER
%token <floatval> FLOAT
%token <comptok> COMPARISON

/* 定义优先级和结合性（根据需要调整） */
%left  ','

%%

/*! * * * * * * * * * * * * * * * * * * * * * * * * */
/* 语法规则段 */

cfg_file:
    {
    /* 刚读入，可进行一些初始化操作 */
    }
    | cfg_file check_block
    ;


check_block:
    CHECK '{' expressions '}'
        {
        //...
        }
    | CHECK '(' IDENTIFIER ')' '{' expressions '}'
        {
        //...
        free($3);
        }
    ;

expressions:
    /* 没有键值对 */
    { $$ = NULL; }
    | expressions expression
    {
        $2->next = $1;
        $$ = $2;
    }
    ;

expression:
    IDENTIFIER  COMPARISON  value ';'
    {
        //用户在其他地方定义了create_expr函数
        $$=create_expr($1, $2, $3);
        free($1);
    }
    |
    IDENTIFIER  COMPARISON  value
    {
        $$=create_expr($1, $2, $3);
        free($1);
    }


%%

• %token定义终结符
• %left/%right定义运算符结合性
• $$表示当前规则的结果
• $1, $2...访问子项的值

# 生成命令，根据.y生成.c和.h
bison --debug xxx_parser.y -o parser_tab.c

5 编写主函数执行解析

// main.c，如果是C++则使用extern "C"

// debug only
yydebug = 1；

//外部声明
extern int yyparse();
extern FILE *yyin；

int main(int argc, char **argv) {
  if (argc > 1) {
    /* 从文件读取输入 */
    FILE *file = fopen(argv[1], "r");
    if (!file) {
      perror("无法打开文件");
      return 1;
    }
    yyin = file;
  }

  /* 解析 CFG 文件 */
  if (yyparse() == 0) {
    // ...
  } else {
    fprintf(stderr, "解析失败\n");
  }

  return 0;
}

6 面向对象的使用方式

前文介绍的传统flex/bison使用风格较为常见，但在处理一些复杂问题上功能稍弱，尤其是参数传递以及调用的灵活性方面。本部分介绍面向对象的flex/bison使用方式，并给出基本框架。

6.1 xxx_driver

驱动器部分，负责调用分析器进行解析，同时也是传递参数的重要枢纽。

// xxx_driver.hpp，展示的均为通用函数
#include <string>
#include <iostream>
#include <fstream>

/*! 可有多个Driver，命名空间不同，其他不变 */
namespace xxx_parse {
/// Forward declarations of classes
class Parser;
class Scanner;
class location;

class Driver {
  // 可定义用于参数传递的变量/成员函数
 public:
  /// enable debug output in the flex scanner
  bool trace_scanning;
  /// enable debug output in the bison parser
  bool trace_parsing;
  /// stream name (file or input stream) used for error messages.
  std::string streamname;
  Driver();
  ~Driver();
  /** Invoke the scanner and parser for a stream.
   * @param in  input stream
   * @param sname  stream name for error messages
   * @return    true if successfully parsed
   */
  bool parse_stream(std::istream& in,
                    const std::string& sname = "stream input");
  /** Invoke the scanner and parser on an input string.
   * @param input  input string
   * @param sname  stream name for error messages
   * @return    true if successfully parsed
   */
  bool parse_string(const std::string& input,
                    const std::string& sname = "string stream");
  /** Invoke the scanner and parser on a file. Use parse_stream with a
   * std::ifstream if detection of file reading errors is required.
   * @param filename  input file name
   * @return    true if successfully parsed
   */
  bool parse_file(const std::string& filename);

  // To demonstrate pure handling of parse errors, instead of
  // simply dumping them on the standard error output, we will pass
  // them to the driver using the following two member functions.
  /** Error handling with associated line number. This can be modified to
   * output the error e.g. to a dialog box. */
  void error(const class location& l, const std::string& m);
  /** General error handling. This can be modified to output the error
   * e.g. to a dialog box. */
  void error(const std::string& m);
 private:
  Scanner* scanner_;
  Parser* parser_;
  /// Allows Parser and Scanner to access private attributes
  /// of the Driver class
  friend class Parser;
  friend class Scanner;
};

}  // namespace xxx_parse

// xxx_driver.cpp，展示的均为通用函数
#include "xxx_driver.hpp"
#include "xxx_scanner.hpp"
#include "xxx_parser.hpp"
#include <sstream>

namespace xxx_parse {

Driver::Driver() : scanner_(new Scanner()), parser_(new Parser(*this)) {
  trace_scanning = false;
  trace_parsing = false;
}
Driver::~Driver() {
  delete parser_;
  delete scanner_;
}
bool Driver::parse_stream(std::istream& in, const std::string& sname) {
  streamname = sname;
  scanner_->switch_streams(&in, &std::cerr);
  scanner_->set_debug(trace_scanning);
#if YYDEBUG
  parser_->set_debug_level(trace_parsing);
#endif
  return (parser_->parse() == 0);
}

bool Driver::parse_file(const std::string& filename) {
  std::ifstream in(filename.c_str());
  if (!in.good()) return false;
  return parse_stream(in, filename);
}

bool Driver::parse_string(const std::string& input, const std::string& sname) {
  std::istringstream iss(input);
  return parse_stream(iss, sname);
}

void Driver::error(const std::string& m) { std::cerr << m << std::endl; }
}  // namespace xxx_parse

6.2 xxx_scanner

扫描器部分，主要负责词法分析。

// xxx_scanner.hpp，展示的均为通用函数，注意命名空间的对应（包括继承的父类名称前缀）
#include "xxx_parser.hpp"
#ifndef YY_DECL
#define YY_DECL                                              \
  xxx_parse::Parser::token_type xxx_parse::Scanner::yylex( \
      xxx_parse::Parser::semantic_type* yylval, xxx_parse::Driver& driver)
#endif
#ifndef __FLEX_LEXER_H
#define yyFlexLexer xxx_parseFlexLexer
#include <FlexLexer.h>
#undef yyFlexLexer
#endif

namespace xxx_parse {
class Scanner : public xxx_parseFlexLexer {
 public:
  Scanner();
  virtual ~Scanner();
  virtual Parser::token_type yylex(Parser::semantic_type* yylval,
                                   Driver& driver);
  void set_debug(bool b);
};
}  // namespace xxx_parse

// xxx_scanner.ll，展示了一个比较丰富的例子，除了规则和状态定义，其他均为通用函数
%option noyywrap
%option debug
%option c++
/* the manual says "somewhat more optimized"，加上后速度快很多 */
%option batch
%option prefix="xxx_parse"
/* enables the use of start condition stacks */
%option stack

%{
#include "xxx_parser.hpp"
#include "xxx_scanner.hpp"
#include "xxx_driver.hpp"

typedef xxx_parse::Parser::token token;
typedef xxx_parse::Parser::token_type token_type;
#define yyterminate() return token::TOK_EOF
%}

//状态定义区
%x COMMENT
%x RIGHTSIDE

%%


//规则定义区
"{"   { return token::L_BRACE;}
"}"   { return token::R_BRACE;}
"["   { return token::L_BRACKETS;}
"]"   { return token::R_BRACKETS;}
"="   { yy_push_state(RIGHTSIDE); return token::EQUAL;}
";"   { return token::SEMICOLON;}
"("   { return token::L_PARENTHESES;}
")"   { return token::R_PARENTHESES;}
","   { return token::COMMA;}

\"([^"\\]|\\.)*\"                  {
                                    char * temp = strdup(yytext);
                                    yylval->str = unquote(temp);
                                    free(temp);
                                    return token::STRING;
                                }

[-+]?[0-9]+                        {
                                    yylval->num = atoi(yytext);
                                    return token::INT;
                                }


[a-zA-Z_]*                         {
                                    yylval->id = strdup(yytext);
                                    return token::IDENTIFIER;
                                }

[-+]?[0-9]+"."[0-9]* |
[-+]?"."[0-9]+ |
[-+]?[0-9]+[eE][-+]?[0-9]+ |
[-+]?[0-9]+"."[0-9]*[eE][-+]?[0-9]+ |
[-+]?"."[0-9]*[eE][-+]?[0-9]+      {
                                    yylval->floatval = atof(yytext) ;
                                    return token::FLOAT; 
                                }

"/*"           { yy_push_state(COMMENT) ; }

[ \t\r\n]+                      /* 忽略空白字符 */

<RIGHTSIDE>{
[-+]?[0-9]+                        {
                                    yylval->num = atoi(yytext);
                                    yy_pop_state();
                                    return token::INT;
                                }
[-+]?[0-9]+"."[0-9]* |
[-+]?"."[0-9]+ |
[-+]?[0-9]+[eE][-+]?[0-9]+ |
[-+]?[0-9]+"."[0-9]*[eE][-+]?[0-9]+ |
[-+]?"."[0-9]*[eE][-+]?[0-9]+      {
                                    yylval->floatval = atof(yytext) ;
                                    yy_pop_state();
                                    return token::FLOAT; 
                                }

[0-9a-zA-Z_+\-*/()\t]+               {
                                    yylval->expr = strdup(yytext) ;
                                    yy_pop_state();
                                    /* 表达式中不能有空格 */
                                    return token::EXPR; 
                                }

[ \t\r\n]+                      /* 忽略空白字符 */

}

"//".*\n                        /* 忽略 C/C++ 风格注释 */

<COMMENT>"*/"  { yy_pop_state(); }
<COMMENT>([^*]|\n)+|.

.               { yyerror("未知字符 '%c'", *yytext); }
%%

/*

   CUSTOM C++ CODE

*/

namespace xxx_parse
{

    Scanner::Scanner()
    : xxx_parseFlexLexer()
    {
    }

    Scanner::~Scanner()
    {
    }

    void Scanner::set_debug(bool b)
    {
        yy_flex_debug = b;
    }
}

#ifdef yylex
# undef yylex
#endif

int xxx_parseFlexLexer::yylex()
{
  std::cerr << "call parsepitFlexLexer::yylex()!" << std::endl;
  return 0;
}

6.3 xxx_parser

解析器，主要负责语法分析。

// xxx_parser.yy，展示的均为通用函数，注意前缀名称的对应
%{
// 其他头文件
#include <stdio.h>
// 必备头文件
#include "xxx_parser.hpp"
#include "xxx_scanner.hpp"

/*! 全局变量定义区 */


#define yylex driver.scanner_->yylex
%}
/*! * * * * * * * * * * * * * * *  * * * * * * * * * * * * * */
%code requires
{
  #include <string>
  #include "xxx_driver.hpp"
  using namespace xxx;
}

%code provides
{
  namespace xxx_parse
  {
    // Forward declaration of the Driver class
    class Driver;

    inline void yyerror(const char *s, ...) {
    va_list ap;
    va_start(ap, s);
    fprintf(stderr, "Error: ");
    vfprintf(stderr, s, ap);
    fprintf(stderr, "\n");
    }

  }
}

// 传递参数driver
%require "3.2"
%language "C++"
/* use newer C++ skeleton file */
%skeleton "lalr1.cc"
%define api.namespace {xxx_parse}
%define api.parser.class {Parser}
%parse-param {Driver &driver}
%lex-param {Driver &driver}
/* verbose error messages */
%define parse.error verbose
%debug

/* 定义令牌 */
%token TOK_EOF 0
%token L_BRACE R_BRACE L_BRACKETS R_BRACKETS EQUAL SEMICOLON L_PARENTHESES R_PARENTHESES COMMA

/* 定义类型 */
%union {
    char *id;
    char *str;
    double floatval;
    int num;
    char * expr;

}

/* 为令牌指定类型 */
%token <id> IDENTIFIER
%token <str> STRING
%token <num> INT
%token <floatval> FLOAT

/* 为非终结符指定类型 */

/* 定义优先级和结合性（根据需要调整） */

%start xxx_file

%%

/*! * * * * * * * * * * * * * * * * * * * * * * * * */
/* 语法规则定义区 */

xxx_file:
    | xxx_file quantity_block
    { }
    ;

%%

namespace xxx_parse
{
    void Parser::error(const std::string& m)
    {
        driver.error(m);
    }
}

6.4 生成命令

#!/bin/sh
cd ${0%/*} || exit 1

# -d --debug 
rm -f xxx_scanner.c* xxx_parser.c* xxx_parser.h* location.hh
flex -o xxx_scanner.cpp xxx_scanner.ll
bison --debug -d xxx_parser.yy -o xxx_parser.cpp

6.5 调用方式

通过driver来调用解析。

std::string full_path="xxx";
xxx_parse::Driver driver;
// driver.trace_scanning = true; /*!< debug */
driver.parse_file(full_path);

7 高级使用（AST）

什么是抽象语法树

抽象语法树（AST）是源代码语法结构的一种树形表示。它将源代码分解为树形结构，其中每个节点代表源代码中的一个语法结构，如表达式、语句或声明。与具体的语法树相比，抽象语法树省略了语法上的一些次要信息，如括号和运算符的优先级等，保留主要的语义内容，以一种更简洁、更抽象的形式展示代码的结构。

为什么要使用抽象语法树

在一些比较复杂的使用场景中，对bison解析的时机（顺序）要求较高，而一般写法是识别->解析->执行的流程，解析后立即会执行规则段中的代码，用户无法控制执行的时机。而使用AST的流程则为识别->解析->生成AST->调用AST执行接口->执行，能够适用更多的场景。

AST示例（基于上面的框架）

namespace xxx_parse {
// 用来处理各种类型的数（整数、浮点等）
class ParsedData; 
/*! \class ASTNode
 *  \brief Abstract syntax tree.  ASTNode is abstract base class for all other
 * nodes.
 */
class ASTNode {
protected:
  Driver *driver_;
public:
  ASTNode(Driver *driver);
  virtual ~ASTNode();
  /*! pure abstract */
  virtual void eval() = 0;
  virtual void push_back(ASTNode *) = 0;
};
/*! * * * * * * * * * * * * * * *  * * * * * * * * * * * * * */
/*! 数学表达式基类 */
class AST_Expression : public ASTNode {
public:
  AST_Expression(Driver *driver) : ASTNode(driver) {}
  virtual ~AST_Expression() {}
  virtual void eval() override {}
  virtual ParsedData *eval_expr() = 0;
  virtual void push_back(ASTNode *n) override {}
};
/*! 变量类型 */
class AST_Expression : public ASTNode {
class AST_Expression_Var : public AST_Expression {
protected:
  std::string var_name_;

public:
  AST_Expression_Var(Driver *driver, std::string name)
      : AST_Expression(driver), var_name_(name) {}
  virtual ~AST_Expression_Var() {}
  void setName(std::string name) { var_name_ = name; }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_Int : public AST_Expression {
protected:
  int value_;
public:
  AST_Expression_Int(Driver *driver, int i)
      : AST_Expression(driver), value_(i) {}
  virtual ~AST_Expression_Int() {}
  void setValue(int i) { value_ = i; }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_Float : public AST_Expression {
protected:
  double value_;
public:
  AST_Expression_Float(Driver *driver, double i)
      : AST_Expression(driver), value_(i) {}
  virtual ~AST_Expression_Float() {}
  void setValue(double i) { value_ = i; }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_Bool : public AST_Expression {
protected:
  bool value_;
public:
  AST_Expression_Bool(Driver *driver, bool i)
      : AST_Expression(driver), value_(i) {}
  virtual ~AST_Expression_Bool() {}
  void setValue(bool i) { value_ = i; }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_ADD : public AST_Expression {
protected:
  AST_Expression *left_;
  AST_Expression *right_;
public:
  AST_Expression_ADD(Driver *driver, AST_Expression *left = NULL,
                     AST_Expression *right = NULL)
      : AST_Expression(driver), left_(left), right_(right) {}
  virtual ~AST_Expression_ADD() {
    delete left_;
    delete right_;
  }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_SUB : public AST_Expression {
protected:
  AST_Expression *left_;
  AST_Expression *right_;
public:
  AST_Expression_SUB(Driver *driver, AST_Expression *left = NULL,
                     AST_Expression *right = NULL)
      : AST_Expression(driver), left_(left), right_(right) {}
  virtual ~AST_Expression_SUB() {
    delete left_;
    delete right_;
  }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_MUL : public AST_Expression {
protected:
  AST_Expression *left_;
  AST_Expression *right_;
public:
  AST_Expression_MUL(Driver *driver, AST_Expression *left = NULL,
                     AST_Expression *right = NULL)
      : AST_Expression(driver), left_(left), right_(right) {}
  virtual ~AST_Expression_MUL() {
    delete left_;
    delete right_;
  }
  virtual ParsedData *eval_expr() override;
};

class AST_Expression_DIV : public AST_Expression {
protected:
  AST_Expression *left_;
  AST_Expression *right_;
public:
  AST_Expression_DIV(Driver *driver, AST_Expression *left = NULL,
                     AST_Expression *right = NULL)
      : AST_Expression(driver), left_(left), right_(right) {}
  virtual ~AST_Expression_DIV() {
    delete left_;
    delete right_;
  }
  virtual ParsedData *eval_expr() override;
};

在xxx_parse.yy中，则需要在union中增加各AST类型，并在解析语句中构造AST类的实例。