2021_Compilation_Principle/CompilationPrinciple3_1.py at main · 1918190/2021_Compilation_Principle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import sys
import numpy as np
import copy


def init_first_matrix(grammar, first_boolean_matrix, first_stack, non_terminals, terminals):
    for gra_line in grammar:
        for i in range(len(gra_line) - 1):
            if gra_line[i] == '→' or gra_line[i] == '|':
                if gra_line[i + 1] in terminals:
                    ter_index = terminals.index(gra_line[i + 1])
                    non_ter_index = non_terminals.index(gra_line[0])
                    first_boolean_matrix[non_ter_index][ter_index] = 'T'
                    first_stack.append([gra_line[0], gra_line[i + 1]])
                if gra_line[i + 1] in non_terminals and i < len(gra_line) - 2:
                    if gra_line[i + 2] in terminals:
                        ter_index = terminals.index(gra_line[i + 2])
                        non_ter_index = non_terminals.index(gra_line[0])
                        first_boolean_matrix[non_ter_index][ter_index] = 'T'
                        first_stack.append([gra_line[0], gra_line[i + 2]])


def calculate_first(grammar, first_boolean_matrix, first_stack, non_terminals, terminals):
    while len(first_stack) > 0:
        tmp = first_stack.pop()
        for gra in grammar:
            for i in range(len(gra) - 1):
                if (gra[i] == '→' or gra[i] == '|') and gra[i + 1] == tmp[0]:
                    ter_index = terminals.index(tmp[1])
                    non_ter_index = non_terminals.index(gra[0])
                    if first_boolean_matrix[non_ter_index][ter_index] == 'F':
                        first_boolean_matrix[non_ter_index][ter_index] = 'T'
                        first_stack.append([gra[0], tmp[1]])


def init_last_matrix(grammar, last_boolean_matrix, last_stack, non_terminals, terminals):
    for gra_line in grammar:
        for i in range(len(gra_line)):
            if i == (len(gra_line) - 1) or (i < (len(gra_line) - 1) and gra_line[i + 1] == '|'):
                if gra_line[i] in terminals:
                    ter_index = terminals.index(gra_line[i])
                    non_ter_index = non_terminals.index(gra_line[0])
                    last_boolean_matrix[non_ter_index][ter_index] = 'T'
                    last_stack.append([gra_line[0], gra_line[i]])
                if gra_line[i] in non_terminals and i > 0:
                    if gra_line[i - 1] in terminals:
                        ter_index = terminals.index(gra_line[i - 1])
                        non_ter_index = non_terminals.index(gra_line[0])
                        last_boolean_matrix[non_ter_index][ter_index] = 'T'
                        last_stack.append([gra_line[0], gra_line[i - 1]])


def calculate_last(grammar, last_boolean_matrix, last_stack, non_terminals, terminals):
    while len(last_stack) > 0:
        tmp = last_stack.pop()
        for gra in grammar:
            for i in range(len(gra)):
                if (i == (len(gra) - 1) or (i < (len(gra) - 1) and gra[i + 1] == '|')) and gra[i] == tmp[0]:
                    ter_index = terminals.index(tmp[1])
                    non_ter_index = non_terminals.index(gra[0])
                    if last_boolean_matrix[non_ter_index][ter_index] == 'F':
                        last_boolean_matrix[non_ter_index][ter_index] = 'T'
                        last_stack.append([gra[0], tmp[1]])


def print_vt(first_boolean_matrix, last_boolean_matrix, non_terminals, terminals):
    first_vt = {}
    last_vt = {}
    for firstVT in non_terminals:
        tmp_first_list = []
        print("FIRSTVT(" + firstVT + ")={", end="")
        non_ter_index = non_terminals.index(firstVT)
        for i in range(len(first_boolean_matrix[non_ter_index])):
            if first_boolean_matrix[non_ter_index][i] == 'T':
                if i != 0:
                    print(',', end="")
                print(terminals[i], end="")
                tmp_first_list.append(terminals[i])
        first_vt[firstVT] = tmp_first_list
        print("}")
    for lastVT in non_terminals:
        tmp_last_list = []
        print("LASTVT(" + lastVT + ")={", end="")
        non_ter_index = non_terminals.index(lastVT)
        for i in range(len(last_boolean_matrix[non_ter_index])):
            if last_boolean_matrix[non_ter_index][i] == 'T':
                if i != 0:
                    print(',', end="")
                print(terminals[i], end="")
                tmp_last_list.append(terminals[i])
        last_vt[lastVT] = tmp_last_list
        print("}")
    return first_vt, last_vt


def calculate_first_and_last(grammar, non_terminals, terminals):
    first_stack = []  # firstVT的栈
    last_stack = []  # lastVT的栈
    boolean_matrix = np.full((len(non_terminals), len(terminals)), 'F')
    first_boolean_matrix = copy.deepcopy(boolean_matrix)
    last_boolean_matrix = copy.deepcopy(boolean_matrix)
    print("first_boolean_matrix:")
    print(first_boolean_matrix)
    init_first_matrix(grammar, first_boolean_matrix, first_stack, non_terminals, terminals)
    print("first_boolean_matrix:")
    print(first_boolean_matrix)
    calculate_first(grammar, first_boolean_matrix, first_stack, non_terminals, terminals)
    print("first_boolean_matrix:")
    print(first_boolean_matrix)
    print("last_boolean_matrix:")
    print(last_boolean_matrix)
    init_last_matrix(grammar, last_boolean_matrix, last_stack, non_terminals, terminals)
    print("last_boolean_matrix:")
    print(last_boolean_matrix)
    calculate_last(grammar, last_boolean_matrix, last_stack, non_terminals, terminals)
    print("last_boolean_matrix:")
    print(last_boolean_matrix)
    return print_vt(first_boolean_matrix, last_boolean_matrix, non_terminals, terminals)


# 输入示例：
# S→a|^|(T)
# T→T,S|S
# Ctrl+D结束输入
if __name__ == '__main__':
    non_terminals = []  # 非终结符
    terminals = []  # 终结符
    first_vt = {}
    last_vt = {}
    print("请输入一个文法：")
    grammar = sys.stdin.read().splitlines()
    grammar = [e for e in grammar if e != '']
    print(grammar)
    for gr in grammar:
        if gr[0] not in non_terminals:
            non_terminals.append(gr[0])
    for gr in grammar:
        for i in range(len(gr)):
            if gr[i] not in non_terminals and gr[i] not in terminals:
                # 箭头输入是->
                # if gr[i] == '-':
                #     if i == len(gr)-1:
                #         terSymbol.append(gr[i])
                #     elif i != len(gr)-1 and gr[i+1]!='>':
                #         terSymbol.append(gr[i])
                # elif gr[i] == '>':
                #     if i != 0 and gr[i-1]!='-':
                #         terSymbol.append(gr[i])
                # 箭头输入是→
                if gr[i] != '|' and gr[i] != '→' and gr[i] != ' ':
                    terminals.append(gr[i])
    print(non_terminals)
    print(terminals)
    first_vt, last_vt = calculate_first_and_last(grammar, non_terminals, terminals)
    print(first_vt)
    print(last_vt)