看到“BNF、巴科斯-诺尔范式”这个标题很多刚接触编译原理的人第一反应是又一个高大上的数学符号体系。但说句实在话BNF 是我在编译原理里见过的最接地气的工具之一。它本质上就干了一件事——用一套严格、无歧义的规则告诉计算机“什么样的句子是合法的”。之所以你感觉它难是因为教材往往一上来就甩出“上下文无关文法”“产生式”“终结符”这类术语让人瞬间劝退。这篇文章我带你把 BNF 彻底剥开看。不仅讲清楚它是什么更会拆解它怎么用、怎么自己写、怎么在真正的解析器Parser里落地还会聊很多课本上不会写、但工作里一定会踩的坑。无论你是正在啃编译原理的学生还是想自己写一个模板引擎、配置文件解析器乃至一门玩具语言的开发者这篇文章都值得你读完。1. BNF 为什么而生计算机需要一本“语法法典”1.1 自然语言的歧义计算机无法承受先想一个问题人和人交流的时候句子不通顺我们能靠常识脑补。比如“苹果我吃”哪怕语序不合常规对方也能意会。但计算机不行它是一台没有“脑补”能力的笨机器。你给它一段程序它只能在 0 和 1 的层面上机械地判断“这串字符符不符合我事先定义好的规则”。问题在于你怎么把规则告诉它直接用文字描述吗比如“一个 if 语句要先写 if然后写括号括号里放条件……”这种描述是模糊的而且面对嵌套、递归、复杂组合时必然产生歧义。所以我们需要一种“语法法典”一套机器可理解、人可书写的形式化规则把“合法句子”的定义精确到不可辩解的地步。这就是 BNF 的历史使命。1.2 从乔姆斯基体系说起上下文无关文法如果要给 BNF 找一个理论靠山那就是乔姆斯基语言学家也是形式语言理论的奠基人提出的文法分层体系。BNF 描述的是其中非常重要的一类——上下文无关文法Context-Free GrammarCFG。“上下文无关”的直觉理解是一个语法成分能否被替换成别的东西只取决于它自己不取决于它在句子里的周围环境。举个例子在程序语言里一个“表达式”不管出现在赋值号右边、函数参数里还是 return 后面它的语法展开规则完全一样不需要看“上下文”脸色。这就大大简化了语法分析的难度让解析器可以自上而下、机械地进行匹配。1.3 一个 BNF 最简单的样子先别把它想复杂。看看这个经典例子——描述一个“小数或整数”number :: digit | digitnumber digit :: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9这段规则的中文意思是一个“数字串”要么是一个“数字”要么是一个“数字”后面再跟一个“数字串”。这是一个递归定义一个“数字”可以是 0 到 9 中的任意一个。注意到没有你已经能感受到 BNF 的两个核心元素了尖括号括起来的叫“非终结符”它还需要继续展开直接写出来的字面量叫“终结符”它是最终句子里的真实字符。::表示“定义为”。这套东西读起来一点不难难的是把它和组织起成千上万行的语法规则以及连成一条链的解析算法。2. 拆开 BNF 的骨架终结符、非终结符与产生式2.1 三大核心要素很多人一看到“终结符”“非终结符”就发怵其实完全可以做个类比。想象你在拼乐高终结符Terminal最小的、不可再拆的积木颗粒比如单个字母a、数字1、符号。在语法层面它们是句子的最终外观。非终结符Nonterminal一个“拼装蓝图”的名字它并不直接出现在最终句子里但它能展开成多个积木。比如“表达式”“语句”“函数定义”。产生式Production一条“拼装说明”。它告诉系统名字为 X 的蓝图可以用哪些零件组合方式替换。X :: A B就是一条产生式。用更贴近编译原理的话说终结符构成语言的“词”Token非终结符构成语言的“句子结构”产生式则定义了从结构到词、从词到句子的全部映射关系。2.2 产生式的四类基本连接方式写 BNF 的时候一个产生式的右侧说白了就是下面几套组合手法写法含义例子并列必须按顺序一个接一个出现stmt :: if ( expr ) stmt选择竖线满足其中之一即可bool :: true递归自己包含自己表达“任意多个”list :: item空串允许什么都不出现opt_else :: else part特别要点名的是“递归”和“空串”。递归是 BNF 表达“重复”的唯一手段。想想看我们没有“重复一次或多次”这种现成运算符所以要表达“一个数字串”只能通过digit number这种自己引用自己的方式。空串通常用希腊字母 ε 表示用来表达“可以有也可以没有”它极其有用但也极其容易引起歧义和解析冲突后面会在实战部分展开。2.3 为什么尖括号和::不可随意更换有些人觉得 BNF 记号不统一有的书用::有的用,有的用→。这只是历史习惯差异。关键是你定义“非终结符”的方式不能含糊。比如用尖括号括起来的expr一定是非终结符而裸写的if、1、一定是终结符。这套约定保证了规则的无歧义性。如果你在写一个 Pratt Parser一种处理表达式优先级的技巧你可能会在代码里自定义一个 Parser 类里面用方法调用模拟 BNF 的展开这是后话。但无论什么工具你的底层结构里必须有一张“终结符 → Token 类型”的对应表以及一张“非终结符 → 产生式集合”的表。3. 从 BNF 到 EBNF上班之后真正在用的形态3.1 BNF 的“反人类”之处你可能会说纯 BNF 递归表达“零个或多个”写起来也太麻烦了。比如一门语言的标识符规则——以字母开头后续可以是字母或数字。用纯 BNF 写是这样identifier :: letter | identifier letter | identifier digit读起来啰嗦写多了眼睛都花。这个问题在 20 世纪 70 年代被注意到了于是出现了 EBNF扩展巴科斯-诺尔范式。EBNF 本身没有改变 BNF 的表达能力但增加了一批“语法糖运算符”大幅提升了可读性。3.2 EBNF 的三大运算符EBNF 最核心的增强是这三个表示法方括号[ ]表示“可选”。例如if_stmt :: if ( condition ) statement [else statement]意思是 else 分支可有可无。花括号{ }表示“重复零次或多次”。例如block :: { {statement} }表示花括号里可以放任意多条语句包括零条。括号( )表示“分组”。例如term :: factor {(* | /) factor}把乘除看成一个整体。有了这三个运算符前面的标识符规则直接写成identifier :: letter { letter | digit }清爽多了。3.3 练习用 EBNF 描述一个小型 JSON 子集我当年第一次上手练习 EBNF是尝试用这套记号去描述 JSON 的一个子集。这里给你看我当时写的一条json :: object | array object :: { [member {, member}] } member :: string : value array :: [ [value {, value}] ] value :: string | number | object | array | true | false | null string :: {char} 写完之后你会立刻发现 EBNF 和纯 BNF 的差别用 BNF 表达“逗号分隔的数组元素”需要额外引入两个非终结符来转接而 EBNF 直接写成了[value {, value}]一眼就能看出“第一个元素可选后续元素必须以逗号开头”。这套定义现在依然是我给学生和同事讲解析器时用的开场案例原因是它覆盖了嵌套结构、分隔符、可选元素三种最常见的语法模式。4. 从定义到推导语法树和最左/最右推导4.1 什么是推导有了 BNF 定义之后“如何判断一个句子属于这门语言”就成了一个机械的动作叫推导Derivation。简单说就是从一个起始非终结符出发不断地用产生式右侧替换左侧的非终结符直到整个序列只剩终结符。比如用一组极其简单的规则expr :: expr term | term term :: number number :: 1 | 2 | 3要想推导出句子1 2可以这样做expr → expr term 用第一条产生式展开最外层 expr → term term 展开左边的 expr → number term 展开左边的 term → 1 term 展开左边的 number → 1 number 展开右边的 term → 1 2 展开右边的 number推导过程本质上是在做“归约”的逆过程也是一个解析器在内部干的事情。理解推导你才算真正拿到了读懂 BNF 的钥匙。4.2 最左推导与最右推导为什么说它们重要在上述每一步中我每次都选择最左边的非终结符进行展开这叫最左推导。如果每次选最右边的就叫最右推导。这两者有实际意义吗有而且不小。自顶向下的递归下降解析器Recursive Descent Parser天然对应最左推导而自底向上的 LR 解析器则对应最右推导。换句话说你选择什么解析算法你就“隐含地”选择了什么样的推导顺序。掌握这一点排查 parse 栈溢出或抱死循环死循环问题时思路会清晰很多。4.3 语法树BNF 的动态表达推导过程中如果把每一步替换关系画出来会得到一个树形结构——语法树Parse Tree也叫具体语法树CST。树根是起始非终结符树叶是终结符内部节点是非终结符。这也揭示了一个非常本质的对应一棵语法树对应一个或多个推导序列当文法存在歧义时一个推导序列对应一棵语法树。所以判断一个文法是否有歧义最直接的方法就是看是否存在某个句子能画出两棵不同的语法树。这个概念在后面的运算符优先级处理中会再次用到。5. 实战用 BNF 设计表达式的优先级和结合性5.1 学 BNF 不能总停留在“读”很多人读文法读得溜一到自己写就抓瞎。原因很简单读只需要理解写需要设计能力。而 BNF 设计中最经典、最受考验的能力就是用分层定义处理运算符的优先级和结合性。优先级的本质是谁离根更远谁就先算。比如1 2 * 3乘法项2 * 3要先算所以“乘法项”这个非终结符应该离终结符更近。经典的四则运算文法没有括号版本是这样写的expr :: term {( | -) term} term :: factor {(* | /) factor} factor :: number | ( expr )对照一下expr位于最外层它里面嵌套termterm里面嵌套factor。当解析1 2 * 3时expr → term term → factor term → 1 term → 1 factor * factor → 1 2 * 3注意2 * 3在语法树中成了term节点的孩子而加法在更外层。这正是乘法优先于加法的结构体现。5.2 左结合与右结合递归位置定生死再来看结合性。1 - 2 - 3我们当然希望是(1 - 2) - 3这叫左结合。如何用 BNF 表达左结合关键技巧是让递归出现在产生式右侧的左边expr :: expr - term | term用这个规则推导1 - 2 - 3得到的是expr → expr - term → (expr - term) - term → ((term) - term) - term这棵树的形状是向左下方倾斜的天然对应左结合。反过来如果要表达右结合比如幂运算的2^3^2等于2^(3^2)那就要让递归出现在产生式右侧的右边expr :: term ^ expr | term这个“递归出现位置决定结合性”的技巧可以说是 BNF 设计里性价比最高的一个知识点。不少面试题就喜欢拿它考人比如“如何用 BNF 定义右结合的赋值运算符”答把目标非终结符放在产生式右侧最右端。5.3 为什么不能直接写expr :: number op expr op number很多新手会这样试图一步到位定义表达式expr :: number { op expr }问题大了。这既模糊了优先级也难以控制结合性。解析1 2 * 3时可能出现多个不同的展开形成多棵语法树——这在编译原理里叫二义性文法Ambiguous Grammar。绝大多数情况我们必须避免它因为多棵语法树意味着多种程序含义这会让编译器不知道该怎么生成代码。正确的做法永远是那套分层法每引入一级优先级就新增一个非终结符层次。优先级有 n 档就写 n1 层最后一层是原子项。6. 每个写解析器的人都会撞上的“左递归”和“回溯地狱”6.1 自顶向下解析器为什么怕左递归如果你真去实现一个递归下降解析器你大概率会遇到一个“爆栈”问题解析器无限递归直接撑爆调用栈。原因就在形如expr :: expr term的产生式上。递归下降解析器在解析非终结符expr时会调用parse_expr()而parse_expr()一开始就调用parse_expr()形成自我无限递归。这就是著名的“左递归灾难”。如果文法是你自己在设计最直接的解决方案是“改写文法”。把左递归文法改写成等价的右递归或循环形式。一组通用做法是把A :: A α | β改写为A :: β { α }EBNF 写法。举个例子expr :: term { ( | -) term }这不就是我前面写的版本吗对当时我为了可读性已经用 EBNF 把左递归“隐形”地消掉了。如果你必须坚持用纯 BNF 写那就写成expr :: term expr_tail expr_tail :: term expr_tail | - term expr_tail | ε注意ε 表示空串。这种引入“尾巴”非终结符的手法标准叫法是“左递归消除Left Recursion Removal”。6.2 还有一个大坑公共前缀和回溯爆炸即便你成功消除了左递归如果两个产生式有公共前缀递归下降解析器仍然可能陷入盲目回溯。例如if_stmt :: if ( expr ) stmt | if ( expr ) stmt else stmt解析器遇到if后先按第一条规则展开实际可能遇到else然后发现不匹配只好回溯重新选择第二条。这在小语法里还好在几千条规则的编译器里回溯代价可能大到无法接受。解决办法之一就是提取左公因子Left Factoring例如改写成if_stmt :: if ( expr ) stmt [else stmt]实际上大多数现代编程语言的设计者会刻意让文法满足 LL(1) 条件一眼即可决定选择的特性尽量避免回溯。你在设计自己的语法时也应遵循这个思路让解析器在每一步只看一个 Token 就知道该选哪条产生式。6.3 左递归并不总是坏事左结合性的另一种实现思路到这里你可能有些迷惑我前面说想表达左结合需要左递归现在又说自顶向下解析器怕左递归。那到底怎么取舍实际上在真正的解析器实现里很多递归下降解析器会采用循环 优先级绑定算法来处理左结合运算符也就是经典的 Pratt Parsing表达式解析算法或运算符优先级解析法。在这些算法中文法本身可以是扁平的但计算结合性是通过代码里的优先级表格实现的。也就是说BNF 是语法的“规范描述”而解析算法是语法的“工程实现”。两者可以不完全一一对应。这在面试或工程里非常常见。所以你一定要分清“概念层面的文法”与“工程层面的解析器”两件事。7. 动手写一个玩具语言从 BNF 到可运行的解析器7.1 目标设定理论聊得不少接下来我们用 BNF 手写一个实用的小玩意一个支持整数、加减乘除、括号和单行注释的表达式解析器。语言本身很小但足够演示 BNF 到代码的迁移过程。我选 Python 写不是因为 Python 多高级而是因为它表达力强大家可以无痛阅读。7.2 定义文法EBNF先把规则写出来expr :: term { ( | -) term } term :: factor { (* | /) factor } factor :: number | ( expr ) number :: digit { digit } digit :: 0 | ... | 9注意最外层expr处理加减中间层term处理乘除内层factor处理括号和原子值。这已经覆盖了我前面说到的优先级分层法。7.3 代码骨架Token 化解析的第一步是分词Tokenize把原始字符串拆成带类型的 Tokenimport re TOKEN_SPEC [ (NUMBER, r\d), (PLUS, r\), (MINUS, r-), (STAR, r\*), (SLASH, r/), (LPAREN, r\(), (RPAREN, r\)), (SKIP, r\s), ] token_re re.compile(|.join(f(?P{name}{pattern}) for name, pattern in TOKEN_SPEC)) def tokenize(text): tokens [] pos 0 while pos len(text): m token_re.match(text, pos) if not m: raise SyntaxError(f无法识别的字符: {text[pos]!r}) kind m.lastgroup if kind ! SKIP: tokens.append((kind, m.group())) pos m.end() tokens.append((EOF, )) return tokens这里的正则表达式其实就是对“终结符定义”的一种机械化翻译。每个 Token 类型对应 BNF 中的终结符。7.4 递归下降解析器直接把 BNF 翻译成函数接下来是最有爽感的部分每一条产生式就是一个函数每一次非终结符的展开就是一次函数调用。直接对照着写class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, kind): token self.peek() if token[0] ! kind: raise SyntaxError(f期望 {kind}, 但遇到 {token[0]}) self.pos 1 return token def parse_expr(self): node self.parse_term() while self.peek()[0] in (PLUS, MINUS): op self.consume(self.peek()[0])[0] right self.parse_term() node (BinOp, op, node, right) return node def parse_term(self): node self.parse_factor() while self.peek()[0] in (STAR, SLASH): op self.consume(self.peek()[0])[0] right self.parse_factor() node (BinOp, op, node, right) return node def parse_factor(self): token self.peek() if token[0] NUMBER: self.consume(NUMBER) return (Num, int(token[1])) if token[0] LPAREN: self.consume(LPAREN) node self.parse_expr() self.consume(RPAREN) return node raise SyntaxError(f意外的 Token: {token})看一眼parse_expr和 BNF 中的expr :: term { (|-) term }对应关系几乎是一比一转译。parse_expr一开始调用parse_term对应产生式右侧的第一个非终结符term随后进入 while 循环对应 EBNF 的花括号{ ... }。7.5 求值器走一遍语法树解析完成后我们对得到的语法树做一个简单的递归求值def evaluate(node): if node[0] Num: return node[1] _, op, left, right node lval, rval evaluate(left), evaluate(right) if op : return lval rval if op -: return lval - rval if op *: return lval * rval if op /: if rval 0: raise ZeroDivisionError(除数不能为零) return lval / rval到这一步一个支持优先级和括号的迷你计算器已经完成了。测试一下text 2 3 * (4 - 1) tokens tokenize(text) parser Parser(tokens) ast parser.parse_expr() print(evaluate(ast)) # 输出 11.0在代码里对应一下3 * (4 - 1)被构造在term层2 被构造在expr层所以计算顺序完全正确。这就是 BNF 分层定义的功劳。7.6 代码里的隐藏细节上面代码有个地方特别值得注意parse_expr里循环while self.peek()[0] in (PLUS, MINUS)。这对应 EBNF 的{ ... }实现的是“零个或多个”的重复。但为什么不是if因为expr后面可能没有加减运算符这时候应该直接结束返回。用循环是正确处理“零次”的唯一方式。还有一个工程细节由于我们处理的是左结合运算符每次循环里都立刻把新节点作为左子树再读入右侧项。也就是node (BinOp, op, node, right)。如果把左右反过来写就变成右结合了。这个位置上的选择正好呼应了第 5 节讲的“递归位置决定结合性”的工程落地。8. 常见问题速查与现实工程里的坑8.1 一张表记住高频问题结合我带过的人和项目里的真实体验把 BNF 相关最常见的求助问题整理如下现象原因解决办法解析器爆栈RecursionError文法存在直接左递归改写文法或采用循环 递归下降写法解析正确性时好时坏文法二义性多棵语法树消除二义性分层、提取左公因子、调整结合性表达式优先级不对分层不够优先级高层被放到了内层检查是否“优先级越高的运算符对应非终结符越接近原子的终结符层”回溯爆炸性能极差同一非终结符多条产生式有公共前缀提取左公因子确保 LL(1) 性空串导致死循环ε 产生式使用不当检查产生式是否出现“能推导出 ε 的非终结符无限展开”8.2 现实工程你其实不一定要手写 BNF 解析器如果你在做的是公司项目而不是练习玩具你有更省力的选择直接用现成的解析器生成器比如 ANTLR、flex/bison、JavaCC、PLY、Lark 等。它们的共同逻辑是你写一套接近 EBNF 的语法文件工具自动生成解析器代码。用 ANTLR 写表达式的一个片段大概是expr : term (( | - ) term)* ; term : factor (( * | / ) factor)* ; factor : NUMBER | ( expr ) ;这几乎就是把第 5 节那道 EBNF 直接搬进工程。所以把 BNF/EBNF 学扎实绝不只是在啃理论它直接影响到你能否顺畅使用这些工业级工具。我个人的建议是作为学习一定要手写一次递归下降解析器。因为解析器生成器会把你和底层的机制隔离导致你永远没有机会真正体会“非终结符函数调用”“终结符Token 匹配”这个和谐对应关系。一旦手写过再看任何语法文件都会有“原来代码里就是这么跑的”这种通透感。8.3 一些你必须亲测的边界用例这里给出几个我在测试自己写的解析器时必测的边界输入大家可以对照跑一跑3单数字能不能正常解析(1)多层括号嵌套能不能退栈干净12*3优先级是否正确1*23优先级分层反了过来是否正确8/4/2左结合性如何会不会算成8/(4/2) 1 2 前后空格能否跳过空串是报错还是静默通过1结尾缺操作数错误信息是否清晰我见过不少人解析器写出来测简单的12没问题一跑8/4/2就露馅算成了4就是因为结合性写反了。这些测试用例几乎可以在不跑代码的情况下提前帮你发现八成问题。9. 延伸从 BNF 到形式语言再到真正的编译器前端9.1 BNF 只是一种描述工具不是算法很多人容易把 BNF 和“解析算法”混为一谈。这里想帮你厘清一个重要的层次BNF/EBNF 是问题定义层它负责说明“什么句子是合法的”。递归下降、LL、LR、Pratt Parsing 等是问题求解层它负责“如何高效判断并构造语法树”。二者不能互相替代但必须配套使用。你给 BNF 却没有算法机器还是一头雾水你有算法却没有 BNF代码会变成无人能维护的黑魔法。9.2 BNF 在学习路径中的位置如果你刚踏入编译原理一个合理的路径是先熟练阅读和手写 BNF/EBNF掌握推导、语法树、结合性、递归。再学词法分析理解终结符如何由正则表达式产生 Token。然后学 LL(1)、LR(1) 等解析算法明白机器如何从输入字符串一步步归约或推导。紧接着走上语法树之后的语义分析类型检查、作用域解析、中间代码生成。最后再回到代码生成和理解运行时机制。可以看到BNF 是整个技术栈的地基但它不是全部。地基打牢后上层建筑才有得谈。9.3 关于“要不要背文法”有读者可能问“我需要把每种文法的写法背下来吗”我的答案是不需要也不太可能背得完。真正值得花时间的是掌握“文法设计通用原则”永远让优先级高的运算符出现在内层左结合用左侧递归或循环右结合用右侧递归不要给同一个非终结符写下多个公共前缀的产生式不要让同一个句子产生两棵语法树尽可能让解析器只看一个 Token 就能决定走向。这几条揣在脑子里比记住任何 N 行语法模板都管用。实际面对任何新的编程语言或 DSL 时你可以在不了解完整文档的情况下仅凭一小段样例和这些原则快速反推出大部分文法结构——我把这个方法叫“与语言作者对弈”。很多开源项目的语法文件读起来就是这种感觉通过 BNF 去理解设计者的意图和权衡比直接看实现代码还要高效。10. 最后想跟你分享的实操体会BNF 这个东西初看是符号游戏但它是连接“人如何表达语法”与“机器如何解析语法”的桥梁。我个人的体会是与其把 BNF 当成一门需要背的学问不如把它当成一门需要写的技艺。每当你需要在项目里引入一个小的配置文件格式、一套规则引擎或者一门迷你查询语言试着先用铅笔在纸上画一遍 EBNF你会发现后续写解析器、写文档、和同事沟通都会顺畅很多。踩过几次坑之后我现在写任何语法文件都会带上三样东西一是从一开始就注意避免左递归和公共前缀二是永远保留一份“语法速查表”三是设计好报错信息让它能指出“我在解析哪个非终结符时发现哪个 Token 不匹配”。后一点的重要性在你调试复杂嵌套表达式时会被放大十倍。这个内容后续还可以这样扩展把上面那个玩具计算器加上变量支持、加赋值语句、加函数调用你就会一步步碰到“符号表”“作用域”这些真正编译器设计问题。到那时候再回头看 BNF你会发现当初学的所有东西都在后台帮你兜底。