goyacc 实战 - 云社区 - 腾讯云 - 《golang 硬核学习》

本文可以看作这篇文章的延伸

要实现一个简单的 DSL 解释器，通常可以简化为下面的过程

graph LR
词解析\--\> 语法解析
语法解析 \--\> 解释执行

每个过程也有很多种做法

词解析是将一个语句解析成 token 的过程，这个过程一般比较简单，可以使用 lex, flex 之类的工具，也可以完全手写
语法解析时将 token 组合解析成语法树的过程，对于比较复杂的 dsl 设计，这个过程可能比较复杂，可以借助如 yacc 这样的工具，但是为了追求效率，也可以完全手写（promql 就是手写，如果是手写，没有太大必要把词解析和语法解析两者分割得太清楚）
执行我们只看即时执行的情况，一般来说可以对上一步的语法树直接执行，也可以做进一步编译，以虚拟机（类似 lua、python 等）的方式执行。先编译的好处是可以做一些优化，执行效率会更高。
goyacc 由 c 版本的 yacc 工具翻译而来
能解释 LALR(1) 语法 (look head one token and decide what action to take).
可以嵌入 go 代码
内部使用状态机实现，很高效

goyacc 内部有两个重要的 interface, 其中 yyLexer 需要使用者自己实现提供，yacc 会生成 yyParser 的实现，其使用 yyLexer 做解释操作。解释的过程和和解释前后都可以嵌入自己的代码逻辑，完成一个程序或者单纯生成一个自定义的语法树结构.

type yyLexer interface {
    Lex(lval \*yySymType) int 
    Error(e string)
}
type yyParser interface {
    Parse(yyLex) int
    Lookahead() int
}

golang 1.8 版本之前 yacc 直接再带与 go tool 无需自行安装。

鉴于使用的频率太少，遂在 golang 1.8 版本后移除默认安装，即之后版本需手动安装（仍然为官方包）。

go get \-u github.com/golang/tools/tree/master/cmd/goyacc

参数

说明

| |
| |

-l

显示 line 指令

|
|

-o string

指定输出解析器的文件名称（默认 y.go）

|
|

-p string

指定解析器输出接口的前缀

|
|

-v string

生成解析过程表（默认 y.output）

先看一个简单的例子, 这个例子来自 go 官方

%union {
    num \*big.Rat
}
%type    <num\>    expr expr1 expr2 expr3
%token '+' '-' '\*' '/' '(' ')'
%token    <num\>    NUM
%%
top:
    expr
    {
        if $1.IsInt() {
            fmt.Println($1.Num().String())
        } else {
            fmt.Println($1.String())
        }
    }
expr:
    expr1
|    '+' expr
    {
        $$ \= $2
    }
|    '-' expr
    {
        $$ \= $2.Neg($2)
    }
expr1:
    expr2
|    expr1 '+' expr2
    {
        $$ \= $1.Add($1, $3)
    }
|    expr1 '-' expr2
    {
        $$ \= $1.Sub($1, $3)
    }
expr2:
    expr3
|    expr2 '\*' expr3
    {
        $$ \= $1.Mul($1, $3)
    }
|    expr2 '/' expr3
    {
        $$ \= $1.Quo($1, $3)
    }
expr3:
    NUM
|    '(' expr ')'
    {
        $$ \= $2
    }
%%

可以看一下这个 y 文件的构成, 时如下的结构

{%
嵌入代码: go 代码
%}
文法定义: 由 %union %type %token %left %right %start 等组成的定义
%%
文法规则: 由 非终结符 与 终结符 组成的匹配 + 动作规则
%%
嵌入代码 （这部分为可选，比如可以 lexer 或者 main 可以写在这里或者单独用文件写 ）

文法定义简单说明如下

描述符

说明

| |
| |

%union

用来定义一个类型并映射 golang 的一个数据类型

|
|

%struct

同 %union 建议使用 %union

|
|

%token

定义终结符，表示不能再拆了的字符是一个 union 中定义的类型, 可无类型

|
|

%type

定义非终结符

|
|

%start

定义从哪个终结符开始解析默认规则段中的第一个终结符

|
|

%left

定义规则结合性质左优先

|
|

%right

定义规则结合性质右优先

|
|

%nonasso

定义规则结合性质不结合

|
|

%perc term

定义优先级与 term 一致

