递归⤵动态规划⤴和语言 parsing🌲

对于该问题，可以采用所谓自顶向下的方法，"顶"(top level) 指的是目标和策略，是一种高层的规划。 这听上去还是有点抽象，在本题中，起点是左上角，目标是在右下角，那么"顶" 的关注对象就是最右下角的格子，由于题目不单单要求到达该目标，还要使得路径和最小，因此要额外考虑到达最右下角格子的"路径"。

注意，不要看到"路径"两个字就立刻陷入细节，去图中试探各种从左上到右下的所有可能，这违背了 top level 的思想，自顶向下核心是保持足够清晰去抵御陷入细节的诱惑，只关注最右下角的目标格子，并只考虑到达该目标的"局部路径"，这只有两种可能： "从上方格子" 和 "从左侧格子" 。 并且要假定这两个方向都带有已经积累的最小路径和，只需要从中选择更小的即可。

这就像一个拥有上万名员工的公司的 CEO 大多数时候只需要关注直接向其汇报的几个助手提供的信息，而不需要关注每个员工的动态。

在这种"顶层思维"下，定义到达某个格子的路径最小和是 s(i,j), 本例中实际关注的就是 s(2, 2)

s(2,2) = grid[2][2]+min(s(1,2), s(2,1))

将这个式子一般化（抽象）：

s(i,j) = grid[i][j]+min(s(i-1,j), s(i,j-1))

至此，top-level 的目标和策略基本就完成了，我们可以直接将其写成代码：

def min_path_sum(grid):

    m, n = len(grid), len(grid[0])

    def s(i, j): 
        # 递归停止条件待定
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)

写代码时很快发现，我们还需要考虑递归的终点（最底层没有下属的员工），对应的到图中就是越界的情况，即 j-1 或者 i-i 小于 0 的情况。

一种做法是，在对 s(i-1,j) 取值的时候，检查 i-1 是否小于 0(也就是 -1), 如果小于 0 就不考虑，即 min(s(-1,j), s(i,j-1)) 应该返回 s(i,j-1), 这等价于把 s(-1,j) 设置为无穷大。但这种把越界视为无穷大的技巧会遇到额外边界情况，即在起点 i=0,j=0 的情况下 ，min(s(-1,j), s(i,-1)) 中两个元素都是无穷大，从而导致 s(0,0) 也是无穷大，这是会得到错误结果。因此还要额外地在 i,j 都等于 0 时直接返回 grid[0][0], 至此可以写出可执行的 top-down 代码了：

def min_path_sum(grid):

    m, n = len(grid), len(grid[0])

    def s(i, j): 
        if i == 0 and j == 0:
            return grid[i][j]
        if i < 0 or j < 0:
            return float("inf") 
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)

min_path_sum(grid = [[1,2,3],[4,5,6]])

12

有了具体代码，就可以分析执行细节的问题，也就是算法复杂度。以上函数的问题在于，计算 s(i,j) 时，要计算 s(i-1, j) 和 s(i,j-1), 而 s(i-1, j) 要计算 s(i-2,j) 和 s(i-1,j-1), s(i,j-1) 要计算 s(i-1,j-1) ， s(i,j-2), 这里 s(i-1,j-1) 被计算了两次，如下图所示（绘图基于 Show HN: Ascii_tree – A way to create beautiful ASCII trees）：

                        +--------+
             +----------| s(i,j) |------------+
             |          +--------+            |
       +----------+                     +-----+----+
    +--| s(i-1,j) |--+              +---| s(i,j-1) |---+
    |  +----------+  |              |   +----------+   |
+---+----+     +=====+====+    +====+=====+      +-----+----+
|s(i-2,j)|     |s(i-1,j-1)|    |s(i-1,j-1)|      | s(i,j-1) |
+--------+     +==========+    +==========+      +----------+

如果继续展开，会有更多的项目被重复计算，因此我们需要一个缓存机制，在递归过程中，如果某个子问题已经被解决，那么直接从缓存里获取结果即可，这里用 python 中的 lru_cache 实现：

import functools
def min_path_sum_cache(grid):

    m, n = len(grid), len(grid[0])

    @functools.lru_cache(1000) #假设 m*n 最大 1000
    def s(i, j): # 用函数 s 记录 s[i][j]
        if i == 0 and j == 0:
            return grid[i][j]
        if i < 0 or j < 0:
            return float("inf") 
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)

grid = [[1,3,1],[1,5,1],[4,2,9]]
min_path_sum_cache(grid)

15

注意分析复杂度并加上缓存的思考和用 top-down 思维分解问题很不一样，后者更像战争中的战略家，设定目标和方向，前者则是战术家，负责实现这些目标的细节，后勤等。

(理想的)自顶向下的思路的特点是：

• 先聚焦到目标本身，把目标分解成更小的相似的目标，因此它可以认为是目标驱动的。
• 由于只需要考虑一次分解而避免陷入细节（唯一的细节是边界条件），所以它常常是递归形式的
• 递归是在目标分解这棵树上从上（大目标）逐渐向下（子目标）执行，因此又会用递归下降来修饰这类算法（尤其是在后文提到的语言解析应用中）
• 在递归树中重复的部分可以通过缓存机制（memo）来快速跳过，缓存有一种把子树变成叶子节点的剪枝能力， 让子树立即返回一个值，减少不必要的重复递归(解重复的子问题）。

自顶向下是从终点的目标状态开始考虑，那么自底向上就是从初始状态或者 base case 开始思考。

在最小路径和题目中，自底向上要从网格的左上角起点开始按照规则向外搜索，在 top-down 思考中，已经把大问题分解成了相似的小问题，因此 bottom-up 要解决的每一步小问题的策略和大问题又是一样的：

s[i][j] = grid[i][j]+min(s[i-1][j], s[i][j-1])

注意这里我们把 s 从上文中的函数调用形式 s(i,j) 写成了数组形式 s[i][j], 它大小和原 grid 一样，s[i][j] 记录了到达 grid[i][j] 的路径和最小值。

除此之外， bottom-up 还要额外考虑解决子目标的顺序问题，这样才能保证进入下一个任务时，该任务所依赖的子任务都已经解决了。

路径和例子中， s[0][0] 是第一个解决的子任务，这毋庸置疑，解决了它之后，就可以按规则向下或向右计算 s[1][0] 和 s[0][1], 先解决哪个并不是很重要。

+--------------------+
|  1  ->  3   |  1   |
|--v---+------+------|
|  1   |  5   |  1   |
|------+------+------|
|  4   |  2   |  9   |
+--------------------+

接着解决对角线上三个子问题：

+------+------+------+
|  1  ->  3  ->  1   |
|--v---+--v---+------+
|  1  ->  5   |  1   |
|--v---+------+------+
|  4   |  2   |  9   |
+------+------+------+

总结来看，bottom-up 思路是从格子图左上角向右下角斜向下推进：

1. 第一轮解决 s[0][0]
2. 第二轮解决 s[1][0], s[0][1] 两个问题，因为它们只依赖 s[0][0]
3. 第三轮解决 s[2][0], s[1][1], s[0][2] 三个问题，其中 s[1][1] 同时依赖上一步解决的两个子问题
4. 第四轮解决 s[2][1], s[1][2]

5. 第五轮解决 s[2][2] 这个最终目标

   把后三步的问题处理顺序和依赖绘制成以下一棵"树", 其中 i,j 都等于 2 。 "树"打引号是因为这不是真正意义上的树，而是一个图，因为 s[i-1][j-1] 即 s[1][1] 只需要计算一次（如果把前两个步骤的图也画上去，会变成一个菱形），但这里我们还是称为树。

                   +--------+
             1 +---| s(i,j) |------+
               |   +--------+      |
               |                   |
         +-----+----+        +-----+----+ 5
    2 +--| s(i-1,j) |--+  +--| s(i,j-1) |---+
      |  +----------+  |  |  +----------+   │
      |              4 |  |6               7│
3 +---+----+       +==========+       +-----+----+
  |s(i-2,j)|       |s(i-1,j-1)|       | s(i,j-1) |
  +--------+       +==========+       +----------+

从第三步到第五步的过程，正是按层次从树的底部向上移动逐渐解决每个子节点对应的问题，这再次体现了自底向上的特点。另外，由于事先已经有意识地制定好了解决子问题的顺序，因此 s(i-1,j-1) 节点只会被解决一次，这和上一节带缓存的递归是一样的， 但递归的劣势在于函数调用的成本比内存取值高很多，比如调用函数需要入栈出栈等操作，可能其中有 10 条指令，但访问内存取出 s[i-1][j-1] 可能只要一条指令，那么相同问题下， bottom-up 方式效率就是 top-down 方式效率的 10 倍了。

然而具体实现中基本不会沿着这样的任务顺序去解决，因为对于方格图来说，沿斜向下方向对 i,j 进行更新的遍历顺序写起来要复杂一点，更常见的是先从左到右解决第一行：

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+------+
|  1   |  5   |  1   |
|------+------+------+
|  4   |  2   |  9   |
+------+------+------+

然后第二行，第三行：

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+------+
|  1  ->  5  ->  1   |
|------+------+------+
|  4   |  2   |  9   |
+------+------+------+

这样只要写两个 for 循环就行了：

for i in range(m):
    for j in range(n):
        ...

逐行遍历优于斜线遍历的原因完全来自语言接口的设计，如果语言提供了一个 diag 函数，能够从中不断返回沿对角线向下移动的 i,j ，那么没有理由拒绝斜向下扫描的方式，因为斜向下更符合问题分解顺序。

之所以从左到右逐行扫描是合理的，是因为题目性质规定只能向右和向下移动，因此从左到右边，从上到下的顺序符合子问题的依赖顺序，但不能从右到左或从下到上来逐一解决问题。

我们按逐行扫描写出动态规划代码：

def min_path_sum_dp(grid):

    m, n = len(grid), len(grid[0])
    s = [[0]*n for _ in range(m)]
    s[0][0] = grid[0][0]

    # 先更精细地解决第一行和第一列中的子问题
    for i in range(1, m):
        s[i][0] = grid[i][0] + s[i-1][0]

    for j in range(1, n):
        s[0][j] = grid[0][j] + s[0][j-1]

    # 多个 for 循环精细避免了边界条件判断
    for i in range(1, m):
        for j in range(1, n): 
            s[i][j] = min(s[i-1][j], s[i][j-1]) + grid[i][j] 

    return s[m-1][n-1]

min_path_sum_dp(grid)

15

自底向上也会称为数据驱动型算法，因为它是从最小的子问题开始解决的，每向前一步都是基于之前解决问题的数据的基础上去解决下一个已经规划好的小目标。

总的来看：对问题的思考上，top-down 和 bottom-up 的出发点是一样的，都是找到目标并且把目标分解成子目标， 只是在具体实现上，top-down 在分解完任务、考虑好极端的边界条件后以 CEO 的视角把问题交给了两个助手，自己只要等待目标是否达成（目标驱动），bottom-up 则在分解完任务后亲自去规划每个子任务的进度安排，跟进每个任务。规划子任务执行路径的行为是它与 top-down 方法的核心差异，这种特点也使得此类算法称为动态规划。

规划子任务的执行顺序是一项严肃的需要投入思考的事情，也是 bottom-up 思想相比 top-down 思想的额外付出，多一份的耕耘也给动态规划带来了效率上的收获，比如它可以在代码中避开或减少边界条件的检查，更好地利用内存中缓存连续性（缓存局部性），也减少了递归中函数调用的开销。然而，有些问题很难自底向上规划出一条明确的解决任务的路线，更多只能在递归（结合自动缓存）中自发地展现出问题解决的路线，比如汉诺塔问题。

假设在最小和路径问题基础上，要求算法能够返回路径和最小的路径，而不单单是最小的路径和。比如，下图中箭头指向的就是和最小的路径。

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+--v---+
|  1   |  5   |  1   |
|------+------+--v---+
|  4   |  2   |  9   |
+------+------+------+

具体来说，就是要返回 [(0,0),(0,1),(0,2),(1,2),(2,2)]

我们还是先以自顶向下的思路，对于 CEO 它只需要向两个助手提要求：”请给我到达你们手里的和最小的路径以及对应的和“，然后 从中挑选最小的那个并把自己所在的位置拼接到路径上。因此这与之前的问题多出来的要求是每个 s(i,j) 函数不单要返回数值，还要返回一个列表记录路径。

可以把 min_path_sum_cache 改写成如下函数，核心就是对 s(i,j) 接口上的适应，并且要用 if else 形式去找到更小的路径和以及路径，而不是用 min 直接获得更小的路径和。

import functools
def min_path_cache(grid):

    m, n = len(grid), len(grid[0])

    @functools.lru_cache(1000) #假设 m*n 最大 1000
    def s(i, j): # 用函数 s 记录 s[i][j]
        if i == 0 and j == 0:
            return grid[i][j], [(0, 0)]
        if i < 0 or j < 0:
            return float("inf"), []
        value_left, path_left = s(i-1, j)
        value_right, path_right = s(i, j-1)
        if value_left < value_right:
            value = grid[i][j] + value_left
            path = path_left + [(i, j)]
        else:
            value = grid[i][j] + value_right
            path = path_right + [(i, j)]
        return value, path

    return s(m-1, n-1)

grid = [[1,3,1],[1,5,1],[4,2,9]]
print(min_path_cache(grid))

(15, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])

