-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathresolve.py
148 lines (135 loc) · 5.27 KB
/
resolve.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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
# **************************************************************************** #
# #
# ::: :::::::: #
# resolve.py :+: :+: :+: #
# +:+ +:+ +:+ #
# By: ngoguey <[email protected]> +#+ +:+ +#+ #
# +#+#+#+#+#+ +#+ #
# Created: 2016/01/05 19:13:48 by ngoguey #+# #+# #
# Updated: 2016/01/25 14:20:45 by ngoguey ### ########.fr #
# #
# **************************************************************************** #
def call_to_string(call):
if call[2] != None:
return " <%s> %s(s%d)" %(call[2], call[0], call[1])
else:
return "%s(s%d)" %(call[0], call[1])
def callstack_to_string(callstack):
string = ""
for call in callstack:
string += call_to_string(call)
return string
def compute_ANY_list(read_by_state, alphabet, spec):
lst = []
if 'SPEC' in read_by_state:
return [x for x in alphabet if x not in read_by_state and x != spec]
else:
return [x for x in alphabet if x not in read_by_state]
def compute_read_chars(lst_chars_read, set_alphabet, set_state_read, spec):
if 'SPEC' in set_state_read and spec == None:
raise Exception("SPEC without specialization")
if lst_chars_read[0] == 'ANY':
return compute_ANY_list(set_state_read, set_alphabet, spec)
elif lst_chars_read[0] == 'SPEC':
return [spec]
else:
return lst_chars_read
def compute_next_call(prog, top_st, callstack, read, rchar):
if read.nexts[0] == 'rep':
return callstack[-1]
elif read.nexts[0] == 'ni':
if len(prog.lst_st) <= top_st.gid + 1:
raise Exception('NextInstruction to end of file')
next_st = prog.lst_st[top_st.gid + 1]
return (next_st.label, next_st.sid, callstack[-1][2])
elif read.nexts[0] == 'pi':
if top_st.gid == 0:
raise Exception('PrevInstruction to begin of file')
next_st = prog.lst_st[top_st.gid - 1]
return (next_st.label, next_st.sid, callstack[-1][2])
elif read.nexts[0] == 'jmp':
next_st = prog.dic_st[(read.nexts[1], 1)]
return (next_st.label, next_st.sid, callstack[-1][2])
elif read.nexts[0] == 'halt':
return None
elif read.nexts[0] == 'call+':
next_st = prog.dic_st[(read.nexts[1], 1)]
return (next_st.label, next_st.sid, rchar)
elif read.nexts[0] == 'ret-':
calling_st = prog.dic_st[(callstack[-2][0], callstack[-2][1])]
next_st = prog.lst_st[calling_st.gid + 1]
return (next_st.label, next_st.sid, callstack[-2][2])
elif read.nexts[0] == 'call':
next_st = prog.dic_st[(read.nexts[1], 1)]
return (next_st.label, next_st.sid, callstack[-1][2])
elif read.nexts[0] == 'ret':
calling_st = prog.dic_st[(callstack[-2][0], callstack[-2][1])]
next_st = prog.lst_st[calling_st.gid + 1]
return (next_st.label, next_st.sid, callstack[-1][2])
def rec(prog, callstack, spec):
top_st = prog.dic_st[(callstack[-1][0], callstack[-1][1])]
callstack_str = callstack_to_string(callstack)
transi = []
if callstack_str in prog.set_resolved_states:
return
# print "rec call with callstack:(%s) spec:(%s)" %(callstack_str, spec)
prog.set_resolved_states.add(callstack_str)
for read in top_st.lst_reads:
read_chars = compute_read_chars(
read.reads, prog.alphabet, top_st.set_readchars, spec)
is_epsilon = read.action == 'E'
action = {'L': 'LEFT', 'R': 'RIGHT'}['L' if is_epsilon else read.action]
suffix = 'Adjust' if is_epsilon else ''
for c in read_chars:
def get_write():
if read.write == None:
return c
elif read.write == 'SPEC':
assert(spec != None) # no spec when writing spec
return spec
else:
return read.write
write = get_write()
next_call = compute_next_call(prog, top_st, callstack, read, c)
tmp_callstack = list(callstack)
tmp_spec = -1
if read.nexts[0] == 'halt':
if is_epsilon:
raise Exception('Epsilon action before halt not allowed')
transi.append((c, write, action, 'HALT'))
continue
elif read.nexts[0] == 'call+':
if spec != None:
raise Exception('Multiple specialization not allowed')
tmp_callstack.append(next_call)
tmp_spec = next_call[2]
elif read.nexts[0] == 'ret-':
if spec == None:
raise Exception('ret- without specialization not allowed')
del tmp_callstack[-1]
tmp_callstack[-1] = next_call
tmp_spec = None
elif read.nexts[0] == 'call':
tmp_callstack.append(next_call)
tmp_spec = spec
elif read.nexts[0] == 'ret':
del tmp_callstack[-1]
tmp_callstack[-1] = next_call
tmp_spec = spec
else:
tmp_callstack[-1] = next_call
tmp_spec = spec
tmp_callstack_str = callstack_to_string(tmp_callstack)
transi.append((c, write, action, tmp_callstack_str + suffix))
if is_epsilon:
prog.set_required_pre.add(tmp_callstack_str)
rec(prog, tmp_callstack, tmp_spec)
prog.dic_st_transi[callstack_str] = transi
return
def resolve(prog):
fst = prog.lst_st[0]
rec(prog, [(fst.label, fst.sid, None)], None)
assert('HALT' not in prog.set_resolved_states)
prog.set_resolved_states.add('HALT')
# print "done:", prog.set_resolved_states
# print prog.dic_st_transi