腾讯云·社区
goyacc 实战
本文可以看作 这篇文章 的延伸
基础
要实现一个简单的 DSL 解释器，通常可以简化为下面的过程
graph LR 词解析--> 语法解析 语法解析 --> 解释执行
每个过程也有很多种做法
- 词解析是将一个语句解析成 token 的过程，这个过程一般比较简单，可以使用 lex, flex 之类的工具，也可以完全手写
- 语法解析时将 token 组合解析成语法树的过程，对于比较复杂的 dsl 设计，这个过程可能比较复杂，可以借助如 yacc 这样的工具，但是为了追求效率，也可以完全手写（promql 就是手写，如果是手写，没有太大必要把词解析和语法解析两者分割得太清楚）
- 执行我们只看即时执行的情况，一般来说可以对上一步的语法树直接执行，也可以做进一步编译，以虚拟机（类似 lua、python 等）的方式执行。先编译的好处是可以做一些优化，执行效率会更高。
GoYacc
- 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 // 这个返回的 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 <num> expr expr1 expr2 expr3
%token '+' '-' '*' '/' '(' ')'
%token <num> 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 对应的解构
}
| '-' expr
{
$$ = $2.Neg($2)
}
expr1:
expr2
| expr1 '+' expr2
{
$$ = $1.Add($1, $3) // 当前结构更新为 expr1.Add(expr2)
}
| 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 Parser
例子来自这里, 写一个编译器识别 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 '}' // json 对象
members: // 表示一组键值对
| pair
| members ',' pair
pair: String ':' value // 一个键值对, 键只能是字符串
array: '[' elements ']' // 数组
elements: // 数组内容, 一组 value
| value
| elements ',' value
value: // 值，值可以是 string, number, literal, object, array
String
| Number
| Literal
| object
| array实战：Brainf**k 解释器
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)
- 优化重复的操作符比如
➜ go build . ➜ ./brainfk "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++." Hello World!
实战: Github Sql
用 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 删除。
相关文章
扫码关注云+社区
领取腾讯云代金券
我来说两句