Context-Free Grammar（CFG，上下文无关文法）

<aside> 💡

**奇怪的类比：**假设 G 是 “人类” 这一物种的设计图。

• $T$ (Terminals)：原子、分子（碳、氢、氧）。（最底层素材，无法继续分解）
• $N$ (Non-terminals)：器官、组织（心脏、大脑、手）。（中间产物，还得往下拆）
• $P$ (Productions)：拆分/组合规则
  • 规则1：心脏 → 心房 + 心室
  • 规则2：手 → 手掌 + 手指
  • 规则3：细胞 → 细胞膜，细胞质，细胞核，线粒体 …
  • …
• $S$ (Start Symbol)：没啥合适的比喻。$S$ 是语法树的根，告诉我们从哪开始解析

**本质上：**CFG 的目的就是 把任意一句语法结构，展开成一个语法树（句 → 树）。具体做法是，从 $S$ 开始，对于每块代码 找到其对应的规则 $P_i$ ，然后识别出该规则中的 $T$ 和 $N$：

• Terminal（$T$） 意思是：这几个符号无法继续展开，已经是atomic了
• non-terminal（$N$）意思是：这几个符号还不是最底层素材，还得继续递归下去！ </aside>

$$ G = (N, T, S, P) $$

1. $G$ 具体是什么？
   • $G$ 是整门该编程语言的 所有规则语法符号的总集（整本法典，包含所有法律条文）
   • 比如：C语言里，$G$ 指的就是 “C 语言” 这个整体本身（而不是某一条规则）
2. $N$（Non-Terminal Symbol）是什么？
   1. $N$ 是语法中更抽象 high-level 的概念，可以继续被递归拆分，进一步解析
   2. 比如 <Statment> （语句），<Expression>（表达式），<Function>（函数）
3. $T$（Terminal Symbol）是什么？
   • $T$ 是语法里的最小单元。意味着 到此为止，不可再分。
   • 比如 if, else, +, *, id, int, (, )。
4. $S$（Start Symbol）是什么？
   • 告诉编译器从哪里开始解析。
   • C里面是 <CompilationUnit>；JSON里面是 <Json>
5. $P$（Productions）是什么？
   • $P$ 是该编程语言的 规则集。它是一个列表，里面列出了成百上千条模版
   • $P$集合可能长这样（点击展开）：
   • 如果说$G$是刑法典，这就是里面的法律条文列表

<aside> ❓

为啥不用 Regular Expression → NFA → DFA 的解析思路？

因为 Regex 是一种有限状态自动机（只知道当前状态 没有存储），像马尔可夫链一样。这导致无法处理需要 计数、嵌套 的语法结构（比如括号需要左右匹配）。

而 CFG 对应的机器叫 PDA (Pushdown Automaton，下推自动机)。相比于 DFA，PDA 多了栈，从而解决了记忆的问题

</aside>

Regular 转 CFG

例子：

规则如下：

1. 对每个状态 $i$，创建一个 nonterminal 状态 $A_i$
2. 对状态转移 $i \xrightarrow{a} j$，创建对应的 $A_i \rightarrow a A_j$
3. 对状态转移 $i \xrightarrow \epsilon j$ ，创建对应的 $A_i \rightarrow A_j$
4. 假如状态 $i$ 有多条状态转移，则用｜拼接
   1. 例如 $i\rightarrow j, i\xrightarrow ak$，创建 $A_i \rightarrow A_j|a A_k$