使用 goyacc 工具構建語法分析程序
使用 goyacc 工具構建語法分析程序
前言
本文仅讨论 goyacc 工具的应用, 而不是编译原理的基础知识. 故想要流畅地阅读本文, 需要首先理解以下问题:
- 词法分析, 语法分析分别是什么?
- 正规文法, 上下文无关文法, 上下文有关文法有何区别?
- 终结符, 非终结符各指代什么?
想要更好地运用 goyacc, 可能还需要掌握以下技能:
- 编写词法分析模式.
- 编写文法推导规则.
- 消除文法左递归.
- 自顶向下和自底向上分析算法.
goyacc 規則文件格式
goyacc 与 yacc 规则文件格式是一致的, 如果你熟知 yacc, 想必对此也不会陌生. 规则文件一般以 *.y 作为扩展名, 由三部分内容构成, 其间以 %% 进行分隔.
定義區
代碼块
定义区主要功能是添加类型定义, 标识符定义, 包声明和引用, 这些代码将会被复制到生成文件的开头. 编写 goyacc 规则时, 首先添加一个代码块:
%{
package myparser
import (
"errors"
"fmt"
"strings"
)
%}
引用块分别以 %{ 和 %} 起始和结束, 用来在最终生成的 *.go 文件开头处插入代码. 这里声明包名为 myparser, 并导入了三个标准库, 用于在之后的规则区嵌入代码中使用.
类型定义
程序在处理文法规则时, 通常一些特定的符号需要携带一些信息, 这时就需要为这些符号指定附加数据的类型, 我们可以使用 %union 来实现这一目标:
%union {
Bool bool // 将 Bool 映射为 bool 类型
Int int64
String string
Expr *ast.Expr // 用 ast 包定义的 Expr 类型来存放抽象语法树信息
}
类型定义将在规则区的嵌入代码中使用, 后文会介绍这些类型如何发挥作用.
符号定义
文法推导规则是由终结符和非终结符构成的, 这些符号在 *.y 文件中通过 %type 和 %token 来声明:
%type expr // 定义非终结符
%type <Int> value // 定义非终结符, 带有 Int 型信息
%token '+' '-' '*' '/' // 定义终结符
%token <String> IDENT // 定义标识符, 带有 String 型信息
一般习惯用小写单词 (如 expr)命名非终结符, 大写单词 (如 IDENT) 命名终结符. 这些符号最终会作为枚举常量添加到生成的 *.go 文件中, 如果不希望导出符号, 也可使用 _Ident 等形式来命名终结符. 此外, '+' 这类单个字符也可直接定义为终结符, 不需要命名.
这里的 <Tag> 用于指定 %union 块中已定义的类型, 在文法推导规则中, 相应的符号将携带指定类型的信息.
默认情况下, 规则区定义的首个非终结符将作为文法的起始符号, 但也可以通过 %start 显式指定:
%start expr // 显式指定 expr 为起始符号
运算符结合性
运算符本身也属于终结符, 与一般性的终结符不同的是它考虑结合性和优先级. 分别使用 %left 和 %right 定义左结合和右结合运算符, 或使用 %nonassoc 来声明此运算符不与前后的其他终结符结合. 同一行定义的运算符具有相同的优先级, 不同行中, 后定义的运算符具有更高的优先级. 例:
%left '+' '-' // 定义左结合运算符
%left '*' '/' // 定义左结合运算符, 比 '+' '-' 优先级更高
%right NOT // 定义右结合运算符, 比 '*' '/' 优先级更高
規則區
前文提到, *.y 文件由两个 %% 符号分为三部分, 在前面定义区的内容结束后, 加一行 %% 来接着编写文法规则:
// 定义区
%{
...
%}
%union { ... }
%type ...
%token ...
%%
// 规则区
%%
// 函数区
yacc 规则与常见的文法推导式十分相似, 我们很容易将已有的文法编写为 yacc 规则, 以常见的四则运算文法为例:
E -> E + T | E - T
T -> T * F | T / F
F -> ( E ) | i
根据以上文法, 我们可以写出以下规则:
expr:
expr '+' term {
$$ = $1 + $3
}
| expr '-' term { ... }
| term { ... }
term:
term '*' factor { ... }
| term '/' factor { ... }
| term { ... }
factor:
'(' expr ')' { ... }
| _Int { ... }
上述文法规则中, expr, term, factor 为非终结符, '+', '-', '*', '/', '(', ')', _Int 为终结符. 每一条推导规则由非终结符起始, 接冒号后编写各个推导分支, 分支之间以 | 分隔, 每个分支后用大括号包裹一个嵌入代码块, 用来执行此分支命中时的动作.
在分支的代码块中, 直接嵌入 go 代码, 使用 $$ 来指代此条规则的起始非终结符的附加信息, 即 %type 定义的数据类型, 如第一条规则的第一条分支中, $$ 指代 expr, 其类型可以定义为 %type <Int> expr. 根据当前分支的推导式, 式中的每个元素可用 $1, $2, $3 等符号来引用, 于是此分支实际生成的 go 代码形如:
switch state {
case x:
// expr: expr '+' term { $$ = $1 + $3 }
// 其中 $$, $1, $3 均定义为 <Int>, 而 '+' 没有定义附加信息类型, 故不可通过 $2 引用其值
value.Int = dollar[1].Int + dollar[3].Int
default:
// 其他状态分支略去
}
作为对照, 下面的例子用来构建抽象语法树:
%union {
Expr *ast.Expr
Term *ast.Term
// ...
}
%type <Expr> expr
%type <Term> term
// ...
%%
// type Expr struct { Terms []*Term }
// type Term struct { ... }
// func NewExpr(*ast.Term) *ast.Expr
// func (*ast.Expr) Add(*ast.Term) *ast.Expr
expr:
term {
$$ = ast.NewExpr($1)
}
| expr '+' term {
$$ = $1.Add($3)
}
// ...
%%
函數區
由于 go 包内函数都是相互可调用的, 也没有先后定义的要求, 故不必在 *.y 文件的函数区编写代码, 而是直接在同目录下创建其他 *.go 文件来添加常量, 类型和函数定义等.
生成 go 代码
goyacc 命名读取 *.y 文件定义的规则, 检查并生成 y.go 文件, 可以通过安装官方 go-tools 包获得:
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")
一般来说直接在 abc.y 同目录下执行 goyacc abc.y 即可生成 y.output 和 y.go 文件, 其中 y.output 对我们来说是无用的, 可以通过 -v 参数指向到 /dev/null 或添加 gitignore 配置忽略之. 如果规则常常变更, 可以考虑增加 -l 参数以去除生成 y.go 文件中的行号注释, 这样在 git diff 中不会看到这些无用的变更行.