本文目录导读：
什么是CF文法？
CF文法（Context-Free Grammar，上下文无关文法）是形式语言理论中的核心概念，也是编译原理、自然语言处理、程序设计语言设计的基础工具，它是一套生成字符串的规则系统,能够描述大多数编程语言的语法结构。
想象一下，你有一座“语言工厂”,里面有两种零件：
- 终结符：不可再分解的基本符号（如数字、运算符、关键字）
- 非终结符：可以进一步展开的抽象概念（如“表达式”、“语句”）
工厂的规则叫产生式，形如：
非终结符 → 一串终结符和非终结符
描述一个简单算术表达式：
Expr → Expr '+' Term | Term
Term → Term '*' Factor | Factor
Factor → '(' Expr ')' | 'id' | 'num'这条规则说：“一个表达式可以是另一个表达式加一个项，或者直接就是一个项”,这就是典型的CF文法。
CF文法的四元组定义
一个完整的CF文法由四部分组成：
G = (V, T, P, S)- V：非终结符集合（变量，如Expr、Term）
- T：终结符集合（字母表上的符号，如'+', '*', 'id'）
- P：产生式集合（规则）
- S：开始符号（属于V,文法生成的起点）
例如上面算术表达式的文法中：
V = {Expr, Term, Factor}
T = { '+', '*', '(', ')', 'id', 'num' }
P = 上述三条产生式
S = Expr
如何用CF文法生成句子？
“推导”是核心操作，从开始符号出发，反复将非终结符替换为产生式右部,直到所有符号都变成终结符。
例子：生成句子 id + id * id
Expr
→ Expr '+' Term （使用 Expr → Expr '+' Term）
→ Term '+' Term （替换第一个Expr为Term）
→ Factor '+' Term （替换Term为Factor）
→ id '+' Term （Factor → 'id'）
→ id '+' Term '*' Factor （Term → Term '*' Factor）
→ id '+' Factor '*' Factor（Term → Factor）
→ id '+' id '*' Factor （Factor → 'id'）
→ id '+' id '*' id （Factor → 'id'）每一步替换都只依赖被替换符号本身，不依赖上下文——这就是“上下文无关”的含义。
语法树：直观理解结构
推导过程可以画成一棵倒立的树——语法分析树（Parse Tree），根节点是开始符号，叶子节点是终结符,内部节点是非终结符。
对于上面的推导,语法树如下：
Expr
/ | \
Expr '+' Term
| / | \
Term Term '*' Factor
| | |
Factor Factor 'id'
| |
'id' 'id'语法树清晰地展示了运算符优先级：乘法先结合,加法后结合。
CF文法的实际用途
编译原理中的语法分析
几乎所有编程语言的语法都用CF文法定义（如C、Java、Python），编译器前端通过递归下降解析或LR解析,将源代码读入并建立语法树。
自然语言处理
句子的语法结构可以用CF文法表示。
S → NP VP（句子由名词短语和动词短语组成）
NP → Det N（名词短语由限定词和名词组成）
数据格式描述
JSON、XML、HTML的语法都可以用CF文法描述,例如JSON的简化文法：
Value → Object | Array | String | Number | true | false | null
Object → '{' Pair (',' Pair)* '}' | '{' '}'
Pair → String ':' Value如何构造一个CF文法？
步骤1：明确要描述的语言是什么（集合）。
所有由a和b组成的、且a的数量等于b的数量的字符串。
步骤2：设计递归的生成规则。
上述语言满足：
- 空串属于语言
- 如果S属于语言，则 aSb 也属于（在两边各加一个a和b）
- 如果S1、S2属于语言，则 S1S2 也属于
由此得到文法：
S → ε | a S b | S S步骤3：检查文法是否产生多余或错误的字符串。
例如上述文法可能产生重复问题,通常我们会用更精确的写法：
S → a S b S | ε这个文法能保证所有合法的字符串都被生成。
常见陷阱与应对策略
左递归
形如 A → A α 的产生式会导致递归下降解析器陷入无限循环。
解决方法：消除左递归（通过引入新非终结符改写）
Expr → Expr '+' Term | Term改写为：
Expr → Term Expr'
Expr' → '+' Term Expr' | ε二义性
同一个句子对应多棵不同的语法树，例如经典“悬挂else”问题：
if C1 then if C2 then S1 else S2可能有两种解释。解决方法：通过优先级规则或修改文法（如强制else匹配最近的if）。
左公因子
两个产生式以相同前缀开头，导致预测时无法选择。解决方法：提取左公因子。
实战：用CF文法设计一个迷你计算器
目标：支持加、乘、括号，数字为整数（id）。
文法设计：
Expr → Expr '+' Term | Term
Term → Term '*' Factor | Factor
Factor → '(' Expr ')' | NUMBER（注意：这里NUMBER是终结符,实际词法分析器会识别）
测试：输入 (2 + 3) * 5
推导如下（简化）：
Expr → Term → Term '*' Factor → Factor '*' Factor → '(' Expr ')' '*' Factor
→ '(' Expr '+' Term ')' '*' Factor → '(' Term '+' Term ')' '*' Factor
→ '(' Factor '+' Factor ')' '*' Factor → '(' NUMBER '+' NUMBER ')' '*' NUMBER解析结果：语法树保证了乘法优先级高于加法（因为乘法在更低层）。
总结与进阶
CF文法是理解计算机语言的一把金钥匙，掌握它之后,你可以：
- 编写简单的解释器或编译器
- 理解编程语言中的语法错误提示
- 设计DSL（领域特定语言）
下一步推荐学习：
- 自顶向下解析（LL(1)）与自底向上解析（LR(0)、SLR、LALR）
- 语法制导翻译（属性文法）
- Chomsky文法分类体系（0~3型,CF属于2型）
CF文法的核心魅力在于：用有限的规则生成无限的语言，动手写几条文法，用在线工具（如Grammophone、ANTLR）测试一下,你会很快上手！
