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

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

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

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

在这种"顶层思维"下，定义到达某个格子的路径最小和是 s(i,j), 本例中核心关注的是 s(2, 2), 它的值应该来自于当前格子的值，以及上方格子 s(1,2)和左侧格子的 s(2,1) 的最小值之和：

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 型文法，它的核心特点在于：

• 同时右边任意位置都允许出现左边已经出现过的变量（即允许递归定义）

  • 如果右侧不允许递归定义，但可以用记号表示某些重复，比如

    username : [a-z]+[0-9]+
    

    这里 [a-z]+ 表示这部分单词只由小写字母组成，可以重复任意多次，例如 abca，同样 [0-9]+ 表示可以由任意数字组成，因此 abca121 就是合法的 username.

    这种语言右侧不能有左侧已经定义过的符号，而只有终结字符，但给予了 "终结符号" 一些组合自由度，比如重复，拼接，这被称为正则语言或 Chomsky 3-型语言。

• 生成规则的左边只有一个变量，也就是说生成规则一定是扩展性质的规则，而不会缩减。
  • 比如 VP -> V NP 这说明不管在什么场景下，动词短语标签都可以展开成一个动词连接一个名词短语， 这是上下文无关的核心意义。

  • 如下是一个反例：

    aXb : aXXb
    

    符号 X 只有在左右分别是 a 和 b 的时候才能扩展，这是上下文有关的（被称为 1-型语言）。

  • 再比如：

    xxxxx : -
    

    假设右侧 - 表示空白，这条规则类似五子棋，只要五个连在一起就消除，这也是上下文有关的。

  • 如果在规则中出现：

    VP VP-> VP
    

    那么这说明一个句子在生成的过程中，它的描述长度可能会缩减，因此当在反推这个语言的结构时，发现其中有一部分是 VP(比如动词短语"追苍蝇"）, 而查看规则后发现 VP 竟然是可以根据两个 VP 缩减而来，因此 "追苍蝇" 这句话的语言结构可能有任意多的 VP （只不过都被这个规则消解了）。

    因此该语言结构可能有无限多种，变得复杂，这可以类比到 3n+1 猜想。这种语法对应的语言称为 0 型文法，

这种语法描述的字符串就像是整数分类里的素数，足够复杂，但却是可控的（可以递归到 basecase）。

四种语言分类如下，数值越大，限制越强，表达能力越弱：

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 文法描述

S -> aSa | bSb | cSc | ... | zSz | 0S0 | 1S1 | ... | 9S9
S -> - | a | b | c | ... | z | 0 | 1 | ... | 9

"-" 表示 S 可以是空的。

现在假设有以下 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)))

还可以用类，比如：

class Node:
    def __init__(self, tag="VP",  children: list[Node]):
        self.tag=tag
        self.children = children

为了使得代码更精简，本文中用嵌套 list 的方式来表示树。

CKY 算法是一个对 CFG 语言进行解析的通用算法，给定一个字符串以及对应文法，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] 的另一个依赖，即第一种分解情况 grid[0][1] 和 grid[2][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]])

对应到语法解析中，歧义就是给定一个句子，算法解析出了不止一棵的解析树，而放在句子本身，就是不同的人对这个句子有不同的理解。而如果放在 CFG 文法的语境里，歧义意味着通过 CFG 规则从最高层的开始符号推导到这个句子时，有多于一种推导方式。 这种多重推导方式会导致生成多个不同的解析树，反映了该句子在该文法下的多重语义解释。

然而这个说法还是不足以覆盖自然语言中所有歧义的场景，比如 I went to the bank, 这里 bank 可以是银行也可以是河岸。尽管这个句子的解析树只有一个，但它却有两种不同的意思。这种词义歧义是语义层面的歧义，而不是句法层面的歧义。

因此，CKY（Cocke-Kasami-Younger）算法或任何解析 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" 看作一个符号，减少解析树的深度，因此句子分词后的结果如下：

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

正如回文 leetcode 例子中，我们先计算出字符串有多少回文子序列，然后再找出所有可能回文（路径）。

下一节我们先是在给定一个以上字符串列表的情况下，用 CKY 算法找出该句子在某个 CFG 规则下有多少种解释（解析树或生成树）。再下一节则找出特定解释下对应的语法树（歧义）以及该歧义的概率。

定义递归函数 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']

这里看到，这句话有两种不同的语法结构（最后一个列表里有两个 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']]]]

第一个解析树如下：

S
|-- Pronoun -> I
|-- VP
    |-- V -> shot
    |-- NP
        |-- Det -> an
        |-- Nominal
            |-- N -> elephant
            |-- PP -> in my pajamas

其语义是，我射击了一只穿着我睡裤的大象（或者我射击了一只藏在我睡裤里的大象），总之 in my pajamas 是修饰大象的。

第二个解析树是：

S
|-- Pronoun -> I
|-- VP
    |-- VP
        |-- V -> shot
        |-- NP
            |-- Det -> an
            |-- N -> elephant
    |-- PP -> in my pajamas

其语义是，我穿着睡裤射击了一只大象，in my pajamas 是修饰射击这个动作的。

如果非要把 in my pajamas 展开，它在两种情况下都是：

PP -> in my pajamas
    |-- P -> in
    |-- NP
        |-- Det -> my
        |-- N -> pajamas

注意得到以上完整的解析书，只是修改了上一节算法里 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]]]]

带有概率的解析树 1:

S
|-- Pronoun -> I (0.3)
|-- VP (0.0144)
    |-- V -> shot (0.2)
    |-- NP (0.12)
        |-- Det -> an (0.2)
        |-- Nominal (1)
            |-- N -> elephant (1)
            |-- PP -> in my pajamas (1)

带有概率的解析树 2:

S
|-- Pronoun -> I (0.3)
|-- VP (0.00384)
    |-- VP (0.0096)
        |-- V -> shot (0.2)
        |-- NP (0.08)
            |-- Det -> an (0.2)
            |-- N -> elephant (1)
    |-- PP -> in my pajamas (1)

至于 cfg_rules 和 lexicons 里概率从何而来，这就是统计学习的知识，本文不展开，如有兴趣可以阅读 CFG and Constituency Parsing, 对本章以及上一章里提到的关于语法知识的更详细描述以及获得概率化解析树之后如何做其他自然语言的任务也可参考此书。

