golang实现自定义语言的基础 - goyacc简易入门 - 马良

0x01 自言自语

一直就对解析文档，比较感兴趣，一直没深入研究，只停留在仅知道 Lex & yacc 和 antlr 的名词阶段，最近看了 go-zero 的 api 解析器，觉得甚好，是时候花时间学习一下了。

简单看了 zero 发现是自己实现了词法分析、语法解析，这不符合我的一贯偷懒作风，所以并未其源码开始学习。既然用 golang 那么他自带的 goyacc 就是我学习的不二之选。当然你可能会听说 Lex&yacc 已经很古老了，antlr 更先进一点。但是既然 goyacc 能成为 golang 官方工具，那么肯定还是值得你学习的。

goyacc 的文档非常的少，少到什么程度？少到你未来一定能搜到这篇。甚至连 github 上的使用例子也不多，大致就分两类：计算器、sql 解析器，其中计算器目测是国外某大学的课程。

所以研究 goyacc 我花了好几个通宵、掉了少许头发。不经让这篇文章有了一个营销文案：花了一夜时间，搞懂了外国的一堂编译原理课。

个人对技术文章的理解是，文章可以有自己的观点、啰嗦、甚至幽默，但尽量不要放在学术部分，毕竟技术是严禁的。所以下面描述，我可尽能做一个无情的打字机，尽可能的按照文档风描述。

0x02 goyacc 简易入门

安装 goyacc

golang 1.8 版本之前 yacc 直接再带与 go tool 无需自行安装。
鉴于使用的频率太少，遂在 golang 1.8 版本后 移除默认安装，即之后版本需手动安装（仍然为官方包）。

一键安装：

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

之后就可以通过执行goyacc 命令来测试安装情况了，如看到如下信息大致就安装成功了

$ goyacc -h
Usage of goyacc:
  -l    disable line directives
  -o string
        parser output (default "y.go")
  -p string
        name prefix to use in generated code (default "yy")
  -v string
        create parsing tables (default "y.output")

goyacc 工具带有一些可选参数

goyacc 编译 .y 文件

goyacc 工具的参数很简单，其作用主要是用来翻译 BNF（一种语法标识方法）语法描述文件（通常以. y 为后缀的文件）

让我们先看一个. y 文件的例子：

file: parser.y

%{
package parser
import (
    "fmt"
)
%}
%union {
   var string
   num int
}
%token <num> NUM
%token <var> ADD SUB '+' '-'
%type <val> expr
%start expr
%%
expr: NUM {
  $$ =$1
}
| expr '+' NUM {
  $$ = $1 + $3
}
| expr '-' NUM {
  $$ = $1 + $3
}
;

复制上面代码命名为 parser.y 然后用我们之前安装好的 goyacc 执行:

$ goyacc parser.y

查看一下文件变化：

$ ls
parser.y y.go     y.output

我们发现生成了两个新文件： y.go y.output

至此 你已经实践了 goyacc 的作用，即：通过文法文件（parser.y）生成语法解析器（y.go） 、解析过程表 （y.output）

请观察一下 y.go 文件的内容 （迫于篇幅，此处不贴 y.go 内容了，请按照上面进行试验即可得到）

下面我们详细说明一下 文法 (.y 文件) 的格式：

.y 构成格式

如同 c 版本的 yacc 一样, goyacc 的. y 文件大致分成几个部分：

1, 由 {% 与 %} 包括的 嵌入代码
2, 用 %% 分割的三段: 文法定义 %% 文法规则 %% 嵌入代码

{%
嵌入代码
%}
文法定义 
%%
文法规则 
%%
嵌入代码 （golang代码，通常忽略此部分直接在写在代码头中）

下面详细描述一下 文法定义 与 文法规则：

文法定义

通常使用 %union %type %token %left %right 等构成

如：
定义一个 val 类型 映射到 golang 的 string 类型,
定义一个 stu 映射到 golang 中定义的一个 Student 结构体类型

%union {
    val string
    stu Student
}

• %type

定义一个 val 类型的 expr 非终结符 （nonterminal）

%type <val> expr

• %token 定义终结符

定义一个 val 类型的 Val 终结符 （terminal）

%token <val>  Val

（这听起来不好懂，可以想象成有个 Val 类型的变量接收器）

也可以定义个没有类型值的终结符，如

%token OP

• %start 定义一个开始终结符

即设置一个开始的终结符，即从这里开始解析语法

%start expr

%left %right 主要用来设置匹配结合方式 这里先不展开了

文法规则

非终结符: 规则描述 {
动作描述
};

“:” 左边的是非终结符 右侧的规则 通常由 非终结符 终结符 构成

非终结符 使用 %type 定义的符号 可以理解为一串特定排序的 token
终结符 可以理解成 一个 token
规则描述 可以是 非终结符、终结符， 可用 | 分割多个规则， {} 内是具体动作,{} 内符合 golang 语法，并且 $$ 代表规约后的值 $1 $2 代表类型变量值
动作描述 即用 “{” 与“}”包裹的部分 符合 golang 语法且拥有特殊宏替换的语法块

一条规则最后要用 “;” 结束

例子 1:

expr1: NUM '+' NUM {
 $$ = $1 + $3
};

这个例子定义了 一个 两数求和的规则 （a+b）
expr 构成终结符这个非 终结符的条件又三个终结符（token）构成 NUM ‘+’ NUM ，方法是求两数之和 返回给 expr

例子 2:

expr2: expr1 '+' NUM {
 $$ = $1 + $3
};

这个例子了 三个数求和，并使用了一个非终结符作为规则的一部分

当需要定一个多个数求和时就需要通过递归定义了

例子 3:

expr3: expr3 '+' NUM {
   $$ = $1 + $3
} | NUM '+' NUM {
  $$ = $1 + $3
};

这个例子通过递归定义了 支持多个数相加的规则 其中 使用 “｜” 分割了两个规则描述

其实语法解析 就是根据 token 去拼出多个解析规则，然后通过递归下降等算法去解析。
yacc 就是是通过. y 描述文件 生成递归下降程序（y.go 程序）实现语法解析的一个过程。

实现 lexer 接口

goyacc 没有对应的 lex 生成工具
通常需要手工写两个方法来实现 yyLexer 接口

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

Lex() 词法分析函数 解析过程会多次回调此方法，每次调用应返一个 token 值， lval 是当前栈状态值
Error() 错误回调方法 在语法解析错误时被回调

一般可以通过 text/scanner 进行基础解析，再换算成自己的 token，省去部分烦劳工作

0x03 附录 A - 名词解释

0x04 附录 B - 常见错误

• default action causes potential type clash: parser.go.y:40
• token illegal on LHS of grammar rule
• rules never reduced
• rule $NAME: $NAME never reduced
• conflicts: 1 shift/reduce

0x04 附录 B - 参考文献

• https://blog.csdn.net/wp1603710463/article/details/50365640
• https://blog.csdn.net/zzhongcy/article/details/93753017

最后更新于 2020-09-14 06:50:09 并被添加「」标签，已有 1599 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
https://www.1thx.com/golang/189.html