使用非递归的预测分析表做语法分析——预测分析表的生成

小鸡
阅读587喜欢0·python 编译发表2019-5-29更新2019-6-3

First集构造流程

对于产生式 E -> ＡＢＣ

  1. 若右边第一个符号是终结符或 null ，则直接将其加入 First（E）
  2. 若右边第一个符号是非终结符，则将其 First 集的的非 null 元素加入 First（E）
  3. 若右边第一个符号是非终结符而且紧随其后的是很多个非终结符，这个时候就要注意是否有 null 。
  4. 若第 i 个非终结符的 First 集有 null ，则可将第 i+1 个非终结符去除 null 的 First 集加入 First（E）。
  5. 若所有的非终结符都能够推导出 null ，则将 null 也加入到 First（E）

Follow集构造流程

  1. 将#符号加入产生开始的非终结符Ｅ
  2. 将所有产生式右部的非终结符的follow集合等于自身follow集合加上后继节点first集合 
    E.G. 用 A -> aBC 来说就是，当前扫描到 B 了，而 B 的右侧有非终结符 C，则将去掉 null 的 First（C）加入 Follow（B）中。若存在 C -> null ，则将 Follow（A）也加入 Follow（B）中。
  3. 若右边没有符号了，例如这里的 C，那么可以将 Follow（A）中的元素全部加入到 Follow（C）中。

一个问题

其中生成follow集合的过程较为复杂（我不知道正常情况是不是这样）非终结符的后继非终结符的first集合可能存在如下情况

  1. A -> BC
  2. C -> D | null
  3. D -> (A) | i

那么在一次遍历过程中，因为C的first集合存在null，所以需要将follow（A）加入follow（B） （重点）但是！此时的follow（A），并不是完整的，它可能在后续的遍历中会继续更新自身的follow集合所以此时follow(B) 中加入的follow(A) 并不是完整的follow（A）

为了解决这种情况，我加入了订阅者模式，一种实时更新的机制，订阅者为一个字典，字典键值为产生式左部，字典内容为产生式右部。 
简而言之：follow（A）发生了更新，那么曾经将follow（A）加入自身的B，C也更新其follow。并且，这是一个递归过程。详细说明见代码。

  1. observer = {}
  3. """
  4. 初始化订阅者
  5. 订阅者： 用于求follow集合的过程中特殊情况：
  6.     非终结符的后继非终结符的first集合可能存在null
  7.     eg： A -> BC     C -> D | null   D -> (A) | i
  8.     那么在一次遍历过程中，因为C的first集合存在null，所以需要将follow（A）加入follow（B）
  9.     （重点）但是！此时的follow（A），并不是完整的，它可能在后续的遍历中会继续更新自身的follow集合
  10.     所以此时会出现遗漏的follow
  11.     所以我在这里用到一个订阅者模式
  12.     订阅者为一个字典，字典键值为产生式左部，字典内容为产生式右部
  13. """
  14. def init_observer():
  15.     for k in grammars:
  16.         follow_table[k] = []
  17.         observer[k] = []
  18.         for next_grammar in grammars[k]:
  19.             last_k = next_grammar.split()[-1]
  20.             if last_k in grammars and last_k != k:
  21.                 observer[k].append(last_k) 
  22. """
  23. 刷新订阅
  24. 检测到某个follow集合更新时，对其订阅的所有产生式左部的follow集合进行更新
  25. 简而言之：follow（A）发生了更新，那么曾经将follow（A）加入自身的B，C也更新其follow
  26. 并且，这是一个递归过程
  27. """
  28. def refresh(k):
  29.     for lk in observer[k]:
  30.         newlk = U(follow_table[k], follow_table[lk])
  31.         if newlk != follow_table[lk]:
  32.             follow_table[lk] = newlk
  33.             refresh(lk)

预测表的构造

  1. 对于每个属于 First(B) 的终结符 m ，都把 A -> BC 添加到预测表中的 [A, m] 中去
  2. 如果 null 也属于 First(B)，那么对于任何属于 Follow(A) 的字符 n，都把 A -> null 加入到 [A, n] 中去