第二个例子更像来自编码领域，假设收到一条信息是 01111100110, 如果它的编码来自于 {11,01,001,10}, 那么这个信息就只有唯一的解码方式，算法如下：

message = "01111100110"
code_book = {'11': "花" ,'01': "问" ,'10': "语", '001': "不"}

current_code = ""
result = []
for char in message:
    current_code += char
    if current_code in code_book:
        result.append(code_book[current_code])
        current_code = ""
print(result)

['问', '花', '花', '不', '语']

该算法有一些特点：

• 是贪心的，复杂度是 O(n).
• current_code 类似一个栈结构，每读取到字符就添加进栈，并且用栈里的所有内容去字典里匹配，如果匹配成功， 就可以直接解码，这是因为 prefix-free 性质使得以 current_code 为前缀的编码是唯一的。考虑一个极端的例子， {"1","11","111","1111"}, 这种情况下，规定信息 "1111", 我们需要考虑四种切分，而每个切分下又要递归，回到了 CKY 算法的复杂度。

注：著名的 huffman 编码就是一种 prefix free 编码，而在编码理论，这种性质的编码直接称为 prefix code

我们继续编写代码来做解析：

pos_tags = ["动词","名词","名词","副词","动词"]

grammar_book = {"动词名词": "VP" ,"副词动词": "VP" ,'名词': "NP"}

current_grammar = ""
result = []
for pos in pos_tags:
    current_grammar += pos
    if current_grammar in grammar_book:
        result.append(grammar_book[current_grammar])
        current_grammar = ""
print(result)

['VP', 'NP', 'VP']

实际上到目前为止，我们自下而上地建立了以下三棵树（或者说森林）

   VP       NP    VP      
  / \       |     /  \
动词 名词   名词  副词  动词
  |  |      |    |    |
 问  花     花    不    语 

可以继续在 ['VP', 'NP', 'VP'] 上迭代

grammar_tags = ['VP', 'NP', 'VP']

grammar_book = {"VPS": "S" ,"NPVP": "S"}

current_grammar = ""
result = []
for tag in grammar_tags:
    current_grammar += tag
    if current_grammar in grammar_book:
        result.append(grammar_book[current_grammar])
        current_grammar = ""
print(result)

[]

实现该算法之前，预期是想建立以下形式的树，

        S
     /      \
   VP        S
  / \      /   \
动词 名词   NP    VP
  |  |    |     /  \
 问  花   名词  副词   动词
          |    |    |
          花   不   语

grammar_tags = ['VP', 'NP', 'VP']

grammar_book = {"VP":"_VP", "NPVP": "S"}

current_grammar = ""
result = []
for tag in grammar_tags:
    current_grammar += tag
    if current_grammar in grammar_book:
        result.append(grammar_book[current_grammar])
        current_grammar = ""
print(result)

['_VP', 'S']

于是目前得到以下树

   _VP       S
   |       /    \
   VP     NP     VP
  / \     |     /  \
动词 名词 名词  副词   动词
  |  |    |    |    |
 问  花   花   不    语  

再把 ['_VP', 'S'] 作为输入， grammar_book 设置为 {"_VPS": "S"} 就得到了以下完整的解析树：

        S
     /     \
   _VP       S
   |       /    \
   VP     NP     VP
  / \     |     /  \
动词 名词 名词  副词   动词
  |  |    |    |    |
 问  花   花   不    语  

这里可以看到，以上算法必须把 CFG 语法强行分层，每一层是 prefix free, 暂且不考虑这在现实中是否可能（实际是可能的，因为编程语言是人为设计的，而我们正是在讨论如何限定 CFG 语法使得能够得到理想的解析效率）。

假设有这样实现分层好的 prefix free 语法，那么对输入长度是 n 的字符串 ，每次都是两两合并，那么最终这类算法的复杂度是 n+n/2+n/4…, 这是一个几何级数，最终复杂度为 2n, 也就是 O(n). 因此如果有这种理想的 CFG 生成语法，那么解析的复杂度是可以降低到线性的。

下一节来真正处理现实中的不是那么理想的 grammar book 。

上一节中，我们利用每个层次上语法组合的 prefix free 性质，分层地实现出了 O(n) 复杂度的解析算法，各层次用到的语法如下：

code_book = {'11': "名词" ,'01': "动词" ,'10': "动词", '001': "副词"}
grammar_book = {"动词名词": "VP" ,"副词动词": "VP" ,'名词': "NP"}
grammar_book = {"VP":"_VP", "NPVP": "S"}
grammar_book = {"_VPS":"S"}

但问题是，现实中，只有关于词汇的部分是分离的，剩下的所有语法都统一放在 grammar_book 中， 无法为了照顾特定句子解析树的层级数量而人为划分出 "VP":"_VP" 这样的纯粹为了把每棵子树“垫高”对齐的语法。

现实中的 CFG 文法更多是如下形式：

grammar_book = {'11': "名词" ,'01': "动词" ,'10': "动词", '001': "副词", #lexicon 部分
                "动词名词": "VP" ,"副词动词": "VP" ,'名词': "NP",
                "NPVP": "S", 
                "VPS":"S"}

注意这是 BNF 范式的逆向形式，BNF 语法条目一般是 “VP:动词 名词” 形式的，而以上是 {"动词名词": "VP"}, 但他们表达的内容是一样的。然而正是这种逆向形式使得该算法是自下而上的动态规划算法，因为我们从最原始的句子触发，逐渐 给词汇、短语添加上语义标签，并且最终得到最高抽象的 "S" 标签。

另外以上 lexicon 部分可以单独取出来，也就是说实际可以分成 lexicon 和 grammar, 但这个例子中，lexicon 和 grammar 合并后的 grammar_book 仍然符合 prefix free 性质，即没有任何一个 key 是其他 key 的前缀，因此可以合起来处理。

此外，除了 "001" 之外，每个更高层的语法对象最多由两个对象所组成（类似 CNF)，这使得我们可以把栈结构更加凸显出来，每次不是检查整个栈里所有元素的组合是否能从 grammar_book 中找到，而是检查栈顶的一个或者两个元素的组合，这会使得复杂度翻倍，但仍然是线性的 O(n) 。

