-
Notifications
You must be signed in to change notification settings - Fork 11
/
re.lc
82 lines (72 loc) · 1.86 KB
/
re.lc
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
doc = path("doc:/re")
#a{n} == aaaaa
#a{n,} == aaaaa+
#a{n,m} == aaaaaa?a?a?a?a?
main = ():
acc = :object()
type = "accept"
s0 = group(
alt(
star(match("a")),
match("b")),
opt(match("c")))(acc)
print(recognize(s0, "aaaad", true))
print(recognize(s0, "aaaac", true))
print(recognize(s0, "bc", true))
print(recognize(s0, "bbc", true))
print(recognize(s0, "", true))
recognize = (s0, string, eol=false):
state0 = [s0]
for ch in string
state1 = []
for node in state0
if next_state(state1, node, ch) and not eol
return true
state0 = state1
if state0.length == 0
return false
for node in state0
if next_state([], node, "")
return true
return false
next_state = (states, node, char):
if node.type == "accept"
return true
elif node.type == "match" and node.char == char
states.append(node.next)
elif node.type == "split"
acc = 0
for next in node.nexts
acc |= next_state(states, next, char)
return acc != 0
return false
match = (char):
return (next):
return :object()
type = "match"
char = char
next = next
star = (group):
return (next):
s0 = object()
return :s0
type = "split"
nexts = [group(s0), next]
alt = (groups...):
return (next):
nexts = []
for group in groups
nexts.append(group(next))
return :object()
type = "split"
nexts = nexts
opt = (group):
return (next):
return :object()
type = "split"
nexts = [group(next), next]
group = (seq...):
return (next):
for group in reversed(seq)
next = group(next)
return next