Skip to content

flex-bison.org

Latest commit

 

History

History
346 lines (301 loc) · 13.1 KB

flex-bison.org

File metadata and controls

346 lines (301 loc) · 13.1 KB

flex和bison简介

本文档简要介绍flex和bison的使用，以期对词法分析、语法分析有粗浅的理解； 另外，词法分析、语法分析也可以用在配置文件解析等场合（如modsecurity）。 通过此文档，希望可以拓宽视野，为架构程序引入更加强大的开源工具。

简介

flex和bison是用来生成程序的工具，它们所生成的程序可以处理结构化的输入； 当然最初，它们是用来生成编译器的。

编译器要追溯到50年代了，这个领域一个关键的想法是把分析工作分成两部分， 词法分析和语法分析。简单说，词法分析把输入分割成一个个有意义的词块儿， 称为记号（token）；而语法分析则确定这些记号是如何彼此关联的。

在unix中，词法分析的工具是flex（早期为lex），语法分析的工具是bison（ 早期为yacc）。

正则表达式

.
匹配除换行符\n外的任意字符
[]
字符类，可匹配方括号内的任意一字符
^
匹配行首（在方括号内表示补集）
$
匹配行尾
{}
前一个模式可以匹配的最大最小次数
\
转义字符
*
匹配>=0次前一个模式
+
匹配>0次前一个模式
?
匹配0~1次前一个模式
|
或
“…”
匹配引号内字面意义上的字符
()
组合括号
/
尾部上下文；0/1匹配01中的0,但不匹配0或者02,并且不消耗/后的字符
<>
在模式开头出现，括起来的名字或名字列表给定了此模式使用的起始状态
<<EOF>>
特殊模式，匹配文件末尾
(?# comment)
perl风格的表达式注释
(?a:pattern)/(?a-x:pattern)
perl风格的模式修饰符 
i   大小写无关
x   忽略空白字符和c风格注释
s   所有字符当作单行匹配，即.可以匹配\n

典型的正则表达式

  • 实数 
    [-+]?([0-9]*\.?[0-9]+|[0-9]+\.)
  • 通用字符名 
    UCN (\\u[0-9a-fA-F]{4}|\\U[0-9a-fA-F]{8})
  • 浮点数指数部分 
    EXP ([Ee][-+]?[0-9]+)
  • 整数长度 
    ILEN ([Uu](L|l|LL|ll)?|(L|l|LL|ll)[Uu]?)
  • 整数 
    0[0-7]*{ILEN}?
[1-9][0-9]*{ILEN}?
0[Xx][0-9a-fA-F]+{ILEN}?
  • 十进制浮点数 
    ([0-9]*\.[0-9]+|[0-9]+\.){EXP}?[f|FL]?
[0-9]+{EXP}[f|FL]?
  • 十六进制浮点数 
    0[xX]([0-9a-fA-F]*\.[0-9a-fA-F]+|[0-9a-fA-F]+\.?)[pP][-+]?[0-9]+[f|FL]?
  • 字符常量，单引号括起来的部分 
    \'([^'\\]|\\['"?\\abfnrtv]|\\[0-7]{1,3}|\\[Xx][0-9a-fA-F]+|{UCN})+\'
  • 字符串字面量，双引号括起来的部分 
    L?\"([^"\\]|\\['"?\\abfnrtv]|\\[0-7]{1,3}|\\[Xx][0-9a-fA-F]+|{UCN})*\"
  • 空白字符 
    [ \t\n]+
  • 续行符 
    \\$

flex

词法分析所做的就是在输入中寻找字符的模式；一般利用简洁明了的模式描述 方式，即正则表达式。

flex程序主要由一系列带有指令的正则表达式组成，它们确定了匹配后相应的动 作；由flex生成的词法分析器，可以读取输入、匹配输入与所有的正则表达式并 且执行每次匹配后适当的关联动作。

flex会把所有的正则表达式翻译成一种高效的内部格式，这使它几乎可以同时 处理所有需要匹配的模式，因此匹配速度可成百倍提高。

结构

  • 文件名通常以 .l 或 .ll 结尾
  • 分三部分，以‘%%’分隔
    • 定义部分
    • 规则部分
    • 用户子例程
  • 自带小型的库
    • 包含辅助例程
    • cc命令末尾添加 -lfl 以链接此库
    • 它包含不同版本的main()和yywrap()
  • 自动生成文件lex.yy.c，可通过 %option outfile 修改
  • 起始状态默认为0, 即INITIAL

语法

BEGIN
切换到另外一个起始状态
ECHO
等价于fprintf(yyout, “%s”, yytext)
REJECT
使得flex退回已经匹配模式的文本
%%
三大部分的分隔符
%{ … %}
定义部分的文字块儿，C代码
yyin
输入文件句柄，默认值stdin
yyout
没有匹配的部分会被拷贝到此
yytext
被已有模式匹配到的token
yyleng
匹配到的token的长度
YY_BUFFER_STATE
更低层次的输入缓冲区
YY_BUFFER_SIZE
指定缓冲区大小，默认16k
%x
定义起始状态
%option case-insensitive
大小写无关
%option nodefault
不添加默认规则，如ECHO输出不匹配的字符等
%option noyywrap
不利用库函数 yywrap()
%option prefix
指定词法分析器使用的名字前缀，默认 yy
%option outfile
指定 flex 编译输出文件明，默认 lex.yy.c
%option yylineno
定义此变量保存当前行号，必须手工初始化
input()
获取输入字符给词法分析器，c++版本 yyinput()
unput()
返回字符给输入流，c++版本 yyunput()
yyless()
推回刚刚读到的记号，比 unput 快
yymore()
使得flex把下一个token添加到当前token中
yylex()
匹配到模式后，返回调用方；下次调用点时继续
yyrestart()
顺序读取多个文件，每打开一个调用此函数一次
yy_scan_bytes/_string/buffer()
使得flex可以从字符串读取输入

如何处理二义性

大多数flex程序具有二义性，相同的输入可能被多种不同的模式匹配，flex通过 两个简单的规则解决：

  • 匹配尽可能多的字符串
  • 匹配在程序中更早出现的模式

小例子

编辑文件fb_wc.l，填入如下代码：

   /* similar to 'wc' of unix */
   %{
   int chars = 0;
   int words = 0;
   int lines = 0;
   %}
   %%
   [a-zA-Z]+    {words++; chars += strlen(yytext);}
   \n           {lines++; chars++;}
   .            {chars++;}
   %%
   main(int argc, char **argv)
   {
       yylex();
	printf("%8d%8d%8d\n", lines, words, chars);
   }

按照如下步骤编译、运行，查看输出：

$ flex fb_wc.l
$ cc lex.yy.c -lfl
$ ./a.out
   just for a test
   it's right!!!
   ^D
  2   7   30
$

bison

bison来源于yacc（yet another compiler compiler），用于语法分析；它基于 flex分析的token，基于逻辑进行组合。

bison语法分析器通过查找能够匹配当前记号的规则来运作；匹配的过程对应两 种动作，移进（shift）和规约（reduction）。

bison分析器可以使用两种分析方法，一种是LALR(1)，另一种是GLR；前者，自左 向右向前查看一个记号，以区分匹配规则；后者，通用的自左向右。前者效率高， 更容易使用。

结构

  • 文件名以 .y 或 .yy 结尾
  • 和flex一样，也分为三部分，利用 %% 分隔：
    • 定义部分，控制信息及执行环境
    • 规则部分，以 ; 结尾，左、右部分利用 : 分隔
    • 用户子例程
  • 没有显式的语义动作代码，规则使用默认动作 $$ = $1
  • 库文件，通常包含main()/yyerror()等函数，使用 -ly 链接
  • 规则中，尽量使用左递归
  • 利用y.output保存日志

语法

$0/$-1
继承属性， 不建议 使用
$$
规则左侧的值
$n
规则右侧第n个token的值
@$
语法规则左侧的位置信息
@n
语法规则右侧第n个token第位置信息
YYABORT
检测到严重错误，无法继续，退出
YYSTYPE
类似于 %define api.value.type ，仅用于c/c++预处理器
%code [place] {…}
类似于%{…%}，但可指定top/provides/requires等位置
%define api.value.type {int}
定义整个程序使用的数据类型，默认 int
%destructor
特定符号被删除时获取控制权，以便于更安全的释放内存
%empty
明确指定空规则
%glr-parser
告知bison使用GLR风格的语法解析器
%inital-action{}
语法分析器启动时，做某些特定初始化
%language “C++”
设定语言
%locations
开启位置信息支持功能
%nonassoc
操作符不具有结合特性，定义优先级，以出现顺序从低到高
%left
操作符具有左结合特性，定义优先级
%right
操作符具有右结合特性，定义优先级
%prec
调整当前规则操作符的优先级， 不建议 使用
%name-prefix
更改语法解析器使用的名字前缀，默认 yy
%parse-param
为 yyparse() 传递参数
%requre “n.m”
约定bison的最低版本
%skeleton “lalr1.cc”
选定C++解析器
%start
定义顶层规则，一般为第一条（所以一般不需要此语句）
%token
声明记号
%type
为非终结符（即规则左部）声明赋值类型
%union
声明符号值的类型
yyerror()
报告错误
yyparse()
语法分析器的入口函数

补充

  • bison支持c++语法分析器
    • 支持C++语言的解析器， %skeleton “lalr1.cc”
    • 支持文件生成， %define
    • 支持多变量类型， %define api.value.type variant 
      后续使用真实类型，如 =%token <std::string> QUOTATION_MARK=
    • 默认命名空间yy，可通过 #define api.namespace 修改
    • 默认类名parser，可通过 #define parser_class_name 修改
    • 类主要函数parse()
    • 生成的文件：file.cc/file.hh/stack.hh/location.hh/position.hh
  • 新版bison如何支持多数据类型
    • 让bison利用%token/%type赋值进行统计， %define api.value.type union
    • 利用%union {}
    • 利用 %define api.value.type {union YYSTYPE}
    • 利用 #define YYSTYPE {union YYSTYPE}

联合flex和bison的简单例子 － 计算器

词法分析器

编辑文件calc.l，填充内容如下：

/*识别用于计算器的记号*/
%{
#include "calc.tab.h"            /* 由语法解析器提供，定义token及变量 */
%}

%%
"+"     {return ADD;}
"-"     {return SUB;}
"*"     {return MUL;}
"/"     {return DIV;}
"|"     {return ABS;}
[0-9]+  {yylval = atoi(yytext); return NUMBER;}
\n      {return EOL;}
[ \t]   {/* 忽略空白字符 */}
"("     {return OP; }
")"     {return CP; }
"//".*  { /* 忽略注释 */ }
.       {printf("mystery character %s\n", yytext);}

%%

语法分析器

编辑文件calc.y，填充内容如下：

%{
#include <stdio.h>
%}

/* declare tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS
%token OP CP
%token EOL

%%

calclist: /* 空规则，匹配输入开头 */
   | calclist exp EOL    {printf(" = %d\n", $2);}  /* EOL代表表达式结束 */
   ;

exp: factor
   | exp ADD factor      { $$ = $1 + $3; }
   | exp SUB factor      { $$ = $1 - $3; }
   ;

factor: term
   | factor MUL term     { $$ = $1 * $3; }
   | factor DIV term     { $$ = $1 / $3; }
   ;

term: NUMBER
   | ABS term            { $$ = $2>0?$2:-$2; }
   | OP exp CP           { $$ = $2; }
   ;

%%

main(int argc, char **argv)
{
    yyparse();
}

yyerror(char *s)
{
    fprintf(stderr, "error: %s\n", s);
}

Makefile

编辑文件，Makefile，填充内容如下：

calc: calc.l calc.y
        bison -d calc.y
        flex -o calc.lex.c calc.l
        cc -o $@ calc.tab.c calc.lex.c -lfl

编译执行：

$ make
$ ./calc
  2 + 3 * 4
   = 14
  1 + 2 * ( 3 + 4 )
   = 15

改进点

  • 单字符操作符可直接通过 yytext[0] 传递，规则表达式利用’+’等表示 
    参考p68 of《flex and bison》
  • 通过抽象语法树暂缓计算
  • 通过操作符优先级，简化语法规则 
    参考p75 of《flex and bison》

名词解释

lexical analysis
词法分析，又称扫描器（scanner）；字符序列–>token
Syntactic analysis
语法分析，又称分析器（parsing）；token–>语法结构
AST
Abstract syntax tree，抽象语法树 wiki
BNF
Backus–Naur Form wiki
LLVM
编译器框架 官网
CFG
context-free grammar，上下文无关文法；标准格式为BNF
LHS/RHS
left/right-hand side, bison的语法规则的左部/右部
终结符/记号
terminal symbol/token, 被词法分析器返回的符号
非终结符
nonterminal symbol, bison的语法规则左部的语法符号

参考

  • 书籍 
    flex and bison