以下算法直接输入原始的信息，但为了避免额外检查长度为 3 的 001, 我们把 001 拆分成 0 和 01 。 这样，由于全局的 prefix free 性质，分词（解码）和语法解析可以在一次扫描中都做完，最后返回一个 list 嵌套格式的树：

message_queue = list("011111") + [ "0", "01"] + list("10")

stack, result = [], []
stack.append([message_queue.pop(0)])
while stack and i:
    if len(stack) >= 2 and stack[-2][0]+stack[-1][0] in grammar_book:
        ele2 = stack.pop()
        ele1 = stack.pop()
        new_ele = [grammar_book[ele1[0]+ele2[0]], ele1, ele2] # add tag
        stack.append(new_ele)
    elif stack[-1][0] in grammar_book:
        ele = stack.pop()
        new_ele = [grammar_book[ele[0]], ele] # add tag
        stack.append(new_ele)
    elif message_queue: # 无法 reduce 时进行 shift
        stack.append([message_queue.pop(0)]) # 添加 list 而不是 char, list 的第一个元素为 query
    elif len(stack) == 1:
        break
pprint(stack)

[['S',
  ['VP', ['动词', ['0'], ['1']], ['名词', ['1'], ['1']]],
  ['S',
   ['NP', ['名词', ['1'], ['1']]],
   ['VP', ['副词', ['0'], ['01']], ['动词', ['1'], ['0']]]]]]

这种算法被称为 shift-reduce, 一般涉及一个栈和一个队列， shift 就是出队列并入栈，reduce 则是对栈上元素打标签。 由于 prefix-free 以及 CFG 文法的 Chomsky Normal 化, 我们只需要去查找栈顶上的最多两个元素，并且找到唯一的语法标签（句子符合语法的情况下）。

相比于上一节的算法，这里并不是每次都对比整个栈里对象组合是否存在语法标签，而是分别检查栈顶元素以及栈顶两个元素组合（如何有两个的话）是否有语法标签，这是根据语法规则中组合标签的长度决定的，比如在 BNF 格式下，如果存在 A:B C D 的情况，那么就需要允许栈能存 3 个元素并依次检查前三个元素组合是否有标签。

以上算法并不是通用的，只是作为特定例子的展示。比如，如果语法中出现了 名词->NP->NNP 这种把一个对象连续抽象的情况，在以上函数的 if 语句中实际要用 while 循环去不断堆叠这个抽象塔才能处理。而这也体现了，我们在做完一次切分后并不能一次性地对前缀打上标签，而是要循环地去抽象， 次数等于抽象塔的最大高度。

现在从自然语言例子进入到编程或计算的例子，以最简单的计算加减乘除为例，常见的表达式形式为： (3 + 4) * (5 + 6) ，运算符号放在数字或变量的中间，这被称为中缀表达式。

由于有运算优先级，使得以上式子中引入了括号，如果直接写成 3+4*5+6 会得到另外的结果。但从解析的角度，括号会使得解析这个式子的算法变得更复杂，因此计算机发展早期出现了许多优化 表达式形式的技巧，使得一方面可以少写括号（过去的内存也是珍贵的，因此可以减少内存），另一方面又可以使得解析 表达式的算法变得精简。

其中就包括前缀表达式（波兰表达式）和后缀表达式（逆波兰表达式）：

• 以上例子的前缀表达式是： * + 3 4 + 5 6
• 以上例子的后缀表达式是： 3 4 + 5 6 + *

由于二者是对称的，因此我们先以后缀表达式为例，在后缀表达式核心表达实际是运算符的顺序，越先计算的运算，其运算符写得越前，以上实际是 ++*, 以为着先做两个加法然后做乘法。然后在运算符左侧添加直接参与的运算对象对象。

为什么后缀表达式可以用运算符排列顺序确定计算优先级，但中缀表达式却不行，要借助括号呢？

• 这实际就是来自语法的歧义问题，中缀表达式的计算是取运算符号左右两边的对象进行结合，比如 1+1, 但如果两个不同优先级的运算符号共享了一个数字时，就会出现歧义，比如 1+1*2 里中间的 1 是划分到 * 节点还是 + 节点？ 而这种歧义体现在了 prefix-free 性质的缺失上， 1+1 是 1+1*2 的前缀，但 1+1*2 却存在一个和 1+1 不同的语义，即 1+1*2 实际是 1+2 。引入括号后虽然 1+1 就不再是 1+(1*2) 的前缀，另外 1+1 似乎是 1+1+1 的前缀，但这并不要紧，因为严格来说，1+1 在右括号的版本中，实际是 (1+1) 而 1+1+1 则是 ((1+1)+1), 前者不是后者的前缀，((1+1)+1) 可以看作是 1+1+1 的最左派生树，这在后文 中会有更多介绍。

  在后缀表达式中，如果要表达先加后乘，那么先写下 +*, 然后插入数字 1 1 + 2 *, 如果要表达先乘后加， 那么写下 *+, 然后 1 2 * 1 + 。 虽然 1 1 + 是 1 1 + 2 * 的前缀，但加上括号的话，它实际是 (1 1 +) 和 ((1 1 +) 2 *), 并没有前缀关系，这里的核心在于，由于排列顺序隐含了优先级，使得某些情况允许打破 prefix-free 性质，但我们知道遇到 + 之后就应该马上求值（等价于构造一个语法节点）， 因此实际上对表达式的切分还是确定性的，不需要考虑多次切分下会导致不同的解析树（语义）。

为什么后缀表达式的计算和解析都很方便？

• 因为表达式中数字（运算对象）和运算符都有两重含意，数字符号不单表示数字本身，还在计算模型层面表示进栈， 运算符符号不单表示一个算术操作，还表示出栈并计算，不过这里前提是每个运算符参数数量是固定的，比如 2。

grammar_book = {"+","-","*","/"}
def eval_reverse_polish(exp: list):
    stack = []
    tokens = exp
    for t in tokens:
        if t not in grammar_book:
            stack.append(int(t))
        else:
            y, x = stack.pop(), stack.pop()
            res = eval(f"{x} {t} {y}")
            stack.append(res)
            
    return stack[0]

