Go 语言 SQL 解析之 goyacc 实战

【导读】本文介绍了语法解析基本概念，结合 goyacc 实战做了详细介绍。

一、Lex & Yacc简介

Lex & Yacc 是用来生成词法分析器和语法分析器的工具，与GNU用户所熟知Flex&Bison所对应（Flex是由Vern Paxon实现的一个Lex，Bison则是GNU版本的YACC）。除了编译器领域，Lex & Yacc对于DSL或者SQL解析领域也大有用处。

Lex （A Lexical Analyzer Generator）用于生成词法分析器，用于把输入分割成一个个有意义的词块（称为token）。

Yacc（Yet Another Compiler-Compiler）用于生成语法解析器，用于确定上述分隔好的token之间的关联。

下图描述了整个处理的流程：

• Lex根据输入的patterns生成词法分析器。
• 词法分析器根据patterns将输入的源代码转换为tokens输出。
• Yacc根据定义的语法规则，生成语法分析器。
• 语法分析器根据语法规则，并以tokens为输入，创建出语法树。

二、词法分析器

词法分析器用于获取一个token流。通过调用yylex()读取输入，然后返回相应的token，之后循环调用，持续返回解析好的token。每个token有两部分组成：

• token类型，一个整数值。该值为yylex()的返回值。
• token取值。结果保存到yylval中。

如下是计算器词法分析器的规则定义。该定义由三部分组成，由%%分隔。

• 第一部分为声明部分。%{、%}之间的代码，会被原样拷贝到C文件中。其中定义了token类型，以及token值的变量

• 第二部分模式匹配部分。每行开头是匹配的模式，接着是要执行的代码。

• 例如，[0-9]+行表示：当匹配为数字时，则转换成整型复制给yylval，并返回token类型为NUMBER。

• 第三部分为主程序代码，负责调用词法分析函数yylex()，并输出结果。

// 计算器词法分析器
%{
    enum yytokentype {
        NUMBER = 258,
        ADD = 259,
        SUB = 260,
        MUL = 261,
        DIV = 262,
        ABS = 263,
        EOL = 264
    };
    int yylval;
%}

%% 
"+"        {return ADD;}
"-"        {return SUB;}
"*"        {return MUL;}
"/"        {return DIV;}
"|"        {return ABS;}
[0-9]+     {yylval = atoi(yytext); return NUMBER;}
\n         {return EOL;}
[ \t]      {/*忽略空白字符*/}
%%

main(int argc, char **argv) {
    int tok;

  while(tok = yylex()) {
    printf("%d", tok);
    if (tok == NUMBER) {
      printf(" = %d\n", yylval);
    } else {
      print("\n");
    }
  }
}

// 运行
/// 输入：
34 + 45

/// 输出：
258 = 34
259
258 = 45

三、语法分析器

语法分析器用于找出输入token之间的关系，使用巴科斯范式（BNF, Backus Naur Form）来书写。同词法分析器规则一样，也是三部分组成。

• 声明部分：

• %{、%}声明部分原样拷贝到C文件。

• %token声明，用于告诉yacc在语法分析程序中token的类型。任何没有声明为token的语法符号，必须出现在至少一条规则的左边。

• 规则部分：通过BNF定义规则。每一条规则中语法符号都有一个语义值。

• 目标符号（冒号左边的语法符号）用$$代替。

• 右边语法符号的语义值以此用2代替。

• C代码部分

样例：

%{
#include <stdio.h>
%}

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

%%
calclist:  /*空规则*/
        |  calclist exp EOL { printf("= %d\n", $2); }
        ;

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

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

term: NUMBER default $$ = $1
    | ABS term { $$ = $2 >=0 ? $2 : - $2; }
    ;

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

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

四、yacc语法规范

整体结构

由三部分组成，其中前两部分必须。

...定义部分...

%%

...规则部分...

%%

...用户子程序...

符号

由词法分析器产生的符号称为终结符或者token。

在规则左侧定义的的符号称为非终结符。

定义部分

• %{ %}之间定义的文字块，通常被原样拷贝到C代码中。

• 声明部分

• %start

• 起始规则，即语法分析器首先分析的规则。默认是第一条规则，如果希望其他规则作为起始规则，需要增加声明：%start somename

• %token

• 也可以叫终结符，是词法分析器传递给语法分析器的符号。

• 语法分析器调用yylex()获取下一个token。

• %left、%right、%nonassoc：

• 定义了运算符的结合性，同一行的运算符优先级相同，不同行的运算符，后定义的行具有更高的优先级。

• %type

• 使用%type来声明非终结符。

• %type的名字必须以%union定义过。

• %union

• %union声明标示了符号值所有的变量类型。

• %union声明将原样拷贝到以YYSTYPE为类型的C的union声明中。

• 如果不存在%union声明，yacc将把YYSTYPE定义为int，这样所有的符号值都是int。

• %type把%union中声明的类型与特定的符号关联起来。

规则部分

包括语法规则和语义动作代码。动作即yacc匹配语法中的一条规则时之行的代码。例如：

date: month '/' day '/' year { $$ = sprintf("date %d-%d-%d", $1, $3, $5); }

