-
Notifications
You must be signed in to change notification settings - Fork 2
/
FiniteAutomata.py
85 lines (71 loc) · 3.22 KB
/
FiniteAutomata.py
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
from graphviz import Digraph, render
from collections import defaultdict
Upper = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
epsilon = 'ε'
dot = '·'
arrow = '→'
comma = ','
class FA:
def __init__(self, symbol = set([])):
self.states = set()
self.symbol = symbol # input symbol 输入符号表
self.transitions = defaultdict(defaultdict)
self.startstate = None
def setStart(self, state):
self.startstate = state
self.states.add(state)
def addSymbol(self, sy):
if sy not in Upper:
self.symbol.add(sy)
def addTransition(self, fromstate, tostate, inputch):
if isinstance(inputch, str):
inputch = set([inputch])
self.states.add(fromstate)
self.states.add(tostate)
if fromstate in self.transitions and tostate in self.transitions[fromstate]:
self.transitions[fromstate][tostate] = \
self.transitions[fromstate][tostate].union(inputch)
else:
self.transitions[fromstate][tostate] = inputch
def displaySimpleSquare(self, fname, pname, pst): # do not contain lookahead terminals
fa = Digraph(pname, filename = fname, format = 'png')
fa.attr(rankdir='LR')
fa.attr('node', shape = 'record')
for fromstate, tostates in self.transitions.items():
for state in tostates:
fromstr = 'I' + str(fromstate) + ': '
for pj in pst[fromstate]:
fromstr += pj[0] + arrow + pj[1] + '\\n'
tostr = 'I' + str(state) + ': '
for pj in pst[state]:
tostr += pj[0] + arrow + pj[1] + '\\n'
fa.node('I' + str(fromstate), label = fromstr)
fa.node('I' + str(state), label = tostr)
fa.edge('I' + str(fromstate), 'I' + str(state), label = list(tostates[state])[0])
fa.attr('node', shape = 'point')
fa.edge('', 'I0')
fa.view()
def displaySquare(self, fname, pname, pst, LATerminal):
fa = Digraph(pname, filename = fname, format = 'png')
fa.attr(rankdir='LR')
fa.attr('node', shape = 'record')
for fromstate, tostates in self.transitions.items():
for state in tostates:
fromstr = 'I' + str(fromstate) + ': '
for pj in pst[fromstate]:
tmp = ' '
for sy in LATerminal[fromstate][(pj[0], pj[1])]:
tmp += sy + '/'
fromstr += pj[0] + arrow + pj[1] + comma + tmp[:-1] + '\\n'
tostr = 'I' + str(state) + ': '
for pj in pst[state]:
tmp = ' '
for sy in LATerminal[state][(pj[0], pj[1])]:
tmp += sy + '/'
tostr += pj[0] + arrow + pj[1] + comma + tmp[:-1] + '\\n'
fa.node('I' + str(fromstate), label = fromstr)
fa.node('I' + str(state), label = tostr)
fa.edge('I' + str(fromstate), 'I' + str(state), label = list(tostates[state])[0])
fa.attr('node', shape = 'point')
fa.edge('', 'I0')
fa.view()