亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

無法計算得到跟隨集

無法計算得到跟隨集

翻過高山走不出你 2022-10-25 15:48:34
一段時間以來,我一直在嘗試計算語法的后續集,但又遇到了另一個問題。這是我的跟隨集計算器: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 β

我們有

  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其實是沒有必要的。


查看完整回答
反對 回復 2022-10-25
  • 1 回答
  • 0 關注
  • 151 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號