专栏首页01ZOOgoyacc 实战
原创

goyacc 实战

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

基础

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

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

每个过程也有很多种做法

  • 词解析是将一个语句解析成 token 的过程,这个过程一般比较简单,可以使用 lex, flex 之类的工具,也可以完全手写
  • 语法解析时将 token 组合解析成语法树的过程,对于比较复杂的 dsl 设计,这个过程可能比较复杂,可以借助如 yacc 这样的工具,但是为了追求效率,也可以完全手写(promql 就是手写,如果是手写,没有太大必要把词解析和语法解析两者分割得太清楚)
  • 执行我们只看即时执行的情况,一般来说可以对上一步的语法树直接执行,也可以做进一步编译,以虚拟机(类似 lua、python 等)的方式执行。先编译的好处是可以做一些优化,执行效率会更高。

GoYacc

  • goyaccc 版本的 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 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • yarn 学习笔记(对比 kubernetes 调度)

    ApplicationMaster(AM),用户提交的每个应用程序都需要包含一个AM, 作用为:

    王磊-AI基础
  • 任务流引擎简介

    任务比如 k8s 概念中的 job,一般指的是短期的会结束的一个离线任务,而人物流就是将一组任务组织起来的流程。比如下面的这个流程。

    王磊-AI基础
  • 谁在主导开源社区

    前段时间微软收购github.com,闹得动静很大。有个评论说微软现在是github最大的贡献者,事实真的是这样吗。

    王磊-AI基础
  • 研究丨中国智能制造业运行特征及转型升级路线

    导读:以互联网为核心的新一代信息技术加快推广普及,推动企业组织流程、商业模式创新。一是互联网技术激发了用户被搁置的多样化个性化需求,企业传统商业模式、组织架构难...

    钱塘数据
  • CSS布局新方案——Grid 网格布局

    在Web Page Layout 的演进历史中,我们从刚开始的 table 到 float、position、inline-block,再到css3的盒子模型F...

    江米小枣
  • 如何让树莓派接入外网并自定义域名

    520当天,本想给媳妇一个精喜,于是计划在云服务器上面部署一个node项目,但是部署过程服务器直接宕机,无奈重启,查询云服务器状态,发现内存只剩下可伶的几十M?

    SAnBlog
  • 小谈 Java 单元测试

    总之有无数种理由不想写UT,作为工作不到三年的菜鸟深有体会。之前在点评工作的时候,团队的“UT”都集中于RPC的服务端。为啥带双引号? 因为RPC的服务端没有页...

    芋道源码
  • jvm linux 时区设置

    在接入集团一个平台的时候,发现录制某个接口到测试环境回放,发现接口入参一致,一个start_day 一个end_day,但回放的时候会多调用一次数据库查询,很是...

    千往
  • 【进阶之定义函数】一个查询树结构数据的集合

    2.1 统计文章分类的数量,分类是树形结构,所以有一个先查询分类树形的级别的集合。使用的函数包括FIND_IN_SET

    用户5640963
  • uvc协议摄像头

    sofu456

扫码关注云+社区

领取腾讯云代金券