exp = "3 4 + 5 6 + *"
print(eval_reverse_polish(exp.split()))

77

在计算器场景里，我们直接返回数字（直接一边解析一边求值），并不返回一个解析树，这就好比前文中统计回文的例子，有的时候我们只要求算法返回回文子串的个数（数字是最终目标），有的时候要返回所有可能的回文（结构是最终目标）。

lisp 语言的表达式是一种前缀表达式，由于不同运算符可以支持不同个参数，比如 (+ 1 3 4) 表示 1+3+4, 所以它 用括号严格区分优先级，因此该语言对应的合法字符串包括变量/数字或者是带括号的表达式（称为 s-expression), 而 s-expression 都是 prefix-free 的， 比如 (* 1 2 3) 和 (* 1 2 3 4 5 6) 都是合法的，但因为括号的功劳，前者并不是后者的前缀。

一个更复杂的例子如下：

((lambda (x) (* x x)) ((lambda (x) (* x x)) 3))

可以用一个 shift-reduce 在 O(n) 来解析这种语言，除了右括号，都是进栈操作（shift)，遇到右括号我们就知道，当前已经搜集到了一个独一无二的表达式，因此先出栈组成一个新的语法节点（reduce)，然后入栈，继续向右扫描。

import string
def to_list_ast(expression):
    """
    ['(', '/', 4, '(',  '*', '1', '1', ')', ')'] -> [ '/', '4', ["*", 1, 1] ]
    """
    stack = []
    for e in expression:
        if e == ")":
            temp = []
            while stack[-1] != "(":
                temp.append(stack.pop())
            stack.pop()
            stack.append(temp[::-1])
        else:
            stack.append(e)
    return stack[0]


def parse(string):
    exp = string.replace("(", " ( ").replace(")", " ) ")
    tokens = exp.split()
    list_tree = to_list_ast(tokens)
    return list_tree

print(parse("((lambda (x) (* x x)) ((lambda (x) (* x x)) 3))"))

[['lambda', ['x'], ['*', 'x', 'x']], [['lambda', ['x'], ['*', 'x', 'x']], '3']]

在这个例子中，在 reduce 的时候，算法并没有到语法字典（如 grammar book）里查询，因为 lisp 代码的每个 s-expression 本身就标记了这个表达式对应的语法，比如 (lambda (x) x) 的语法标签可以认为就是 lambda, (* x x) 的语法标签是乘法 * ，这种把字符串里的关键运算符直接作为语法标签节点的结构一般不被称为解析树， 而是叫作抽象语法树，而解析树还有一个名称– 具体语法树。“具体”和“抽象”的区别在于，解析树（具体语法树）里包括 语法词典（或者文法）里的语法标签名，而抽象语法树里则没有，有的只是 token 之间的关系。

另外，由于 lisp 的求值模式更为复杂，因此这里没有像上一节计算器的例子里直接返回表达式的最终值，而是返回一个 嵌套 list 表达的解析树，该解析树一般可以作为参数传入到 evaluate 函数中求出表达式的值，这是编程语言解释器设计的内容，本文不做详细说明，但下一节会用一个足够 简单的例子来展示出解析和求值的两个步骤。

由于后缀表达式计算函数非常简单，因此据说一些早期计算器（比如惠普）会基于这种表达式实现核心求值函数，然后额外实现 将其他表达式转换成后缀表达式的解析算法，被称为运算优先级解析器（operator precedence parsers）。

由于对称性，似乎比较容易把前缀表达式转换成后缀表达式，但要注意的是：

• 不能在字符串层面直接去做反转, 因为会把 123 变成 321
• 也不能在分词后 token list 层面直接反转，因为会把 [- 3 2] 变成 [2 3 -], 前者结果是 1, 后者是 -1

因此这里要反转的只是运算符的顺序，

grammar_book = {"+","-","*","//"}
def prefix2suffix(exp):
    stack = []
    result = []
    for t in exp:
        if t not in grammar_book:
            stack.append(int(t))
        else:
            while stack:
                result.append(stack.pop())
            result.append(t)
    
    while stack:
        result.append(stack.pop())
    return result[::-1]

exp = "* + 3 4 // 8 2".split()
suffix_exp = prefix2suffix(exp)
print(suffix_exp)
print(eval_reverse_polish(suffix_exp))

[8, 2, '//', 3, 4, '+', '*']
28

该算法的一些特点：

• 用一个 stack 来保存运算对象，另一个 stack （result 可以看作 stack）保存整个结果
• 函数返回的是一个 list 而不是 string ， list 是一种内存中结构，因此这种算法才称为 parsing, 如果输出

字符串的话，也许称为翻译或编译。

接着考虑如何将一般的中缀表达式转换为不带括号的后缀表达式？先假设表达式中没有括号，比如 1+2*3, 乘法优先级高于 加法，和前缀转后缀算法不一样的是，可以构造一个专门保存运算符的栈，扫描过程中，对于数字，直接添加到结果数组（或栈），因为优先级高的运算放在末尾，因此当前运算符优先级低于栈顶运算符时，当前运算符就必须出栈（因为栈是先进后出的，因此后出的运算符优先级更高），类似地，如果是相同优先级，中缀表达式是按从左到右顺序执行，因此先入栈的运算符应该 先计算，此时也需要弹出。

接着考虑加入了括号的场景，上一节 lisp 解析中，当遇到右括号，那么就说明组成了一个子表达式，在本算法里，括号 意味着括号里的运算符优先计算，因此，一旦遇到右括号，应该直接把运算符栈顶的运算弹出去。

完整算法实现如下：

def infix2suffix(exp: list):
    ops = {"_":-2,"(":-1, "+":0, "-": 0,  "*": 1, "//":1 }
    op_stack = ["_"] # placeholder
    res = []
    for t in exp:
        if t == ")":
            res.append(op_stack.pop())
            assert op_stack.pop() == "(", "() should be matched"
        elif t == "(":
            op_stack.append(t)
        elif t not in ops:
            res.append(t)
        elif ops[t] > ops[op_stack[-1]]:
            op_stack.append(t)
        elif ops[t] <= ops[op_stack[-1]]:
            res.append(op_stack.pop())
            op_stack.append(t)
    while len(op_stack)> 1:
        res.append(op_stack.pop())
    return res

