（来源：图灵人工智能）

一、压缩的核心问题

1.1 什么是语言压缩？

当我们说"语言是一种压缩"时，这意味着什么？让我们从信息论的角度理解。

想象一个场景：你需要记录世界上所有合法的句子。如果不借助任何规则，你必须穷举每一个句子——这将是无限长的清单，永远无法完成。但人类语言并非无限混乱：它遵循规律。这些规律，就是语法；而语法本身，就是一种压缩机制。

压缩的本质，是用有限的规则描述无限的可能。一条语法规则可以生成无数个合法句子。比如"S → NP VP"这条规则，配合其他规则，可以生成"The dog sees a cat"、"A bird flies over the river"——无限多的句子，只需有限条规则。

1956年，乔姆斯基在《语法的形式属性》中提出了一个革命性的问题：不同的文法系统，压缩能力是否相同？这个问题的答案，最终导向了著名的Chomsky层级——一套揭示认知压缩极限的数学框架。

1.2 Chomsky层级：压缩能力的四种等级

Chomsky证明，所有形式文法可以按压缩能力分为四个层级，从强到弱，形成嵌套结构：

Type 0（无限制文法）：压缩能力的极致。这种文法的规则可以写成任意形式 α → β，其中α和β是任意符号串。这意味着Type 0能够描述任何能用数学定义的符号模式——它的压缩能力最强，但代价是：无法有效计算。对于任意给定的字符串，我们可能无法判断它是否由这个文法生成。

Type 1（上下文有关文法，CSG）：中等压缩能力。规则形式为 αAβ → αγβ，其中A是非终结符，γ非空。这种文法要求替换必须考虑上下文——只有当A处于特定语境时才能被替换。CSG的压缩能力比Type 0弱，但计算上更可控。

Type 2（上下文无关文法，CFG）：有限压缩。规则形式为 A → γ，其中A是单个非终结符。无论A出现在哪里，替换规则都一样。这使得CFG成为计算机科学中最广泛使用的形式文法——它的压缩能力恰到好处：足够强大以描述大多数编程语言的语法，又足够简单以实现高效分析。

Type 3（正则文法）：最弱压缩，但最高效。规则只能是 A → aB 或 A → a（右线性）。正则文法恰好等于有限状态自动机可识别的语言——这意味着它可以用极其简单的机器来识别。但代价是：正则文法无法描述任何递归结构。

压缩与效率的张力，在Chomsky层级中得到了完美体现：压缩能力越强，计算代价越高。

图1：Chomsky层级结构图。四个层级呈嵌套结构：Type 0（无限制文法）包含Type 1（上下文有关文法），后者包含Type 2（上下文无关文法），最内层是Type 3（正则文法）。表达能力向上递增，计算效率向下递增。

二、正则文法的极限：为什么自然语言无法被正则压缩？

2.1 泵浦引理：正则压缩的数学证明

正则文法（Type 3）是最弱的压缩系统——它的压缩能力究竟有多弱？数学给出了一个冰冷的答案：正则文法无法压缩自然语言的递归结构。这个结论来自正则语言的一个重要性质——泵浦引理（Pumping Lemma）。

泵浦引理的核心思想是：所有正则语言都有一个"泵长"p，使得任何长度超过p的字符串，都可以被"泵送"——也就是重复其中的某个片段若干次，得到的字符串仍然属于这个语言。

这听起来很抽象，但结论是明确的：如果自然语言是纯正则压缩的产物，那么对于任意长度的句子，我们都可以通过重复某个片段来创造新的合法句子。但这是荒谬的——"The cat sat on the mat"合法，但"The the cat sat on the mat"就不合法。

泵浦引理揭示了正则压缩的根本局限：它无法处理递归结构中的约束。自然语言充满了嵌套递归——主句中包含从句，从句中再包含从句。无限嵌套的可能性，使得正则压缩必然失败。

2.2 为什么编程语言的词法分析可以用正则文法

有趣的是，编程语言的词法分析（lexer）恰恰使用了正则文法。为什么编程语言的词法可以用正则压缩，而自然语言不行？

答案在于设计目标的不同。编程语言的词元（token）是有限长度的符号：标识符是字母开头的字母数字串，数字是连续的数字序列，运算符是固定的字符组合。这些模式都是局部的、有限的——它们确实符合正则文法的压缩能力。

但即便在编程语言中，正则压缩也只限于词法层面。一旦进入句法层面——也就是语句的结构——正则文法就不够用了。这时必须使用上下文无关文法（Type 2）来进行语法分析（parsing）。

这是一个深刻的教训：正则压缩只能处理扁平结构，无法处理递归嵌套。人类的语言能力恰恰在于处理这种无限递归——这是正则压缩无法触及的领域。

三、上下文无关文法：编程语言的压缩标准

3.1 BNF：形式化压缩语法规则

1959年，IBM的程序员约翰·巴科斯（John Backus, 1924-2007）发明了Backus-Naur Form（BNF）——一种描述编程语言语法的元语言。BNF与Chomsky的上下文无关文法（CFG）惊人地相似：它用尖括号包围非终结符，用"::="表示定义，用"|"表示或然选择。