其中最常用的时 union/token/type, union 用来表示, token, type 的类型，也就是说 token, type 可能是 union 中的一个类型，并且这个结构会出现在生成的 symType 里面，会由 lexer 传给 parser. 在下面的文法规则的动作里面，匹配后的变量 $1, $2 等等，都可以当成定义好的类型.
%union {
num big.Rat
}
%type expr expr1 expr2 expr3
%token ‘+’ ‘-‘ ‘‘ ‘/‘ ‘(‘ ‘)’
%token NUM
文法规则表示匹配了符号之后，怎么完成动作. 一般写作下面的形式, 规则描述可以是非终结符、终结符，可用 | 分割多个规则. 动作描述可以没有，写成 {} 或者不写, 动作描述由 golang 表示，一般会取动作描述中的元素作为参数使用 $1, $2 这样的形式表示第一个，第二个符号，符号的类型在 union 中已经定义。$$ 则表示当前整个符号对应的结构
非终结符:
规则描述1
{
动作描述2
}
| 规则描述2
{
动作描述2
}
top:
expr
{
if $1.IsInt() {
fmt.Println($1.Num().String())
} else {
fmt.Println($1.String())
}
}
expr:
expr1
| ‘+’ expr
{
$$ = $2
}
| ‘-‘ expr
{
$$ = $2.Neg($2)
}
expr1:
expr2
| expr1 ‘+’ expr2
{
$$ = $1.Add($1, $3)
}
| expr1 ‘-‘ expr2
{
$$ = $1.Sub($1, $3)
}
expr2:
expr3
| expr2 ‘*’ expr3
{
$$ = $1.Mul($1, $3)
}
| expr2 ‘/‘ expr3
{
$$ = $1.Quo($1, $3)
}
expr3:
NUM
| ‘(‘ expr ‘)’
{
$$ = $2
}

这个例子时上面的示例的完整版本，来自 go 官方, 本质是实现了一个大数的计算器，支持 "+", "-", "*", "/", "(", ")", 值得注意的是 expr 定义了几种，里面蕴含了优先级关系.

本文将原始的代码分成 .y, lexer, main 多个文件，并且做了一定的简化，使得代码可读性更高，可以参考这里

例子来自这里, 写一个编译器识别 json 格式的字符串，【这个解释器做得比较简单，并无完全符合 json 标准】

这个例子的关键在于写出 json 的表达式树, 简化如下

%{
package jsonparser
type pair struct {
  key string
  val interface{}
}
%}
%union{
  obj map\[string\]interface{}
  list \[\]interface{}
  pair pair
  val interface{}
}
%token <val\> String Number Literal
%type <obj\> object members
%type <pair\> pair
%type <val\> array
%type <list\> elements
%type <val\> value
%%
object: '{' members '}' 
members: 
| pair
| members ',' pair
pair: String ':' value 
array: '\[' elements '\]' 
elements: 
| value
| elements ',' value
value: 
  String
| Number
| Literal
| object
| array

brainfuck 语言的解释器，这个语言比较简单，支持如下几种操作：

\# \>    Move the pointer to the right
# <    Move the pointer to the left
# +    Increment the memory cell under the pointer
# \-    Decrement the memory cell under the pointer
# .    Output the character signified by the cell at the pointer
# ,    Input a character and store it in the cell at the pointer
# \[    Jump past the matching \] if the cell under the pointer is 0
# \]    Jump back to the matching \[ if the cell under the pointer is nonzero

代码在这里

我们除了 lexer.go parser.y 之外还写了一个 env.go, 这是执行使用的结构体，目的是优化和执行代码。
这里我们用了几种优化策略：
- 优化重复的操作符比如 +++ 可以优化成 (+, 3)
- 对循环进行优化，比如 [+] 或者 [-], 表示持续加 1 直到变为 0 可以优化成 (setzero)； [>] 或者 [<], 表示向左 / 右移动指针直到指针下面的值为 0，可以优化成 (moveptr)； [-<+>] 或者 [->+<] 表示向指针下 / 上 n 个位置移动当前指针下的值，可以优化成 (movedata, n)

用 sql 的方式查询 github api，这个例子目前实现得比较简单，只支持 user repo api，并且只支持 select a from repo count x page y 这样的语句，不过大致的思路可以体现出来了. 代码在这里, 运行的时候需要先填入 github access token. 运行效果如下.

➜ ./githubsql
s\>  select \* from repo count 10 page 0
+\--\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--+\--\--\--\--\--\--\--\--\--\--\--\--\--\--\-+
|       NAME        |   OWNER LOGIN   |  LANGUAGE  |           TOPICS            |
+\--\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--+\--\--\--\--\--\--\--\--\--\--\--\--\--\--\-+
| kubebox           | arlert          |            |                             |
| kubepipe          | arlert          | Go         |                             |
| malcolm           | arlert          | Go         |                             |
| malcolm\-ui        | arlert          | TypeScript |                             |
| ymir              | arlert          | Go         |                             |
| fengming          | cargogogo       | Go         | \["container","image","p2p"\] |
| Dockerfiles       | goodow          |            |                             |
| bird              | kirk\-enterprise | C          |                             |
| calico            | kirk\-enterprise | Python     |                             |
| calico\-bgp\-daemon | kirk\-enterprise | Go         |                             |
+\--\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--\--\--\-+\--\--\--\--\--\--+\--\--\--\--\--\--\--\--\--\--\--\--\--\--\-+

原创声明，本文系作者授权云 + 社区发表，未经许可，不得转载。

如有侵权，请联系 yunjia_community@tencent.com 删除。
https://cloud.tencent.com/developer/article/1744609

goyacc 实战 - 云 社区 - 腾讯云

goyacc 实战 - 云社区 - 腾讯云