for exp in [
        "1 + 2 * 3 - 4" ,
        "( 1 + 2 ) * 3 - 4",
        "( 1 + 2 ) * ( 3 - 4 )",
        "3 + 4 * 2 // ( 1 - 5 ) * 2 * 3"
]:
    exp = exp.split()
    print(infix2suffix(exp))
    print(eval_reverse_polish(infix2suffix(exp)))

['1', '2', '3', '*', '4', '-', '+']
3
['1', '2', '+', '3', '*', '4', '-']
5
['1', '2', '+', '3', '4', '-', '*']
-3
['3', '4', '2', '*', '1', '5', '-', '//', '2', '*', '3', '*', '+']
-9

这种算法最初由 Edsger Dijkstra 提出，称为 Shunting yard algorithm, 名称很是形象。

现在的问题是，既然可以从中缀表达式解析成后缀，为什么不直接就求值呢？还要转成这么别扭的后缀表达式？

这是因为对于某些机器，其 cpu 实现就是一个基于栈的模型，而不是现在典型的 寄存器机器，这种机器的汇编可能直接就有 push pop 之类的原语，因此用后缀表达式（运算符对应出栈，数字是入栈）可以更方便编译成这种栈机器的汇编

比如假设以下是某个栈机器支持的汇编：

code = [('const', 2), ('const', 3), ('const', 0.1) , ("mul",), ("add",)]

它实际是 "2 3 0.1 * +" 的编译结果，那么可以实现一个很简单的编译器：

def stack_compiler(suffix):
    assemble = []
    op2code = {"+":"add","-":"minus","*":"mul","//": "div"}
    for ele in suffix.split():
        if ele not in op2code:
            assemble.append(('const', float(ele) if "." in ele else int(ele)))
        else:
            assemble.append((op2code[ele],))
    return assemble

print(stack_compiler("2 3 0.1 * +"))

[('const', 2), ('const', 3), ('const', 0.1), ('mul',), ('add',)]

这种汇编语言，比如 "const" 2 在机器码层面可能对应的是 1101 0010, 其中 1101 是 const 的编码，而 1101 在数字电路层面，可能就对应了 push 操作，会将 0010 移动到某个内存栈上。比如以下是栈机器的简单模拟器：

class Machine:
    _binary = {"add": lambda a,b: a+b,
               "mul": lambda a,b: a*b,
               "div": lambda a,b: a//b,
               "minus": lambda a,b: a-b,}
    def __init__(self):
        self.stack = []

    def push(self, ele):
        self.stack.append(ele)

    def pop(self):
        return self.stack.pop()
        
    def execute(self, instructions):
        for op, *args in instructions:
            if op == "const":
                self.push(args[0])
            elif op in self._binary:
                right = self.pop()
                left = self.pop()
                self.push(self._binary[op](left, right))

        res = self.stack.pop()
        return res

Machine().execute(stack_compiler("2 3 0.1 * +"))

2.3

