-
Notifications
You must be signed in to change notification settings - Fork 0
/
transforms.py
72 lines (46 loc) · 1.91 KB
/
transforms.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
import functools
from collections import defaultdict
class TransformTable:
def __init__(self, start, final, default):
self.start = start
self.final = final
self.elements = defaultdict(lambda: defaultdict(default))
def __getitem__(self, location):
last = location[0]
char = location[1]
return self.elements[last][char]
class NFATransforms(TransformTable):
@functools.cached_property
def all_characters(self):
return {char for transform in self.elements.values() for char in transform.keys() if char != 'ε'}
def closure(self, status_set):
status_closure = status_set.copy()
status_buffer = status_set.copy()
while len(status_buffer) > 0:
current_status = status_buffer.copy()
status_buffer.clear()
for status in current_status:
status_buffer = status_buffer.union(self.elements[status]['ε'] - status_closure)
status_closure = status_closure.union(status_buffer)
return frozenset(status_closure)
def move(self, status, char):
return {next for last in status for next in self.elements[last][char]}
def next_status(self, status, char):
return self.closure(self.move(status, char))
class DFATransforms(TransformTable):
def __setitem__(self, condition, destination):
last = condition[0]
char = condition[1]
self.elements[last][char] = destination
def exist(self, last, char):
return char in self.elements[last]
class TransformsBuilder:
@staticmethod
def nfa(grammar):
nfa_transforms = NFATransforms(grammar.start, grammar.final, set)
for element in grammar.parse_formulas():
nfa_transforms.elements[element.last][element.char].add(element.next)
return nfa_transforms
@staticmethod
def dfa():
return DFATransforms(None, None, None)