先说一个上周发生的事。有朋友写了个简单的表达式计算器输35*2他第一版代码从左到右扫遇到加号相加、遇到乘号相乘结果算出16而不是13。问题不在于他不知道乘除法优先而在于程序里缺少一种规则来描述什么样的字符序列才算合法的算术表达式。这类规则就是上下文无关文法CFG。CFG是计算机科学里最基础也最容易被低估的工具之一编译器、解释器、JSON解析器、配置文件解析器底层都在用这套东西。这篇文章不打算照本宣科讲形式语言理论而是从实际写代码的角度把CFG拆开揉碎讲清楚它是什么、怎么写、怎么落地成解析器以及在实际项目里它到底能帮我们解决什么问题。适合正在学编译原理的学生、写过一点解析逻辑的程序员以及所有想知道为什么正则表达式解析不了HTML这类问题答案的人。1. 先搞清楚CFG到底在描述什么1.1 四个组成部分从做菜说起形式语言理论里CFG的定义是一个四元组G (V, T, P, S)。V是非终结符集合T是终结符集合P是产生式规则集合S是开始符号。这四个概念不用背用做菜来类比一下就通透了。终结符T原材料比如西红柿、鸡蛋、盐。在文法里终结符就是最终出现在字符串里的最小单元对程序来说就是数字、加号、括号这类token。非终结符V半成品比如一盘西红柿炒鸡蛋。它不直接出现在最终字符串里但它是构建过程中的中间状态。产生式P菜谱步骤比如西红柿炒鸡蛋 → 切西红柿 打鸡蛋 翻炒。它规定了一个非终结符可以怎么被替换成别的东西。开始符号S整桌菜的起点从它开始按照菜谱一步步加工最终得到成品。做菜是从原料开始往上做成菜而解析字符串是反过来从一个完整的字符串出发尝试用产生式一步步归约回开始符号。比如你看到字符串35*2要证明它是不是一个合法的算术表达式就要从这个字符串倒推看它能不能通过产生式一步步约回到expr这个开始符号。这个过程本质上是给字符串做身份认证。需要注意的是这套理论本身不关心35*2算出来是多少它只关心这个字符串结构上合不合法。求值是在确认结构合法之后另外加的一层动作。这个区分很重要很多人一开始会把文法和计算逻辑混在一起后面会讲区别。1.2 上下文无关这四个字怎么理解这是CFG名字里最劝退的部分其实拆开就一句话产生式左边只有一个非终结符替换它的时候不需要看这个非终结符出现在句子的什么位置、旁边跟着谁。比如产生式 expr → expr term意思就是只要遇到expr不管它左边是括号还是数字右边是加号还是乘号都照这条规则替换。规则本身对周围环境完全不敏感这就是上下文无关的意思。对比一下自然语言。中文里我去学校和他去学校动词去不随主语变化但英语里He goes to school和I go to school动词会随主语人称变化。这种情况下替换go的时候得知道主语是he还是I也就是上下文有关。编程语言的语法层面基本上不需要这种跨符号约束所以CFG就足够用了。这对我们写代码的人有个实际好处解析时看一个token只需要看它本身和当前正在处理的非终结符不需要扫一遍全局上下文。这让手写解析器成为可能否则光是状态同步就够让人崩溃了。2. 动手写文法从0到1搭一个表达式文法2.1 先罗列字符再抽象语法成分理论说完了直接上手。假设我要设计一个支持加减乘除和小括号的算术表达式语言第一步不是写代码而是先列两样东西终结符集合数字、、-、*、/、(、)。这些都是token层面的东西空格和换行属于词法层的噪音不属于文法范围。非终结符集合expr表达式、term项、factor因子。为什么需要三层因为运算符优先级本质上要靠分层来实现。优先级规则是这样的先算括号再算乘除最后算加减。对应到文法里优先级越高它在推导树里越靠下。所以最底层是factor因子只能是一个数字或者一个带括号的表达式往上一层是term项由因子通过乘除连接而成再往上是expr表达式由项通过加减连接而成。很多初学者直接写 expr → expr expr | expr * expr | (expr) | num 这样一条规则看似省事但这样写有两个致命问题一是优先级完全没体现乘除和加减混在一起二是文法会产生二义性。比如123既可以先算12再乘3也可以先算23再加1同一个字符串对应两棵不同的推导树。所以优先级必须靠分层解决不存在捷径。2.2 产生式的细节设计基于上面的分层思路完整的表达式文法可以写成这样expr → expr term | expr - term | term term → term * factor | term / factor | factor factor → ( expr ) | number number → [0-9]这里的 | 表示或者number用正则风格的[0-9]只是为了说明方便实际词法分析阶段会把连续数字拼成一个token。注意观察expr和term这两条规则都是左边那个非终结符在箭头右边又出现在最左边这叫直接左递归。理论上左递归对应的是左结合运算也就是345要先算左边的34再5这正好符合加减乘除的运算规则。但左递归对另一种常用解析方法——递归下降解析——是致命的因为解析expr时第一步调用解析expr不消耗任何token就陷入无限递归。所以实际写解析代码时通常不会直接照搬这条左递归文法而是用迭代循环来处理同层级的运算符既绕开左递归又保住左结合。后面第三部分会给出完整代码。这里先记住一个结论文法设计时关注优先级和结合性实现时用循环代替左递归。2.3 优先级与括号的处理逻辑用这套文法手动推导一下58*2看看优先级是怎么被逼出来的从expr开始匹配58*2最外层是 expr term。expr的左部解析5直到它成为expr的一部分。遇到号进入右部term的解析。term的解析规则要求先解析factor。8是一个有效的factor但后面跟着*号所以term的规则继续term * factor再次factor匹配2。所以8*2被完整包在term里而term只是expr右侧的一个部分。整个推导树里82的层级比58更深因此求值时必然是82先算。这就是优先级在文法里的体现被包得越深的东西先被计算。括号的处理也是同一个逻辑。factor → ( expr ) 的意思是把一对括号里的整个表达式提升为一个因子。因为因子是最高优先级的单元所以(34)*2里34先被整体算成一个因子再参与乘法的计算。本质上括号是人为把一段表达式的层级提升了一层。3. 把文法变成能跑的解析器3.1 先分词再解析解析流程通常分成两阶段词法分析和语法分析。词法分析把原始字符串切成token序列语法分析按照文法把token序列组装成结构。为什么要拆开因为CFG里的终结符本质上是token不在语法分析阶段处理字符和空格可以让文法描述更干净。用Python写一个极简分词器import re def tokenize(text): pattern re.compile(r\s*(\d|[()\-*/])) tokens [] pos 0 while pos len(text): m pattern.match(text, pos) if not m: raise SyntaxError(f无法识别的字符: {text[pos]}) token m.group(1) if token.isdigit(): tokens.append((num, token)) else: tokens.append((op, token)) pos m.end() return tokens这个分词器把3 5 * 2切成了 [(num,3), (op,), (num,5), (op,*), (num,2)] 这样的序列。模式里的\s*负责吃掉空格所以用户怎么写空格都无所谓。3.2 手写递归下降解析器分词之后按照文法写递归下降解析器。核心思路每个非终结符对应一个函数函数内部根据当前看到的token决定走哪条分支。前面提过左递归问题所以代码里用while循环处理同一层级的运算符而不是直接递归。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): if self.pos len(self.tokens): return self.tokens[self.pos] return (None, None) def consume(self): token self.peek() self.pos 1 return token def parse_expression(self): left self.parse_term() while self.peek()[1] in (, -): op self.consume()[1] right self.parse_term() if op : left left right else: left left - right return left def parse_term(self): left self.parse_factor() while self.peek()[1] in (*, /): op self.consume()[1] right self.parse_factor() if op *: left left * right else: left left / right return left def parse_factor(self): token_type, value self.peek() if token_type num: self.consume() return float(value) if value (: self.consume() result self.parse_expression() if self.peek()[1] ! ): raise SyntaxError(缺少右括号) self.consume() return result raise SyntaxError(f意外的 token: {value})仔细看parse_expression里先解析一个term作为左操作数然后循环看后面是不是或-如果是就再解析右边的term。因为循环是从左往右处理的3-4-5会先算3-4再减5天然是左结合这就是绕过左递归保留结合性的标准手法。最后的调用入口def evaluate(expression): tokens tokenize(expression) parser Parser(tokens) result parser.parse_expression() if parser.peek()[1] is not None: raise SyntaxError(表达式结束后还有多余内容) return result print(evaluate(35*2)) # 13.0 print(evaluate((35)*2)) # 16.0最后那个检查很重要。解析完一个expr后如果token流还没到末尾说明这个字符串不是合法的表达式比如35)parse_expression解析完35后还剩一个右括号这时候必须报错不能静默通过。3.3 从解析结果到抽象语法树上面的解析器直接求值了但很多场景下你并不只是想算个结果你还想拿到结构做进一步处理。比如写一个编译器你需要知道35*2里哪个节点是加法、哪个节点是乘法、谁是谁的子节点这就是抽象语法树AST。改造起来很简单把直接计算的部分改成构造节点。class Number: def __init__(self, value): self.value value class BinaryOp: def __init__(self, op, left, right): self.op op self.left left self.right rightparse_factor遇到数字时返回Number节点parse_term和parse_expression遇到运算符时返回BinaryOp节点。这样35*2的AST结构大致是BinaryOp() / \ Number(3) BinaryOp(*) / \ Number(5) Number(2)而(35)*2的AST结构是BinaryOp(*) / \ BinaryOp() Number(2) / \ Number(3) Number(5)两个字符串结构完全不同文法分层在树上一目了然。有了AST你可以做代码生成、静态分析、自动格式化、代码补全这些都是后续工作了。4. 实际案例与应用场景CFG的威力4.1 用CFG理解为什么正则表达式解析不了HTML社区里流传一句话当你用正则表达式解析HTML时问题就会多一个。这句话背后的理论依据正是CFG和正则语言的能力边界差异。正则表达式描述的是正则语言本质上由有限状态自动机识别。有限状态自动机只有有限个状态它无法记录当前嵌套深度这种无限增长的信息。但HTML和XML的标签是嵌套的一个div里套一个div再套一个div深度可以是任意的。要验证这种结构的合法性你至少需要能表示递归的文法也就是CFG。看一个最经典的嵌套结构括号匹配。文法就两条规则S → ( S ) S S → εε表示空串。这个文法可以生成()、()()、(())、(()())等所有括号正确匹配的字符串。正则表达式描述不了这个语言因为你无法用有限状态机处理任意深度。同理HTML的标签嵌套本质上也是这种结构所以正则解析必然会漏。这不是说正则没用而是说要选对工具。能匹配的内容用正则使需要嵌套、递归、结构验证的内容交给CFG。4.2 案例手写一个简易JSON解析器JSON是大家最熟悉的格式它的结构完全可以用CFG描述清楚。简化版的JSON文法json → value value → object | array | string | number | true | false | null object → { } | { pair (, pair)* } pair → string : value array → [ ] | [ value (, value)* ]这里的*是为了方便阅读引入的扩展写法表示零个或多个。严格的标准CFG需要把这种重复展开成递归但思想上没区别。对照这份文法写解析器时逻辑会非常清晰。parse_value函数看一眼当前token的类型如果是{就进入parse_object如果是[就进入parse_array如果是就进入parse_string数字就走parse_number。每一种类型的解析逻辑都可以单独写一个函数互不干扰。这个案例里有价值的点在于文法实际上是解析器的设计图。你不需要把所有的if-else堆在脑子里先把文法写出来代码不过是把文法逐条翻译成函数和控制流。我从接触CFG开始解析任何格式都先写文法这个习惯帮我省了无数调试时间。4.3 影响范围CFG无处不在除了计算器和JSONCFG在真实开发场景里的应用面非常广。编译器前端几乎所有编程语言的语法都靠CFG描述。词法分析器生成token流语法分析器按文法构建AST。IDE工具链语法高亮、代码折叠、重构、自动补全都依赖对代码结构的完整解析背后都有文法在支撑。数据库SQL解析器要把文本查询转成执行计划SQL的语法规则同样是CFG。前端工程化JSX、Vue模板、CSS预处理器都在做语法层面的解析和转换。数据交换格式除了JSONYAML、TOML、Protocol Buffers的文本表示层都有明确的文法定义。自然语言处理句法分析里的短语结构文法跟CFG在形式上高度同源。模糊测试需要根据文法生成大量语法正确但内容随机的输入用来测试解析器的健壮性。你会发现凡是涉及文本转结构的场景基本都有CFG的影子。学CFG最核心的价值不是背定义而是获得一种先用规则描述语言再动手写代码的思维模式。有了这个思维你在处理任何格式时会少踩很多坑。5. 常见问题与排查技巧实录5.1 问题速查表在实际写解析器的过程中我遇到过不少问题整理成一张速查表方便你对照排查。症状典型原因解决方案解析器一运行就栈溢出递归下降解析器遇到未改写的左递归把左递归改成循环或用右递归文法同一个字符串得到多种解析结果文法存在二义性增加优先级分层或明确结合规则合法输入却报错文法覆盖范围不够缺少某条产生式补充产生式检查分支是否完整非法输入却通过了解析结束后没检查剩余token或文法过宽在入口处检查token流是否已消费完括号不匹配还继续解析缺少对右括号的显式检查parse_factor里遇到)必须报错优先级算错没有分层所有运算符放在同一层按优先级拆分成expr/term/factor多层5.2 排查思路写解析器时最容易遇到的是错误定位难。几年前我写过一个简单的脚本语言解析器遇到一次诡异的问题合法的if语句能过去但if后面多一个分号就崩。排查了大半天最后发现是词法阶段的分号处理漏了在语法分析阶段才暴露。我的经验是解析器报错时先把token列表打印出来。看报错位置附近还剩哪些token再对照当前正在解析的非终结符判断是文法规则缺失还是代码逻辑跳错分支。比如递归下降解析器里parse_factor里抛出意外的token你就要看当前token是什么如果是一个*号那说明调用方根本没有调用parse_term问题在上层而不是factor。另一个我常用的技巧是推导演练。写完一份文法后拿一个合法输入和一个非法输入在纸上或文本里手动推一遍完整的解析过程。不要嫌麻烦这能提前发现大量文法设计缺陷比你后来调试代码要省时间得多。5.3 三个绕不开的避坑心得第一不要一开始就用复杂的解析器生成器。ANTLR这样的工具很强大但如果你不懂文法原理生成的代码表现不符合预期时你根本不知道从哪查起。我建议先手写一两个递归下降解析器把CFG的语法、优先级、左递归、结合性这些核心概念吃透再去用工具否则容易浮在表面。第二非终结符命名用描述性的名字不要用单字母。刚开始学CFG时喜欢用E、T、F这种简写因为在理论教材里简洁。但实际项目里文法文件就是你的设计文档expression、term、factor、statement、declaration这样的名字一个月后回来看还能一眼看懂单字母就得从头推。第三解析结束时的收尾检查不能省。很多人写完parse_expression就以为万事大吉忘了检查token流是否已经到末尾。我见过不少解析器的bug都是这个原因非法输入的前半段长得像合法输入于是被静默接受直到后续逻辑才爆出莫名其妙的错误。入口处加一个peek() is None的判断能挡掉一大类问题。有一点补充。手写文法时如果某个产生式的分支特别多比如一个statement可能有十几种不同写法这说明你的非终结符划分可能太粗了。试着把不同类型的语句拆成更细的非终结符比如if_statement、while_statement、assignment_statement每个的解析逻辑单独维护整体清晰度和可测性会好很多。我自己最早接触CFG也是在大学编译原理课上当时只觉得这是考试要背的抽象概念。直到工作后有次做配置解析和表达式求值的需求才意识到这套理论的价值。现在遇到任何带格式的文本我的第一反应都是先写一段文法描述再动手写代码。建议你也试试拿一个天天在用的JSON配置或者SQL查询手写一份它的简化文法不用多复杂写完你对解析的理解会完全不一样。