以上代码参考了 A Talk Near the Future of Python (a.k.a., Dave live-codes a WebAssembly Interpre_哔哩哔哩_bilibili 前几分钟里给出的例子，如果想了解如何给这个机器加上内存指令，比如 load, store, 如何执行函数，循环等，可以看完整个视频。

实际上， python 的虚拟机就类似一个栈机器，比如 x+y*z 这段代码，反汇编之后结果如下：

import dis
x = 1
y = 2
z = 3
dis.dis(lambda :x+y*z)

5           0 LOAD_GLOBAL              0 (x)
            2 LOAD_GLOBAL              1 (y)
            4 LOAD_GLOBAL              2 (z)
            6 BINARY_MULTIPLY
            8 BINARY_ADD
           10 RETURN_VALUE

python 字节码对应就是类似 x y z * + 的后缀表达。

其他栈机器的参考： Stack machine - Wikipedia

本节用命题逻辑的例子来展现用 shift-reduce 方式自下而上构建（抽象）语法树，并且用递归方式自上而下后序遍历语法树从而求值。

考虑称为命题逻辑的语言，每个命题用变量来表示，比如 p,q,r, 同时这些变量加上数字也是合法变量，比如 p12, q234 ，这是词法描述。语法层面，用递归的方式来定义，比如 P, Q 都是命题，那么：

~P 是合法命题
(P&Q) 是合法命题
(P|Q) 是合法命题
(P->Q) 是合法命题

因此，在这个规则下，"~((p->q)|r)" 就是一个合法的命题逻辑字符串

额外地，我们还定义 T 和 F 表示常量，其语义就是 python 中的 True 和 False,

可以写出以下几个（词法）判定函数：

def is_constant(string: str) -> bool:
    return string == 'T' or string == 'F'

def is_unary(string: str) -> bool:
    return string == '~'

def is_binary(string: str) -> bool:
    return string == '&' or string == '|' or string == '->'

def is_variable(string: str) -> bool:
    return (
        string[0] >= "p"
        and string[0] <= "z"
        and (len(string) == 1 or string[1:].isdecimal())
    )

接着用类来定义逻辑公式的抽象语法树（因为这个结构中不包括 CFG 文法中的变量），并实现语法树的打印算法：

from __future__ import annotations
from typing import Mapping, Optional, Set, Tuple, Union
class Formula:
    root: str
    first: Optional[Formula]
    second: Optional[Formula]

    def __init__(self, root: str, first: Optional[Formula] = None,
                 second: Optional[Formula] = None):
        if is_variable(root) or is_constant(root):
            assert first is None and second is None
            self.root = root
        elif is_unary(root):
            assert first is not None and second is None
            self.root, self.first = root, first
        else:
            assert is_binary(root)
            assert first is not None and second is not None
            self.root, self.first, self.second = root, first, second

    def __repr__(self) -> str:
        if is_variable(self.root) or is_constant(self.root):
            return self.root
        elif is_unary(self.root):
            return self.root + repr(self.first)
        return f"({repr(self.first)}{self.root}{repr(self.second)})"

    def variables(self) -> Set[str]:
        res = set()
        def dfs(formula):
            if is_constant(formula.root):
                return
            if is_variable(formula.root):
                res.add(formula.root)
                return
            if hasattr(formula, "first"):
                dfs(formula.first)
            if hasattr(formula, "second"):
                dfs(formula.second)

        dfs(self)
        return res


f = Formula('~', Formula('&', Formula('p'), Formula('q76')))
print(f, f.variables())

~(p&q76) {'p', 'q76'}

注意以上 Formula 类中对各个参数都进行了复用：

• 对于变量或者 T/F 常量，root 直接指向变量名或 T/F，first 和 second 为 None
• 如果是 ~P 类型的节点，那么 root 就是 ~, first 就是 P, second 为 None;
• 如果是 (P|Q) 类型节点， root 就是 |, first 和 second 分别为 P 和 Q

以上还实现了一个 dfs 算法去遍历语法树，从而得到所有的变量，方便以下求值函数。

为了对逻辑表达式求值，需要给出各个变量的真假值，这些变量的真假值的集合称为模型，它就是一个字典，其中 key 覆盖了表达式里的所有变量，value 是真或者假，那么求值函数的实现如下：

def evaluate(formula: Formula, model: dict) -> bool:
    assert formula.variables().issubset(set(model.keys()))
    if formula.root == "T":
        return True
    if formula.root == "F":
        return False
    if is_unary(formula.root):
        return not evaluate(formula.first, model)
    if is_variable(formula.root):
        return model[formula.root]
    if formula.root == "&":
        return evaluate(formula.first, model) and evaluate(formula.second, model)
    if formula.root == "|":
        return evaluate(formula.first, model) or evaluate(formula.second, model)
    if formula.root == "->":
        return not evaluate(formula.first, model) or evaluate(formula.second, model)

这时候，给定公式和一个模型，，就可以求值了：

f = Formula('~', Formula('&', Formula('p'), Formula('q76')))
model = {"p":True, "q76":False}

evaluate(f, model)

True

但目前我们还无法把一个 ~(p&q76) 类型的字符串反向解析成 Formula 对象进行求值，为此需要编写 parsing 算法。由于任何命题表达式（除了变量如 p 和 p1）都是 prefix-free 的，因此可以用 shift-reduce 算法。

注意命题变量名不是 prefix-free 并不会导致问题，因为变量名的词法规则可以写成：

VAR_NAEM: p
VAR_NAEM: pInt

由于 p 是一个长度为 1 的常量，它不能被扩展，因此我们在检查的时候只需要额外检查两个字符就可以区分出两个变量， 因此从两个字符的角度来看，它的词法可以写成以下形式

VAR_NAEM: pEMPTY
VAR_NAEM: pInt

pEMPTY 和 pInt 是 prefix-free 的。

以下是解析算法：

def logic_parse(s: str) -> Formula:
    op_stack = [] # 存储 ~, |, &, ->
    stack = [] # 存储变量或 formula 
    def handle_not(i, t):
        if op_stack and op_stack[-1] == "~" and stack and type(stack[-1]) is Formula:
            stack[-1] = Formula("~", stack[-1])
            op_stack.pop()
    for i,t in enumerate(s):
        if t == " ":
            continue
        elif t in {"~","|","&", "-"}:
            op_stack.append(t)
        elif t == ">": # merge "->"
            op_stack[-1] += t
        elif t in "pqr0123456789":
            stack.append(t if t in "pqr" else stack.pop() + t)
            if i+1 == len(s) or s[i+1] not in "0123456789": # lookahead
                stack.append(Formula(stack.pop()))
                handle_not(i, t)
        elif t in "TF": # direct parse to a Tree Node
            stack.append(Formula(t))
            handle_not(i, t)
        elif t == "(":
            op_stack.append(t)
        elif t == ")": # pop and reduce
            op = op_stack.pop()
            if op == "~":
                stack[-1] = Formula("~", stack[-1])
            else:
                second, first = stack.pop(), stack.pop()
                stack.append(Formula(op, first, second))
                handle_not(i, t)
            assert op_stack[-1] == "(", "parenthsis should be match"
            op_stack.pop()
        else:
            stack.append(t)
    while op_stack:
        op = op_stack.pop()
        assert op == "~"
        stack[-1] = Formula("~", stack[-1])
        
    return stack[0]

print(logic_parse("~((p&q1)->r)"))
print(evaluate(logic_parse("(~((p&q1)->r))"), {"p": True, "q1": False, "r": True}))

~((p&q1)->r)
False

一些说明：

• 以上算法假定输入的字符串都是单行的，因此直接忽视空格而不考虑换行。
• 当变量解析结束后，需要将其包装成 Formula, 这里需要多看一个字符（lookahead），检查当前字符是否是变量名最后一个字符，比如 p1234, 解析到 4 的时候发现下一个字符不是 int （或结束），那么就要把整个字符串变量包装成 Formula 对象。

• 由于否定运算 ~p 可以不需要括号，并且有最高的优先级，这使得只要当前解析到一个新的完整 formula, 就应该检查 op_stack 里是否有 ~ ，如果有的话马上组装成一个新的 formular 。而新的完整 formula 构建有三种情况：

  • 遇到右括号 ")" 后的 reduce
  • 遇到 T/F 后的 reduce
  • 解析完整个变量后的 reduce

  前两者都好办，问题在于最后一个，当遇到 p 时需要触发 ~ 检查，遇到 p123 时也需要，这使得我们还是需要一个 lookahead 机制，如果当前是 pqr 但下一个不是数字，那么要触发 ~ 检查，如果当前是数字并且下一个不是数字 就

• 当循环结束后，还要清空 op 栈
• 这个算法中也有一个 op_stack, 这和 Shunting yard 算法一样，而本算法中的 stack 和 shunting yard 算法里的 res 也是类似的结构。

关于这个语言的解析（包括 prefix-free 的证明）和求值的更详细说明，可以参考： 数理逻辑及其 python 实现 第一和第二章

到目前为止，我们只在谈论语言的现象，即 prefix-free 性质（可能是隐含的，比如不带括号的后缀表达式），这种性质体现在属于这个语言的所有字符串之间，但属于某种语言的具体的字符串是无限的（比如回文），而生成这些 字符串的规则是有限的，因此如果我们能够直接从语法规则层面来谈论 prefix-free, 那么在 CFG 里划定一个子集，通过这个子集中文法生成的语言就都有 prefix-free 性质，这样的话对于设计出能够被高效解析的编程语言 就有一个明确的指导。

而实践发现，要能够在语法层面说清楚 prefix-free, 光限制生成规则右侧变量的数量（比如 CNF) 或者某些变量的排列顺序是不够的， 我们需要谈论用 CFG 生成具体字符串时，替换变量的顺序，这就引出了派生（derivation) 的概念。

