语法分析与上下文无关文法

有了单词序列，怎么知道谁是主语谁是谓语？

词法分析给了你一串 Token：int a = 42 ;——但这只是一串单词，没有结构。语法分析要回答：这些单词按什么规则组合在一起？

🏫 类比：句子的语法分析 “我喜欢编程” → 主谓宾结构。你知道这个结构是因为中文的语法规则。

编程语言的语法规则就是用上下文无关文法（Context-Free Grammar, CFG） 来定义的。

上下文无关文法

文法（Grammar） 由一组产生式（Production） 组成，每条产生式描述如何拆分一个语法成分：

表达式 → 数字
表达式 → 表达式 "+" 表达式
表达式 → 表达式 "*" 表达式
语句 → "int" 标识符 "=" 表达式 ";"
程序 → 语句 程序 | ε

文法的组成部分

G = (N, T, P, S)

N = 非终结符（需要展开的符号）：表达式、语句、程序
T = 终结符（Token）：int, =, +, ;, 标识符, 数字
P = 产生式：N → (N ∪ T)*
S = 开始符号：程序的顶层结构

推导——从开始符号生成句子

程序
→ 语句 程序
→ "int" 标识符 "=" 表达式 ";" 程序
→ "int" 标识符 "=" 表达式 "+" 表达式 ";" 程序
→ "int" 标识符 "=" 数字 "+" 数字 ";" 程序
→ "int" a "=" 42 "+" 1 ";" （没有更多语句了）

语法树（Parse Tree）

        程序
       /    \
    语句    程序（空）
   / |  |  | \
int id = 表达式 ;
         /  |  \
      表达式 + 表达式
        |       |
       42       1

二义性文法

同一个句子可能有多种语法树——这就是二义性。

表达式 → 表达式 '+' 表达式
表达式 → 表达式 '*' 表达式
表达式 → 数字

输入：1 + 2 * 3

两种可能的语法树：
     +                 *
    / \               / \
   1   *             +   3
      / \           / \
     2   3         1   2

    结果：9          结果：7

解决方案：

1. 改写文法——引入优先级层次
2. 结合性声明——规定左结合或右结合

// 改写后的无二义文法
表达式 → 表达式 '+' 项 | 项
项 → 项 '*' 因子 | 因子
因子 → 数字 | '(' 表达式 ')'

// 1 + 2 * 3 只有一种推导：
// 表达式 → 表达式 + 项 → 项 + 项 → 因子 + 项
//        → 1 + 项 → 1 + 项 * 因子 → 1 + 2 * 3

语法分析的两种方式

方式	方向	做法	适用文法
自顶向下	从开始符号→句子	预测推导路径	LL 文法
自底向上	从句子→开始符号	归约为非终结符	LR 文法

自顶向下：程序 → 语句 → int a = 表达式; → ...
自底向上：int → 类型 ... → 语句 → 程序

💡 两种方法的对比如下：自顶向下（LL）实现简单、错误定位好，但能处理的文法种类有限；自底向上（LR）能处理更多文法，但实现更复杂。

Yacc / Bison——语法分析器生成器

Unix 工具 Yacc（Yet Another Compiler Compiler） 从文法规则自动生成语法分析器：

%{
#include "ast.h"
%}

%token NUMBER IDENTIFIER
%left '+' '-'
%left '*' '/'

%%

expression: expression '+' expression
          | expression '*' expression
          | NUMBER
          | IDENTIFIER
          ;

%%

int main() {
    yyparse();
    return 0;
}

小结

概念	要点
上下文无关文法	用产生式描述语言结构
推导	从开始符号逐步展开到句子
语法树	推导过程的树形表示
二义性	同一句子多棵语法树 → 需要改写文法
自顶向下 vs 自底向上	两种不同的解析策略

为什么先学这个？ 理解语法分析后，接下来深入两种具体实现：自顶向下分析（LL）和自底向上分析（LR）。你也可以直接跳到抽象语法树（AST）。