一、文法就是一串规则

先搭一个最小的中文文法。七条规则，八成的句子都能拆：

二、一步步试：回溯解析

最直白的算法就是逐个断点试。要问「从第 4 个词到第 6 个词能不能当 NP」，就试遍每一种断开方式。 「张三 追 那只 猫」只有一棵树：

S
  NP
    N
      张三
  VP
    V
      追
    NP
      Det
        那只
      N
        猫

这棵树把「谁在做什么」摆明了：结构就是意义。同一个意思换个说法，树就换了形状； 可只要树没变，核心关系就没变。 这就是句法分析的全部野心：把「意思」装进「结构」里。

三、同一串词，两棵树

换一句。「张三 看见 那只 狗 用 望远镜」——两棵树。

四、句子一长，树的数量按卡特兰数翻

在基础句后面一条一条加介词短语，把树全数出来：

五、这一节的位置

把三件事串起来：文法定义结构，回溯找结构，歧义说明结构不够用。 文法是人写的，这是它的长处也是它的短处。长处是精确、可解释； 短处是写不全——真实语言里的例外，写规则的人永远追不上。 后来的统计方法（11.2）换了个思路：不写规则，改从语料里数概率。 两种思路在 11.3 会合到一起——用概率给每种结构打分，再挑最高的那棵。

六、动手 Demo：一句话能画出几棵树，就看文法给不给它机会

四段：文法长什么样、一句话的树、歧义句的两棵树、树的数量与算法代价。 第 3 段和第 4 段是一对：一个说「能有多解」，一个说「多解有多贵」。 解析器是手写的回溯，没用什么库。树的缩进图直接打印出来， 这样「层次」这件事是看得见的，不是抽象的。

def go(cat, i, j):                 # 从第 i 个词到第 j 个词，能不能当 cat
    key = (cat, i, j)
    if key in memo:
        return memo[key]           # 问过就查表，别重算
    out = []
    if j - i == 1 and tags[i] == cat:
        out.append((cat, [WORDS[i]]))      # 一个词自己就是一个成分
    for rhs in RULES.get(cat, []):
        if len(rhs) == 1:          # 一元规则：NP -> N 这种
            if rhs[0] != cat:
                for c in go(rhs[0], i, j):
                    out.append((cat, [c]))     # 本层节点要套回去
            continue
        if j - i < 2:              # 二元规则至少要覆盖两个词
            continue
        for k in range(i + 1, j):  # 在哪里断开，逐个试
            for a in go(rhs[0], i, k):
                for b in go(rhs[1], k, j):
                    out.append((cat, [a, b]))
    memo[key] = out
    return out

实跑输出：

--------------------------------------------------------------------
一句话能画出几棵树，就看文法给不给它机会
--------------------------------------------------------------------
==============================================================

[1] 文法就是一串「谁由谁组成」的规则

  七条规则：

    S     -> NP VP
    NP    -> Det N
    NP    -> N
    NP    -> NP PP
    VP    -> V NP
    VP    -> VP PP
    PP    -> P NP

  词典把词映射到词性：

    张三/N          猫/N            狗/N            望远镜/N        
    那只/Det        追/V            看见/V          用/P            

  **NP 是名词短语，VP 是动词短语，PP 是介词短语，S 是句子。**
  **注意 NP 和 VP 的规则都是递归的——NP 里还能套 PP，PP 里还能套 NP。**
  **递归是这套办法能描述无穷多句话的原因，也是下一段麻烦的来源。**

[2] 给一句话，枚举它能怎么拆

  句子：「张三 追 那只 猫」
  词性： N V Det N
  解析树的棵数：1

    S
      NP
        N
          张三
      VP
        V
          追
        NP
          Det
            那只
          N
            猫

  **树是从上往下读的：S 由 NP 和 VP 组成，NP 由「张三」一个词充当。**
  **VP 又由动词和宾语组成——这棵树把「谁在做什么」摆明了：结构就是意义。**
  **这棵树把「谁在做什么」摆明了：结构就是意义。**

