一段時間以來,我一直在嘗試計算語法的后續集,但又遇到了另一個問題。這是我的跟隨集計算器: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條經驗 獲得超6個贊
每當非終結N符出現在生產中時
M → α N β
我們有
FIRST(α) ? FOLLOW(N)如果
β可以為空,那么FOLLOW(M) ? FOLLOW(N)
如果 β 為空(即N在產生式末尾)或 β 中的第一個符號不可為空,則您的代碼可以正常工作。在其余情況下,您的代碼有錯誤:
如果 β 中的第一個符號可以為空,則將 FIRST(β) 計算為 β 中前兩個符號的 FIRST 集的并集。由于您從不檢查第二個(或后續)符號是否可為空,因此您可能會錯過 FIRST(β) 中的符號。
僅測試下一個符號的可空性的另一個結果是您不計算 NULLABLE(β); 相反,您使用 β 中第一個符號的可空性。所以你可能會錯過
FOLLOW(M).
我不相信這些錯誤中的任何一個都是由您的實際語法觸發的。但下一個是;
如果您的(不充分的)測試表明 β 可以為空,請使用
FIRST(M)而不是FOLLOW(M).一個密切相關的問題是,如果已經達到生產的結尾,則計算
la哪個提議作為下一個符號。term這將導致使用FIRST(term)而不是FOLLOW(term),但當然這永遠不會發生,因為使用的唯一代碼分支在生產結束時la不會執行。N既然如此,la其實是沒有必要的。
添加回答
舉報
0/150
提交
取消
