mirror of
https://github.com/HyperDbg/HyperDbg.git
synced 2026-07-11 18:19:36 +00:00
81 lines
2.2 KiB
Python
81 lines
2.2 KiB
Python
class Automaton:
|
|
def __init__(self):
|
|
self.states = []
|
|
self.id_from_state = dict()
|
|
self.goto = dict()
|
|
|
|
|
|
def get_automaton(gr):
|
|
dfa = Automaton()
|
|
dfa.states = [closure(gr, [(0, 0)])]
|
|
next_id = 0
|
|
|
|
dfa.id_from_state[dfa.states[-1]] = next_id
|
|
next_id += 1
|
|
|
|
seen = set(dfa.states)
|
|
set_queue = dfa.states
|
|
while len(set_queue) > 0:
|
|
new_elements = []
|
|
for item_set in set_queue:
|
|
item_set_id = dfa.id_from_state[item_set]
|
|
|
|
for symbol in gr.symbols:
|
|
next_item_set = goto(gr, item_set, symbol)
|
|
if len(next_item_set) == 0:
|
|
continue
|
|
|
|
if next_item_set not in seen:
|
|
new_elements += [next_item_set]
|
|
seen.add(next_item_set)
|
|
|
|
dfa.states += [next_item_set]
|
|
dfa.id_from_state[dfa.states[-1]] = next_id
|
|
next_id += 1
|
|
|
|
dfa.goto[(item_set_id, symbol)] = dfa.id_from_state[next_item_set]
|
|
|
|
set_queue = new_elements
|
|
|
|
return dfa
|
|
|
|
|
|
def closure(gr, item_set):
|
|
result = set(item_set)
|
|
set_queue = item_set
|
|
|
|
while len(set_queue) > 0:
|
|
new_elements = []
|
|
|
|
for itemProdId, dot in set_queue:
|
|
pname, pbody = gr.productions[itemProdId]
|
|
if dot == len(pbody) or pbody[dot] not in gr.nonterms:
|
|
continue
|
|
|
|
nt = pbody[dot]
|
|
nt_offset = gr.nonterm_offset[nt]
|
|
for idx in range(len(nt.productions)):
|
|
new_item_set = (nt_offset + idx, 0)
|
|
if new_item_set not in result:
|
|
new_elements += [new_item_set]
|
|
result.add(new_item_set)
|
|
|
|
set_queue = new_elements
|
|
|
|
return frozenset(result)
|
|
|
|
|
|
def goto(gr, item_set, inp):
|
|
result_set = set()
|
|
|
|
for prod_index, dot in item_set:
|
|
pname, pbody = gr.productions[prod_index]
|
|
if dot < len(pbody) and pbody[dot] == inp:
|
|
result_set.add((prod_index, dot + 1))
|
|
|
|
result_set = closure(gr, result_set)
|
|
return result_set
|
|
|
|
|
|
def kernels(item_set):
|
|
return frozenset((x, y) for x, y in item_set if y > 0 or x == 0)
|