这里选择 Context-free grammar - Wikipedia 中的例子：

S->S+S
S->1
S->a

根据以上文法生成 1+1+1 有很多条路径：

1. S->S+S, ->1+S, ->1+S+S, ->1+1+S, ->1+1+1 最左派生，因为每次展开公式里第一个变量， 对应的解析树：

      S
    / | \
   S  +  S
   |   / | \
   1  S  +  S
      |     |
      1     1
   

2. S->S+S, ->S+S+S, ->1+S+S, ->1+1+S, ->1+1+1 第二个公式由展开第一个 S 得到，这也是最左派生，但对应的解析树和 1 不一样，如下

         S
       / | \
      S  +  S
    / | \   |
   S  +  S  1
   |     |
   1     1
   

3. S->S+S, ->S+S+S, ->1+S+S, ->1+1+S, ->1+1+1 这条路径和 2 完全一样，但第二个公式由展开前一步的第二个 S 得到，它不是最左也不是最右派生，可以说是左右交替派生，对应的解析树和 1 的是一样的

      S
    / | \
   S  +  S
   |   / | \
   1  S  +  S
      |     |
      1     1
   

4. S->S+S, ->S+S+S, ->S+S+1, ->S+1+1, ->1+1+1 第二个公式由展开第二个 S 得到，这是最右派生，解析树和 3 一样

      S
    / | \
   S  +  S
   |   / | \
   1  S  +  S
      |     |
      1     1
   

5. S->S+S, ->S+1, ->S+S+1, ->1+S+S, ->1+1+1 （左右交替派生）

         S
       / | \
      S  +  S
    / | \   |
   S  +  S  1
   |     |
   1     1
   

6. S->S+S, ->S+1, ->S+S+1, ->S+1+1, ->1+1+1 （最右派生）

         S
       / | \
      S  +  S
    / | \   |
   S  +  S  1
   |     |
   1     1
   

实际还有其他的生成路径，但不在此一一列出，这里可以看到，以上语法中，最左派生可以有不同解析树，而不同派生可以有相同 解析树。

在实际编程中，我们并不会随机 去选择当前去展开哪个变量， 因此派生的顺序在实际算法中一般是确定的，而最常见的就是最左和最右派生。

如果对于任何一个符合语法的字符串，它只有唯一一条最左派生路径（因此也只有唯一的最左派生解析树），那么该语法被称为确定性上下文无法关文法（DCFG)。根据定义可知，以上例子的文法并不是 DCFG 。

可以证明，DCFG 文法生成的任何字符串（以及中间状态）都是 prefix free 的。比如说，给定字符串 xy 和 x, 如果他们都是通过某个 DCFG 生成的，那么根据定义，x 和 xy 都有唯一的最左派生路径，那么 x 的最左派生路径可能是 S=>1=> x ，而 xy 的最左派生路径是 S=>2=>xy, 由于最左派生的唯一性， S=>1=>x 一定是在 S=>2=>xy 中的一部分，但问题在于 S=>1=>x 中的这个 S 不可能是 S=>2=>xy 中的第一个 S, 否则 x 和 xy 就相同了，只可能在 S=>2->xy 中有一个子结构 S=>…S=>1=>x…=>xy, 但这意味着我们可以通过 S=>…S=>1=>x 生成 x, x 的最左派生路径就不唯一了。

注意这里 x 和 y 不单单是字符串，还可以是中间的变量。正是这种在各个层次的 prefix-free 性质使得我们可以从 CKY 的 \( n^{3} \) 复杂度降低到 O(n) 复杂度，因为它使得切分过一次之后左侧的对象的语法标签能够在 O(1) 复杂度内唯一确定下来（由解析树的树高决定）。

前文出现的算法中，不断出现了栈结构，它在计算机理论领域对应的是下推自动机，而各函数中 for 循环里的多个 if elif 条件判断，实际是在根据栈以及当前字符的状态来决定要进行的动作，比如是入栈（shift）还是进行抽象（打语法标签，也称 reduce），这种固定数量的条件分支语句在计算理论中对应的是有限状态机（DFA），因此在许多解析相关的书本里，在实现此类 算法时，会去讨论一个 DFA 表格（或者状态转移表格），实际就是 if else 的字典化（或者数据结构化）。

本章所有小节实际都是属于 LR 算法，这里 L 是从左到右扫描的意思，从算法里看是显而易见的，而 R 表示的是解析后构建 起来的解析树是最右派生，体现在解析过程中就是，越右侧的元素语法标签相对来说贴得越少（因此相当于有限被扩展成字符），一个例子如下：

文法：
E −→ E+T
E −→ T
T −→ id

Derivations for id + id:

LEFTMOST RIGHTMOST
(第二个 T 直到最后一步才派生成 id)
E =⇒ E+T
  =⇒ T+T
  =⇒ id+T
  =⇒ id+id

RIGHTMOST:

(T 在第二步就直接派生成 id, 体现在算法中，是因为 id 之前的元素都被解析了，最后只剩下 id 没有标签，因此贴上 T,
所以从解析树角度来看，派生越早的元素在 LR 算法中被解析得越晚，因为它是 bottom-up 的，而作为演示的派生过程
是 top-down 的):

E =⇒ E+T
  =⇒ E+id
  =⇒ T+id
  =⇒ id+id

参考： https://www3.cs.stonybrook.edu/~cse304/Fall08/Lectures/lrparser-handout.pdf

实现前文提到的命题逻辑语言的递归下降算法，思路是：

