用python编写LR(0)分析表的构造 含界面设计的完整代码注解

由于LR(0)分析表的构造过程比较复杂，因此我们需要将其分解为多个步骤来实现。以下是用python编写LR(0)分析表的完整代码注解：

from collections import defaultdict

# 定义文法
grammar = {
    'S': ['E'], # 文法规则1
    'E': ['E+T', 'T'], # 文法规则2
    'T': ['T*F', 'F'], # 文法规则3
    'F': ['(E)', 'id'] # 文法规则4
}

# 定义终结符号和非终结符号
terminals = {'+', '*', '(', ')', 'id'}
non_terminals = {'S', 'E', 'T', 'F'}

# 定义LR(0)自动机
action = defaultdict(dict) # 动作表
goto = defaultdict(dict) # 转移表

# 计算FIRST集和FOLLOW集
first = defaultdict(set)
follow = defaultdict(set)

# 计算FIRST集
def compute_first(symbol):
    if symbol in terminals:
        first[symbol].add(symbol)
    else:
        for rule in grammar[symbol]:
            if rule[0] in terminals:
                first[symbol].add(rule[0])
            else:
                compute_first(rule[0])
                first[symbol].update(first[rule[0]])

# 计算FOLLOW集
def compute_follow():
    follow['S'].add('$') # 将$添加到S的FOLLOW集中
    for symbol in non_terminals:
        for rule in grammar[symbol]:
            for i in range(len(rule)):
                if rule[i] in non_terminals:
                    if i == len(rule) - 1: # 如果该符号是产生式的最后一个符号
                        follow[rule[i]].update(follow[symbol]) # 将FOLLOW(S)加入FOLLOW(A)中
                    else:
                        if rule[i+1] in terminals: # 如果下一个符号是终结符
                            follow[rule[i]].add(rule[i+1]) # 将该终结符加入FOLLOW(A)中
                        else:
                            follow[rule[i]].update(first[rule[i+1]]) # 将FIRST(β)中的所有符号加入FOLLOW(A)中

# 构造LR(0)自动机
def construct_LR0_machine():
    items = {} # 项目集
    C = [] # 项目集规范族
    start_item = ('S\'', ['S']) # 初始项目
    items[start_item] = 0 # 将初始项目加入项目集中，并将其编号为0
    C.append(set([start_item])) # 将初始项目集加入项目集规范族中
    i = 0 # 项目集编号
    while i < len(C):
        item_set = C[i] # 取出一个项目集
        i += 1
        for symbol in terminals.union(non_terminals): # 对于文法中的每个符号
            G = set() # G表示通过该符号能够到达的项目集
            for item in item_set: # 对于项目集中的每个项目
                if item[1] != [] and item[1][0] == symbol: # 如果该项目的下一个符号是当前符号
                    G.add((item[0], item[1][1:])) # 将该项目的点向后移动一位，并加入G中
            if G != set(): # 如果G不为空
                if G not in C: # 如果G不在项目集规范族中
                    items.update({item: len(items) for item in G}) # 将G中的所有项目加入项目集中，并分配编号
                    C.append(G) # 将G加入项目集规范族中
                action[item_set][symbol] = ('S', items[G]) # 将action表中对应的项设为'State'
            else:
                for item in item_set: # 对于项目集中的每个项目
                    if item[1] != [] and item[1][0] in non_terminals: # 如果该项目的下一个符号是非终结符
                        G = set() # G表示通过该非终结符能够到达的项目集
                        for rule in grammar[item[1][0]]: # 对于该非终结符的每个产生式
                            G.add((item[1][0], list(rule))) # 将该产生式加入G中
                        if G not in C: # 如果G不在项目集规范族中
                            items.update({item: len(items) for item in G}) # 将G中的所有项目加入项目集中，并分配编号
                            C.append(G) # 将G加入项目集规范族中
                        goto[item_set][item[1][0]] = items[G] # 将goto表中对应的项设为'State'

        for item in item_set: # 对于项目集中的每个项目
            if item[1] == []: # 如果该项目的点已经到达了产生式的末尾
                if item[0] == 'S\'': # 如果该项目是初始项目
                    action[item_set]['$'] = ('Accept', None) # 将action表中对应的项设为'Accept'
                else:
                    for a in follow[item[0]]: # 对于该项目的非终结符的每个FOLLOW符号
                        action[item_set][a] = ('Reduce', item[0] + '->' + ''.join(item[1])) # 将action表中对应的项设为'Reduce'
                        
# 输出LR(0)自动机
def output_LR0_machine():
    print('Action Table:')
    print('{:20s}'.format('State'), end='')
    for a in terminals.union({'$'}):
        print('{:10s}'.format(str(a)), end='')
    print()
    for i in range(len(C)):
        print('{:20s}'.format(str(i)), end='')
        for a in terminals.union({'$'}):
            if a in action[C[i]]:
                print('{:10s}'.format(str(action[C[i]][a][0]) + ' ' + str(action[C[i]][a][1])), end='')
            else:
                print('{:10s}'.format(''), end='')
        print()

    print('\nGoto Table:')
    print('{:20s}'.format('State'), end='')
    for a in non_terminals:
        print('{:10s}'.format(str(a)), end='')
    print()
    for i in range(len(C)):
        print('{:20s}'.format(str(i)), end='')
        for a in non_terminals:
            if a in goto[C[i]]:
                print('{:10s}'.format(str(goto[C[i]][a])), end='')
            else:
                print('{:10s}'.format(''), end='')
        print()

# 主函数
if __name__ == '__main__':
    # 计算FIRST集和FOLLOW集
    for symbol in terminals.union(non_terminals):
        compute_first(symbol)
    compute_follow()

    # 构造LR(0)自动机
    construct_LR0_machine()

    # 输出LR(0)自动机
    output_LR0_machine()

上述代码中，我们首先定义了文法的规则、终结符号和非终结符号，并使用`defaultdict`定义了动作表`action`和转移表`goto`。接着，我们定义了计算FIRST集和FOLLOW集的函数`compute_first`和`compute_follow`。

在构造LR(0)自动机时，我们使用了项目集法，并定义了如下函数：

- `construct_LR0_machine`: 构造LR(0)自动机的函数。
- `items`: 用于存储项目集中的所有项目，并为每个项目分配一个编号。
- `C`: 用于存储所有项目集。
- `start_item`: 初始项目。
- `item_set`: 当前处理的项目集。
- `symbol`: 当前处理的符号。
- `G`: 通过当前符号能够到达的项目集。
- `rule`: 产生式。
- `output_LR0_machine`: 用于输出LR(0)自动机的函数。

最后，我们在主函数中调用`compute_first`、`compute_follow`和`construct_LR0_machine`函数，然后输出LR(0)自动机。