无法计算得到跟随集

Question

一段时间以来，我一直在尝试计算语法的后续集，但又遇到了另一个问题。这是我的跟随集计算器：def gen_follow_set(grammar, start_sym, first_sets):    follow_sets = {nterm: set() for nterm in grammar}    follow_sets[start_sym].add("$")    for _, prods in grammar.items():        for alt in prods:            for item in alt:                if item.isupper():                    follow_sets[item] = set()    while True:        changes = copy.deepcopy(follow_sets)        for nterm, prods in grammar.items():            for alt in prods:                for i, item in enumerate(alt):                    la = alt[i + 1] if i + 1 != len(alt) else nterm                    if i == len(alt) - 1 and item != "":                        follow_sets[item] |= follow_sets[nterm]                    elif item != "":                        if "" in first_sets[la]:                            follow_sets[item] |= first_sets[la].union(                                first_sets[alt[i + 2] if i + 2 <= len(alt) -                                           1 else nterm]) - {""}                        else:                            follow_sets[item] |= first_sets[la]        if changes == follow_sets:            return follow_sets这被称为：grammar = {    "expr": [["term", "etail"]],    "term": [["LPAREN", "expr", "RPAREN"], ["INT", "ttail"]],    "etail": [["PLUS", "expr"], [""]],    "ttail": [["TIMES", "term"], [""]]}first = calc_first_set(...)pprint.pprint(gen_follow_set(grammar, "expr", first))etail并且expr是正确的，但term并不ttail正确。我怎样才能得到正确的答案？

Answer 1

每当非终结N符出现在生产中时

M → α N β

我们有

1. FIRST(α) ⊂ FOLLOW(N)

2. 如果β可以为空，那么FOLLOW(M) ⊂ FOLLOW(N)

如果 β 为空（即N在产生式末尾）或 β 中的第一个符号不可为空，则您的代码可以正常工作。在其余情况下，您的代码有错误：

• 如果 β 中的第一个符号可以为空，则将 FIRST(β) 计算为 β 中前两个符号的 FIRST 集的并集。由于您从不检查第二个（或后续）符号是否可为空，因此您可能会错过 FIRST(β) 中的符号。

• 仅测试下一个符号的可空性的另一个结果是您不计算 NULLABLE(β); 相反，您使用 β 中第一个符号的可空性。所以你可能会错过FOLLOW(M).

我不相信这些错误中的任何一个都是由您的实际语法触发的。但下一个是；

• 如果您的（不充分的）测试表明 β 可以为空，请使用FIRST(M)而不是FOLLOW(M).

• 一个密切相关的问题是，如果已经达到生产的结尾，则计算la哪个提议作为下一个符号。term这将导致使用FIRST(term)而不是FOLLOW(term)，但当然这永远不会发生，因为使用的唯一代码分支在生产结束时la不会执行。N既然如此，la其实是没有必要的。