[3] 换个句子，树就分叉了

  句子：「张三 看见 那只 狗 用 望远镜」
  词性： N V Det N P N
  解析树的棵数：2

  **这几棵树的读法不一样，区别全在「用望远镜」挂在哪：**

    第 1 棵（挂在名词短语上）：
      S
        NP
          N
            张三
        VP
          V
            看见
          NP
            NP
              Det
                那只
              N
                狗
            PP
              P
                用
              NP
                N
                  望远镜

    第 2 棵（挂在动词短语上）：
      S
        NP
          N
            张三
        VP
          VP
            V
              看见
            NP
              Det
                那只
              N
                狗
          PP
            P
              用
            NP
              N
                望远镜

  挂在动词短语上：**「用望远镜」修饰「看见」这个动作**——拿望远镜去看。
  挂在名词短语上：**「用望远镜」修饰「那只狗」**——被看见的是「带着望远镜的狗」。

  **同一串词，同一个词性序列，两种意思。这就是句法歧义。**
  **人靠常识一眼就能排除第二种（狗不太可能被望远镜修饰），**
  **可文法本身只管结构合不合法，它不知道狗是什么。**

[4] 句子一长，树的数量就爆炸

  在「张三 看见 那只 狗」后面一条一条加介词短语，
  把解析树全部枚举出来，同时数一遍「算」的代价：

    词数  解析树棵数  不记忆的调用次数    记忆后
    4     1           38                  30
    6     2           217                 92
    8     5           1101                205
    10    14          5421                391
    12    42          26614               690

  **树的棵数是 1、2、5、14、42——这个数列叫卡特兰数。**
  **每多加一条短语，能拆出来的结构就多一批，长句的歧义就是这么来的。**

  **再看调用次数那一列：不记忆的一路往上冲，记忆的慢得多。**
  **因为回溯会反复重算同一个子问题——第 3 到第 5 个词能不能是 NP，被问了几十遍。**
  **把答案记下来，就是动态规划。11.3 要讲的 CYK 算法，本质就是这张记忆表。**

  四段连起来：**文法告诉你句子能怎么拆**；**一句话常常能拆出不止一棵树**；
  **词一多树就指数增长**；**而重复的子问题让「把中间结果记住」变成必需。**

第 2 段那棵树要竖着读。每一层缩进代表一层结构， NP 底下是 N，N 底下才是具体的词——结构是夹在词和句之间的那一层。 第 3 段那两棵树值得对着看：叶子顺序完全相同，只是挂的层不同。 这就是「结构的差别可以不带一个字的差别」。 第 4 段那张表的第三列最有说服力：38、217、1101、5421、26614。 而第四列是 30、92、205、391、690。同一个答案，两条代价曲线差着数量级。 最后那句「CYK 本质就是这张记忆表」不是比喻。11.3 会把这张表画出来， 你会看到它就是一个二维数组。

30 秒实验

1. 把第 3 段的句子改成「用 望远镜 张三 看见 那只 狗」（介词短语挪到句首），重跑。 树会只剩一棵——位置一换，能挂的地方就少了。
2. 往文法里加一条 VP → V NP PP，重跑第 3 段。 树的数量会变——规则多一条，可能的层次就多一批，这也说明「文法写多写少」直接影响歧义。
3. 把第 4 段的句子加到 16 个词，重跑。 不记忆那一列会涨到几十万——指数增长在前几步看着温和，再走两步就上天了。

常见误区

1. 以为「解析就是找一棵树」。真实句子常常有几十棵树， 解析器真正要做的是「给这些树排序」，挑出最可能的那棵。
2. 以为「歧义是句子写得不好」。歧义是语言的常态， Demo 第 3 段那句话，母语者天天在说，一点不别扭。
3. 以为「文法规则写得越细越好」。规则越多，覆盖越窄； 真实语料里的口语、错别字、网络新词，规则永远追不上。
4. 以为「记忆化只是优化，不影响结果」。对， 不影响结果——可它把代价从指数压到多项式，这就从「不可用」变成了「可用」。

下一节换一条路：不写规则，改数概率。 看看一个词的意思能不能只从「它跟谁一起出现」里学出来。 这条路不需要语法学家，只需要一大堆文本。

• ☐ （本节完，下一节 11.2 知识获取和统计语义学）

相关笔记

• 语音识别
• 知识获取和统计语义学
• 无监督学习
• 📘 图解人工智能 · 索引