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 之間的關聯。

下圖描述了整個處理的流程：

二、詞法分析器

詞法分析器用於獲取一個 token 流。通過調用 yylex() 讀取輸入，然後返回相應的 token，之後循環調用，持續返回解析好的 token。每個 token 有兩部分組成：

如下是計算器詞法分析器的規則定義。該定義由三部分組成，由 %% 分隔。

// 計算器詞法分析器
%{
    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）來書寫。同詞法分析器規則一樣，也是三部分組成。

樣例：

%{
#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。

在規則左側定義的的符號稱爲非終結符。

定義部分

規則部分

包括語法規則和語義動作代碼。動作即 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

但是如果引入乘法後，可能會產生衝突，造成如下不同的語法結構。

對於這種情況需要顯示指定優先級和結合性來解決衝突：

// 意義：+ - * /都是左結合，* /的優先級高於+ -。
%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

# 定義部分
%{
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)
  }
// 對應.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 {

}
// 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
}

轉自： zhuanlan.zhihu.com/p/264367718

Go 開發大全

參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qSbftFcRfigqEl_2-bfw3A

猜你喜歡