gocc 解析器生成器源码逐行解读：action table 与 LR(1) 运行时工作原理

gocc 解析器生成器源码逐行解读action table 与 LR(1) 运行时工作原理【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/goccgocc 是一款用 Go 语言实现的解析器生成器Parser / Scanner Generator你只要写好一份 .bnf 语法文件它就能自动生成词法分析器lexer与 LR(1) 语法分析器parser的完整 Go 源码。本文以项目自带的计算器示例为例逐行解读 gocc 生成的解析器源码重点讲透 action table动作表的数据结构与运行时工作原理帮助新手彻底看懂 parser.go、actiontable.go、gototable.go 这些机器生成的文件。什么是 gocc 解析器生成器从 BNF 到可运行源码的完整流程gocc 的用法非常直观写好一份 EBNF 风格的语法描述文件如example/calc/calc.bnf运行 gocc它就会在目标目录下自动生成 5 个子包lexer/词法分析器负责把字符流切成 token见example/calc/lexer/lexer.goparser/语法分析器核心是 LR(1) 查表驱动的 shift/reduce 引擎token/token 类型定义与 TokenMapexample/calc/token/token.goerrors/错误类型封装example/calc/errors/errors.goutil/字面量转换等工具example/calc/util/litconv.go以计算器示例为例语法文件example/calc/calc.bnf的核心部分长这样Calc : Expr; Expr : Expr Term $0.(int64) $2.(int64), nil | Term; Term : Term * Factor $0.(int64) * $2.(int64), nil | Factor; Factor : ( Expr ) $1, nil | int64 util.IntValue($0.(*token.Token).Lit) ;生成流程在源码里也有迹可循internal/parser/gen/gen.go是代码生成的总入口它依次调用GenAction、GenActionTable、GenGotoTable、GenParser、GenProductionsTableLR(1) 项目集的构建发生在internal/parser/lr1/items最终通过internal/parser/gen/golang下的模板文件渲染输出。gocc 生成的解析器源码清单parser 包里的文件各司其职在example/calc/parser/目录下gocc 生成了 6 个文件每个文件开头都带着 Code generated by gocc; DO NOT EDIT. 标记action.go定义动作接口与三类动作类型actiontable.go核心的 action table动作表二维查找表gototable.go归约后的状态跳转表goto tableproductionstable.go产生式表内含语义动作ReduceFuncparser.go解析器主体含栈结构与 Parse 主循环context.go用户上下文接口其中 action table 是整个 LR(1) 解析器的大脑其余文件都围绕它运转。action table 数据结构逐行解读action.go 里的三类动作打开example/calc/parser/action.gogocc 只定义了一个接口和三个极简类型type action interface { act(); String() } type ( accept bool // 接受语法分析成功 shift int // 移入值是下一个状态的编号 reduce int // 归约值是产生式编号 )在 LR 解析理论中每一时刻解析器面对当前状态 当前 token只需回答一个问题接下来做什么gocc 给出的答案只有三种shift(n)把当前 token 移入栈并跳转到状态 n继续读下一个 tokenreduce(n)用第 n 条产生式把栈顶若干符号归约成一个非终结符accept整个输入已被接受语法分析成功结束表格里出现nil的位置则代表非法动作即语法错误会触发错误处理逻辑。actiontable.go 源码逐行解读一张二维查找表如何驱动语法分析example/calc/parser/actiontable.go的核心数据结构极其简洁type ( actionTable [numStates]actionRow actionRow struct { canRecover bool actions [numSymbols]action } )也就是说整张 action table 就是一个状态数 × 符号数的二维数组。以计算器为例numStates 2323 个 LR 状态、numSymbols 1212 种符号含终结符与非终结符。查表方式就是actionTab[栈顶状态].actions[当前token类型]一次数组下标访问O(1) 完成决策。看 S0 这一行初始状态就能明白它的含义actionRow{ // S0 canRecover: false, actions: [numSymbols]action{ nil, // INVALID nil, // ␚ (EOF) nil, // nil, // * shift(5), // ( nil, // ) shift(6), // int64 }, },含义初始状态 S0 下如果读到(就移入并跳转状态 5读到int64就移入并跳转状态 6其余 token 都是nil报错。每一行注释里 gocc 都贴心标注了对应的 token 名称读起来一目了然。canRecover字段则用于错误恢复时判断某个状态能否作为恢复点。gototable.go 与 productionstable.go归约后的去向与语义动作goto tableexample/calc/parser/gototable.go负责回答归约后去哪个状态type gotoTable [numStates]gotoRow type gotoRow [numNTSymbols]int // -1 表示无跳转例如 S0 行Calc → 1、Expr → 2、Term → 3、Factor → 4。当栈顶归约出一个非终结符时解析器就用gotoTab[当前栈顶][产生式的NTType]找到下一个状态并压栈。产生式表example/calc/parser/productionstable.go则把语法规则和语义动作绑定在一起type ProdTabEntry struct { String string // 产生式的可读描述 Id string // 左部非终结符名 NTType int // 左部在 goto 表中的列号 Index int // 产生式编号 NumSymbols int // 右部符号个数决定弹栈数量 ReduceFunc func([]Attrib, interface{}) (Attrib, error) }注意第 2 条产生式Expr : Expr Term的ReduceFunc是X[0].(int64) X[2].(int64)——这正是你在 .bnf 里写的 $0.(int64) $2.(int64), nil 语义动作被 gocc 编译后的形态。也就是说你在语法文件里写的语义代码最终会成为这里的一个闭包函数。运行时工作原理Parse 主循环中的 shift/reduce 完整流程现在看example/calc/parser/parser.go中最重要的Parse方法。它维护一个双数组栈stack.state存状态编号stack.attrib存对应的属性值token 或归约结果。主循环非常紧凑for acc : false; !acc; { action : actionTab[p.stack.top()].actions[p.nextToken.Type] switch act : action.(type) { case accept: res p.stack.popN(1)[0] // 取出最终结果 acc true case shift: p.stack.push(int(act), p.nextToken) // 移入 token 并跳转 p.nextToken scanner.Scan() // 读下一个 token case reduce: prod : productionsTable[int(act)] attrib, _ : prod.ReduceFunc(p.stack.popN(prod.NumSymbols), p.Context) p.stack.push(gotoTab[p.stack.top()][prod.NTType], attrib) } }整个运行时工作原理可以概括成四步循环查表以栈顶状态和当前 token 为下标从actionTab取动作移入shifttoken 压栈、状态跳转、读取下一个 token归约reduce按NumSymbols弹出若干栈项执行ReduceFunc计算属性值再按 goto 表压回新状态接受accept弹出最终结果解析完成打开调试开关internal/parser/gen/golang/parser.go模板中的Debug分支后每一步都会打印形如S0 int64 shift:6的日志是学习 LR 解析原理的绝佳工具。实例跟踪解析 23*4 的完整过程用上面的表手动推演一遍token 序列int64(2) int64(3) * int64(4) EOF步骤栈状态当前 token动作说明1S0int64shift(6)2 入栈2S0,S6reduce(7)Factor→int64得 23S0,S4reduce(5)Term→Factor得 24S0,S3reduce(3)Expr→Term得 25S0,S2shift(7)运算符 入栈6S0,S2,S7int64shift(6)3 入栈7S0,S2,S7,S6*reduce(7)Factor→int64得 38S0,S2,S7,S4*reduce(5)Term→Factor得 39S0,S2,S7,S14*shift(8)运算符 * 入栈10S0,S2,S7,S14,S8int64shift(6)4 入栈11S0,S2,S7,S14,S8,S6EOFreduce(7)Factor→int64得 412S0,S2,S7,S14,S8,S15EOFreduce(4)Term→Term*Factor3×41213S0,S2,S7,S14EOFreduce(2)Expr→ExprTerm2121414S0,S2EOFreduce(1)Calc→Expr15S0,S1EOFaccept结果为 14注意第 12、13 步因为*的归约先于发生3*4先被算成 1221214得到正确结果——这正是 LR 语法分析自动实现运算符优先级的过程无需任何手工处理。完整推演与测试代码见example/calc/calc_test.go。如何快速上手用 gocc 生成你的第一个解析器想动手体验 gocc 解析器生成器的完整流程只需三步获取源码git clone https://gitcode.com/gh_mirrors/go/gocc然后按根目录Makefile或gen.sh构建出 gocc 可执行文件写语法文件仿照example/calc/calc.bnf编写你自己的 .bnf 文件生成并测试在example/calc这样的示例目录下执行makegocc 会自动重新生成所有源码并运行单元测试项目还自带丰富的进阶示例可对照学习example/astx生成 AST、example/errorrecovery错误恢复、example/usercontext用户上下文等。更详细的 API 说明可以翻阅用户手册doc/gocc_user_guide.pdf。常见问题action table 太大、冲突与调试技巧Q状态多、表很大的时候生成的 actiontable.go 会不会很占空间Agocc 内置了压缩方案。当配置开启 zip 模式时见internal/parser/gen/golang/actiontable.go中的GenCompActionTableaction table 会被序列化后用 gzip 压缩再在init()中解压还原显著减小生成的 Go 源码体积。Q语法有歧义生成时报冲突怎么办Agocc 会报告具体的冲突位置和行。项目提供了example/srshift/reduce 冲突和example/rrreduce/reduce 冲突两个专门示例展示了冲突出现的原因与处理思路值得逐一调试理解。Q解析出错时如何定位A每个 action row 都带canRecover标记配合parser.go中的Error、popNonRecoveryStates方法实现错误恢复开启 Debug 后还能看到每一步的 shift/reduce 日志配合栈内容打印stack.String()即可精准定位问题。写在最后gocc 生成的解析器源码看似机器味很重但拆开来看核心不过是一张 action table 加一个 while 循环查表、移入、归约、接受周而复始。理解了 action table 与 LR(1) 运行时的工作原理你不仅能自信地使用 gocc 生成解析器也为读懂任何表驱动的语法分析器打下了坚实基础。想深入了解从internal/parser/lr1/items的项目集构造算法开始你会看到 LR 理论的优雅全貌。【免费下载链接】goccParser / Scanner Generator项目地址: https://gitcode.com/gh_mirrors/go/gocc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考