SLR1分析表构建的步骤如下:

  1. 对于每个非终结符A,求出A的FIRST集合和FOLLOW集合。
  2. 对于每个产生式A → α,将FIRST(α)中的所有终结符加入到A的FOLLOW集合中。
  3. 对于每个产生式A → α,对于FIRST(α)中的每个终结符a,将A → α加入到ACTION[A, a]中。
  4. 对于每个产生式A → α,如果ε ∈ FIRST(α),则对于FOLLOW(A)中的每个终结符a,将A → α加入到ACTION[A, a]中。
  5. 对于每个非终结符A,对于FOLLOW(A)中的每个终结符a,将A → ε加入到ACTION[A, a]中。
  6. 对于每个状态i,对于每个终结符a,如果GOTO[i, a] = j,则将GOTO[i, a]加入到GOTO表中。

下面是补充完整的SLR1分析表构建代码:

# 计算某个符号的FIRST集合
def first(symbol, productions, first_dict):
    if symbol in first_dict:
        return first_dict[symbol]
    if symbol.is_terminal():
        return set([symbol])
    result = set()
    for production in productions[symbol]:
        if production.is_empty():
            result.add(epsilon)
        else:
            first_set = first(production[0], productions, first_dict)
            result |= first_set
            i = 1
            while epsilon in first_set and i < len(production):
                first_set = first(production[i], productions, first_dict)
                result |= (first_set - set([epsilon]))
                i += 1
            if i == len(production) and epsilon in first_set:
                result.add(epsilon)
    first_dict[symbol] = result
    return result

# 计算所有符号的FIRST集合
def compute_first_set(start_symbol, productions):
    first_dict = {}
    for symbol in productions:
        first(symbol, productions, first_dict)
    return first_dict

# 计算某个非终结符的FOLLOW集合
def follow(symbol, start_symbol, productions, first_dict, follow_dict):
    if symbol in follow_dict:
        return follow_dict[symbol]
    result = set()
    if symbol == start_symbol:
        result.add(end_of_input)
    for non_terminal in productions:
        for production in productions[non_terminal]:
            if symbol in production:
                i = production.index(symbol)
                if i == len(production) - 1:
                    result |= follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
                else:
                    first_set = first(production[i + 1], productions, first_dict)
                    result |= (first_set - set([epsilon]))
                    if epsilon in first_set:
                        result |= follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
    follow_dict[symbol] = result
    return result

# 计算所有非终结符的FOLLOW集合
def compute_follow_set(start_symbol, productions, first_dict):
    follow_dict = {}
    for non_terminal in productions:
        follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
    return follow_dict

# 构建SLR1分析表
def build_slr1_table(start_symbol, productions):
    first_dict = compute_first_set(start_symbol, productions)
    follow_dict = compute_follow_set(start_symbol, productions, first_dict)
    table = {}
    for i, state in enumerate(states):
        for symbol in start_symbol + terminals:
            if symbol in goto_dict[i]:
                j = goto_dict[i][symbol]
                if symbol in terminals:
                    table[(i, symbol)] = ('S', j)
                else:
                    table[(i, symbol)] = ('G', j)
        for item in state:
            production = item.production
            if item.dot_index == len(production):
                for symbol in follow_dict[production.left]:
                    table[(i, symbol)] = ('R', production)
            elif production[item.dot_index].is_terminal():
                symbol = production[item.dot_index]
                j = goto_dict[i][symbol]
                table[(i, symbol)] = ('S', j)
            else:
                symbol = production[item.dot_index]
                for a in follow_dict[production.left]:
                    if (i, a) in table:
                        raise ValueError('Conflict')
                    table[(i, a)] = ('R', production)
    return table
``
请给出SLR1分析表构建的步骤给出补充完整的代码。

原文地址: http://www.cveoy.top/t/topic/hjMD 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录