1. 从“正则不够用”说起为什么需要上下文无关语言很多人学计算理论时第一个真正感到“卡住”的地方不是图灵机也不是可计算性而是上下文无关语言。原因很简单前面刚学完正则语言和有限自动机感觉一切都挺直观——状态跳来跳去能识别就识别不能识别就拉倒。结果一遇到“括号匹配”“嵌套结构”“表达式求值”这类问题正则语言立刻露怯。我举个最经典的例子判断一个字符串里的左右括号是否配对。比如(()())是合法的(()是不合法的。你可能会想这有什么难但如果你只能用有限状态机来做就会发现一个致命问题有限状态机没有“计数”能力。它不知道当前已经遇到了多少个左括号因此无法判断右括号是否够用。你可以为“最多嵌套3层”写一个自动机但题目要求的是任意嵌套深度有限状态机就彻底没辙了。这就是上下文无关语言登场的时刻。它比正则语言强强在它能处理递归嵌套结构。而递归嵌套恰恰是编程语言、配置文件、数学表达式、自然语言句法里无处不在的东西。你写的每一行代码背后几乎都有一棵语法树而描述这棵语法树的文法通常就是上下文无关文法。所以这一篇我想把上下文无关语言的核心脉络讲清楚它到底解决什么问题文法长什么样推导和语法树怎么玩歧义性为什么让人头疼以及它和自动机、下推栈之间的对应关系。如果你正在学计算理论、编译原理或者单纯想搞明白“为什么正则表达式不能解析HTML”这篇应该能帮你把思路理顺。2. 上下文无关文法的四元组把“规则”写成数学2.1 文法不是语法书而是一套替换规则很多人第一次看到“上下文无关文法”这个词会以为它是一本讲语法的书。其实不是。它是一套形式化的替换规则用来生成或识别某个语言中的所有字符串。你可以把它想象成一种“字符串生产流水线”从起始符号出发不断把非终结符替换成右边的串直到只剩下终结符为止。一个上下文无关文法CFG由四部分组成终结符集合最终字符串里出现的字符比如a、b、(、)、if、while。非终结符集合中间变量用来表示“还没展开完的结构”比如S、E、T、F。产生式集合形如A → α的规则左边必须是一个非终结符右边可以是任意终结符和非终结符的串。起始符号整个推导的出发点通常记作S。关键点在于“上下文无关”这四个字。它指的是产生式左边永远只有一个非终结符不需要关心这个非终结符左右两边出现了什么。也就是说只要看到A你就可以把它替换成α不管A周围是什么。这种“局部替换”的特性让文法分析变得相对可控也让下推自动机的设计成为可能。对比一下上下文有关文法它的产生式可能是αAβ → αγβ意思是只有在A左边是α、右边是β的时候才能把A替换成γ。这就麻烦多了因为替换不再局部必须看上下文。上下文无关语言之所以成为编译原理的基石正是因为它卡在了一个“表达能力够用、分析效率可接受”的甜蜜点上。2.2 一个文法到底怎么“生成”字符串光看定义容易发懵我们直接上手推一个。假设有这样一个文法S → (S) | ε终结符是(和)非终结符只有S起始符号是S。这条规则的意思是一个S要么是左括号加S加右括号要么是空串。现在我想生成(())。推导过程是这样的S ⇒ (S) ⇒ ((S)) ⇒ (())每一步都是把当前的S替换成(S)最后把最里面的S替换成ε得到(())。如果你想要()()那就需要另一条文法比如S → SS | (S) | ε。这条文法能生成所有括号匹配的串包括并列和嵌套。这里有个很实用的理解方式文法规则就是“结构模板”。S → (S)告诉你一个合法的括号结构可以是在一对括号里再套一个合法结构。S → SS告诉你两个合法结构并排放在一起还是合法结构。这种递归定义正是上下文无关文法的灵魂。2.3 推导、句型与句子别被术语吓到在形式语言里有几个术语经常把人绕晕推导、句型、句子、语言。我用大白话翻译一下。推导从起始符号开始一步步应用产生式得到中间串的过程。句型推导过程中出现的任何串允许含有非终结符。句子只含终结符的句型也就是最终生成出来的字符串。语言所有能从起始符号推导出来的句子的集合。举个例子文法S → aSb | ε。推导S ⇒ aSb ⇒ aaSbb ⇒ aabb。其中aSb、aaSbb都是句型aabb是句子。这个文法生成的语言是{a^n b^n | n ≥ 0}也就是若干个a后面跟着同样数量的b。这个语言是经典的“非正则”语言。用泵引理可以证明它不能被有限自动机识别但用上下文无关文法一条规则就搞定了。这就是上下文无关语言的价值用递归规则描述计数和嵌套。3. 语法树与推导策略同一句话的两种“看法”3.1 语法树把推导过程“拍平”了推导是一步一步的替换语法树则是把这种替换关系画成一棵树。根节点是起始符号每个内部节点是一个非终结符它的子节点就是该非终结符被替换后得到的符号串。叶子节点从左到右读出来就是最终生成的句子。还是用S → aSb | ε生成aabb。语法树是这样的S /|\ a S b /|\ a S b | ε这棵树非常直观地展示了嵌套结构外层a...b包着内层a...b内层再包着空串。语法树在编译原理里就是抽象语法树AST的雏形。你写编译器时解析器干的事就是把 token 流变成这样一棵树然后语义分析、代码生成都在这棵树上做文章。3.2 最左推导与最右推导解析器的两种口味同一棵语法树可以对应多种推导顺序。如果每次总是替换当前句型里最左边的非终结符叫最左推导总是替换最右边的叫最右推导。拿文法E → E E | E * E | (E) | id举例生成id id * id。最左推导可能是E ⇒ E E ⇒ id E ⇒ id E * E ⇒ id id * E ⇒ id id * id最右推导可能是E ⇒ E E ⇒ E E * E ⇒ E E * id ⇒ E id * id ⇒ id id * id这两种推导对应不同的解析策略。自顶向下的解析器比如递归下降通常模拟最左推导自底向上的解析器比如 LR 分析器通常对应最右推导的逆过程。理解这一点对后面学 LL 和 LR 分析非常有帮助。3.3 语法树不关心顺序只关心结构这里有一个容易被忽略的点语法树和推导顺序无关。只要最终生成的句子一样并且每一步替换的非终结符位置不同它们可能对应同一棵语法树。真正重要的是树的结构因为它决定了语义。比如表达式id id * id如果语法树是在根、*在子树那先算乘法再算加法如果*在根、在子树那就先算加法再算乘法。结果完全不同。所以语法树不是“画着玩”的它是语义的载体。4. 歧义性同一个句子两棵语法树4.1 歧义不是“意思多”而是“结构多”一个上下文无关文法如果是歧义的意味着存在至少一个句子它有两棵不同的语法树。注意是语法树不同不是推导顺序不同。推导顺序不同但语法树相同那不算歧义。最经典的歧义例子就是表达式文法E → E E | E * E | (E) | id对于id id * id它可以解析成(id id) * id也可以解析成id (id * id)。这两棵语法树结构不同所以这个文法是歧义的。歧义在编程语言里是灾难。如果编译器对同一个表达式有两种理解那程序行为就不可预测了。所以实际语言设计里要么通过优先级和结合性规则消除歧义要么直接改写文法让它天生无歧义。4.2 改写文法消除歧义分层法消除表达式歧义的常用手段是分层。把表达式分成多个层级最外层是加减里面是乘除再里面是括号和原子。文法写成E → E T | T T → T * F | F F → (E) | id这样一来*的优先级高于因为T必须先归约成F才能参与加法。id id * id只有唯一一棵语法树乘法在更深的层次先结合。这个技巧在编译原理里叫“消除左递归”和“提取公因子”的配套操作实际写递归下降解析器时天天用。4.3 歧义不可判定这是理论给我们的警告有一个很重要的理论结果上下文无关文法的歧义性是不可判定的。也就是说不存在一个通用算法能对任意 CFG 判断它是否有歧义。你只能针对特定文法去分析或者用一些充分条件来保证无歧义。这个结论听起来有点丧但它其实在提醒我们不要指望“自动消除歧义”这种银弹。实际工程里语言设计者必须手动设计无歧义的文法或者用解析器生成器时小心处理冲突。Yacc/Bison 里的 shift/reduce 冲突本质上就是歧义或文法不够强导致的。5. 下推自动机上下文无关语言的“机器模型”5.1 有限自动机差在哪没有栈正则语言对应有限自动机上下文无关语言对应下推自动机。下推自动机和有限自动机最大的区别就是多了一个栈。栈是后进先出的可以无限增长这就给了机器“计数”和“记忆嵌套”的能力。你可以这样理解有限自动机像一个只有当前状态的人过去的事全忘了下推自动机像一个带着一摞便签纸的人每读一个字符可以往栈顶压一张便签也可以弹出一张便签来看。栈里存的就是“还没匹配完的结构”。5.2 下推自动机的两种接受方式下推自动机有两种接受字符串的方式终态接受读完输入后机器处于某个接受状态栈里剩什么无所谓。空栈接受读完输入后栈恰好为空状态无所谓。这两种方式在能力上是等价的。也就是说任何终态接受的下推自动机都能改造成空栈接受的反过来也一样。这个结论在证明“CFG 与 PDA 等价”时会用到。5.3 从文法到自动机非确定性是必须的给定一个 CFG可以机械地构造一个下推自动机来识别它。基本思路是自动机先把起始符号压栈然后每次栈顶是非终结符时就非确定性地选择一条产生式把栈顶替换成产生式右部如果栈顶是终结符就和输入字符匹配匹配成功就弹出。注意这里的关键词非确定性。下推自动机天生就是非确定的因为同一个非终结符可能有多条产生式自动机需要“猜”用哪一条。确定下推自动机DPDA只能识别上下文无关语言的一个真子集叫确定上下文无关语言。编程语言的语法通常要求是确定的所以实际编译器用的都是确定性分析技术比如 LL 和 LR。6. 泵引理与封闭性上下文无关语言的边界6.1 泵引理证明“不是上下文无关”的武器和正则语言一样上下文无关语言也有泵引理。它的直观意思是如果一个上下文无关语言包含足够长的字符串那么这个字符串里一定有一部分可以“泵”起来——重复任意次得到的字符串仍然属于该语言。形式化地说存在一个泵长度p对于语言中长度不小于p的字符串s可以把它分成五部分s uvxyz满足|vy| ≥ 1也就是v和y不能同时为空|vxy| ≤ p对所有i ≥ 0uv^i xy^i z仍然属于该语言。用这个引理可以证明{a^n b^n c^n | n ≥ 0}不是上下文无关语言。直观理解是下推自动机只有一个栈没法同时记住a的数量和b的数量再去和c比较。一个栈只能做“后进先出”的匹配处理不了三个符号的等量关系。6.2 封闭性并、连接、星号封闭交、补不封闭上下文无关语言在一些运算下是封闭的并两个 CFG 的语言并起来还是 CFG。把两个起始符号合到一个新的起始符号加两条产生式即可。连接两个 CFG 的语言连接起来还是 CFG。新起始符号产生两个旧起始符号的拼接。星号一个 CFG 的语言的 Kleene 星还是 CFG。新起始符号产生S S或ε。同态对终结符做替换保持 CFG 性质。但它在交和补下不封闭。两个上下文无关语言的交集可能不是上下文无关的。经典反例是{a^n b^n c^m}和{a^m b^n c^n}它们各自是 CFG但交集是{a^n b^n c^n}不是 CFG。补运算也不封闭因为如果补封闭结合并封闭就能推出交封闭矛盾。这个封闭性表在考试和实际判断中非常有用。遇到一个语言先看它能不能通过封闭运算从已知 CFG 构造出来能就说明是 CFG不能就考虑用泵引理证明不是。7. 实际应用从编译器到配置文件解析7.1 编程语言语法几乎都是 CFG你写的每一门编程语言它的语法规范几乎都是用上下文无关文法描述的。比如 Java、C、Python 的语法手册里那些ifStatement → if ( Expression ) Statement之类的规则就是 CFG 产生式。编译器前端的工作流程是词法分析把字符流变成 token 流语法分析把 token 流变成语法树。语法分析器要判断 token 流是否符合文法并构造语法树。LL 解析器自顶向下LR 解析器自底向上它们都依赖 CFG 的结构。7.2 配置文件与数据格式JSON、XML、YAML 这些数据格式它们的语法也常用 CFG 描述。JSON 的嵌套对象和数组天然就是递归结构。用 CFG 可以精确描述“对象里可以嵌套对象数组里可以嵌套数组”这种规则。不过实际解析时很多人会用正则表达式去“凑合”解析 JSON结果遇到嵌套就崩了。原因就是正则语言处理不了递归嵌套。这个坑我在实际项目里见过不止一次有人用正则去匹配 HTML 标签简单页面还能跑一遇到嵌套 div 就彻底乱套。正确的做法是用 CFG 驱动的解析器或者至少用支持递归下降的解析库。7.3 自然语言处理中的句法分析在自然语言处理里上下文无关文法也被用来描述句子的句法结构。比如“主语 谓语 宾语”这种规则可以用 CFG 表示。虽然自然语言比编程语言歧义多得多但 CFG 仍然是句法分析的基础模型之一。概率上下文无关文法PCFG给每条产生式加上概率用来在多个语法树中选最可能的那个。8. 学习路径与常见误区8.1 先动手推几个文法再去看自动机我自己的学习经验是不要一上来就啃下推自动机的形式定义那样很容易被状态转移函数绕晕。先找几个简单语言手动写 CFG手动推导几个句子画语法树。比如{a^n b^n | n ≥ 0}S → aSb | ε回文串S → aSa | bSb | a | b | ε平衡括号S → SS | (S) | ε推上十几个例子之后你对“递归嵌套”会有肌肉记忆。这时候再去看下推自动机就会发现它不过是把“推导”变成了“栈操作”本质是一回事。8.2 不要混淆“文法歧义”和“语言歧义”一个语言可能是固有歧义的意思是所有生成该语言的 CFG 都是歧义的。这种语言叫固有歧义语言。而一个文法有歧义不代表语言本身有歧义可能换一个文法就无歧义了。考试里经常考这个区分实际工作中也要注意解析器报冲突先看看是不是文法写得太随意而不是语言本身有问题。8.3 泵引理用错方向是常见错误泵引理只能用来证明“不是 CFG”不能用来证明“是 CFG”。很多人试图用泵引理证明某个语言是上下文无关的这是逻辑错误。要证明是 CFG正确做法是直接构造一个 CFG或者用封闭性从已知 CFG 推导出来。另外泵引理里的p是存在性的你不能自己选一个p然后说“对任意分割都不行”。正确用法是假设语言是 CFG那么存在泵长度p然后你选择一个长度不小于p的字符串s接着对所有满足条件的分割uvxyz证明存在某个i使得uv^i xy^i z不在语言中。这个逻辑顺序不能乱。8.4 下推自动机的非确定性不是缺陷刚开始学 PDA 时很多人觉得“非确定性”很别扭总想把它改成确定的。但非确定性是 PDA 的本质特征之一。确定下推自动机识别不了所有上下文无关语言这是理论上的硬限制。实际编译器里用的 LL 和 LR 是确定性的分析技术它们处理的文法类LL(k)、LR(k)是 CFG 的真子集。所以如果你发现某个文法用递归下降写不出来不一定是你的问题可能是文法本身不适合确定分析。9. 一个完整的推导实例从文法到语法树再到分析为了把前面的概念串起来我们完整走一遍。假设要描述“算术表达式”文法如下E → E T | T T → T * F | F F → (E) | id输入串是id id * id。我们做最右推导E ⇒ E T ⇒ E T * F ⇒ E T * id ⇒ E F * id ⇒ E id * id ⇒ T id * id ⇒ F id * id ⇒ id id * id对应的语法树根节点是E左子节点是E右子节点是T。左E最终展开成id右T展开成T * F其中T是idF是id。这棵树明确表示乘法先于加法结合。如果用 LR 分析器它会维护一个栈读入id时移进遇到可归约的句柄就归约。比如读到id id时栈里可能是E T然后看到*因为*优先级高于所以不归约E T而是继续移进*和后面的id先把T * F归约成T再把E T归约成E。这个“移进-归约”的决策就是 LR 分析表的核心。理解了这个过程你再看 Yacc/Bison 的语法文件就不会觉得那些%left、%right声明是魔法了。它们就是在告诉解析器遇到冲突时按优先级和结合性决定是移进还是归约。10. 最后聊几句实在的上下文无关语言这一块理论性确实强但它离实际工程并不远。你写的每一行代码被编译器解析你用的每一个 JSON 配置文件被程序读取背后都有 CFG 的影子。学的时候不要只盯着形式定义多动手写几个文法多画几棵语法树多想想“这个结构为什么正则搞不定”。把递归嵌套这个核心概念吃透后面学 LL、LR、语法分析器生成器都会顺很多。我在实际带新人的时候发现那些能自己手写一个简单表达式解析器的人对 CFG 的理解通常比只做题的人深得多。所以如果你有时间不妨找一个周末用递归下降写一个支持加减乘除和括号的计算器。写完之后你对上下文无关语言的感觉会完全不一样。