BNF的本质，是一种压缩语法的形式化方法。请看一个ALGOL语言的简化定义：

 ::=  :=   ::=  |  +   ::=  |  *   ::=  | (  )  ::=  |  

这几行BNF定义，可以生成无限多个合法的赋值语句——"x := 1"、"y := x + 2"、"z := (a + b) * c"，等等。BNF的压缩效率是惊人的：几行符号，就能捕获无限多的句子结构。

历史惊人的相似：语言学家后来发现，公元前约500年的印度语法学家波你尼（Panini），在《八章书》（Ashtadhyayi）中发明了一套类似的元语言符号系统。这比BNF早了整整2500年。看来，用形式规则压缩语言结构，是人类思维的自然趋向。

3.2 歧义是压缩的天敌

编程语言必须无歧义——这不仅是设计偏好，更是压缩的内在要求。

歧义为什么是压缩的天敌？因为歧义意味着同一个符号串可以对应多种结构。在压缩视角下，这意味着：为了唯一确定句子的含义，压缩系统必须额外存储"选择哪种结构"的信息。这种信息的添加，等同于降低压缩比。

歧义使得压缩效率大幅下降。对于自然语言，这种"结构不确定性"是普遍存在的——"The chicken is ready to eat"既可以指鸡肉已煮熟，也可以指鸡准备吃东西。这种多义性虽然降低了压缩效率，却增加了语言的表达能力。

编程语言选择消除歧义，以提高压缩效率并确保计算确定性。编译器必须能够为每段代码生成唯一正确的机器指令——歧义会导致编译失败或运行错误。

自然语言则容忍歧义，将其作为表达丰富性的来源。同一个句子可以有多重含义，说话者无需每次都明确所有细节，因为语境会帮助听者消解歧义。这种设计差异，揭示了两种语言的根本目标：编程语言追求精确执行，人类语言追求高效交流。

3.3 编译器的两层压缩架构

编译器是形式语言理论最成功的应用。它的架构体现了Chomsky层级的两层压缩：

词法分析层（Lexical Analysis）：使用正则文法（Type 3）压缩源代码中的词素序列。标识符、数字、运算符——这些局部模式被识别为有限的token类。这一层的压缩是轻量的，但对于编程语言来说已经足够。

语法分析层（Syntax Analysis）：使用上下文无关文法（Type 2）压缩token序列为语法树。语句的结构、表达式的嵌套、程序的层次——这些递归结构需要CFG才能有效压缩。

这种两层架构并非偶然，而是压缩能力与计算效率权衡的必然结果。正则文法虽然压缩能力最弱，但识别速度最快——它只需线性扫描即可完成。上下文无关文法压缩能力更强，但识别需要更复杂的算法（如LR分析）。

图2：编译器两层压缩架构图。第一层（词法分析）基于正则文法（Type 3），将源代码转换为记号流；第二层（语法分析）基于上下文无关文法（Type 2），将记号流转换为语法树。

四、自然语言的压缩困境

4.1 为什么形式文法无法完全压缩自然语言

1957年，乔姆斯基在《句法结构》中宣称：英语的大部分语法现象可以用上下文无关文法描述。这一论断在语言学界引起轰动——如果自然语言可以用CFG压缩，那么计算机就能处理人类语言。

然而后来的研究揭示：上下文无关文法对自然语言的压缩是失败的。这不是因为CFG太弱，而是因为自然语言中存在一类被称为"强交叉歧义"（strong crossing ambiguity）的现象。

中文的省略问题：中文可以省略主语而仍然保持语法正确和语义清晰："（我）吃了饭（就）去图书馆"、"下雨了，（我）回家（了）"。省略不仅是删除符号，更涉及隐含结构的恢复。这种"零形回指"现象，是CFG无法优雅处理的。

英语的控制结构问题：

"John promised to leave." —— John承诺自己离开

"John attempted to leave." —— John试图让自己离开

"John persuaded Mary to leave." —— John说服Mary离开

这三种情况的"to leave"主语不同——这种控制关系取决于动词的语义，无法从形式结构中读出。形式文法压缩了句法结构，却无法压缩语义信息。

4.2 歧义：压缩失败的积极意义

自然语言的歧义不是缺陷，而是压缩失败的副作用——但这种失败可能是值得的。

歧义意味着信息冗余度降低。完全消除歧义的语言（如编程语言）需要更多符号来消除不确定性。自然语言允许歧义，实际上是在用更少的符号传递更多的潜在含义——这是一种信息压缩的策略。

语境的作用，正是解压。当我们听到"The chicken is ready to eat"时，语境（是关于晚餐的谈话）帮助我们选择正确的解释。这个过程本质上是解压缩：语境信息作为"解压密钥"，帮助我们恢复被压缩的语义。

歧义使语言更简洁。正是因为允许多重解释，自然语言可以用更少的词语表达更丰富的含义。这是一种以歧义换效率的权衡。

