上下文无关文法与推导
搞懂产生式怎样生成合法句子、推导树如何生长、歧义性为何不可避免
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
上下文无关文法与推导
搞懂产生式怎样生成合法句子、推导树如何生长、歧义性为何不可避免
什么是上下文无关文法
上一页我们用规则一步步把 S 推成了句子。但「规则」本身到底长什么样？又为什么叫「上下文无关」？这一页拆开它的形式定义。
{{name}} 不管出现在哪一句，都用同一条规则换成具体名字，与左右邻居无关
文法的四元组定义
前面用一句话开始连续替换，知道每次改写都受规则约束。现在把一部文法本身拆开：它记录了哪些符号、允许哪些改写，以及推导从哪里开始？
V 像符号总表，T 像不可再拆的零件，P 像加工规则，S 像第一道工序。
终结符与非终结符
上页我们看到文法的字母表 V 里装着两类符号。一个像是推导的终点站，到此打住；另一个像是中转站，还得继续往下展开。这两类该怎么区分？
食材是原子不能再拆；菜名是占位符，还得拆成具体食材和步骤
产生式的基本形式
上页我们把符号分成终结符与非终结符——非终结符是「待解释」的占位符。那么用什么方式把「待解释」一步步换成「具体字符」？答案就是产生式。
都是「用自身定义自身」；递归函数靠 base case 终止，CFG 靠「不带 A 的产生式」终止
什么是推导
前面看到一条产生式左边可以替换成右边。那怎么从「一句完整的话」开始，一步步展开成「一个具体的句子」呢？这就是推导要做的事。
从「一道菜」出发，每步把抽象食材替换成更具体的食材，直到变成可下锅的实物
最左推导与最右推导
不同的推导路径，相同的结果
规约：推导的逆过程
推导是从 S 一路往下推到句子 w；规约就是反过来——拿着 w，往回找最后用上的那条产生式，把右部换回左部，直到只剩 S。
推导像搭乐高：设计图(S)→零件→成品 w；规约就是从成品倒拆，最后拼上的那块先拆
推导过程的代码演示
用 Python 把「最左推导」一步步跑出来，看句型从 S 演变到 aaaabbbb。
4 个高亮行就是推导机制的四要素：产生式集合 P、选产生式的策略 strategy、`index('S')` 锁最左非终结符、切片替换完成一次展开。
语法分析树的概念
推导是一条线性序列：每一步左写当前句型，右写下一步句型。但推导本质是「哪个符号展开成什么」，把这个信息单独画出，从 S 开始层层往下，就得到一棵树——语法分析树。
CEO 对应开始符号 S，部门是非终结符，员工是终结符
语法分析树的构成
从下往上读这棵树：底部黄色是叶节点（终结符），中部青色是内部节点（产生式展开），顶部红色是根节点（推导起点）。
分析树的完整示例
自顶向下读：从根 S 出发，每一步用一条产生式把非终结符展开成子树，直到全部叶子为终结符，从左到右拼成输入串 aabb。
推导与分析树的对应
上一节的分析树把推导过程「压扁」成了图。但推导有顺序（先选哪个非终结符展开），树没有——那么一棵树背后藏着多少种推导？
图纸固定，工人可先砌三楼再砌二楼，只要结构最终长成图纸
最左推导vs最右推导的树
两条推导路径可能产生截然不同的中间序列，却总是推出同一棵树。
- 每步替换最左侧非终结符
- 树的左分支优先展开
- 对应先根遍历次序
- 自顶向下分析的自然镜像
- 每步替换最右侧非终结符
- 树的右分支优先展开
- 对应后根遍历次序
- 自底向上分析的自然镜像
规约在分析树中的体现
规约沿推导的逆路径,从叶子逐层向上合并节点,最终回到根。从下往上看即规约推进方向。
上下文无关语言的定义
前面看了推导、规约、分析树，知道了'一个串怎么从文法里推出来'。但文法能推出一堆串——有的还含非终结符。得划条线：哪些算语言里的句子？这就是上下文无关语言的形式定义。
菜谱一步步把食材做成成品，能做出的菜就是'菜谱语言'。但'三味调料等量'这类规则菜谱写不出来
CFG与其他语言类
CFG 和正则文法都能描述 a*b* 这类重复，但面对 a^n b^n 这种需要"数几层"的嵌套就分出高下——这是理解两者边界最锋利的一刀。
- 能描述重复/并列，如 a*b*
- 无法识别 a^n b^n（状态有限）
- 对应有限状态自动机
- 用正则表达式描述
- 也能描述重复，还能嵌套递归
- 可识别 a^n b^n（递归展开 n）
- 对应下推自动机（多一个栈）
- 用 CFG 产生式描述
核心概念自测
同一棵语法分析树，可以对应多少种不同的推导过程？
本章要点回顾
- ✓产生式只看单个非终结符如何展开，与上下文无关
- ✓推导、语法树、规约是同一过程的三种观察视角
- ✓最左与最右推导是搜索策略，不改变所生成的语言
- ✓CFG擅长描述嵌套结构，但管不了跨位置的上下文约束
课后思考
带着问题继续探索形式语言的边界