-
Notifications
You must be signed in to change notification settings - Fork 0
/
impl.py
109 lines (82 loc) · 3.01 KB
/
impl.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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
__all__ = ["Automata", "FollowAutomata", "PositionAutomata", "automata_match"]
from abc import ABC, abstractmethod
from automata.parser import Parser
from automata.tree import Node
from typing import Generic, Self, TypeAlias, TypeVar
T = TypeVar("T")
class Automata(ABC, Generic[T]):
@classmethod
@abstractmethod
def from_node(cls, node: Node) -> Self:
raise NotImplementedError
@property
@abstractmethod
def final(self) -> set[T]:
raise NotImplementedError
@property
@abstractmethod
def initial(self) -> set[T]:
raise NotImplementedError
@abstractmethod
def transition(self, state: T, symbol: str) -> set[T]:
raise NotImplementedError
def accepts(self, word: str) -> bool:
states = self.initial
for symbol in word:
if len(states) == 0:
return False
states = {t for s in states for t in self.transition(s, symbol)}
return len(states.intersection(self.final)) > 0
class PositionAutomata(Automata):
def __init__(self, node: Node) -> None:
self.pos = node.pos()
self.first = node.first()
self.last_0 = node.last_0()
self.follow = node.follow()
@classmethod
def from_node(cls, node: Node) -> Self:
return cls(node)
@property
def initial(self) -> set[int]:
return {0}
@property
def final(self) -> set[int]:
return self.last_0
def transition(self, state: int, symbol: str) -> set[int]:
if state == 0:
follow_i = self.first
else:
follow_i = {j for i, j in self.follow if i == state}
return {j for j in follow_i if self.pos[j] == symbol}
FollowState: TypeAlias = tuple[frozenset[int], bool]
class FollowAutomata(Automata):
def __init__(self, node: Node) -> None:
self.pos = node.pos()
self.first = node.first()
self.last_0 = node.last_0()
self.follow = node.follow()
self.init = (frozenset(self.first), 0 in self.last_0)
self.states = {0: self.init}
for idx in node.pos():
f_set = frozenset({j for i, j in self.follow if i == idx})
self.states[idx] = (f_set, idx in self.last_0)
self.final_set = {(s, fin) for s, fin in self.states.values() if fin}
@classmethod
def from_node(cls, node: Node) -> Self:
return cls(node)
@property
def final(self) -> set[FollowState]:
return self.final_set
@property
def initial(self) -> set[FollowState]:
return {self.init}
def transition(self, state: FollowState, symbol: str) -> set[FollowState]:
select = {i for i in state[0] if self.pos[i] == symbol}
return {self.states[j] for j in select}
def automata_match(pattern: str, string: str, engine: type[Automata]) -> bool:
# special case empty pattern, we cannot parse empty strings
if pattern == "":
return string == ""
node = Parser(pattern).parse()
auto = engine.from_node(node)
return auto.accepts(string)