无法计算得到跟随集

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&nbsp;→&nbsp;α&nbsp;N&nbsp;β我们有FIRST(α) ⊂ FOLLOW(N)如果β可以为空，那么FOLLOW(M) ⊂ FOLLOW(N)如果 β 为空（即N在产生式末尾）或 β 中的第一个符号不可为空，则您的代码可以正常工作。在其余情况下，您的代码有错误：如果 β 中的第一个符号可以为空，则将 FIRST(β) 计算为 β 中前两个符号的 FIRST 集的并集。由于您从不检查第二个（或后续）符号是否可为空，因此您可能会错过 FIRST(β) 中的符号。仅测试下一个符号的可空性的另一个结果是您不计算 NULLABLE(β);&nbsp;相反，您使用 β 中第一个符号的可空性。所以你可能会错过FOLLOW(M).我不相信这些错误中的任何一个都是由您的实际语法触发的。但下一个是；如果您的（不充分的）测试表明 β 可以为空，请使用FIRST(M)而不是FOLLOW(M).一个密切相关的问题是，如果已经达到生产的结尾，则计算la哪个提议作为下一个符号。term这将导致使用FIRST(term)而不是FOLLOW(term)，但当然这永远不会发生，因为使用的唯一代码分支在生产结束时la不会执行。N既然如此，la其实是没有必要的。