• 如果是 T 或 F, 直接返回包装后的 Formula
• 如果是 ~, 那么先解析其之后的所有内容，将返回的 Formula 添加上 ~ 构造新的 Formula
• 如果是变量，则要读取完整变量然后返回 Formula
• 如果匹配到左括号，那么先找到对应的右括号（需要计算左右括号数量），接着递归地解析括号内的对象

以下先实现一种纯直觉的朴素解析算法

from typing import Mapping, Optional, Set, Tuple, Union

def _parse_prefix(string: str) -> Tuple[Union[Formula, None], str]:
    if string == "":
        return None, "Empty Formula Error"
    if string[0] != "(":
        if is_constant(string[0]):  # T or F
            return Formula(string[0]), string[1:]
        if is_unary(string[0]):  # ~
            f, remain = _parse_prefix(string[1:])
            if f is None:
                return None, "Unary Syntax Error"
            return Formula("~", f), remain
        if not is_variable(string[0]):
            return None, "Variable Sytax Error"

        # read variable
        n = len(string)
        v_end = n
        for i in range(1, n):
            if not string[i].isdecimal():
                return Formula(string[:i]), string[i:]
        return Formula(string), ""
    else:
        # get first ()
        left_b = 0
        for i, ele in enumerate(string):
            if ele == "(":
                left_b += 1
            elif ele == ")":
                left_b -= 1
            if left_b == 0:
                break

        f1, remain = _parse_prefix(string[1:i])
        if f1 is None:
            return None, remain
        if not remain or (
            remain[0] not in ["|", "&", "+"]
            and remain[:2] not in ["->"]
        ):
            return None, "binary syntax Error"
        if remain[0] in ["|", "&"]:
            root = remain[0]
            f2, remain = _parse_prefix(remain[1:])
            if remain != "":
                return (
                    None,
                    f"Error: {string[:i+1]} is Not a valid formula",
                )
            return Formula(root, f1, f2), string[i + 1 :]
        if remain[:1] == "-":
            operator = remain[:2]
            f2, remain = _parse_prefix(remain[2:])
            if remain != "":
                return (
                    None,
                    f"Error: {string[:i+1]} is Not a valid formula",
                )
            return Formula(operator, f1, f2), string[i + 1 :]

print(_parse_prefix("~(p&(q->r))"))

(~(p&(q->r)), '')

上一节基本是一种非常朴素的思路，匹配到括号，然后去去递归解析，但如果给出文法，可以依照文法的规则去编写 LL 解析器

CONST: "T" | "F"
VAR: {"p"|"q"|"r"} [0-9]*
OR: "(" E "|" E ")"
AND: "(" E "&" E ")"
IMP: "(" E "->" E ")"
NOT: "~" E
EXP: OR | AND | IMP | NOT | CONST | VAR

相比于 shift/reduce, LL 是一种采用 predict/match 策略的算法，根据 prefix-free 性质，查看前几个字符确定 当前会是什么样的语法结构，然后用特定的函数直接去匹配字符串。

该文法没有左递归，我们用一个类来处理，以上每一行都封装成一个子匹配函数

class LLParser():
    def __init__(self, s):
        self.s = "".join(s.split()) # delete spacees
        self.i = 0

    def match_const(self):
        f = Formula(self.s[self.i]) 
        self.i += 1
        return f

    def match_var(self):
        start = self.i
        self.i += 1
        while self.s[self.i] in "0123456789" and i < len(self.s):
            self.i += 1
        return Formula(self.s[start: self.i])
        
    def match_op(self):
        if self.s[self.i] == "|":
            res, offset = "|", 1
        elif self.s[self.i] == "&":
            res, offset = "&", 1
        elif self.s[self.i] == "-":
            res, offset = "->", 2
        self.i += offset
        return res

    def match_binary(self):
        assert self.s[self.i] == "("
        self.i += 1
        first = self.match_exp()
        op = self.match_op()
        second = self.match_exp()
        assert self.s[self.i] == ")"
        self.i += 1
        return Formula(op, first, second)

    def match_not(self):
        assert self.s[self.i] == "~"
        self.i += 1
        first = self.match_exp()
        return Formula("~", first)

    def match_exp(self):
        if self.i == len(s):
            return None, ""
        elif self.s[self.i] in "pqr":
            return self.match_var()
        elif self.s[self.i] in "TF":
            return self.match_const()
        elif self.s[self.i] == "~":
            return self.match_not()
        elif self.s[self.i] == "(":
            return self.match_binary()
        else:
            raise Exception("invalid expression")

LLParser("~(p&(q->r))").match_exp()

~(p&(q->r))

可以看到，如果给出了文法，编写 LL parser 是一件比较机械的事情，很多语法结构和代码是一一对应的，比如文法中的 | 对应的就是 if else, 文法中的 [0-9]* 就是 for 循环。这或许是为什么 Backus 在通过经验试错设计出 Fortran 语言之后，着手设计第二个语言的时候引入了 BNF 文法，这样他就可以系统地文法来谈论语言解析了。 这就像计算理论中用下推自动机可以更系统地描述栈，用 DFA 可以更系统地描述 if else 判断，因为相比不同编程语言不同机器上栈、条件判断语言表达的多样性，下推自动机和 DFA 是一套更统一的数学化符号语言 本文更多是以 python 编程语言实现案例并添加自然语言解说来谈论这些思想，而不是用严格的符号化语言。

这种文法和编程实现一一对应的规整性质带来的另一个好处是，编写 parser 这件事情是可以自动化的，这引出了 parser generator, 只要给出文法就可以输出类似以上功能的程序文件，然后执行这个程序就可以返回一个解析树。

上一节是从面向对象角度编写出一个 LL parser, 本节则用函数式的方式

整个 parser 高层躬耕伪代码如下：

def parser(s):
    # 读取 s 中部分子串
    return result, remain

接着向下一层，确定更具体规则，比如从左到右解析的场景：

def parser(arguments):
    def inner(s):
        return result, s
    return inner

从这个角度看，在递归树上任何一个节点的过程都可以看作一个 parser, 比如解析一个空格，一个特定字母或数字，这些 parser 可以组合起来解析更大的对象，比如多个解析数字的 parser 用 for 循环组合起来就可以解析一个数字字符串，继续组合可以解析数组、字典等等，由于这种组合性，他们都被称为 parser combinator.