4.3 超越上下文无关文法

为了解决自然语言的压缩问题，语言学家发展了更强大的形式框架：

树邻接文法（TAG）：能够描述递归嵌套结构，同时保持多项式时间的解析算法。词汇功能语法（LFG）：将句法结构与语义功能分离，允许更灵活的语言描述。中心语驱动短语结构语法（HPSG）：融合了短语结构语法的优点，同时引入中心语驱动的思想。

这些框架的本质，是尝试用更强的压缩能力来捕获自然语言的复杂性。然而，每一个更强大的形式系统，都带来更高的计算代价——这就是压缩与效率的张力。

五、大语言模型的压缩启示

5.1 Transformer：神经网络时代的压缩

2017年，Transformer架构问世。与Chomsky的形式文法不同，Transformer采用了完全不同的压缩策略：它不依赖手工设计的语法规则，而是通过大规模文本统计学习语言的压缩表示。

Attention机制的本质，是学习哪些词最值得压缩在一起。当模型处理"The chicken is ready to eat"时，注意力机制学会将"chicken"与"ready"关联，因为这是消解歧义的关键。

GPT等大语言模型，在海量文本上训练后，能够生成极其流畅的自然语言文本。这意味着：语言的压缩规律可以通过统计学习被捕获，而不必显式地编码为形式规则。

5.2 对普遍语法的挑战

乔姆斯基的核心假设是：人类语言能力来自天赋的普遍语法——一套所有人类共有的语言器官。这个假设的一部分含义是：语言是可以被高度压缩的，这种压缩能力是天生的。

大语言模型的成功，对这个假设提出了挑战。如果神经网络可以通过统计学习掌握语言，那就意味着：语言的压缩规律可以从大量文本中提取，而不需要天赋的语言模块。

当然，LLM与人类语言能力之间仍有巨大差距。LLM不理解语境、缺乏真正的语义、无法进行真正的推理。但它们证明了一点：语法层面的压缩规律可以通过学习获得——这本身就是对"天赋语法"假设的深刻挑战。

结语：压缩的极限与语言的本质

形式语言理论的核心洞察，是揭示了压缩能力与计算效率之间的根本张力：

正则文法（Type 3）：压缩能力最弱，但计算最简单——只能处理扁平的、局部的模式。上下文无关文法（Type 2）：压缩能力适中，计算复杂度可控——适合描述大多数编程语言。上下文有关文法（Type 1）：压缩能力较强，但计算代价更高——能够处理递归嵌套。无限制文法（Type 0）：压缩能力极致，但可能是不可计算的。

自然语言选择了什么？它们选择了超越正则文法，但停留在上下文无关文法或更弱的上下文有关文法附近。这种选择不是偶然的：它反映了人类认知的计算限制。我们的大脑无法处理无限递归的深度嵌套——虽然理论上上下文无关文法允许无限嵌套，但实际语言使用中的嵌套深度是有限的。

语言的压缩极限，定义了人类语言的本质。正则文法太弱，无法捕获递归结构；无限制文法太强，无法有效计算。自然语言恰好位于这个边界的内侧——足够强大以表达复杂思想，又足够简单以适应人类认知的计算限制。

从波你尼到乔姆斯基，从BNF到Transformer，两千五百年的语言研究揭示了一个核心真相：语言是对世界进行认知压缩的工具。形式语言理论告诉我们，这种压缩是有极限的——而正是这些极限，赋予了人类语言独特的面貌。

下期预告

形式主义的统治遇到了挑战者。Part 7 将介绍George Lakoff和Mark Johnson如何用"概念隐喻"和"体验哲学"，彻底颠覆了Chomsky的形式主义语言学。

七、参考文献

[1] Chomsky, N. (1956). "Formal Properties of Grammars." Handbook of Mathematics. North-Holland Publishing Company.

[2] Chomsky, N. (1957). Syntactic Structures. Mouton Publishers.

[3] Chomsky, N. (1965). Aspects of the Theory of Syntax. MIT Press.

[4] Backus, J. (1959). "The Syntax and Semantics of the Proposed International Algebraic Language." Proceedings of the International Conference on Information Processing. UNESCO.

[5] Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (3rd edition).

[6] Vaswani, A., et al. (2017). "Attention Is All You Need." arXiv:1706.03762.https://arxiv.org/abs/1706.03762

[7] Jurafsky, D., & Martin, J. H. (2023). Speech and Language Processing (3rd edition draft). Stanford University.

[8] Joshi, A. K. (1985). "Tree Adjoining Grammars: How Much Context-Sensitivity Is Required to Provide a Reasonable Description of Natural Language?" Natural Language Parsing. Cambridge University Press.

[9] Pinker, S. (1994). The Language Instinct: How the Mind Creates Language. William Morrow and Company.

[10] Pullum, G. K. (1991). "Evidence for Nonexistence of some Context-Free Languages." Linguistics and Philosophy, 14(1), 103-113.