代码

  1. grammars = {
  2.     "Program":["type M C Pro"],
  3.     "C":["( cc )"],
  4.     "cc":["null"],
  5.     "Pro":["{ Pr }"],
  6.     "Pr":["P ; Pr", "null"],
  7.     "P":["type L", "L","printf OUT"],
  8.     "L":["M LM"],
  9.     "LM":["= E", "null"],
  10.     "M":["name"],
  11.     "E":["T ET"],
  12.     "ET":["+ T ET", "- T ET", "null"],
  13.     "T":["F TT"],
  14.     "TT":["* F TT", "/ F TT", "null"],
  15.     "F":["number", "BRA"],
  16.     "BRA": ["( E )"],
  17.     "OUT":["( " TEXT " , V )"],
  18.     "V":["name VV", "null"],
  19.     "VV":[", name VV", "null"],
  20. }
  22. first_table = {}
  23. follow_table = {}
  24. predict_table = {}
  25. observer = {}
  27. """
  28. 初始化订阅者
  29. 订阅者： 用于求follow集合的过程中特殊情况：
  30.     非终结符的后继非终结符的first集合可能存在null
  31.     eg： A -> BC     C -> D | null   D -> (A) | i
  32.     那么在一次遍历过程中，因为C的first集合存在null，所以需要将follow（A）加入follow（B）
  33.     （重点）但是！此时的follow（A），并不是完整的，它可能在后续的遍历中会继续更新自身的follow集合
  34.     所以此时会出现遗漏的follow
  35.     所以我在这里用到一个订阅者模式
  36.     订阅者为一个字典，字典键值为产生式左部，字典内容为产生式右部
  37. """
  38. def init_observer():
  39.     for k in grammars:
  40.         follow_table[k] = []
  41.         observer[k] = []
  42.         for next_grammar in grammars[k]:
  43.             last_k = next_grammar.split()[-1]
  44.             if last_k in grammars and last_k != k:
  45.                 observer[k].append(last_k) 
  46. """
  47. 刷新订阅
  48. 检测到某个follow集合更新时，对其订阅的所有产生式左部的follow集合进行更新
  49. 简而言之：follow（A）发生了更新，那么曾经将follow（A）加入自身的B，C也更新其follow
  50. 并且，这是一个递归过程
  51. """
  52. def refresh(k):
  53.     for lk in observer[k]:
  54.         newlk = U(follow_table[k], follow_table[lk])
  55.         if newlk != follow_table[lk]:
  56.             follow_table[lk] = newlk
  57.             refresh(lk)
  59. """
  60. 合并两个list并且去重
  61. """
  62. def U(A,B):
  63.     return list(set(A+B))
  65. """
  66. 查找指定非终结符的first集合
  67. """
  68. def find_first(key):
  69.     if key not in grammars:
  70.         return [key]
  71.     l = []
  72.     for next_grammar in grammars[key]: 
  73.         next_k = next_grammar.split()[0]
  74.         l.extend(find_first(next_k))
  75.     return l
  77. """
  78. 查找所有非终结符follow
  79. """
  80. def find_follow():
  81.     init_observer()
  82.     follow_table["E"] = ["#"]
  83.     for k in grammars:
  84.         for next_grammar in grammars[k]:
  85.             next_k = next_grammar.split()
  87.             for i in range(0,len(next_k)-1):
  88.                 if next_k[i] in grammars:
  89.                     if next_k[i+1] not in grammars:
  90.                         """
  91.                         如果后继字符不是终结符，加入
  92.                         """
  93.                         new_follow = U([next_k[i+1]], follow_table[next_k[i]])
  94.                         if new_follow != follow_table[next_k[i]]:
  95.                             follow_table[next_k[i]] = new_follow
  96.                             refresh(next_k[i])
  97.                     else:
  98.                         new_follow = U(first_table[next_k[i+1]], follow_table[next_k[i]])
  99.                         """
  100.                         如果后继字符的first集合中含有null，通知所有订阅者更新follow集合
  101.                         """
  102.                         if "null" in first_table[next_k[i+1]]:
  103.                             new_follow = U(follow_table[k], new_follow)
  104.                             observer[k].append(next_k[i])
  105.                         if new_follow != follow_table[next_k[i]]:
  106.                             follow_table[next_k[i]] = new_follow
  107.                             refresh(next_k[i])
  108.             """
  109.             产生式左部的follow集合加入最后一个非终结符的follow集合
  110.             """
  111.             if next_k[-1] in grammars:
  112.                 if next_k[-1] not in follow_table:
  113.                     follow_table[next_k[-1]] = []
  114.                 if next_k[-1] != k:
  115.                     follow_table[next_k[-1]] = U(follow_table[next_k[-1]], follow_table[k])
  117.     for k in follow_table:
  118.         if "null" in follow_table[k]:
  119.             follow_table[k].remove("null")
  121. """
  122. 获取所有非终结符的first集合
  123. 在此同时直接将first集合加入predict表中
  124. """
  125. def get_first_table():
  126.     for k in grammars:
  127.         predict_table[k] = {}
  128.         first_table[k] = []
  129.         for next_grammar in grammars[k]:
  130.             next_k = next_grammar.split()[0]
  131.             kl = find_first(next_k)
  132.             first_table[k].extend(kl)
  133.             for kk in kl:
  134.                 if kk != "null":
  135.                     predict_table[k][kk] = next_grammar
  137. """
  138. 将follow集合中的部分内容加入predict表中
  139. """
  140. def get_predict_table():
  141.     for k in grammars:
  142.         for next_grammar in grammars[k]:
  143.             next_k = next_grammar.split()[0]
  144.             if next_k in grammars and "null" in first_table[next_k] or next_k == "null":
  145.                 for fk in follow_table[k]:
  146.                     predict_table[k][fk] = next_grammar




随想
博客
机器学习
教程
邻家酒肆
前端
深度学习
算法
小程序
资源
cpp
html
javascript
python
sql
node

最近文章