对于动态规划，在具体做每一个小问题的时候，思路仍然和 top-down 方式是一样的，每次解决一个问题，都对当前任务所依赖的两个子任务中路径和更小（最优）的那个做一个标记，当解决最后一个问题时，要沿着标记反向把路径找出来。可以把 s[i][j] 改成存储两个变量：路径和 value 以及指向最优子问题的标记（指针） prev

把 min_path_sum_dp 改写成 min_path_dp：

def min_path_dp(grid):

    m, n = len(grid), len(grid[0])
    s = [[[0, None] for _ in range(n)] for _ in range(m)]
    s[0][0][0] = grid[0][0]
    # s[0][0][1] is None

    for i in range(1, m):
        s[i][0][0] = grid[i][0] + s[i-1][0][0]
        s[i][0][1] = (i-1, 0)

    for j in range(1, n):
        s[0][j][0] = grid[0][j] + s[0][j-1][0]
        s[0][j][1] = (0, j-1)

    for i in range(1, m):
        for j in range(1, n): 
            value_up, _ = s[i-1][j] # 不需要知道 prev 变量
            value_left, _ = s[i][j-1]
            if value_left < value_up:
                s[i][j][0] = value_left + grid[i][j] 
                s[i][j][1] = (i, j-1)
            else:
                s[i][j][0] = value_up + grid[i][j]
                s[i][j][1] = (i-1, j)

    path = []
    end = (m-1, n-1)
    while end:
        path.append(end)
        i, j = end
        end = s[i][j][1]
    return s[m-1][n-1][0], path[::-1]

print(min_path_dp(grid))

(15, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])

注意这里用了 value_left 和 value_up ，它表示的是 grid 里左侧和上方的位置，而上节递归中的 value_left, 和 value_right 表示的是递归树里左节点和右节点，它们和 grid 上的物理位置方向是无关的。

假设当前字符串 s, 长度是 n, 那么一种做法是，作为 CEO, 你找到 n 个助手，告诉他们，请你们分别把第 i 个字符删除，然后告诉我剩下的长度为 n-1 的各字符串的最长回文子序列长度是多少？然而这种做法会让自己变得困难：即便你拿到助手返回的 n 个数字，也无法根据这些数字计算出大目标的结果，因为问题中要求满足 "回文" 性质，光拿到助手告诉你的数字而没有能够判断回文的结构信息是无法完成最后一步决策的。

举个例子，如果你把手上的 "aba" 分给三个助手，他们分别拿到了 "ba","aa","ab", 然后返回了结果 0,2,0, 如果光看这三个数字，无法得到最后的结果 3.

你需要对删除字符的位置信息保持关注，比如第二个人返回了 2, 而你是把最中间的 b 删除了给他的，最中间意味着 b 不可能和其他额外的字符组成回文，它自身就是回文，因此你知道手上的 "aba" 回文子序列长度至少是 2+1. 支撑这个决策的关键是你记住了当前助手返回的结果是基于自己删除了最中间的字符后的字符串这个信息。

但这仍然不够，如果你手上的是 abba ，删除了 s[1], 即第一个 b 后得到 aba 交给了某个助手，返回了结果 3, 这时候你还需要考虑把 s[1] 加入之后是如何影响最长回文的，因此你继续要求助手额外返回它们发现的回文子序列的下标，比如 [0,1,2], 然后你根据删除的那个字符的下标去修正这个下标序列，变成 [0,2,3], 接着把 s[1] 的下标 1 拿出来，加入到这个下标序列，得到 [0,1,2,3], 检查一次这是否是回文，结果确实是回文，因此你返回了 [0,1,2,3]

问题在于，这还不够，因为最长回文子序列可能有多个，比如 abab, 其中 aba 和 bab 都是最长回文子序列，因此每次可能要返回多个结果，这使得你向助理索要的信息越来越多，助理的工作量越来越高，而由于每个人处理的问题是相似的（递归性），因此实际自己的工作量也越来越高，每个人都很累，结果还解决不了问题 …

上一轮失败的原因在于，分解成子问题时少了一点对回文性质的思考，你期望用一种不带"先验"信息的暴力分解方式：遍历式地对字符串每个字符进行删除，但这导致在回收信息和整理决策的时候付出巨大代价。

实际上，不需要找 n 个助手来解决问题，而是最多只需要三个，这种分解来自于一个关键的问题： "第一个字符和最后一个字符是否相同"

• 这个问题完全来自于回文性质的驱动，在字符串长度大于 2 的情况下，如果一个字符串的第一个字符和最后一个字符不同，那么这两个字符不可能同时出现在最长的回文子序列中, 这意味着要找到最长的回文子序列，只需要考虑以下两种情况之一：去掉第一个字符的子字符串 s[1:]， 或去掉最后一个字符的子字符串 s[:-1]。
• 如果一个字符串的第一个字符和最后一个字符相同，那么有可能这两个字符会在最终的最长回文子序列中， 因此你还需要额外找一个助手去解决 s[1:-1] 这个子问题，同时汇总 s[:-1] 和 s[1:]. 注意，有些情况下我们甚至可以不考虑 s[:-1] 和 s[1:], 但直到讨论了有关歧义的内容后才会额外说明。

问题树的分解如下，其中中间的分支是按条件选择的：

             +--------+
             | s[i:j] |
             +--------+
                | | |
     +----------+ | +-----------+
     |            |             |
+---------+  +----+-----+  +---------+
|s[i+1:j] |  |s[i+1:j-1]|  |s[i:j-1] |
+---------+  +----------+  +---------+

注意这里为了更方便说明， s[i:j] 表示的是起点是 s[i] 终点是 s[j] 的字符串，而不是 python 里去掉 s[j] 后的字符串，当然也可以把 s[i:j] 看作是自定义的函数 s(i,j), 表示起点和终点分别是 s[i] 和 s[j] 的字符串的最长回文子序列长度。

在这个定义下，考虑到边界条件：

• i==j 的时候，说明只有一个字符，因此最长回文长度是 1
• 如果 i>j 那么是空串，返回长度应该就是 0; 注意 i>j 只有在字符串长度为 2, 且 s[0]==s[-1] 情况下才会发生，因此我们也可以结合 len(s)==2 以及 s[0]==s[-1] 来联合判断，不过以下第一个实现中还是用 i>j 分支表示。

我们可以写出如下代码，@lru_cache 不带参数意味着大小是一直可增长的：

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1
        if i > j: return 0
        i_1 = sub(i+1, j)
        j_1 = sub(i, j-1)
        if s[i] == s[j]:
            return max(sub(i+1, j-1) + 2, i_1, j_1)
        return max(i_1, j_1)

    return sub(0, len(s) - 1)

longestPalindromeSubseq("abacab")

5

有了以上带记忆的递归版本后，本节考虑这个问题的动态规划版本。前文说过，动态规划需要在递归的基础上额外投入一点思考，即对解决问题的路径的“规划”，从最小的子问题开始，按规划去逐个解决更大一点的问题。

比如给定例子 "abacab":

• 要解决的最小子问题就是问 "a","b","a","c","a","b" 这些长度为 1 的子串的最长回文串长度，那么自然就是 1, 这个后文称为 unigram
• 长度为 2 的子串是 "ab", "ba", "ac", "ca", "ab", 称为 bigram
• 长度为 3 的子串称为 trigram

• 依此类推，这个时候我们可以重新画出类似上一章路径和里的格子图：

  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  |     |  a  |  b  |  a  |  c  |  a  |  b  |
  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  | a   |    1|    2|    3|    4>    5|    6|
  +-----+-----+-----+-----+-----+--^--+-----+
  |     |     |     |     |     |     |     |
  | b   |    0|    1|    2|    3|    4|    5|
  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  | a   |     |    0|    1|    2|    3|    4|
  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  | c   |     |     |    0|    1|    2|    3|
  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  | a   |     |     |     |    0|    1|    2|
  +-----+-----+-----+-----+-----+-----+-----+
  |     |     |     |     |     |     |     |
  | b   |     |     |     |     |    0|    1|
  +-----+-----+-----+-----+-----+-----+-----+
  

我们先解决对角线上标记为 1 的那些子问题，然后对角线上为 2 的子问题，而每个问题是直接依赖左侧和下侧格子的结果，此外还依赖左下格子（比上一章找路径的问题多出的额外依赖）

前文也分析过，i>j 会在字符串长度为 2, 且 s[0]==s[-1] 情况下发生，具体到图中，就是那些标记为 0 的斜线上的点会被访问，因此只需要对这些位置初始化为 0, 就可以很好地处理这种情况。

我们写出按对角线扫描的方式：

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n-2, -1, -1):
        for j in range(i + 1, n):
            cand = max(dp[i+1][j], dp[i][j-1])
            if s[i] == s[j]:
                cand = max(dp[i+1][j-1] + 2, cand)
            dp[i][j] = cand

    return dp[0][-1]

