实战用 gocc 从零打造一个迷你编程语言词法、AST 与求值全流程【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/goccgocc 是一个用 Go 编写、面向 Go 开发者的 Parser / Scanner Generator解析器与扫描器生成器你只需写一份 BNF 文法文件它就能自动生成词法分析器DFA、LR(1) 解析器PDA以及完整的 token 包。这篇 gocc 实战教程将带你从安装 gocc 开始用 BNF 定义一门支持变量与四则运算的迷你编程语言完整走通词法分析、AST 抽象语法树构建与表达式求值全流程帮助新手快速入门编译原理。gocc 是什么一个能生成编译器的 Go 编译器工具gocc 的全称是 Go Compiler Compiler本质上是编译器的编译器。它的工作方式非常直观你把一门语言的规则写进一个.bnf文件gocc 就会自动产出可以直接使用的词法分析器、LR(1) 语法分析器和 token 定义省去手写状态机与查表算法的痛苦。词法分析器是 DFA确定性有限自动机支持 UTF-8 输入语法分析器是 LR(1) 的 PDA下推自动机并支持自动解决移进/归约冲突生成的代码自带调试开关还提供errors、util等配套包。gocc 甚至用自己生成的解析器来解析自己的文法文件spec/gocc2.ebnf属于典型的自举self-hosting项目工程上非常优雅。gocc 安装与环境准备一键开始在动手写迷你语言之前先把 gocc 装好。前提是电脑上已经安装了 Go1.16 以上即可然后克隆项目并编译git clone https://gitcode.com/gh_mirrors/go/gocc cd gocc go install编译完成后把go install的 bin 目录加入 PATH在任意目录执行gocc -h能打印帮助信息就说明安装成功。仓库里的gen.sh展示了 gocc 自举时的调用方式参数含义一目了然gocc -o internal/frontend -p github.com/goccmack/gocc/internal/frontend spec/gocc2.ebnf第一步用 gocc BNF 文法定义迷你语言现在开始设计我们的迷你语言。目标支持整数、变量、加/减/乘/除、括号与赋值语句。把规则写进minilang.bnf文件分词法部分与语法部分_digit : 0-9 ; _idchar : a-z | A-Z | 0-9 | _ ; id : (a-z | A-Z | _) {_idchar} ; int64 : 1-9 {_digit} | 0 ; !whitespace : | \t | \n | \r ; import minilang/ast Program : StmtList ; StmtList : Stmt | StmtList ; Stmt ; Stmt : id Expr ast.NewAssign($T0, $2) | Expr $0 ; Expr : Expr Term ast.NewBinary(, $0, $2) | Expr - Term ast.NewBinary(-, $0, $2) | Term ; Term : Term * Factor ast.NewBinary(*, $0, $2) | Term / Factor ast.NewBinary(/, $0, $2) | Factor ; Factor : ( Expr ) $1 | int64 ast.NewNumber($T0) | id ast.NewVar($T0) ;几个值得注意的 gocc BNF 写法以!开头的 token如!whitespace会被词法分析器自动忽略{...}表示重复a-z表示字符区间 ... 是语义动作action expression里面直接写 Go 代码$0、$1表示对应位置的子节点$T0是$0的类型断言简写等价于$0.(*token.Token)。仓库里example/calc/calc.bnf就是一个最精简的算术表达式文法example/bools/example.bnf则展示了、|、字符串比较等更丰富的写法都是绝佳的参考资料。第二步一条命令生成词法分析器与解析器文法写好后在minilang.bnf所在目录执行gocc minilang.bnfgocc 会立刻生成lexer/DFA 词法分析器、parser/LR(1) 解析器、token/、errors/和util/五个包。example/calc目录里就是一份完整的生成结果其Makefile里只有一行gocc calc.bnf说明重新生成就是这么简单。如果只想保留自定义的扫描器可以用-no_lexer参数只生成解析器-v可以输出 LR(1) 项集、FIRST 集等调试信息-o、-p用于指定输出目录与包名。所有参数定义在internal/config/config.go中需要的可以自行查阅。第三步用语义动作构建 AST 抽象语法树词法、语法都齐了但解析出来的还只是 Token 流我们要把它变成可求值的 AST 抽象语法树。BNF 里的 ast.NewNumber($T0) 就是在告诉 gocc归约到这条规则时调用ast包里的构造函数。对应的ast/ast.go可以这样写package ast type Node interface{} type Number struct{ Val int64 } type Var struct{ Name string } type Binary struct { Op string L, R Node } type Assign struct { Name string Val Node } func NewNumber(t interface{}) (Node, error) { ... } func NewVar(t interface{}) (Node, error) { ... } func NewBinary(op string, l, r interface{}) (Node, error) { return Binary{op, l.(Node), r.(Node)}, nil } func NewAssign(name interface{}, v interface{}) (Node, error) { return Assign{string(name.(*token.Token).Lit), v.(Node)}, nil }可以看到gocc 的语义动作只需要返回(Node, error)把 Token 与子节点拼装成 AST 的责任完全交给你。参考实现可以看example/astx/ast/ast.go语句列表拼接与example/astx/ast.bnf$T0的用法另外example/usercontext/example.bnf还演示了通过$Context把自定义上下文传进语义动作的高级玩法。第四步递归求值让迷你语言真正跑起来AST 构建完成后求值就是一次简单的递归遍历——这是整个流程里最舒服的部分func Eval(n Node, env map[string]int64) int64 { switch t : n.(type) { case *Number: return t.Val case *Var: return env[t.Name] case *Binary: l, r : Eval(t.L, env), Eval(t.R, env) switch t.Op { case : return l r case -: return l - r case *: return l * r case /: return l / r } case *Assign: env[t.Name] Eval(t.Val, env) return env[t.Name] } return 0 }至此一门迷你编程语言已经活了a 1 2 * 3; a 4会被正确解析成 AST再被求值为11。第五步编写测试验证全流程最后写一个测试把词法分析、语法分析、AST 与求值串起来验证func TestEval(t *testing.T) { lex : lexer.NewLexer([]byte(a 1 2 * 3; a 4)) st, err : parser.NewParser().Parse(lex) if err ! nil { t.Fatal(err) } if got : Eval(st, map[string]int64{}); got ! 11 { t.Fatalf(expect 11, got %d, got) } }example/calc/calc_test.go就是这么做的它用一组{1 2 * 3, 7}这样的输入-期望对批量跑测试。注意测试里同时用到了lexer.NewLexer与parser.NewParser().Parse这正是 gocc 生成产物最标准的调用方式。gocc 常见问题LR(1) 冲突如何自动解决写复杂文法时移进/归约shift/reduce与归约/归约reduce/reduce冲突很常见。gocc 默认会报错并输出冲突明细但加上-a参数后它会按内置策略自动解决冲突对大多数场景足够用。仓库的example/sr/与example/rr/就是为演示这两类冲突准备的example/errorrecovery/er.bnf还展示了错误恢复的写法建议逐个跑一遍。总结gocc 进阶学习路线到这里你已经用 gocc 完成了一个迷你编程语言从词法到求值的完整闭环。如果想继续深入官方用户手册doc/gocc_user_guide.pdf是最系统的资料spec/gocc2.ebnf定义了 gocc BNF 的完整语法example/下十几个示例计算器、布尔表达式、邮件地址、错误恢复等每个都值得动手生成并跑一遍。从手写编译器到用 gocc 生成编译器这条路比想象中短得多祝你在编译原理的世界里玩得开心【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/gocc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 实战：用 gocc 从零打造一个迷你编程语言（词法、AST 与求值全流程）
实战用 gocc 从零打造一个迷你编程语言词法、AST 与求值全流程【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/goccgocc 是一个用 Go 编写、面向 Go 开发者的 Parser / Scanner Generator解析器与扫描器生成器你只需写一份 BNF 文法文件它就能自动生成词法分析器DFA、LR(1) 解析器PDA以及完整的 token 包。这篇 gocc 实战教程将带你从安装 gocc 开始用 BNF 定义一门支持变量与四则运算的迷你编程语言完整走通词法分析、AST 抽象语法树构建与表达式求值全流程帮助新手快速入门编译原理。gocc 是什么一个能生成编译器的 Go 编译器工具gocc 的全称是 Go Compiler Compiler本质上是编译器的编译器。它的工作方式非常直观你把一门语言的规则写进一个.bnf文件gocc 就会自动产出可以直接使用的词法分析器、LR(1) 语法分析器和 token 定义省去手写状态机与查表算法的痛苦。词法分析器是 DFA确定性有限自动机支持 UTF-8 输入语法分析器是 LR(1) 的 PDA下推自动机并支持自动解决移进/归约冲突生成的代码自带调试开关还提供errors、util等配套包。gocc 甚至用自己生成的解析器来解析自己的文法文件spec/gocc2.ebnf属于典型的自举self-hosting项目工程上非常优雅。gocc 安装与环境准备一键开始在动手写迷你语言之前先把 gocc 装好。前提是电脑上已经安装了 Go1.16 以上即可然后克隆项目并编译git clone https://gitcode.com/gh_mirrors/go/gocc cd gocc go install编译完成后把go install的 bin 目录加入 PATH在任意目录执行gocc -h能打印帮助信息就说明安装成功。仓库里的gen.sh展示了 gocc 自举时的调用方式参数含义一目了然gocc -o internal/frontend -p github.com/goccmack/gocc/internal/frontend spec/gocc2.ebnf第一步用 gocc BNF 文法定义迷你语言现在开始设计我们的迷你语言。目标支持整数、变量、加/减/乘/除、括号与赋值语句。把规则写进minilang.bnf文件分词法部分与语法部分_digit : 0-9 ; _idchar : a-z | A-Z | 0-9 | _ ; id : (a-z | A-Z | _) {_idchar} ; int64 : 1-9 {_digit} | 0 ; !whitespace : | \t | \n | \r ; import minilang/ast Program : StmtList ; StmtList : Stmt | StmtList ; Stmt ; Stmt : id Expr ast.NewAssign($T0, $2) | Expr $0 ; Expr : Expr Term ast.NewBinary(, $0, $2) | Expr - Term ast.NewBinary(-, $0, $2) | Term ; Term : Term * Factor ast.NewBinary(*, $0, $2) | Term / Factor ast.NewBinary(/, $0, $2) | Factor ; Factor : ( Expr ) $1 | int64 ast.NewNumber($T0) | id ast.NewVar($T0) ;几个值得注意的 gocc BNF 写法以!开头的 token如!whitespace会被词法分析器自动忽略{...}表示重复a-z表示字符区间 ... 是语义动作action expression里面直接写 Go 代码$0、$1表示对应位置的子节点$T0是$0的类型断言简写等价于$0.(*token.Token)。仓库里example/calc/calc.bnf就是一个最精简的算术表达式文法example/bools/example.bnf则展示了、|、字符串比较等更丰富的写法都是绝佳的参考资料。第二步一条命令生成词法分析器与解析器文法写好后在minilang.bnf所在目录执行gocc minilang.bnfgocc 会立刻生成lexer/DFA 词法分析器、parser/LR(1) 解析器、token/、errors/和util/五个包。example/calc目录里就是一份完整的生成结果其Makefile里只有一行gocc calc.bnf说明重新生成就是这么简单。如果只想保留自定义的扫描器可以用-no_lexer参数只生成解析器-v可以输出 LR(1) 项集、FIRST 集等调试信息-o、-p用于指定输出目录与包名。所有参数定义在internal/config/config.go中需要的可以自行查阅。第三步用语义动作构建 AST 抽象语法树词法、语法都齐了但解析出来的还只是 Token 流我们要把它变成可求值的 AST 抽象语法树。BNF 里的 ast.NewNumber($T0) 就是在告诉 gocc归约到这条规则时调用ast包里的构造函数。对应的ast/ast.go可以这样写package ast type Node interface{} type Number struct{ Val int64 } type Var struct{ Name string } type Binary struct { Op string L, R Node } type Assign struct { Name string Val Node } func NewNumber(t interface{}) (Node, error) { ... } func NewVar(t interface{}) (Node, error) { ... } func NewBinary(op string, l, r interface{}) (Node, error) { return Binary{op, l.(Node), r.(Node)}, nil } func NewAssign(name interface{}, v interface{}) (Node, error) { return Assign{string(name.(*token.Token).Lit), v.(Node)}, nil }可以看到gocc 的语义动作只需要返回(Node, error)把 Token 与子节点拼装成 AST 的责任完全交给你。参考实现可以看example/astx/ast/ast.go语句列表拼接与example/astx/ast.bnf$T0的用法另外example/usercontext/example.bnf还演示了通过$Context把自定义上下文传进语义动作的高级玩法。第四步递归求值让迷你语言真正跑起来AST 构建完成后求值就是一次简单的递归遍历——这是整个流程里最舒服的部分func Eval(n Node, env map[string]int64) int64 { switch t : n.(type) { case *Number: return t.Val case *Var: return env[t.Name] case *Binary: l, r : Eval(t.L, env), Eval(t.R, env) switch t.Op { case : return l r case -: return l - r case *: return l * r case /: return l / r } case *Assign: env[t.Name] Eval(t.Val, env) return env[t.Name] } return 0 }至此一门迷你编程语言已经活了a 1 2 * 3; a 4会被正确解析成 AST再被求值为11。第五步编写测试验证全流程最后写一个测试把词法分析、语法分析、AST 与求值串起来验证func TestEval(t *testing.T) { lex : lexer.NewLexer([]byte(a 1 2 * 3; a 4)) st, err : parser.NewParser().Parse(lex) if err ! nil { t.Fatal(err) } if got : Eval(st, map[string]int64{}); got ! 11 { t.Fatalf(expect 11, got %d, got) } }example/calc/calc_test.go就是这么做的它用一组{1 2 * 3, 7}这样的输入-期望对批量跑测试。注意测试里同时用到了lexer.NewLexer与parser.NewParser().Parse这正是 gocc 生成产物最标准的调用方式。gocc 常见问题LR(1) 冲突如何自动解决写复杂文法时移进/归约shift/reduce与归约/归约reduce/reduce冲突很常见。gocc 默认会报错并输出冲突明细但加上-a参数后它会按内置策略自动解决冲突对大多数场景足够用。仓库的example/sr/与example/rr/就是为演示这两类冲突准备的example/errorrecovery/er.bnf还展示了错误恢复的写法建议逐个跑一遍。总结gocc 进阶学习路线到这里你已经用 gocc 完成了一个迷你编程语言从词法到求值的完整闭环。如果想继续深入官方用户手册doc/gocc_user_guide.pdf是最系统的资料spec/gocc2.ebnf定义了 gocc BNF 的完整语法example/下十几个示例计算器、布尔表达式、邮件地址、错误恢复等每个都值得动手生成并跑一遍。从手写编译器到用 gocc 生成编译器这条路比想象中短得多祝你在编译原理的世界里玩得开心【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/gocc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考