用户子程序

原样被拷贝到C文件的代码片段。

移进/归约

移进（shift）：语法分析器读取token时，当读取的token无法匹配一条规则时，则将其压入一个内部堆栈(union为压入堆栈的结构体)，然后切换到一个新的状态，这个新的状态能够反映出刚刚读取的token。

归约（reduction）：当发现压入的token已经能够匹配规则时，则把匹配的符号从堆栈中取出，然后将左侧符号压入堆栈。

例如，fred = 12 + 13的处理过程：

// 规则
statement: NAME '=' expression
expression: NUMBER + NUMBER

// 处理过程
fred 
fred = 
fred = 12
fred = 12 + 
fred = 12 + 13 //匹配expression: NUMBER + NUMBER，可以归约
fred = expression //匹配statement: NAME '=' expression
statement

但是如果引入乘法后，可能会产生冲突，造成如下不同的语法结构。

对于这种情况需要显示指定优先级和结合性来解决冲突：

• 优先级：决定了那个操作符先执行。例如，乘除法的优先级高于加减法。

• 结合性：表示具有相同优先级的操作符的结合顺序。

• 自左向右：a-b-c等价于(a-b)-c。

• 自右向左：a=b=c等价于a=(b=c)。

// 意义：+ - * /都是左结合，* /的优先级高于+ -。
%left '+' '-'
%left '*' '/'

五、goyacc

github.com/cznic/goyacc是 golang 版的 Yacc。和 Yacc 的功能一样，goyacc 根据输入的语法规则文件，生成该语法规则的 go 语言版解析器。goyacc 生成的解析器 yyParse 要求词法分析器符合下面的接口：

type yyLexer interface {
    Lex(lval *yySymType) int
    Error(e string)
}

或者

type yyLexerEx interface {
    yyLexer
    // Hook for recording a reduction.
    Reduced(rule, state int, lval *yySymType) (stop bool) // Client should copy *lval.
}

Lex应该返回token类型，并将token值放到放在lval中（与yacc的yylval对应）。Error相当于原yacc中的yyerror。

六、goyacc样例

电话号码解析

源代码：github.com/sougou/parser_tutorial/tree/master/v3

• 功能实现

• 支持电话号码4085551212、408-555-1212解析。

• 语法解析器定义parser.y(github.com/sougou/parser_tutorial/blob/master/v3/parser.y)

# 定义部分
%{
package jsonparser

func setResult(l yyLexer, v Result) {
  l.(*lex).result = v
}
%}

%union{
  result Result
  part string
  ch byte
}

%token <ch> D

%type <result> phone
%type <part> area part1 part2

%start main

%%
# 规则部分
main: phone
  {
    setResult(yylex, $1)
  }

phone:
  area part1 part2
  {
    $$ = Result{area: $1, part1: $2, part2: $3}
  }
| area '-' part1 '-' part2
  {
    $$ = Result{area: $1, part1: $3, part2: $5}
  }

area: D D D
  {
    $$ = cat($1, $2, $3)
  }

part1: D D D
  {
    $$ = cat($1, $2, $3)
  }

part2: D D D D
  {
    $$ = cat($1, $2, $3, $4)
  }

• 生成parser.go （goyacc -l -o parser.go parser.y自动生成）。比较关键的定义：

// 对应.y中union的结构体
type yySymType struct {
    yys    int
    result Result
    part   string
    ch     byte
}
//token类型
const (
    yyDefault = 57347
    yyEofCode = 57344
    D         = 57346
    yyErrCode = 57345

    yyMaxDepth = 200
    yyTabOfs   = -7
)

//词法分析器接口
type yyLexer interface {
    Lex(lval *yySymType) int
    Error(s string)
}

type yyLexerEx interface {
    yyLexer
    Reduced(rule, state int, lval *yySymType) bool
}

//语法解析入口
func yyParse(yylex yyLexer) int {

}

• 词法解析定义lex.go，这里没有采用lex定义。

// Result is the type of the parser result
type Result struct {
    area  string
    part1 string
    part2 string
}

// 解析的总入口。输入电话号码，输出为Result的解析结果。
func Parse(input []byte) (Result, error) {
    l := newLex(input)
    _ = yyParse(l)
    return l.result, l.err
}

// 手动定义词法解析器
type lex struct {
    input  *bytes.Buffer
    result Result
    err    error
}

func newLex(input []byte) *lex {
    return &lex{
        input: bytes.NewBuffer(input),
    }
}

// 词法分析器满足Lex接口。能够逐个读取token。
// 如果是有效的电话号码数字，返回D类型，并赋值lval.ch。
func (l *lex) Lex(lval *yySymType) int {
    b := l.nextb()
    if unicode.IsDigit(rune(b)) {
        lval.ch = b
        return D
    }
    return int(b)
}

func (l *lex) nextb() byte {
    b, err := l.input.ReadByte()
    if err != nil {
        return 0
    }
    return b
}

// Error satisfies yyLexer.
func (l *lex) Error(s string) {
    l.err = errors.New(s)
}

func cat(bytes ...byte) string {
    var out string
    for _, b := range bytes {
        out += string(b)
    }
    return out
}