longestPalindromeSubseq("abacab")

5

然而，正如上一章最小路径和问题中更加偏向按行扫描的方式进行规划，本例也可以考虑按行扫描而不是按对角线扫描，但由于依赖关系总体是从主对角线往右上方移动的，因此不能从上往下按行扫描，而是从下往上，对应到具体的场景里，对于 "abacab", 应该先解决最后一个 unigram "b", 然后解决倒数第二个 "a" 以及最后一个 bigram "ab", 依次向上扫描每一行

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        for j in range(i+1, n):
            cand = max(dp[i+1][j], dp[i][j-1])
            if s[i] == s[j]:
                cand = max(dp[i+1][j-1] + 2, cand)
            dp[i][j] = cand

    return dp[0][-1]

longestPalindromeSubseq("abacab")

5

接着考虑不单单要获得最长回文子序列长度，还要获得这个子序列的下标的情况，经过一点思考会发现，最长回文子序列可能是有多个的，比如 "abca" 包括 "aba" 和 "aca" 两个长度为 3 的回文子序列。而 "abaa" 包括 "aba","aaa" 这个两个，并且 "aba" 可以对应下标 [0,1,2] 和 [0,1,3] 两个子序列，因此如果问题改成

给你一个字符串 s ，找出其中最长的回文子序列。

那么这个问题对于不同的人是有不同结果的，因此这会导致"歧义"。可以把问题改成

给你一个字符串 s ，找出其中所有的最长的回文子序列，用序列下标方式返回。

对于自顶向下的递归方式：

• 首先 sub 函数应该返回两个对象：最长回文子序列长度以及最长回文子序列集合。

• 我们用 left,mid, right 区分以下三种子情况，并且分别比较它们返回结果中序列长度的部分，根据大小关系返回不同序列组合

               +--------+
               | s[i:j] |
               +--------+
                  | | |
       +----------+ | +-----------+
       |            |             |
  +---------+  +----------+  +---------+
  |s[i+1:j] |  |s[i+1:j-1]|  |s[i:j-1] |
  +---------+  +----------+  +---------+
     left          mid         right
  

函数实现如下

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1, [[i]]
        if i > j: return 0, []
        len_left, res_left = sub(i+1, j)
        len_right, res_right = sub(i, j-1)
        if len_left > len_right:
            len_cand, res_cand = len_left, res_left
        elif len_left < len_right:
            len_cand, res_cand = len_right, res_right
        else:
            len_cand = len_left
            res_cand = res_left + res_right
        if s[i] == s[j]:
            len_mid, res_mid = sub(i+1, j-1)
            if len_mid + 2 > len_cand:
                return len_mid + 2, [[i] + res + [j] for res in res_mid]
            elif len_mid + 2 == len_cand:
                return len_cand, [[i] + res + [j] for res in res_mid] + res_cand
        return len_cand, res_cand

    return sub(0, len(s) - 1)

print(longestPalindromeSubseq("abacab"))
print(longestPalindromeSubseq("abca"))
print(longestPalindromeSubseq("abaa"))

(5, [[1, 2, 3, 4, 5]])
(3, [[0, 2, 3], [0, 1, 3]])
(3, [[0, 2, 3], [0, 1, 3], [0, 1, 2]])

接着考虑动态规划方式，我们基于上一节中从下往上扫描的算法来修改，核心就是，在每个 grid 格子里，那些对最长回文子序列有贡献的格子做上标记，为了保持原本的 dp 数组接口不变，这里引入新的 mark 数组来记录 每个子问题里的符合要求的回文序列下标：

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    mark = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        mark[i][i] = [[i]]
        for j in range(i+1, n):
            if dp[i+1][j] > dp[i][j-1]:
                cand = dp[i+1][j]
                mark[i][j] = mark[i+1][j]
            elif dp[i+1][j] < dp[i][j-1]:
                cand = dp[i][j-1]
                mark[i][j] = mark[i][j-1]
            else:
                cand = dp[i+1][j]
                mark[i][j] = mark[i+1][j] + mark[i][j-1]
            if s[i] == s[j]:
                if dp[i+1][j-1] + 2 > cand:
                    cand = dp[i+1][j-1] + 2
                    mark[i][j] = [[i] + x + [j] for x in mark[i+1][j-1]]
                elif dp[i+1][j-1] + 2 == cand:
                    mark[i][j].extend([[i] + x + [j] for x in mark[i+1][j-1]])
            dp[i][j] = cand

    return dp[0][-1], mark[0][-1]

print(longestPalindromeSubseq("abacab"))
print(longestPalindromeSubseq("abca"))
print(longestPalindromeSubseq("abaa"))

(5, [[1, 2, 3, 4, 5]])
(3, [[0, 2, 3], [0, 1, 3]])
(3, [[0, 1, 2], [0, 2, 3], [0, 1, 3]])

这部分完全是一些算法优化技巧，可以跳过

现在我们再回到最初的问题，即只返回回文的长度，而不考虑所有子序列。实际上当 s[i] == s[j] 的时候，dp[i+1][j-1] + 2 就是唯一结果。

原因可以引用 参考 leetcode 里某用户回答：

以 dp[i+1][j]为例，设 dp[i+1][j]中的回文子串最大值为 m。

若回文子串中不包含 s[j]，那么 dp[i+1][j]=dp[i+1][j-1]，那 dp[i+1][j-1]+2 肯定大于 dp[i+1][j]。

若回文子串中包含 s[j]，在 dp[i+1][j]中的最大回文串中，我们掐头去尾，删除 s[j]和某个等于 s[j]数，寻找内部 dp[i+1][j-1]中最大回文子串，其最大值为 m-2，即 dp[i+1][j-1]=m-2=dp[i+1][j]-2。等式两边同时加上 2，就有 dp[i+1][j-1]+2=dp[i+1][j]。

综上所述 dp[i+1][j-1]+2>=dp[i+1][j]。

@尚小锋

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1
        if i > j: return 0
        if s[i] == s[j]:
            return max(sub(i+1, j-1) + 2, sub(i+1, j), sub(i, j-1))
        return max(sub(i+1, j), sub(i, j-1))

    return sub(0, len(s) - 1)

longestPalindromeSubseq("abacab")

5

动态规划形式：

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][-1]

longestPalindromeSubseq("abacab")

5

上文都是在讨论 leetcode 里的玩具模型，它能够让我在一个理想环境中看待算法本身，本节则把注意力转移回到现实中的问题 – 语言的解析，但在真正进入算法前，还需要介绍一点理论背景。

在计算机科学中，没有特别说明时，语言指的就是符合某种规则的字符串的集合。比如说所有的回文就组成了一种语言（生活在回文星球的人可能说的就是回文），因为所有的回文 s 都符合以下规则：

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome(""),is_palindrome("a"),is_palindrome("aba"))

True True True

这种描述语言的规则一般称为语法（语言的法则），Chomsky 在 1960 年代根据描述语言规则的复杂性对语言进行了划分，这里我用一个类比来说明对语言如何进行划分以及划分的动机。

首先，对某种事物进行精确分类的样板是在数学之中，比如关于整数就有非常多不同的划分：自然数，偶数，奇数，完全平方数，素数等等

对于这些数可以提出至少两个需求：

• 判定需求：给定一个数，判断它是不是某个类型的数，比如是不是平方数
• 生成需求：请生成 1000 到 2000 之间的所有素数

这些判断和生成的需求会对应不同的难度，比如判断某个数是否是素数就比判断某个数是否是偶数更难。然而即便判断素数更难，但我们知道，判定是否为素数这个算法是存在的，因为素数的定义有一种 “分解”性质：判断 n 是否为素数，只需要找比 n 小的数（且大于 1 的正数）作为除数去除 n 就可以，“比 n 小的大于 1 的整数”这个性质使得问题是可控的（就像 top-down 方法里针对的问题是可以往更小的方向分解的）。

另外，对于偶数，判定规则和生成规则的难度是类似的，都一样简单，比如可以根据 n 是否可以被 2 整除来判断 n 是否为偶数，也可以在给定一个范围 [a,b] 后，如果 a 是偶数，那么就用 x=a, x+=2 的算法来不断生成偶数，直到这个值超过 b 。 但对于素数，判定算法和生成算法则不太一样，标准的判定算法以上已经提到，但生成素数则还有筛选法等各种基于判定算法的变种，这里主要是突出，有些数的分类中，判定和生成可能很不一样。

数学里还有一个叫做 3n+1 的猜想（也叫 Collatz 猜想，奇偶归一猜想，冰雹猜想等等，参见 考拉兹猜想 - 维基百科，自由的百科全书）, 它说的是，给定任何一个数 n，如果这个数是偶数，那么把这个数重新赋值成 n/2, 如果是奇数，那么重新赋值成 n=3n+1, 如果依次迭代下去，最终 n 等于 1, 那么就称它为 Collatz 数，这个猜想是说：所有正整数都是 Collatz 数。

然而，之所以这是一个猜想，是因为目前为止它还是未解之谜，也就是说，给定任意一个数，我们不一定能确认它是否为 Collatz 数，同样的，我们也无法找到一个可靠的算法（一定会停止），生成所有的 Collatz 数。相比来说，我们很容易写出一个算法找出所有素数（尽管效率很低并且会永远执行下去，但我们知道它返回都是素数，并且不会有遗漏），而无法找出所有 Collatz 数的一个很宽泛但也有用的解释是： collatz 数产生或判断的规则中，不单单有朝着数字减小的方向（n/2），也有增大的方向（3*n+1) ，数字增大的方向可能导致算法永远无法回到一个 basecase(也就是 n=1)，而判断素数的规则里只涉及比 n 小的数。

现在类比回到语言，如下 5 是数字，而字符串就是语言

5
"abcba" # 语言

对于一个语言，我们也有两个需求：

• 判定：这是否是回文、英文、中文
• 生成：生成所有长度为 4 的英文回文，生成诗歌

