写编译器的朋友多半都有这种体会词法分析还能手写正则一到语法分析就开始头疼尤其是表达式这种带优先级、又要处理括号嵌套的东西手写递归下降不是不行但改文法、加运算级别的时候特别容易把自己绕进去。我最近在凹语言里做一个小工具需要用表达式解析做配置计算研究了一圈发现凹语言官方工具链里已经内置了一个 yacc 实现可以像传统 LALR 解析器生成器那样用一份文法文件直接生成解析器代码。这篇文章就基于我实际跑通的例子聊聊凹语言版本 yacc 的使用方法、文法设计思路以及我在调试冲突和做错误恢复时踩过的坑。这个内容适合谁看主要是三类人想在凹语言里做模板引擎、配置解析、DSL 解释器的人用过 Go 的 goyacc 或 C 的 bison/yacc想知道凹语言这边怎么接的人还有就是刚接触编译原理想找一个能快速上手、能实际生成代码的语法分析器练手的学习者。我会以四则运算表达式为例从文法设计讲到代码集成尽量把每一步怎么做、为什么这么做讲清楚。1. 凹语言 yacc 是什么为什么写解析器的人需要它1.1 从一个需求说起解析器不是只能手写先交代下背景。凹语言是一套面向 WebAssembly 设计的通用编程语言语法风格接近 Go工具链整体用 Go 实现可以编译成 wasm 在浏览器里跑。它自带不少周边工具其中就包括 yacc——一个 LALR(1) 语法分析器生成器。你提供一份类似 Bison 语法的 .y 文件它就能生成一整套解析器代码你只需要在词法层面提供 token 流剩下的状态机、移进归约、语法树构造逻辑全都由生成代码帮你搞定。在实际做项目之前我一直以为解析器这种东西手写递归下降就够了。确实查表运算符优先级这种简单场景手写也就几十行。但一旦语法规则多起来比如要支持赋值语句、函数调用、数组下标、类型标注递归下降的代码量会迅速膨胀而且每个优先级函数之间互相调用规则改起来非常痛苦。yacc 这种声明式方案的好处就在这你用 BNF 描述规则规则之间的层级关系直接决定了优先级描述完之后冲突检测、状态机生成、归约动作这些脏活累活它全包了。凹语言版本 yacc 继承了这一整套思路写出来的解析器还能直接编进 wasm跟凹语言生态无缝配合。1.2 凹语言 yacc 与经典 yacc / goyacc 的异同用凹语言的 yacc 不会让你感到陌生因为它的整体风格和 goyacc 非常接近。同样是定义 token、定义类型、写文法规则同样使用$$、$1这类位置变量访问语义值。凹语言 yacc 还支持在规则段直接嵌入凹语言代码这些代码会被拷贝到生成的解析器里作为语义动作执行。跟经典 yacc 相比凹语言版本有几个特点值得注意类型系统走的是凹语言的路子语义值类型在%union里定义解析器生成的代码也是凹语言源码而不是 C 或 Go。它在生成解析器的同时会输出一个可读的 report 文件把状态机、冲突情况列得非常清楚调试冲突特别好用。跟 goyacc 一样它默认处理的是 8-bit 的 token 值但你通过%token声明的 token 编号会映射到正确的整数值不受 ASCII 范围限制。我当时选择凹语言 yacc除了因为项目本身就在凹语言生态里还有一个原因它生成的解析器代码不依赖运行时反射所有状态迁移都是整型数组查表编译成 wasm 之后体积和性能都非常可控。这一点在某些嵌入式浏览器环境里特别有价值跑在内存受限的终端上也毫无压力。1.3 表达式解析为什么是“最好的入门案例”你可能会有疑问为什么讲解 yacc 一定要拿表达式解析举例因为表达式解析恰好覆盖了语法分析器生成器最核心的几个机制终结符与非终结符的定义、文法递归、优先级和结合性声明、冲突消解、语义动作构造 AST。这些东西一旦在表达式这个例子上吃透了迁移到完整的语句解析、声明解析本质上只是多堆几条规则而已。四则运算表达式看起来简单但如果你尝试手写递归下降会发现至少要拆成四个层级expression处理加减、term处理乘除、factor处理一元负号和括号、number处理数字字面量。如果还要考虑右结合的赋值运算符又得单独处理。用 yacc 写优先级和结合性直接用%left、%right声明文法规则可以扁平很多。它的底层机制会自动构造出正确处理运算符优先级的 LALR 状态机这就省掉了手写时最繁琐的逻辑分支。2. 表达式解析的设计思路文法、优先级与 AST2.1 先理清词法分析和语法分析的边界在写 yacc 文件之前必须把一件事想清楚yacc 只负责语法分析不负责词法分析。它从你手上接受的是 token 流而不是字符流。token 的定义和识别还是得自己处理。我的做法是写一个独立的词法器函数lex()它从源码字符串里识别数字、运算符、括号并返回 (token类型, token字面量) 给 yacc 生成的解析器使用。比如数字123会被识别成NUM类型会被识别成类型。yacc 内部会根据当前状态和接下来的 token 决定是移进还是归约归约时触发你写的语义动作。这种方法的好处是逻辑完全解耦词法器可以处理字符串、跨行、注释、关键字语法分析器只关心 token 序列是否符合文法。我在凹语言的例子里就是这样用一个凹语言写的nextToken()函数扫描输入串每次调用返回(tokenID, tokenText)如果扫描到源码末尾就返回一个代表 EOF 的特殊 token。这种设计让词法部分可以单独测试我实际调试中 80% 的解析异常其实是词法 token 给错了跟语法规则无关。先把 token 打出来再去看语法问题会省很多时间。2.2 终结符、非终结符与 BNF 文法设计文法是一份 yacc 文件的核心。它由产生式组成每个产生式的左侧是一个非终结符右侧是一串终结符和非终结符。终结符就是你从词法里返回的 token 类型非终结符是语法层的抽象。比如一个支持加减乘除和括号的表达式文法expression: expression term | expression - term | term ; term: term * factor | term / factor | factor ; factor: ( expression ) | - factor | NUMBER ;这里expression、term、factor是非终结符、-、*、/、(、)、NUMBER是终结符。递归的产生式expression term表示一个表达式后面跟加号和 term 仍然是表达式这种左递归在 LALR 解析器里很重要因为它天然对应了循环而不是无限递归yacc 生成的状态机可以高效处理左递归不会爆栈。相比之下手写递归下降通常用右递归或迭代实现两者处理方式完全不同。你可能会问为什么factor里放一元负号而不是把它丢进term因为一元负号的优先级应该比乘法更高-2*3应该解析成(-2)*3。放在factor层的效果就是一元负号只能作用于括号、数字和其他 factor这样它天然就比term层的乘法更紧密。2.3 优先级与结合性%left 声明到底在干什么上面这个写法没有用到%left声明因为文法层级已经天然区分了优先顺序。但很多教科书和实际项目会采用更简化的文法配合优先级声明来消除冲突。凹语言 yacc 完全支持这种方案。比如你可以写%left - %left * / %right UNARY_MINUS %% expression: expression expression | expression - expression | expression * expression | expression / expression | - expression %prec UNARY_MINUS | ( expression ) | NUMBER ;这个文法比前面的版本简洁得多但它是有歧义的12*3既可以先归约12再乘 3也可以先归约2*3再加 1。两者的语法树不同。yacc 遇到这种情况会产生 shift/reduce 冲突默认动作是 shift移进。%left、%right声明会修改冲突处理策略如果你声明和*都是左结合那么对于123解析器应该在遇到第二个时选择归约而不是移进因为左结合表示(12)3对于12*3由于*的优先级高于解析器在读到2后面的*后会选择移进让2*3先被归约。我个人的建议是初学者尽量用第一种分层文法因为它直观且不会产生任何冲突跑起来稳稳当当。但你要理解%left机制因为很多现成文法都依赖它而且遇到冲突时你需要通过%prec指定某条规则的优先级。后面第四部分我会具体演示怎样通过 report 文件看到并解决这种冲突。2.4 语义动作与 AST 构建光能识别语法还不够我们真正要的是解析结果。yacc 规则后面的{}代码块就是语义动作它告诉解析器一旦归约了这条规则要执行什么操作。以构建 AST 为例expression: expression term { $$ NewNode(OP_ADD, $1, $3) } | expression - term { $$ NewNode(OP_SUB, $1, $3) } | term { $$ $1 } ;$1、$3分别代表规则右侧第 1 个和第 3 个符号的语义值$$代表归约后左侧非终结符的语义值。这样一层层往上解析结束后最顶层的$$就是完整的表达式 AST。之后你可以遍历 AST 求值、编译成字节码、生成代码或做类型检查。我在凹语言例子里用的是语义值联合体%union里定义了val int和node *ExprNode两种字段不同规则根据需要把结果赋给不同字段。凹语言的类型约束比 C 严格所以我在语义动作里会显式做类型断言这类代码生成后不太容易出隐蔽的类型错误这也是凹语言 yacc 用起来更省心的一个点。3. 从零跑通一个凹语言 yacc 表达式解析器3.1 搭建环境与准备测试文件要跑通这个例子第一步是安装凹语言工具链。凹语言官方仓库的 release 页面有对应平台的二进制文件下载解压后把wa和wayacc不同版本可能叫wa yacc子命令放到 PATH 里。接着建一个项目目录我习惯命名为expr-parser里面放两个核心文件parser.yyacc 文法文件包含 token 声明、类型定义、文法规则和语义动作。main.wa凹语言主程序包含词法器、yyLexer接口实现、AST 定义和入口main函数。如果还没有现成文件可以用一个最简单的表达式只包含数字和加号来起步。不要一开始就上完整文法否则出了问题你分不清是哪条规则导致的。我每次都是先把12跑通了再逐步加减法、乘法、括号每加一个层次就编译测试一次。这比一次性写完再排查要快得多。3.2 编写一份可运行的 yacc 文法文件下面这份是我实际跑通的精简版本它对应前面那个分层文法支持数字、加减乘除、括号和一元负号。你直接保存为parser.y即可%{ # 这里可以放一些生成代码的前导内容 # 比如 import 声明、辅助函数定义 %} %union { val int node *ExprNode } %token val NUMBER %token ADD SUB MUL DIV LPAREN RPAREN %type node expression term factor unary %% expression: expression ADD term { $$ NewNode(OP_ADD, $1, $3) } | expression SUB term { $$ NewNode(OP_SUB, $1, $3) } | term { $$ $1 } ; term: term MUL unary { $$ NewNode(OP_MUL, $1, $3) } | term DIV unary { $$ NewNode(OP_DIV, $1, $3) } | unary { $$ $1 } ; unary: SUB unary { $$ NewNode(OP_NEG, $2, nil) } | factor { $$ $1 } ; factor: LPAREN expression RPAREN { $$ $2 } | NUMBER { $$ NewNum($1) } ; %% func yyError(msg string) { println(parse error:, msg) }这里我把unary单独拆出来一层让负号可以嵌套比如--5factor只管括号和数字。%token val NUMBER的意思是 NUMBER 这个终结符的语义值类型是int在词法器里把数字的值填进去。%type node则声明各非终结符的语义值类型是*ExprNode。语法动作里的NewNode、NewNum需要你在主程序里实现这是典型的“动作代码与生成解析器通过约定接口协作”的模式。3.3 生成解析器代码并集成到凹语言项目执行生成命令wayacc -o parser.wa parser.y如果文法存在冲突终端会打印 warning同时会生成y.output文件里面是详细的状态表。你的预期输出是一个凹语言源码文件parser.wa它内部定义了yyParse()函数我们会在main.wa里调用它。注意一个隐藏约定parser.y里提到的yyError、yyLexer是生成代码要用的两个外部符号。其中yyLexer必须是实现了Lex(lval *yySymType) int方法的类型Lex每次返回一个 token 编号并把 token 的语义值写入lval。下面这段凹语言代码展示了main.wa里如何实现一个最小词法器type ExprLexer struct { src string pos int } func (l *ExprLexer) Lex(lval *yySymType) int { for l.pos len(l.src) { c : l.src[l.pos] if c || c \t || c \n { l.pos continue } l.pos switch c { case : return ADD case -: return SUB case *: return MUL case /: return DIV case (: return LPAREN case ): return RPAREN default: if c 0 c 9 { v : int(c - 0) for l.pos len(l.src) l.src[l.pos] 0 l.src[l.pos] 9 { v v*10 int(l.src[l.pos]-0) l.pos } lval.val v return NUMBER } return -1 } } return 0 }这里 token 常量ADD、SUB等在生成的parser.wa里会作为常量导出所以词法器里直接引用即可。最后一个return 0代表 EOF这是 yacc 系列的惯例。词法器里lval.val v对应%token val NUMBER的声明这样语法动作里$1就能拿到数字的值。每次 Lex 被调用时yacc 生成的状态机会根据当前状态决定是移进还是归约不断驱动这个循环。3.4 调用 yyParse 与验证计算结果有了词法器和文法文件主程序里只需要这样几行func main { lexer : ExprLexer{src: 1 2 * 3} parser : yyParserImpl{} root : parser.Parse(lexer) if root nil { return } val : Eval(root) println(val) }不同版本的凹语言 yacc 生成的 API 可能略有差别常见的是通过yyParse(lexer)直接返回起始非终结符的语义值。因为我们的起始符号是expression所以最终返回的就是一个 AST 节点调用Eval(root)可以递归求值。Eval的实现是对 AST 节点做深度优先遍历func Eval(n *ExprNode) int { if n.op OP_NUM { return n.val } left : Eval(n.left) if n.op OP_NEG { return -left } right : Eval(n.right) switch n.op { case OP_ADD: return left right case OP_SUB: return left - right case OP_MUL: return left * right case OP_DIV: return left / right } return 0 }编译运行wa build -o expr.wasm main.wa parser.wa然后在支持 wasm 的运行环境里执行或者用wa run直接跑控制台会输出7。到这里一个凹语言 yacc 表达式解析器就跑通了。整个过程下来你会发现真正难的不是写代码而是把文法想清楚以及理解 yacc 在冲突时做了什么选择。4. 踩坑实录冲突、报错恢复与调试技巧4.1 shift/reduce 冲突与 reduce/reduce 冲突用 yacc 系列工具最常遇到的就是 shift/reduce 冲突和 reduce/reduce 冲突。前者意味着解析器在读入某个 token 时既可以继续移进这个 token也可以先归约当前规则yacc 默认选择移进后者意味着同一条规则有多个归约候选yacc 默认选择先声明的规则。这两个默认行为大多数时候能满足需求但如果你声明的优先级和结合性不合理就会得到预料之外的解析结果。我在写表达式文法的早期版本时把一元负号直接放进了termterm: term MUL term | term DIV term | - term | factor ;结果编译时 yacc 报告了 shift/reduce 冲突。原因是-2*3读到2之后的*时状态机不知道应该先按term - term归约成-2还是把*移进让2*3先结合。用%left *声明可以解决但我后来干脆把它拆到unary层不仅冲突消失语义也更明确——负号只作用于原子的东西。如果你想清楚冲突根源y.output文件非常重要文件里会把每个状态标出冲突的项集看state N里哪些规则和哪些 token 产生冲突。我第一次排查时就是靠y.output定位到状态 9 的省了不少瞎猜的时间。4.2 优先级声明的正确姿势与 %prec 的用途在不拆分文法的方案里%prec是一个很有用的修饰符。它可以把某条规则的优先级临时指定成别的 token 的优先级。比如常见的解法%left - %left * / %right UMINUS %% expression: expression expression | expression - expression | expression * expression | expression / expression | - expression %prec UMINUS ;%prec UMINUS的意思是尽管这条规则的右侧有-但它的优先级按照UMINUS声明来处理。由于UMINUS声明在%left * /之后它的优先级高于乘除自然也就高于加减。这样-2*3会先按 UMINUS 归约再乘得到(-2)*3符合数学惯例。我踩过的坑是忘记给%prec用到的伪 token 加%left或%right声明结果 UMINUS 没有优先级冲突照样存在。所以伪 token 也必须在%left/%right/%nonassoc里声明它才能参与优先级比较。4.3 悬挂 else 之外的另一个经典例子括号归约说到二义性表达式解析还有一个容易踩的坑括号。比如(12)*3如果你在文法里把factor写成ID | NUMBER | ( expression )这是没问题的。但如果你写成factor: ID | NUMBER | factor并且某处不太小心加了一条expression: factor就会出现 reduce/reduce 冲突。我的经验是每加一条规则就编译一次一旦出现冲突立刻看y.output对比发生冲突的状态会比写完所有规则再排查容易得多。尤其是括号的归约因为它会把 expression 的语义值直接提升为 factor 的语义值如果类型标注不匹配凹语言编译器还会再报一轮类型问题这种“双重报错”容易让人误解是 yacc 的问题但其实是你文法写岔了。4.4 语法错误处理与错误恢复yyError 怎么写实际解析中不可能总是合法的输入串。凹语言 yacc 沿用了yacc的错误处理机制当解析器遇到无法移进或归约的 token 时会调用yyError(msg)如果你想从错误中恢复可以在文法里使用专门的错误 token。比如expression: expression ADD term | expression SUB term | term | error ADD term ;这里的error是保留关键字它匹配任意一串无法归约的 token。遇到错误时状态机会把错误位置的 token 丢掉然后尝试移进error并继续解析。这样你可以在错误后继续收集后面的语法结构。我的实际做法是在yyError里记录错误行号和消息但不立即终止同时在文法适量的位置放error产生式让解析尽可能继续。凹语言 yacc 里错误 token 的处理规则跟 bison 基本一致你可以在同一段落查看生成报告里的 error 条目。调试时注意别在error后面直接跟一个必须出现的终结符否则错误恢复会变得特别激进一口气吞掉大量内容反倒掩盖了真正的错误位置。4.5 词法错误与语法错误的边界划分很多人调试 yacc 解析器时把语法解析的报错归因于 yacc 规则但实际是词法器返回了错误的 token。我发生过一个典型问题源码里数字后面直接跟字母比如12abc我的词法器会把12解析成 NUMBER把abc解析成别的 token然后语法分析器就在12和abc之间报 syntax error。从 yacc 的角度看这是文法不允许NUMBER IDENT相邻但从人的角度看这其实是词法错误——12abc应该整体报错。因此我把词法器里的数字识别做了改进读取完连续数字后如果下一个字符是字母或下划线则返回错误 token。这样就把这类问题挡在语法分析之前报错信息也更友好。4.6 调试心得把 token 流打出来比看状态机快最后分享一个非常实用的小技巧。遇到诡异的解析结果时先不要盯着 yacc 规则冥思苦想而是在词法器里临时打印每个 token 的类型和字面量。我自己调试时经常看到NUMBER(12) NUMBER(34)这种不该出现的序列或者token 丢失的诡异情况这些都是词法器状态没有正确推进导致的。把 token 流打印出来后问题一般三分钟就能定位。确定词法没问题再去看y.output的状态冲突这时才轮到文法和优先级排查。这个顺序我用了很多年效率极高。凹语言 yacc 生成的代码本身有很详细的状态表你甚至可以逐步打印yyParse内部的yyState变化不过大部分情况下没必要深入到底层token 流 状态冲突报告已经覆盖了绝大多数问题。5. 实际工程量评估与扩展方向5.1 从四则运算扩展到完整的迷你语言四则运算跑通之后往真实语言扩展的路子就很清晰了。表达式之外你可以增加声明语句、赋值语句、函数调用、流程控制。比如在文法里加入statement: IDENT ASSIGN expression | IF expression THEN statement ELSE statement | WHILE expression DO statement ;这些规则只需要注意一点IF和ELSE的组合会引入经典的悬挂 else 二义性你需要在%nonassoc里声明THEN再用%prec调整。凹语言 yacc 处理这类问题的机制和 bison 一致所以你能在网络上找到大量现成例子。我建议你每增加一个语言特性就把它作为一个独立的非终结符抽象出来并且给每个非终结符明确标注%type的语义值类型编译期就能帮你查出一大批类型问题。5.2 性能与体积在 wasm 环境里的实测感受我在凹语言里跑过上万行的表达式解析实测下来整个解析器的状态机是静态数组没有运行时构造图表的开销解析性能远高于手写递归下降中最慢的那种模式匹配实现。生成代码体积也不大核心解析表压缩后大概几十 KB 级别在浏览器里加载几乎无感。如果你的应用场景是浏览器端动态计算、在线公式编辑器、低代码平台的表达式引擎凹语言 yacc 生成的解析器完全撑得住。我自己的项目里还顺手把 AST 序列化成 JSON 发到前端展示语法树前后端用同一份文法定义极大减少了维护成本。5.3 关于工具链版本的小提示凹语言迭代速度挺快不同版本之间 yacc 子命令的调用方式、生成的解析器 API 会有细微差异。我写这篇文章用到的wayacc命令在你下载最新版工具链时可能会变成wa yacc子命令生成的yyParse签名也可能调整。建议你以官方文档和当前版本内置的示例为准。如果编译报错提示某个函数未定义优先去工具链的 examples 目录里翻对应示例那里的代码和当前版本的生成器是同步维护的往往比文档更可靠。5.4 我在实际项目里最终选择的组合方案这里也给你一个参考如果解析的语法不复杂、优先级层级不超过三四个我会直接手写递归下降但如果语法规则可能持续增长、希望以后用同一份文法生成其他语言版本的解析器我会选择 yacc 方案。凹语言 yacc 的定位恰好就在这条分界线上它把文法的可维护性和生成代码的执行效率做到了一个很舒服的平衡。我在实际写凹语言项目时yacc 主要负责处理表达式、语句块、模块声明这些“规则密集”的部分词法和语义分析仍由手写代码承担——这既是 yacc 生态的经典用法也是我认为最不容易翻车的分工方式。
