Python - Невозможно рассчитать, чтобы получить следующий набор

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))

Это выводит:

Working on: term ; la has epsilon; la: etail
Working on: etail ; it is at the end of the production: expr
Working on: LPAREN ; la doesn't have epsilon; la: expr
Working on: expr ; la doesn't have epsilon; la: RPAREN
Working on: RPAREN ; it is at the end of the production: term
Working on: INT ; la has epsilon; la: ttail
Working on: ttail ; it is at the end of the production: term
Working on: PLUS ; la doesn't have epsilon; la: expr
Working on: expr ; it is at the end of the production: etail
Working on: TIMES ; la doesn't have epsilon; la: term
Working on: term ; it is at the end of the production: ttail
Working on: term ; la has epsilon; la: etail
Working on: etail ; it is at the end of the production: expr
Working on: LPAREN ; la doesn't have epsilon; la: expr
Working on: expr ; la doesn't have epsilon; la: RPAREN
Working on: RPAREN ; it is at the end of the production: term
Working on: INT ; la has epsilon; la: ttail
Working on: ttail ; it is at the end of the production: term
Working on: PLUS ; la doesn't have epsilon; la: expr
Working on: expr ; it is at the end of the production: etail
Working on: TIMES ; la doesn't have epsilon; la: term
Working on: term ; it is at the end of the production: ttail
Working on: term ; la has epsilon; la: etail
Working on: etail ; it is at the end of the production: expr
Working on: LPAREN ; la doesn't have epsilon; la: expr
Working on: expr ; la doesn't have epsilon; la: RPAREN
Working on: RPAREN ; it is at the end of the production: term
Working on: INT ; la has epsilon; la: ttail
Working on: ttail ; it is at the end of the production: term
Working on: PLUS ; la doesn't have epsilon; la: expr
Working on: expr ; it is at the end of the production: etail
Working on: TIMES ; la doesn't have epsilon; la: term
Working on: term ; it is at the end of the production: ttail
{'INT': {'INT', 'TIMES', 'LPAREN'},
 'LPAREN': {'INT', 'LPAREN'},
 'PLUS': {'INT', 'LPAREN'},
 'RPAREN': {'INT', 'LPAREN', 'PLUS'},
 'TIMES': {'INT', 'LPAREN'},
 'etail': {'$', 'RPAREN'},
 'expr': {'$', 'RPAREN'},
 'term': {'INT', 'LPAREN', 'PLUS'},
 'ttail': {'INT', 'LPAREN', 'PLUS'}}

etail и expr верны, но term и ttail не верны. Как я могу получить правильный ответ?

Answer 1

Всякий раз, когда нетерминал N появляется в производстве

M → α N β

У нас есть

1. FIRST(α) ⊂ FOLLOW(N)

2. Если β обнуляем, то FOLLOW(M) ⊂ FOLLOW(N)

Ваш код работает правильно, если β пуст (т. Е. N находится в конце производства) или если первый символ в β не обнуляется. В остальных случаях ваш код содержит ошибки:

• Если первый символ в β обнуляется, вы вычисляете FIRST (& beta) как объединение наборов FIRST первых двух символов в β. Поскольку вы никогда не проверяете, являются ли вторые (или последующие) символы обнуляемыми, вы можете пропустить символы в ПЕРВОМ (β).

• Другим результатом проверки только обнуляемости следующего символа является то, что вы не вычисляете NULLABLE (β); вместо этого вы используете обнуляемость первого символа в β. Так что вы можете пропустить символы в FOLLOW(M).

Не думаю, что какие-либо из этих ошибок вызваны вашей фактической грамматикой. Но следующий:

• В случае, если ваш (недостаточный) тест показывает, что β обнуляем, вы используете FIRST(M) вместо FOLLOW(M).

• Тесно связанной проблемой является вычисление la, которое предлагает term в качестве следующего символа, если достигнут конец производства. Это привело бы к использованию FIRST(term), а не FOLLOW(term), но, конечно, этого никогда не произойдет, поскольку единственная ветвь кода, которая использует la, не выполняется, если N находится в конце производства. В таком случае la на самом деле не требуется.