Chomsky 的贡献之一是，他发现自然语言的句法结构可以通过生成规则来描述，并且试图通过分析生成规则的复杂性从而理解语言的复杂性，正如可以通过研究数的判定/生成规则来研究数的性质。(其思想被吸收到计算机科学后，人们发展出可以通过分析生成规则来获得判定的方法，也就是后文要讲的语言解析相关的技术）

用一个例子说明基于句法结构的生成规则和其他规则的差别，我们可以定义一种语言，看到 a 之后生成 c, 看到 c 之后生成 b, 看到 b 之后生成 a, 我们可以用以下方式返回生成该语言中特定长度的句子的函数

def abc_rule(n):
    def _rule(cur_char):
        sentence = ""
        for i in range(n):
            sentence += cur_char
            if cur_char == "a":
                cur_char = "c"
            elif cur_char == "c":
                cur_char = "b"
            elif cur_char == "b":
                cur_char = "a"
            else:
                return ""
        return sentence
    return _rule

因此如果第一个字符是 a 就得到以下句子：

abc_rule(10)("a")

acbacbacba

如果第一个字符是 b:

abc_rule(10)("b")

bacbacbacb

如果是其他字符则返回空串：

abc_rule(10)("x")

''

以上这种生成规则是基于字符序列之间的关系或者状态来定义的，它看上去是水平方向的，是扁平的：规则是针对字符实例来描述的，不太具有结构性。

当我们说"公司的结构"时，很多时候实际是在谈论这个公司对职位等级的划分，句法的结构也是如此，给定一个句子，我们不单单看到一个一个的词，还会看到他们的标签（某个员工的职位），它们组成的团体的标签（组、部），因此当要组建一个开发团队时，我们可能先考虑到的是找到某个开发过类似产品的部门，从里面找一个产品经理，三四个开发，一两个测试，然后再根据这个层级的规划，去找根据职位找到对应的人选。

句法结构的生成规则也是如此：我们想表达某个句子的时候，先是想到了这应该有个主体、一个动作以及宾语，然后再替换成具体的表达某个对象的词。

这种做法实际非常反直觉，因为人在造句的时候似乎不会用"公司管理" 中分层派发任务的办法，却更像上文提到的基于字之间关系而生成的。 但问题在于，Chomsky 之前也没有人能提出一套比较有说服力的理论解释人是如何掌握和使用语言的，Chomsky 的贡献就在于，这套很不明显的规则被他表达了出来，并且他认为这是大脑潜意识里生成语言时所遵循的结构，从而把语言学、认知科学、教育学、哲学、人类学（比如他还认为人类可能在十万到五万年前因为基因突变，导致了递归枚举能力，来源： 尼克｜乔姆斯基 vs ChatGPT_上海书评_澎湃新闻-The Paper ）等领域都串起来了，而这套精确的语法定义在计算机科学里又被进一步发展和应用。

(注：如今 chatgpt 的预训练方式和 Chomsky 理论是有冲突的，chatgpt 完全就是基于前文提到的字符实例的前后关系来进行句子生成的，即根据上文的词预测下一个词，从训练手段来看，这是纯粹扁平而无结构的，但 gpt 目前无法形成一套解释性理论来反驳 Chomsky)

因此，假设有一套以下的语法规则：

S -> NP VP （一个句子由名词短语和动词短语组成）
NP -> Det N （名词短语由限定词和名词组成）
NP -> N （名词短语也可以直接是名词）
VP -> V NP （动词短语由动词和名词短语组成）

按照 Chomsky 的理论， 我说话时潜意识是这样的：一个句子由名词短语和动词短语组成，名词短语只能是名词或者限定词加名词，动词短语只能是动词接一个名词短语。而由于当前所看到的景象，动词、冠词、名词的生成规则几乎被限定如下：

V -> 追
Det -> 一只
N -> 苍蝇 
N -> 小猫 (当前脑子里只想到了苍蝇和小猫，可能眼前就是它们)

因此我不需要有意识地去组织句子或思考，大脑对语言结构本身的理解就促使我说出了一句 "小猫追一只苍蝇”，而这是符合语法的。

反过来，当看到 "小猫追一只苍蝇" 时，可以构建出一棵语法解析树：

          +--------+
    +-----|   S    |--------+
    |     +--------+        |
+--------+            +-----------+
|   NP   |        +---|     VP    |---+
+--------+        |   +-----------+   |
    |             |                   |    
+---+----+   +---------+          +-------+
|   N    |   |    V    |       +--|  NP   |---+
+--------+   +---------+       |  +-------+   |
    |             |         +------+       +-----+
    |             |         | Det  |       |  N  |
    |             |         +------+       +-----+
    |             |            |              |
+-------+     +-------+     +------+       +-----+
| 小猫   |     |  追   |     | 一只  |       | 苍蝇 |
+-------+     +-------+     +------+       +-----+

注意这种生成规则是天然地从抽象层级向下不断递归发展的过程（递归下降）。

而如果我们从下往上看，最底层是具体的词，向上一层是这些词的词性，再上一层是对词性级别按照规则的组合，最终组成了一个句子 S。

后文会继续回顾这种类型的树，当前先回到语法的描述上，以上例子中给出的语法被称为 context free grammar （CFG），它是 Chomsky 对语法结构划分的类别结果之一，被称为 Chomsky 2 型文法，它的核心特点在于，生成规则的左边只有一个变量，也就是说生成规则一定是扩展性质的规则，而不会缩减，同时右边任意位置都允许出现左边已经出现过的变量（即允许递归定义），这种语法描述的字符串就像是整数分类里的素数，足够复杂，但却是可控的（可以递归到 basecase）。

如果在规则中出现 VP VP-> VP, 那么这说明一个句子在生成的过程中，它的描述长度可能会缩减，因此当在反推这个语言的结构时，发现其中有一部分是 VP(比如动词短语"追苍蝇"）, 而查看规则后发现 VP 竟然是可以根据两个 VP 缩减而来，因此 "追苍蝇" 这句话的语言结构可能有任意多的 VP （只不过都被这个规则消解了），因此该语言结构可能有无限多种，变得复杂，这可以类比到 3n+1 猜想。这种语法对应的语言称为 0 型文法，当然还有 1 型（上下文相关语言）和 3 型（正则语言），数值越大，限制越强：

Chomsky hierarchy:

/-------------------------------------------\
|                                           |
|     Recursively enumerable languages      | Type 0: γ->α
|                                           |
|   /-----------------------------------\   | <- recursive language(type 0.5)
|   |                                   |   |
|   |    Context-sensitive languages    |   | Type 1: αAβ->αγβ
|   |                                   |   |
|   |   /---------------------------\   |   |
|   |   |                           |   |   |
|   |   |  Context-free languages   |   |   | Type 2: A->α
|   |   |                           |   |   |
|   |   |   /-------------------\   |   |   |
|   |   |   | Regular languages |   |   |   | Type 3: A->aB|a
|   |   |   \-------------------/   |   |   |
|   |   \---------------------------/   |   |
|   \-----------------------------------/   |
\-------------------------------------------/
α： terminal
A,B： non-terminal
α，β，γ： string of terminals and/or non-terminals

注：图片基于 The true power of regular expressions, 对这些语言的更多介绍也可参考该链接。

上一节中，我们介绍了语法，用来描述某一类字符串，其中引入了一个语法例子：

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

V -> 追
Det -> 一只
N -> 苍蝇 
N -> 小猫 

要注意的是，以上代码也是一串字符串，因此它也是某种语言，具有某种规则，比如每行有一个箭头，箭头左边只有一个变量，右边有多个，从左到右的箭头表示左边的变量可以被右边的变量组合替换掉，这种描述语法的语言可以称为元语法，或者叫做范式。语言的有趣和混乱就来自于描述语言的对象也是语言，而这可以无限递归下去，不过在实现上，必须找到一个递归的终点，而一般到范式层就算是终点了。

可以很容易用另外一种形式来描述相同的语法，比如最简单的，把箭头改成冒号：

S   : NP VP 
NP  : Det N 
NP  : N 
VP  : V NP 

V   : 追
Det : 一只
N   : 苍蝇 
N   : 小猫 

对于最后两条规则，即名词可以被"苍蝇"替换，也可以被 "小猫" 替换，这是一个集合，因此可以写成：

N   :{"苍蝇","小猫" }

这种精简后的语法称为巴科斯范式（Backus-Naur Form，BNF），标准的 BNF 范式如下

S   ::= NP VP 
NP  ::= Det N 
NP  ::= N 
VP  ::= V NP 

V   ::= 追
Det ::= 一只
N   ::= 苍蝇 | 小猫

也就是说生成符号用 ::= 表示，而集合关系用 | 表示，但实际用这些符号并不重要，BNF 范式的核心是其结构，从左到右生成，并且右侧支持集合这种表示，比如以下是用 python 列表对以上语言的 BNF 文法表示：

simple_grammar = [
  ("S " , ["NP", "VP"]) ,
  ("NP" , ["Det", "N"]) ,
  ("NP" , ["N"] ),
  ("VP" , ["V", "NP"] ),
  ("V"   , "追"),
  ("Det" , "一只"),
  ("N " , {"苍蝇", "小猫"}),
]

接着，可以看到，以上有两类很不一样的符号，一组是 "NP", "VP"， "S" 这样的结构性描述变量，比如 S 是对句子的标签，NP 是对短语的标签，另一组如 "V", "Det","N" 是对词的标签，而 "追", "一只", "苍蝇", "小猫" 这些是具体的词库。

对于最后三条规则，类似于替换的终点（递归树的叶子节点），因为一旦执行到这些规则，至少在该分支下就无法继续替换了

simple_grammar_lexicon = [
  ("V"   , "追"),
  ("Det" , "一只"),
  ("N " , {"苍蝇", "小猫"}),
]

这部分规则称为 POS category, 它描述了所有可能的用词以及这些用词的语法标签（动词、名词形容词等）, 也称 lexicon 。甚至严格来说，这部分不是语法，因为它没有描述语言组件之间组合的规则，而只是各个词的可能类别。

simple_grammar 的另一部分如下，这里描述的纯粹是句子的组成规则，规则的两边都是抽象变量，它是递归树里非叶子节点部分，也称为 CFG rules 。

simple_grammar_cfg_rules = [
  ("S " , ["NP", "VP"]) ,
  ("NP" , ["Det", "N"]) ,
  ("NP" , ["N"] ),
  ("VP" , ["V", "NP"] ),
]

对 rules 和对 lexicon 的区分可以带来实践上的灵活性， 比如有些场景下只需要分析词库，那么只需要 lexicon，但如果要进一步做句法分析，则需要把 cfg rules 也带上。

有很多其他范式可以描述 CFG 语法，比如 Grammatical Framework, 其一个例子如下（来自 Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning - ACL Anthology Appendix B）：

abstract Food = {
flags startcat = Comment ;
cat
Comment ; Item ; Kind ; Quality ;
fun
Pred : Item -> Quality -> Comment ;
This , That : Kind -> Item ;
Mod : Quality -> Kind -> Kind ;
Wine , Cheese , Fish : Kind ;
Very : Quality -> Quality ;
Fresh , Warm , Italian , Expensive , Delicious , Boring : Quality ;
}

GPT 对以上例子的解释是：

现在假设有以下 CFG 语法（该例子基于 Probabilistic CKY Algorithm）：

cfg_rules = [
  ["S" , ["NP", "VP"]],
  ["NP" , ["Det", "N"]],
  ["VP" , ["V", "NP"]],
]
  
lexicon = [
  ["V" , "includes"] ,
  ["V" , "price"],
  ["Det" , "the"],
  ["Det" , "a"],
  ["N" , "price"]
]

现在希望设计一个算法，能够给定一个通过该语法规则所生成的句子，比如 "The price includes a facemsk" 返回这个句子的语法构成，它可以是解析树的一种表达式。比如手动解析的话， "The price" 应该是名词短语，它由冠词 The 和名词 price 组成，includes a facemask 是动词短语，它由动词 includes 和 a facemask 名词短语组成，而后者又继续由冠词和名词构成，因此这句话和 "小猫追一只苍蝇" 的解析树是很像的，只是第一个名词短语是冠词加名词，而不是一个名词，它的解析树如下：

                   +--------+
             +-----|   S    |--------+
             |     +--------+        |
         +--------+            +-----------+
  +------|   NP   |        +---|     VP    |---+
  |      +--------+        |   +-----------+   |
  |          |             |                   |    
+-----+  +---+----+   +---------+          +-------+
| Det |  |   N    |   |    V    |       +--|  NP   |---+
+-----+  +--------+   +---------+       |  +-------+   |
  |         |             |         +------+       +-----+
  |         |             |         | Det  |       |  N  |
  |         |             |         +------+       +-----+
  |         |             |            |              |
+-----+ +-------+    +---------+    +------+      +--------+
| the | | price |    |includes |    |   a  |      |facemask|
+-----+ +-------+    +---------+    +------+      +--------+

有许多表示这种树的方法，比如嵌套的方式（只给出 includes a facemask 部分）

(VP (V includes) (NP (Det a) (N facemask)))

也可以返回一个树的表征，比如返回 root 对象，其中包括子树 NP, VP 对象的索引

本节用 CKY 算法来解决这个问题，CKY 是三个科学家的名字，因此有时候也叫 CYK.

CKY 的思路的展开和前文中寻找最长回文子序列的 grid 非常类似，从最短的子串开始，在长度这个维度上逐渐增加并分步解析。 解析实际就是在做抽象，比如说，当你知道熊猫是一种动物的时候，再看到熊猫时说这是动物，这就是抽象的过程。

在字符串解析中，第一步抽象也就是对每个词(长度为 1 的字符串)找到它的词性标签, 标记在对角线上，因为对角线表示的就是 s[i:i+1] 这个词。

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det |        2|       3 |        4|        5|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |        2|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

注意 price 一词可以是动词也可以是名词，因此两种可能都要标上。

接着考虑长度为 2 的序列，也就是以下 bigram 是什么语法结构

from pprint import pprint
s = "The price includes a facemask".split()
pprint([s[i:i+2] for i in range(len(s)-1)])

[['The', 'price'], ['price', 'includes'], ['includes', 'a'], ['a', 'facemask']]

这里的核心在于，由于在文法中区分了 Grammar rule 和 lexicon , 因此我们不需要从具体的 string pair （比如 "the price","price include"）来分类，而只需要根据上一步解析的词的词性的组合进行分类，比如当考虑 "The price" 是属于什么语法类别时，只需要对 Det N 组合以及 Det V 组合进行分类，从语法规则里逆向匹配发现 Det N 有语法标签的 NP, 而 Det V 则没有语法标签，因此对于 The price, 只有 NP 这个语法标签，我们写在第 1 行第二列：

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det | ->  NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |     ↑   |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |        2|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

从 grid 操作上看，我们就是从当前格子的左边和下方读取标签，然后组合起来，再到语法表中去进行匹配，找到合适的分类。 用这种方式可以把所有 bigram 都进行语法分类，如果没有分类，则保留表示长度的数字，得到如下结果

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det | ->  NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |     ↑   |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det | ->    NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |       ↑ |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

接着考虑 trigram, 也就是长度为 3 的子序列，如下

s = "The price includes a facemask".split()
pprint([s[i:i+3] for i in range(len(s)-2)])

[['The', 'price', 'includes'],
 ['price', 'includes', 'a'],
 ['includes', 'a', 'facemask']]

从这里开始，格子操作和回文判断有所不同了，我们不能继续取左边的格子和下方的格子拼接起来，比如，假设 grid[0][2] 表示的是 "The price includes" 子字符串的语法分类，如果从它左侧格子 grid[0][1] 和下方格子 grid[1][2] 进行判断的话，就相当于认为 "The price includes" 是根据 "The price" 和 "price includes" 这两个子串拼接起来的，但事实上是 "The price includes" 的子串分解有两种情况：

1. "The price" + "includes": 对应的是 grid[0][1] 和 grid[2][2]
2. "The" + "price includes": 对应的是 grid[0][0] 和 grid[1][2]

对于第二种分解情况，如下图所示：

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |        ------------->       |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |      ↑ 3|        4|        5|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

这里由于 grid[1][2] 没有语法标签，因此组合后的子串也没有语法标签

接着看 grid[0][2] 的另一个依赖，它要求对 NP V 组合找到标签，结果也没有：

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |      ----->       |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |      ↑ 3|        4|        5|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
price    |         |         |      |  |         |         |
         |         |     N/V |      | 2|        3|        4|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

用更精确的语言来描述就是， s[i][j] 的依赖是 s[i][j-k] 以及 s[i+(len-k)][j], 这里 len 就是当前处理的子串长度，此时 3, 按这个方式填补完长度为 3 的子序列对应的其他格子，只有 grid[2][4] 也就死 includes a facemask 才有对应的有效标签

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |       ----------------> VP  |
         |         |         |       V |        2|      ↑ 3|
         +---------+---------+---------+---------+------|--+
         |         |         |         |         |      |  |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

同理，对长度为 4 的子串寻找标签，那么 len 就是 4. 它包括两个子句 "The price includes a" 和 "price includes a facemask", 按照前文提到方法，检查各种组合发现都没有语法标签存在。

最后进入到长度为 5 的字符串，这就是句子本身，可以发现 grid[0][4] 从 grid[0][1] （对应 NP） 和 grid[2][4] （对应 VP） 上能够找到一个语法标签，即 S, 如下：

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |       ------------------------> S     |
         |     Det |     NP  |        3|        4|   ↑    5|
         +---------+---------+---------+---------+---|-----+
         |         |         |         |         |   |     |
price    |         |         |         |         |   |     |
         |         |     N/V |        2|        3|   |    4|
         +---------+---------+---------+---------+---|-----+
         |         |         |         |         |   |     |
includes |         |         |         |         |     VP  |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

以上例子中，我们之所以可以只从格子的左侧和下方两个方向作为依赖，是因为给出的 CFG rules 规则中，右侧的数组长度都是 2:

cfg_rules = [
  ["S" , ["NP", "VP"]],
  ["NP" , ["Det", "N"]],
  ["VP" , ["V", "NP"]],
]

比如 "S" : ["NP", "VP"] 表示对于一个句子可以切成两个子串，左子串的标签是 NP, 对应格子的左边，右子串的标签是 VP 对应格子的下方。

问题在于，是否所有 CFG 规则都能写成这种形式呢？ Chomsky 证明可以把所有 CFG rules 都写成右侧只有两个变量的情况，这种形式称为 CNF 形式(Chomsky Normal Form), 它要求所有规则必须是以下两种形式之一：

A -> BC（其中A、B和C是非终结符，B和C不能是开始符号）
A -> a（其中A是非终结符，a是终结符）

注意第二条也可以扩展到右侧可以是多个终结符的集合。

证明方法是，考虑所有生成规则的形式，对这些形式构建对应的转换规则，将其转为 CNF 形式：

• 消除右侧大于 2 个变量的情况

  A->BCD
  

  可以引入一个额外的语法标签 I

  A->BI
  I->CD
  

  对于右侧有更多的情况，只需要引入更多层级的规则。

• 消除混合右部（非终结符和终结符混合出现）的产生式。

  A->Ba
  

  这里 B 是变量（非终结符号或语法标签），a 是具体的词 这时候可以对 a 引入单独的一个语法标签 I：

  I->a
  A->BI
  

  对于更多混合的情况，比如 A->BCdef, 则结合本条规则和上一条规则

• 消除右侧只有一个变量的情况

  A -> B
  

  注意我们不能引入一个表示空字符串的非停止符号 E，比如 A->BE, 这种情况没有意义，因为在格子世界中，相当于要去检查一个空串的标签，也就是类似 grid[-1][2] 的元素，这没有什么意义。

  消除方法是，根据前两条规则，实际上对于 B 它要么是生成两个非终结符，如 B->CD, 要么是生成终结符如 B->b, 因此 B 的展开规则已经是 CNF 了，因此只需要把 B 替换成 CNF 替换的结果之后就变成

  A -> CD
  //or
  A -> b
  

所以 CNF 形式实际是于抽象的格子世界形式上的对齐，另一方面它使得递归形式很规范，递归的树是一棵二叉树。

首先回忆一下 回文里歧义的例子，比如 abaa 里有三个子序列都是回文：

print(longestPalindromeSubseq("abaa"))

(3, [[0, 1, 2], [0, 2, 3], [0, 1, 3]])

对应到语法解析中，歧义就是给定一个句子，算法解析出了不止一棵的解析树，而放在句子本身，就是不同的人对这个句子有不同的理解。 然而这个说法还是宽泛了，自然语言中歧义有很多种，包括词的歧义，比如 I went to the bank, 这里 bank 可以是银行也可以是河岸，这句话本身就不是上下文无关的，因此 CKY 或任何解析 CFG 的算法都无法处理。

而我们本节讨论的是自然语言里歧义的某个子集，首先这些句子基本能够被上下文无关文法描述，因此可以被 CKY 算法解析，但解析之后还是有语法结构上的歧义，比如一个经常拿来说明结构性歧义的例子

One morning I shot an elephant in my pajamas.

Groucho Marx, Animal Crackers, 1930

这里 I shot an elephant in my pajamas 的 in my pajamas 可以和 an elephant 组合成一个名词短语，表示穿着睡裤的大象，也可以和 shot an elephant 组合成一个动词短语，表示我穿着睡裤射击了一头大象（这里还有歧义，比如也可以解释成我在睡裤里射击了大象，但这是语法结构无法区分的）。

这种介词可以跟随不同对象而发生的歧义在英文里不少见，因此还有一个专门的名字来描述： PP-attachment 歧义。

人类在读到有歧义句子时，可能会说，我觉得它应该更倾向于这种意思 …, 也就是说人类会通过概率性地比较来试图消除歧义，把这中想法放到算法里就是概率话的 CKY, 这里的核心就是对返回的解析树赋予一个概率，如何赋予？这里做法是，对每个生成规则附加一个概率，动态规划中每次找到一个合并规则时，就把这个概率附加进去。用 I shot an elephant in my pajamas. 的例子来说明，

imp_cfg_rules = [
  ["S" , (1, ["Pronoun", "VP"])],
  ["VP" ,(0.6, ["V", "NP"])],
  ["NP" ,(0.6, ["Det", "Nominal"])],
  ["NP" ,(0.4, ["Det", "N"])],
  ["Nominal", (1, ["N", "PP"])],
  ["VP" ,(0.4, ["VP", "PP"])]
]

imp_lexicon = [
    ["Pronoun" , (0.3, "I")],
    ["V" , (0.2, "shot")],
    ["V" , (0.5, "like")],
    ["Det" , (0.4, "the")],
    ["Det" , (0.2, "an")],
    ["PP" , (1, "in my pajamas")], 
    ["N" , (1, "elephant")]
]

这里把 "in my pajamas" 看作一个符号，后文有时候直接简称为 imp

就好比前文中 leetcode 题要求造出一个字符串有多少回文子序列，本节则给定一个字符串用 CKY 算法找出该句子在某个语法规则下有多少种解释。

我们不考虑分词，而是把分词结果作为算法输入，那么输入的就是：

pajamas = ["I", "shot", "an", "elephant", "in my pajamas"]

定义递归函数 s(i,j) 表示句子 sent[i:j+1] 可能包含的解释数量，但有这个统计值还不够，我们每一步子问题分解过程中，还需要知道子句子的语法标签，可以定义 g(i,j) 表示 sent[i:j+1] 的语法标签，比如可以是 "V", "Det" 也可以是 None

那么可以写出递归的表达式：

g(i,j) = sum([rule(g(i,k), g(k+1,j)) for k in range(i, j)])
s(i,j) = len(g(i, j))

rule([a,c], [b]) 会先对两个参数做笛卡儿积，比如得到 [a,b], [c,b], 然后分别去 grammar rules 中找生成规则是这些结果的变量名，返回所有结果，如果没有，则返回 []

base case 中，如果 g(i,i+1) 则是从 lexicon 里搜索到的 POS 集合，只需要计算函数 g

编写这个算法：

from functools import lru_cache
from itertools import product
def cky_num(s: str) -> int:
    @lru_cache
    def g(i, j):
        if i == j: return pos(s[i])
        res = sum([rule(g(i,k), g(k+1, j)) for k in range(i, j)], [])
        return [x for x in res if x]

    return g(0, len(s) - 1)

def pos(token):
    return [p for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [pos for pos,(prob, toks) in imp_cfg_rules if toks == [t1,t2]]
        res.extend(x)
    return res

print([pos(x) for x in pajamas])
print(rule(["Det"], ["N"]), rule(["Det"], ["Nominal"]))
print(cky_num(pajamas))

[['Pronoun'], ['V'], ['Det'], ['N'], ['PP']]
['NP'] ['NP']
['S', 'S']

这里看到，这句话有两种不同的语法结构，也就对应两种解释

现在继续扩展，不单单要给出解释的数量，还要给出这些解释所对应的语法树以及该语法树下解释的概率。

对于递归情况，可以把每个阶段的解析树返回，而不单单返回树的根节点，这里我们用嵌套列表来表示树：

from functools import lru_cache
from itertools import product
cky_trees = cky_num

def pos(token):
    return [[p] for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [[pos, t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]
        res.extend(x)
    return res

print([pos(x) for x in pajamas])
pprint(cky_trees(pajamas))

[[['Pronoun']], [['V']], [['Det']], [['N']], [['PP']]]
[['S', ['Pronoun'], ['VP', ['V'], ['NP', ['Det'], ['Nominal', ['N'], ['PP']]]]],
 ['S', ['Pronoun'], ['VP', ['VP', ['V'], ['NP', ['Det'], ['N']]], ['PP']]]]

注意这里只修改了 pos 返回结果的部分

return [p for p,(prob, tok) in imp_lexicon if tok == token]
# 改成
return [[p] for p,(prob, tok) in imp_lexicon if tok == token]

rule 函数中

x = [pos for pos,(prob, toks) in imp_cfg_rules if toks == [t1,t2]]
# 改成
x = [[pos, t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]

接着把概率也加进去：

def pos(token):
    return [[p, prob] for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [[pos, prob*t1[1]*t2[1], t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]
        res.extend(x)
    return res

cky_prob_trees = cky_num
print([pos(x) for x in pajamas])
pprint(cky_prob_trees(pajamas))

[[['Pronoun', 0.3]], [['V', 0.2]], [['Det', 0.2]], [['N', 1]], [['PP', 1]]]
[['S',
  0.00432,
  ['Pronoun', 0.3],
  ['VP',
   0.0144,
   ['V', 0.2],
   ['NP', 0.12, ['Det', 0.2], ['Nominal', 1, ['N', 1], ['PP', 1]]]]],
 ['S',
  0.001152,
  ['Pronoun', 0.3],
  ['VP',
   0.0038400000000000005,
   ['VP',
    0.009600000000000001,
    ['V', 0.2],
    ['NP', 0.08000000000000002, ['Det', 0.2], ['N', 1]]],
   ['PP', 1]]]]

至于 cfg_rules 和 lexicons 里概率从何而来，这就是统计学习的知识，本文不展开，如有兴趣可以阅读 https://web.stanford.edu/~jurafsky/slp3/17.pdf, 对本章以及上一章里提到的关于语法的知识的更详细描述也可参考此书。

我们先构造那些只解析一个字符的 parser, 比如只识别 a 或者数字，为了避免对识别没给字符都首先一个这样的 parser, 可以构建一个通用的工厂函数，输入对象识别条件，返回一个根据该条件对字符串拆解的 parser:

def satisfy(predicate):
    def inner(s):
        head, tail = s[0], s[1:]
        if predicate(head):
            return head, tail
        raise Exception('Predicate not satisfied')
    return inner

这样，可以用 satisfy 构建出一个识别任何字符的 parser:

def any_char(s):
    return satisfy(lambda x: True)(s)

print(any_char("abc"))
print(any_char("bc"))
print(any_char("c"))

('a', 'bc')
('b', 'c')
('c', '')

接着构建出识别给定某些集合里词（或字符）的 parser, 比如对上文提到的 leicon ("N " , {"苍蝇", "小猫"}) 的解析

def one_of(chars):
    return satisfy(lambda x: x in chars)

print(one_of(["小猫","苍蝇"])(["小猫","追", "一只", "苍蝇"]))

('小猫', ['追', '一只', '苍蝇'])

以此构建出只识别特定字符的 char 的组合子

def char(c):
    return one_of(c)

print(char("a")("ab"))

('a', 'b')

识别不在某个集合里的 parser:

def none_of(chars):
    return satisfy(lambda x: x not in chars)

print(none_of("abc")("xyz"))

('x', 'yz')

以上只是识别一个字符或元素，为了能够识别更多，比如多个字符组成的词，或者多个元素组成的子序列，可以连续应用多次 parser:

def series(*parsers):
    def inner(s):
        result = []
        for p in parsers:
            x, s = p(s)
            result.append(x)
        return result, s
    return inner

def string(x):
    return series(*map(char, x))

print(string("abc")("abcde"))

(['a', 'b', 'c'], 'de')

到目前为止，我们只是在根据条件识别并拆分序列或字符串，还没有对识别出的部分进行任何的解释，而当谈到解释时，就涉及到语义了，比如要说清楚当前解析的目的是什么，因为可能对于语法上完全相同的对象，在不同语言下解释结果完全不同，以下例子目的是解析 json 格式的文件。

首先解析 null 字符串，解释成 python 中的 None:

def json_null(s):
    _, s = string('null')(s)
    return None, s

print(json_null("null"))

(None, '')

json_null 也是一个 parser, 它只能解析 null, 遇到其他情况则会报错，我们可以不要这么严格，比如可以先去识别当前是不是 null, 如果不是，并不要直接报错，而是继续调用其他解析器去解析，因此引入一个 branch 工具，它可以传入多个解析器，一个一个轮番去解析，直到成功为止。

def branch(*parsers):
    def inner(s):
        for p in parsers:
            try:
                return p(s)
            except:
                pass
        raise Exception("No parser succeeded")
    return inner

这样，就可以识别 bool 值，因为 bool 只有 true 和 false 两种，因此传入两个解析器给 branch 即可：

def json_bool(s):
    def true(s):
        _, s = string('true')(s)
        return True, s

    def false(s):
        _, s = string('false')(s)
        return False, s

    return branch(true, false)(s)

print(json_bool("true,"), json_bool("false."))

(True, ',') (False, '.')

为了能够识别拥有连续的相同模式的序列，需要一种重复解析的能力，以下 many 函数只接受一个 parser, 但它贪婪地不断重复解析，直到解析失败。

def many(parser):
    def inner(s):
        result  = []
        try:
            while True:
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

这样就可以解析数字了，因为它们是连续的相同类型的字符序列

def json_number(s):
    number_chars, s = many(one_of('0123456789.'))(s)
    number = ''.join(number_chars)
    return float(number), s

print(json_number("123abc"))

(123.0, 'abc')

同时可以解析字符串, 字符串的特殊性在于要考虑转义字符，比如 "\"hello\"" 要解释成 "hello", 也就是说，在每一步解析的时候，应该先查看是否是转义字符，如果是那么只需要获得转义字符后的那个字符，如果不是，则解析任何字符（除了引号本身），因此这里逻辑稍微复杂一点：

def json_string(s):
    _, s = char('"')(s)

    def escaped_char(s):
        _, s = char('\\')(s)
        c, s = any_char(s)
        return c, s

    contents, s = many(branch(escaped_char, none_of('"')))(s)

    _, s = char('"')(s)

    return ''.join(contents), s

print(json_string('"hello \\"John"'))

('hello "John', '')

注意以上要加两个转义，如果只有一个 python 会自己转义

'"hello \"John"'

"hello "John"

这样识别出来的就只有 hello

print(json_string('"hello \"John"'))

('hello ', 'John"')

要处理 json 里的 array, 首先主要是要忽略空格，比如以下 python 里的 list 和 json array 类似，中间可以有任意多空格、tab 或换行符

print([1,    2,
       3])

[1, 2, 3]

def whitespace(s):
    return many(one_of(' \n\t'))(s)

为了匹配元素和分隔符交替出现的模式（但分隔符比元素个数要少一个），我们再引入一个工厂函数，用来构造组合子

def interspersed(parser, separator):
    def inner(s):
        result = []
        try:
            while True:
                # 读取到第一个元素后读取分隔符
                if result:
                    _, s = separator(s)
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

注意这里和 many 的区别就在于只有读取了第一个元素之后才会读取 (分隔符，元素) 重复出现模式

def many(parser):
    def inner(s):
        result  = []
        try:
            while True:
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

这样就可以实现 json 里的 array 和对象的读取了：

def json_array(s):
    _, s = series(char('['), whitespace)(s)
    separator = series(whitespace, char(','), whitespace)

    result, s = interspersed(json_value, separator)(s)
    _, s = series(whitespace, char(']'))(s)
    return result, s

def json_object(s):
    _, s = series(char('{'), whitespace)(s)

    def kv_pair(s):
        k, s = json_string(s)
        _, s = series(whitespace, char(':'), whitespace)(s)
        v, s = json_value(s)
        return (k, v), s

    separator = series(whitespace, char(','), whitespace)
    result, s = interspersed(kv_pair, separator)(s)

    _, s = series(whitespace, char('}'))(s)

    return dict(result), s

def json_value(s):
    return branch(json_null, json_bool, json_number, json_string, json_array, json_object)(s)

注意 json_value 函数中出现了 json_array 和 json_object，而后两者实现中又调用了 json_value, 这是递归。

branch(json_null, json_bool, json_number, json_string, json_array, json_object)(s)

这一句是典型的 top-down 自顶向下的思路，因为它只是把 json 看作以上的 null, bool,number,string, array,object 几种类型之一，要解析 json, 那么只需要解析到其中任何一个即可。加上其中的递归性质，这个解析器就称为递归下降解析器，它是模块化的，像堆积木一样整合起来，因此被称为 parser combinator, 它又是函数式的，因为每个 parser combinator 大多是闭包的形式。

另外，以上 branch 函数是如何写出来的？如果要用 BNF 格式书写 json 文件的文法（grammar），那么其中可能包括：

JSON_VALUE : NULL|BOOL|NUMBER|STRING|ARRAY|OBJECT
NUMBER: [0-9\.]+
BOOL: false|true
NULL: null
...

而第一条文法可以直接写成以上代码，这种文法和代码实现的一一对应关系如此明确，以至于可以再编写一个程序，这个程序读取文法并直接生成一段解析该语言的 parser 的代码，这种工具被称为 Parser Generator, 下一章还会提到此概念。

另外，如果文法中有：

NAME : NAME string

那么对 name 的 parser combinator 可能定义是

def name(s):
    return series(name, json_string)(s)

这会导致陷入无限递归，这就是左递归问题，LL parser 需要避免这种文法，大部分情况下，交换一下文法里右侧对象的顺序即可。

NAME : string NAME

def name(s):
    return series(json_string, name)(s)

这样先执行了 json_string 后，s 会被消耗部分，因此再调用 name 就不会无限递归了。

最后，如果额外考虑 json 对象的合法性，那么最终 json 的 parser 如下：

def json(s):
    result, s = json_value(s)
    _, s = whitespace(s)
    assert s == '', f'did not consume entire string: {s}'
    return result

test = '{ "a": 1.23, "b": [1, false, null], "c": {"d": {"e": false}}}'
expected = {'a': 1.23, 'b': [1, False, None], 'c': {'d': {'e': False}}}

assert json(test) == expected

这里我们用 list 语言作为例子，它类似 python 的 list, 可以嵌套，可以有不同类型的元素。

[1,2,3,[3,4,5],[23]]

文法（grammar）文件的写法如下，它就是一种生成规则：

list     : '[' elements ']' ;        // match bracketed list
elements : element (',' element)* ;  // match comma-separated list
element  : NAME | list ;             // element is name or nested list

以上文法是一种上下文无关文法（Context-Free Grammar，CFG），并且它采用了巴科斯范式（Backus-Naur Form，BNF）的形式来描述这种文法。这里再对 CFG 和 BNF 进行解释（因为场景和之前自然语言的有点不一样）：

• BNF: 完全是以人名命名的，因此字面意义不重要。

  它用来描述语法，但它本身也是一种语法规则：冒号左边是类型名，右边是组成这个类型名的规则，其中 ; 是结束符号，而不是描述的语法对象的一部分， () 是 BNF 里的语言也不是描述对象语言里的， | 是或，空格是拼接，* 是 0 个或多个（和正则表达式里的 * 功能一样）

  尽管 BNF 也是一种语法，但我们不需要用另外的文法描述语言来描述 BNF 了，因为 BNF 语法足够简单清晰和通用，它可以描述构词规则（词法），构句规则（语法）等等，因此我们约定这是元递归（用语法描述语法）的终点。因此我们只需要构造一个最基础的解析 BNF 文法的解析器，给定任何语言的 BNF 描述，就可以生成一个针对该语言的 parser。

  这种 BNF 解析器先对每一行根据冒号 split 成两部分，然后核心是针对右侧分析出各个符号。 有意思的是，BNF 文法规则可以对应一个函数，并且能够对应不同的函数，比如：

  • | 对应 if elif 链
  • * 对应 do while
  • . 对应 if else 链
  • + 对应 while
• CFG: 它的字面体现了核心意义 – 上下文无关，从 list 的文法看出 CFG 的部分特点：

  • 左侧只有一个符号，比如 element : NAME | list; 这说明，不管在什么场景下，element 都可以替换成某个常量 NAME. 这是上下文无关的核心意义。

    如下是一个反例：

    aXb : aXXb
    

    这里符号 X 只有在左右分别是 a 和 b 的时候才能扩展，这是上下文有关的。

    再比如

    xxxxx : *
    

    这类似五子棋，只有五个连在一起可以消除，用 * 表示消除，这也是上下文有关的。

    当然以上例子都是最简单的区分什么是上下文有关和无关，真正上下文有关语言是更加复杂的，比如自然语言， 某个字的意义甚至发音在不同的场景都是不同的。

  • 右侧规则中允许出现左侧已经出现的符号（递归定义），这是 CFG 和正则表达的关键区别。

先引入 annotations 来支持未定义的类型

from __future__ import annotations

把语言的形式化定义（称为文法）转换为一个解析器，这里定义一个基类：

class Parser:
    def __init__(self, input: Lexer):
        self.input = input 
        self.lookahead = None     # 当前的预览词法单元
        self.consume()

    def parse(self):
        raise NotImplementedError

    def match(self, type: str):
        if self.lookahead.type == type:
            self.consume()
        else:
            raise ValueError(f"Expecting type: {type}; found {self.lookahead} with type {self.lookahead.type}")

    def consume(self):
        """前进到下一个词法单元。"""
        try:
            self.lookahead = next(self.input)
        except StopIteration:
            self.lookahead = Token(self.input.EOF_TYPE, self.input.EOF)

这里定义了两个函数：

• match 用来根据当前看到的单元，它是通过 input 对象定义的，也就是词法规则所定义的，模式二中将详细介绍
• consume 用于移动到下一个 token
• 对 self.input 对象（Lexer）也有几个接口的约定：
  • 可以支持 next, 每次调用 next 就返回下一个 token
  • 有一个 type 通过 token 查询 type
  • 有一个 EOF_TYPE 常量

这个 Parser 是没有实际用途的，它只提供了解析所需要的最基础的两个函数的接口，也就是不断与当下的 token 匹配并根据 token 的不同类型而执行不同的动作。

注意本节甚至本文都不会实现一个读取 grammar 文件后自动生成一个 paser 功能的文法解析器,
这类开源工具已经比较成熟，比如 python 中的 Lark,  java 中的 ANTL 。它们被称为 Parser Generator

词法分析器的目的是将字符流切分成 token（词法单元）

对 Lexer 的期望是，可以把字符流输入 Lexer 的实例, 然后返回一个具有 generator 属性的对象, 每次调用 next 就可以获得下一个合法的词，为此先定义什么是 token:

• 一般带有类型，对于编程语言来说，有 int,float,string 等，对于自然语言，则有动词名词等
• 对于每种 token 的类型，都有其特别的识别特征，比如 string 是根据引号来找的，int 是根据连续的整数来识别， float 是根据连续整数里的小数点等。

以下类是对 token 的抽象，只包括符号和类型两种属性，这足够通用

class Token:
    def __init__(self, type: str, text: str):
        self.type = type
        self.text = text

    def __repr__(self):
        return f"<'{self.text}','{self.type}'>" 

接着实现 Lexer 的抽象类，它和 Parser 类有类似的 consume （也可以定义 match 接口），consume 的区别在于，当前默认输入就是字符串，因此可以直接用 python 内置的获取字符的接口。

另外 init 中对用 setattr 方式把字典里的变量名作为类属性

class Lexer:
    '''
    A Abstract Lexert class
    '''
    # string with < > is the token and the string without < > is the token type
    type_map = {"<NA>": "NA", "<EOF>": "EOF"}

    def __init__(self, input: str):
        self.input = input

        # set all key, value in type_map to class attribute
        for token, token_type in self.type_map.items():
            setattr(self, token_type, token)
            setattr(self, f"{token_type}_TYPE", token_type)

        self.p = 0  # Index into input of current character
        self.c = self.input[self.p] if self.input else self.EOF  # Prime lookahead

    def consume(self):
        """Move one character; detect 'end of file'."""
        self.p += 1
        if self.p >= len(self.input):
            self.c = self.EOF
        else:
            self.c = self.input[self.p]

    def match(self, x):
        """Ensure x is next character on the input stream."""
        if self.c == x:
            self.consume()
        else:
            raise ValueError(f"Expecting {x}; found {self.c}")

    def get_type(self, token_type):
        """Abstract method to get the token name."""
        raise NotImplementedError

实现具体的解析 list 的词法的类：

class ListLexer(Lexer):
    type_map = {"<EOF>": "EOF", "NAME": "NAME",
                ',': "COMMA", '[': "LBRACK", ']': "RBRACK"}

    def __init__(self, input: str):
        super().__init__(input)

    def get_type(self, x):
        return self.type_map[x]

    def is_letter(self):
        return len(self.c) == 1 and self.c.isalpha()

    def __iter__(self):
        return self

    def __next__(self):
        while True:
            if self.c == self.EOF:
                raise StopIteration
            elif self.c in [' ', '\t', '\n', '\r']:
                self.ws()
            elif self.c == ',':
                self.consume()
                return Token(self.COMMA_TYPE, self.COMMA)
            elif self.c == '[':
                self.consume()
                return Token(self.LBRACK_TYPE, self.LBRACK)
            elif self.c == ']':
                self.consume()
                return Token(self.RBRACK_TYPE, self.RBRACK)
            else:
                if self.is_letter():
                    return self.name()
                raise ValueError(f"Invalid character: {self.c}")

    def name(self):
        buf = []
        buf.append(self.c) #do while
        self.consume()
        while self.is_letter():
            buf.append(self.c)
            self.consume()
        return Token("NAME", ''.join(buf))

    def ws(self):
        while self.c in [' ', '\t', '\n', '\r']:
            self.consume()

__next__(self) 中是对以下构词文法进行解析的核心实现

NAME     : LETTER+ ;                 // name is sequence of >=1 letter
LETTER   : 'a'..'z'|'A'..'Z';        // define what a letter is
WS       : (' '|'\t'|'\n'|'\r')+ {skip();} ; // throw out whitespace

比如以下分支和对应的 ws 函数对应了以上文法的最后一行，文法中的 | 符号对应了 python 中的 in, 文法中的 + 符号对应了 python 中的 while 循环（严格来说应该是 do while, elif 充当了 do 操作），这种对应关系很是工整。

elif self.c in [' ', '\t', '\n', '\r']:
    self.ws()

def ws(self):
    while self.c in [' ', '\t', '\n', '\r']:
        self.consume()

再比如 name 函数是对文法里 NAME 规则的实现，也是一个 do while 结构去找到连续的 alphabet 字符串。

之所以是 LL(1), 这里 1 体现在， __next__(self) 函数的每个条件分支里都只需要判断 self.c 这 1 个 token 是什么，然后根据它进行不同解析。

测试如下：

lexer = ListLexer("[a, b ]");
for token in lexer:
    print(token)

<'[','LBRACK'>
<'a','NAME'>
<',','COMMA'>
<'b','NAME'>
<']','RBRACK'>

它相比于 text.split() 的好处是，可以提取出 token 的类型

注意当前完全是分词，不考虑语法合法性，比如以下错误语法

lexer = ListLexer("[a, b ],,,");
for token in lexer:
    print(token)

<'[','LBRACK'>
<'a','NAME'>
<',','COMMA'>
<'b','NAME'>
<']','RBRACK'>
<',','COMMA'>
<',','COMMA'>
<',','COMMA'>

另外尽管说是 LL(1) 递归下降解析，但这里基本没有用到递归，因为本例子以及大部分编程语言的构词法都不会涉及到递归， 之所以本例的词法解析也称为递归下降，是因为代码框架和递归下降的写法是类似的。

上节定义了 list 语言的词法，并根据词法规则实现了一个词法解析，本节则定义 list 语言的文法

grammar NameList;

list     : '[' elements ']' ;        // match bracketed list
elements : element (',' element)* ;  // match comma-separated list
element  : NAME | list ;             // element is name or nested list

一般的实践中，我们只需要写以上的文件，然后交给一个第三方的文法解析工具后，直接就可以获得对目标语言的 parser 但这里直接手动实现它：

class ListParser(Parser):
    def __init__(self, input: ListLexer):
        super().__init__(input)

    def list(self):
        """list : '[' elements ']' ; // match bracketed list"""
        self.match(self.input.LBRACK_TYPE)
        self.elements()
        self.match(self.input.RBRACK_TYPE)

    def elements(self):
        """elements : element (',' element)* ;"""
        self.element()
        while self.lookahead.type == self.input.COMMA_TYPE:
            self.match(self.input.COMMA_TYPE)
            self.element()

    def element(self):
        """element : name | list ; // element is name or nested list"""
        if self.lookahead.type == self.input.NAME_TYPE:
            self.match(self.input.NAME_TYPE)
        elif self.lookahead.type == self.input.LBRACK_TYPE:
            self.list()
        else:
            raise ValueError(f"Expecting name or list; found {self.lookahead}")

这里每个类函数对应了文法里的三行，并且函数名称和每行右侧的变量名都一样：

• 对于 list, 由于这是一个组合式（都是空格分隔），因此代码是线性的
• 对于 elements, 由于其中有 * 可选符号, 因此这是一个 while 循环，注意 while 本身是有条件判断的，它的条件是通过 lookahead 的类型，因为只有看到了逗号才需要进入循环。
• 对于 element, 由于其中有 | 这个多种可能的选择符号，于是用 if else, 这里 if 里条件也是 lookahead 的类型，因为要区分 NAME 和 list 两种子结构，而子结构的类型通过当前看到的该结构的第一个 token 就可以识别出来。

整个解析看上去甚至有点死板（尽管递归下降这些词带一点浪漫色彩），这也是为什么大多数实际场景中会用 parser generator 来根据文法自动生成 parser 。

如果阅读了上一章，以上代码中类似 combinator 的性质体现在类函数中，elements, element, list 都可以视为一个 parser （但不是典型的 combinator, 一般来说 combinator 是函数式里无状态的过程，但这里类函数都共享了类变量，比如 lookahead）。 另外，如果文法中有以下形式

element  : element NAME ;

element 函数的实现里第一句就需要调用 self.element, 这会导致陷入无限递归，这就是左递归问题，LL parser 需要避免这种文法，大部分情况下，交换文法里右侧对象的顺序即可，比如：

element  : NAME element;

这样会先解析 NAME 从而消耗了部分 token ，使得继续解析 element 的时候序列变短了，因此不会导致无限递归。

def element(self):
    """element : name | list ; // element is name or nested list"""
    self.element()
    if self.lookahead.type == self.input.NAME_TYPE:

接着就可以测试，注意我们要重新初始化一个 lexer, 因为上文从 lexer 打印 token 时就消耗了 generator

list_lexer = ListLexer("[a, b ]");
list_parser = ListParser(list_lexer)
list_parser.list()

以上是正确语法，由于没有对解析结果做任何操作，因此没有结果返回。

以下是输入错误的语法的句子后返回异常的情况：

list_lexer = ListLexer("[a, b ,,]");
list_parser = ListParser(list_lexer)
list_parser.list()

ValueErrorTraceback (most recent call last)
<ipython-input-130-c3c70399a716> in <module>
      1 list_lexer = ListLexer("[a, b ,,]");
      2 list_parser = ListParser(list_lexer)
----> 3 list_parser.list()

<ipython-input-128-53a59d51bca3> in list(self)
      6         """list : '[' elements ']' ; // match bracketed list"""
      7         self.match(self.input.LBRACK_TYPE)
----> 8         self.elements()
      9         self.match(self.input.RBRACK_TYPE)
     10 

<ipython-input-128-53a59d51bca3> in elements(self)
     14         while self.lookahead.type == self.input.COMMA_TYPE:
     15             self.match(self.input.COMMA_TYPE)
---> 16             self.element()
     17 
     18     def element(self):

<ipython-input-128-53a59d51bca3> in element(self)
     23             self.list()
     24         else:
---> 25             raise ValueError(f"Expecting name or list; found {self.lookahead}")

ValueError: Expecting name or list; found <',','COMMA'>

由于在 list 函数里只匹配了左括号，elements 和右括号，因此如果右括号后还有内容，会忽略，也不会报错

list_lexer = ListLexer("[a, b ],,xsdf");
list_parser = ListParser(list_lexer)
list_parser.list()

回顾一下当前的进展：

• 词法分析的关键在于，看到当前 token 是 a 的时候，我们知道这只有可能是一个变量名，因此进入一个 name 函数把完整变量名搜集齐全，如果是 [ 符号，直接添加到 token list 结果里。
• 语法分析的关键在于，看到当前 token 是 [ 的时候，预期接下来要么是 ] 要么是变量名
• 总的来说，这是一种限制性规则，根据当前看到的 token，去限制接下来可能出现的 token, 这也是用语法规则对语言模型采样进行限制的关键 – 语法和词法规则限定了每个时刻的 token 输出范围，即便它允许某些自由的选择，那也是一种完整词表的限制。
• 目前都只需要看当前的一个字符

但有些语言要看到两个字符才能决定接下来的动作，比如对 list 语法的扩展， list 里可以放置 b=c 这种表达式：

[a, b=c, [d,e]].

那么看到 b 这个字符之后，不能断定它是一个单独的变量还是一个表达式。体现在文法规则里如下， element 的扩展选项中，有两个选项拥有相同的 NAME 前缀

list : '[' elements ']' ;
elements : element (',' element)* ;
element : NAME '=' NAME
        | NAME
        | list

有两种方式处理这种情况：

• 改成 LL(1) 能适用的文法：

  list : '[' elements ']' ;
  elements : element (',' element)* ;
  element : NAME ('=' NAME)?
          | list
  

  这里引入了一个 ?, 它对应的是一个 if 语句

  首先要修改 Lexer, 以支持对 = 的读取：

  class ListLexerWithEqual(ListLexer):
      type_map = {"<EOF>": "EOF", "NAME": "NAME",
                  ',': "COMMA", '[': "LBRACK", ']': "RBRACK", '=': "EQUALS"}
  
      def __next__(self):
          while True:
              if self.c == self.EOF:
                  raise StopIteration
              elif self.c in [' ', '\t', '\n', '\r']:
                  self.ws()
              elif self.c in [self.COMMA, self.LBRACK, self.RBRACK, self.EQUALS]:
                  last_c = self.c
                  self.consume()
                  return Token(self.get_type(last_c), last_c)
              else:
                  if self.is_letter():
                      return self.name()
                  raise ValueError(f"Invalid character: {self.c}")
  

  这里在 type_map 里加入 = 符号，并且把多个判断一句合并成

  elif self.c in [self.COMMA, self.LBRACK, self.RBRACK, self.EQUALS]:
  

  接着在 element 对 NAME 的判断分支中多加一个 if

  class ListParserWithEqual(ListParser):
      def element(self):
          if self.lookahead.type == self.input.NAME_TYPE:
              self.match(self.input.NAME_TYPE)
              if self.lookahead.type == self.input.EQUALS_TYPE:
                  self.match(self.input.EQUALS_TYPE)
                  self.element()  
          elif self.lookahead.type == self.input.LBRACK_TYPE:
              self.list()
          else:
              raise ValueError(f"Expecting name or list; found {self.lookahead}")
  

  list_lexer = ListLexerWithEqual("[a, b=a, x]");
  list_parser = ListParserWithEqual(list_lexer)
  list_parser.list()
  

• 编写 LL(2) 解析算法： LL(k) 是把 LL(1) 里保存 lookahead 的 buffer 的大小从 1 变成 k, 而在具体的 if 条件判断中，我们要根据 k 个 token 的类型组合来决定接下来解析什么样的表达式，这里用一个循环的数组来保存读取到的 k 个元素。

  class Parser:
      def __init__(self, input_lexer, k=2):
          self.input = input_lexer  # 从词法分析器获取词法单元
          self.k = k               # 前瞻符号的数量
          self.lookahead = [None] * k  # 创建前瞻缓冲区
          self.p = 0               # 循环索引，指向下一个要填充的令牌位置
          for _ in range(k):       # 用 k 个前瞻符号填充缓冲区
              self.consume()
  
      def consume(self):
          try:
              self.lookahead[self.p] = next(self.input)
          except StopIteration:
              self.lookahead[self.p] = Token(self.input.EOF_TYPE, self.input.EOF)
          self.p = (self.p + 1) % self.k  # 循环递增索引
  
      def __getitem__(self, i):
          """允许使用索引操作获取第 i 个前瞻令牌。"""
          if isinstance(i, slice):
              # 支持切片操作
              return [self.lookahead[(self.p + idx - 1) % self.k] for idx in range(i.start or 0, i.stop or self.k, i.step or 1)]
          else:
              return self.lookahead[(self.p + i - 1) % self.k]
  
      def match(self, type: str):
          """匹配预期的令牌类型。"""
          if self[1].type == type:
              self.consume()
          else:
              raise ValueError(f"Expecting type: {self[1].type}; found {self[1]} with type {self[1].type}")
  

  原本 self.lookahead 是一个 token ，当前是一个 list of tokens

  class LookaheadParser(Parser):
      def __init__(self, input: ListLexer):
          super().__init__(input)
  
      def list(self):
          """list : '[' elements ']' ; // match bracketed list"""
          self.match(self.input.LBRACK_TYPE)
          self.elements()
          self.match(self.input.RBRACK_TYPE)
  
      def elements(self):
          """elements : element (',' element)* ;"""
          self.element()
          while self[1].type == self.input.COMMA_TYPE:
              self.match(self.input.COMMA_TYPE)
              self.element()
  
      def element(self):
          """element : name | list ; // element is name or nested list"""
          if self[1].type == self.input.NAME_TYPE and self[2].type == self.input.EQUALS_TYPE:
              self.match(self.input.NAME_TYPE)
              self.match(self.input.EQUALS_TYPE)
              self.match(self.input.NAME_TYPE)
  
          elif self[1].type == self.input.NAME_TYPE:
              self.match(self.input.NAME_TYPE)
          elif self[1].type == self.input.LBRACK_TYPE:
              self.list()
          else:
              raise ValueError(f"Expecting name or list; found {self.lookahead}")
  

  这里通过以下语句判断连续两个 token 组合的情况：

  if self[1].type == self.input.NAME_TYPE and self[2].type == self.input.EQUALS_TYPE:
  

  list_lexer = ListLexerWithEqual("[a, b=a, x]");
  list_parser = LookaheadParser(list_lexer)
  list_parser.list()