目录

• • 1. 概念
• • 2. 文法与自动机对应关系
• • 3. 正则文法与有限自动机
• • 4. 上下文无关文法与下推自动机
• • 5. 程序语言属于什么文法
• • 6. 自然语言属于什么文法
• • 7. 程序与自然语言的区别
• • 8. 总结

1. 概念

文法体系与自动机是形式语言理论中的两个核心概念。

• • 文法体系：用于生成或描述语言中的合法字符串。
• • 自动机：用于识别或判定一个输入字符串是否属于某种语言。
  

文法回答“什么样的字符串是合法的”；自动机回答“如何判断一个字符串是否合法”。

2. 文法与自动机的对应关系

文法体系和自动机之间存在经典的对应关系，通常用 乔姆斯基层级 来描述。

乔姆斯基层级可以理解为一种“表达能力”的层次划分。

3 型文法：正则文法    ↓2 型文法：上下文无关文法    ↓1 型文法：上下文有关文法    ↓0 型文法：无限制文法

从上到下：

• • 表达能力逐渐增强；
• • 能描述的语言越来越复杂；
• • 对应的自动机能力越来越强；
• • 分析和判定的计算复杂度通常也会增加。

3. 正则文法与有限自动机

正则文法 是最简单的一类文法，对应 有限自动机，适合描述简单、局部、无嵌套的模式，例如：

[0-9]+

这个正则表达式表示匹配一个或多个数字。

正则文法和有限自动机常用于：

• • 字符串模式匹配；
• • 关键词识别；
• • 标识符识别；
• • 数字识别；
• • 简单格式校验；
• • 编译器中的词法分析。

例如，程序语言中的变量名可以用类似规则描述：

[a-zA-Z_][a-zA-Z0-9_]*

• • 第一个字符必须是字母或下划线；
• • 后面可以是字母、数字或下划线。

4. 上下文无关文法与下推自动机

上下文无关文法，即 CFG，适合描述具有递归和嵌套结构的语言，对应的自动机是 下推自动机 PDA。下推自动机相比有限自动机，多了一个“栈”，因此可以处理嵌套关系。例如括号匹配：

()(())(()())

这种结构不能仅靠普通有限自动机完整处理，因为它需要记住左括号的数量。上下文无关文法可以写成：

S → (S)S → SSS → ε

这个文法可以生成多种合法括号结构。

5. 程序语言属于什么文法？

程序语言的核心语法通常可以用 上下文无关文法 CFG 描述。例如表达式语法：

表达式 → 表达式 + 项项 → 项 * 因子因子 → 数字 | 标识符 | ( 表达式 )

这种文法可以描述：

• • 表达式嵌套；
• • 括号匹配；
• • 语句组合；
• • 代码块结构；
• • 函数调用结构。

例如：

if x > 0:    print(x)

程序语言中的 if 语句、循环语句、函数调用、表达式等结构，通常可以用上下文无关文法描述。

但是，程序语言不仅有语法，还有语义约束。例如：

int x;x = "hello";

这段代码在语法上可能能形成语法树，但类型不匹配。再如：

y = 10;

如果变量 y 没有声明，那么它也不符合程序语言的语义要求。

这些问题需要额外的语义分析，例如：

• • 类型检查；
• • 变量声明检查；
• • 作用域分析；
• • 符号表分析；
• • 数据流分析。

因此，程序语言更准确地说是：

程序语言 ≈ CFG + 语义分析

程序语言的核心语法通常属于上下文无关文法；但类型、作用域、变量声明等约束需要额外的语义分析。

6. 自然语言属于什么文法？

自然语言比程序语言更加复杂。自然语言中的一部分句法结构可以用上下文无关文法描述。例如英语句子：

The cat eats fish.

可以进行如下句法分析：

S → NP VPNP → Det NVP → V NP

其中：

• • S 表示句子；
• • NP 表示名词短语；
• • VP 表示动词短语；
• • Det 表示限定词；
• • N 表示名词；
• • V 表示动词。

但是，自然语言不仅有句法结构，还涉及语义、语境和世界知识，例如：

他看见了那个人，很高兴。

这里的“很高兴”到底指“他”高兴，还是“那个人”高兴，需要结合上下文理解。

自然语言还涉及：

• • 指代消解；
• • 省略理解；
• • 主谓一致；
• • 语义角色；
• • 语境推理；
• • 常识知识；
• • 语用含义。

因此，自然语言不能简单地归为某一种低层级文法。

自然语言 = 局部句法可用 CFG 建模 + 完整理解依赖语义、语境和知识

7. 程序语言与自然语言的区别

简单来说：

程序语言更形式化、更严格；自然语言更灵活、更依赖上下文。

8. 总结

文法体系描述语言的生成规则，自动机描述语言的识别过程。在乔姆斯基层级中：

正则文法       ↔ 有限自动机上下文无关文法 ↔ 下推自动机上下文有关文法 ↔ 线性有界自动机无限制文法     ↔ 图灵机

程序语言的核心语法通常属于上下文无关文法，但还需要类型检查、作用域分析等语义分析。自然语言的局部句法可以用文法建模，但完整理解通常更加复杂，需要结合语义、语境和世界知识。可以概括为：

程序语言 ≈ CFG + 语义分析自然语言 ≈ 局部 CFG/依存句法 + 语义理解 + 语境推理 + 世界知识