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

小鸡
阅读219 喜欢0 python 编译 更新2019-6-3

First集构造流程

对于产生式 E -> ABC

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