首頁猿問無法計算得到跟隨集

無法計算得到跟隨集

Python

翻過高山走不出你 2022-10-25 15:48:34

一段時間以來，我一直在嘗試計算語法的后續(xù)集，但又遇到了另一個問題。這是我的跟隨集計算器：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正確。我怎樣才能得到正確的答案？

查看完整描述

1 回答

慕哥9229398

TA貢獻1877條經(jīng)驗獲得超6個贊

每當非終結(jié)N符出現(xiàn)在生產(chǎn)中時

M → α N β

我們有

FIRST(α) ? FOLLOW(N)
如果β可以為空，那么FOLLOW(M) ? FOLLOW(N)

如果 β 為空（即N在產(chǎn)生式末尾）或 β 中的第一個符號不可為空，則您的代碼可以正常工作。在其余情況下，您的代碼有錯誤：

如果 β 中的第一個符號可以為空，則將 FIRST(β) 計算為 β 中前兩個符號的 FIRST 集的并集。由于您從不檢查第二個（或后續(xù)）符號是否可為空，因此您可能會錯過 FIRST(β) 中的符號。
僅測試下一個符號的可空性的另一個結(jié)果是您不計算 NULLABLE(β); 相反，您使用 β 中第一個符號的可空性。所以你可能會錯過FOLLOW(M).

我不相信這些錯誤中的任何一個都是由您的實際語法觸發(fā)的。但下一個是；

如果您的（不充分的）測試表明 β 可以為空，請使用FIRST(M)而不是FOLLOW(M).
一個密切相關(guān)的問題是，如果已經(jīng)達到生產(chǎn)的結(jié)尾，則計算la哪個提議作為下一個符號。term這將導致使用FIRST(term)而不是FOLLOW(term)，但當然這永遠不會發(fā)生，因為使用的唯一代碼分支在生產(chǎn)結(jié)束時la不會執(zhí)行。N既然如此，la其實是沒有必要的。