-
Notifications
You must be signed in to change notification settings - Fork 0
/
code_gen_parser.py
253 lines (242 loc) · 17.2 KB
/
code_gen_parser.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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
# In The Name Of GOD
# Ahmad Zaferani 97105985
# Ali Shirmohammadi 97106068
from scanner import get_next_token
from intermediate_code_generator import code_gen, action_symbols, program_block, id_first_occurrence
valid_tokens = {"KEYWORD", "SYMBOL", "NUM", "WHITESPACE", "ID", "COMMENT"}
errors = {"Invalid number", "Invalid input", "Unmatched comment", "Unclosed comment"}
parse_table = [
['', 'int', 'void', '$', '{', 'break', ';', 'if', 'while', 'return', 'switch', 'ID', '+', '-', '(', 'NUM', '}', '[',
',', ')', 'else', 'case', 'default', ']', '=', '*', '<', '==', ':'],
['Program', ['Declaration-list', '$'], ['Declaration-list', '$'], ['Declaration-list', '$'], '', '', '', '', '', '',
'', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ''],
['Declaration-list', ['Declaration', 'Declaration-list'], ['Declaration', 'Declaration-list'], 'epsilon', 'epsilon',
'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon', 'epsilon',
'epsilon', 'epsilon', '', '', '', '', '', '', '', '', '', '', '', ''],
['Declaration', ['Declaration-initial', 'Declaration-prime'], ['Declaration-initial', 'Declaration-prime'], 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch',
'synch', '', '', '', '', '', '', '', '', '', '', '', ''],
['Declaration-initial', ['Type-specifier', 'ID'], ['Type-specifier', 'ID'], '', '', '', 'synch', '',
'', '', '', '', '', '', 'synch', '', '', 'synch', 'synch', 'synch', '', '', '', '', '', '', '', '', ''],
['Declaration-prime', 'synch', 'synch', 'synch', 'synch', 'synch', ['Var-declaration-prime'], 'synch', 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', ['Fun-declaration-prime'], 'synch', 'synch',
['Var-declaration-prime'], '', '', '', '', '', '', '', '', '', '', ''],
['Var-declaration-prime', 'synch', 'synch', 'synch', 'synch', 'synch', ['#id_declaration', ';'], 'synch', 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch',
['[', '#pnum', 'NUM', ']', '#arr_declaration', ';'], '', '', '', '', '', '', '', '', '', '', ''],
['Fun-declaration-prime', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch',
'synch', 'synch', 'synch', ['#activation_record', '(', 'Params', ')', 'Compound-stmt', '#function'], 'synch',
'synch', '', '', '', '', '', '', '', '', '', '', '', ''],
['Type-specifier', ['int'], ['void'], '', '', '', '', '', '', '', '', 'synch', '', '', '', '', '', '', '', '', '',
'', '', '', '', '', '', '', ''],
['Params', ['int', 'ID', 'Param-prime', '#parameter_declaration', 'Param-list'], ['void', 'Param-list-void-abtar'],
'', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'synch', '', '', '', '', '', '', '', '', ''],
['Param-list-void-abtar', '', '', '', '', '', '', '', '', '', '', ['ID', 'Param-prime', 'Param-list'], '', '', '',
'', '', '', '', 'epsilon', '', '', '', '', '', '', '', '', ''],
['Param-list', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '',
[',', 'Param', 'Param-list', '#parameter_declaration'], 'epsilon', '', '', '', '', '', '', '', '', ''],
['Param', ['Declaration-initial', 'Param-prime'], ['Declaration-initial', 'Param-prime'], '', '', '', '', '', '',
'', '', '', '', '', '', '', '', '', 'synch', 'synch', '', '', '', '', '', '', '', '', ''],
['Param-prime', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ['[', ']'], 'epsilon', 'epsilon',
'', '', '', '', '', '', '', '', ''],
['Compound-stmt', 'synch', 'synch', 'synch', ['{', 'Declaration-list', 'Statement-list', '}'], 'synch', 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', '', '', '', 'synch',
'synch', 'synch', '', '', '', '', '', ''],
['Statement-list', '', '', '', ['Statement', 'Statement-list'], ['Statement', 'Statement-list'],
['Statement', 'Statement-list'], ['Statement', 'Statement-list'], ['Statement', 'Statement-list'],
['Statement', 'Statement-list'], ['Statement', 'Statement-list'], ['Statement', 'Statement-list'],
['Statement', 'Statement-list'], ['Statement', 'Statement-list'], ['Statement', 'Statement-list'],
['Statement', 'Statement-list'], 'epsilon', '', '', '', '', 'epsilon', 'epsilon', '', '', '', '', '', ''],
['Statement', '', '', '', ['Compound-stmt'], ['Expression-stmt'], ['Expression-stmt'], ['Selection-stmt'],
['Iteration-stmt'], ['Return-stmt'], ['Switch-stmt'], ['Expression-stmt'], ['Expression-stmt'],
['Expression-stmt'],
['Expression-stmt'], ['Expression-stmt'], 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '', '', '', ''],
['Expression-stmt', '', '', '', 'synch', ['break', '#jp_break', ';'], [';'], 'synch', 'synch', 'synch', 'synch',
['Expression', '#correct_assign', ';'], ['Expression', '#correct_assign', ';'],
['Expression', '#correct_assign', ';'], ['Expression', '#correct_assign', ';'],
['Expression', '#correct_assign', ';'], 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '', '', '', ''],
['Selection-stmt', '', '', '', 'synch', 'synch', 'synch',
['if', '(', 'Expression', ')', '#save', 'Statement', 'else', '#else', 'Statement', '#if'], 'synch', 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '',
'', '', ''],
['Iteration-stmt', '', '', '', 'synch', 'synch', 'synch', 'synch',
['while', '#label', '(', 'Expression', ')', '#save', 'Statement', '#while'], 'synch', 'synch', 'synch', 'synch',
'synch', 'synch', 'synch', 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '', '', '', ''],
['Return-stmt', '', '', '', 'synch', 'synch', 'synch', 'synch', 'synch', ['return', 'Return-stmt-prime', '#return'],
'synch', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '',
'', '', ''],
['Return-stmt-prime', '', '', '', 'synch', 'synch', [';'], 'synch', 'synch', 'synch', 'synch', ['Expression', ';'],
['Expression', ';'], ['Expression', ';'], ['Expression', ';'], ['Expression', ';'], 'synch', '', '', '', 'synch',
'synch', 'synch', '', '', '', '', '', ''],
['Switch-stmt', '', '', '', 'synch', 'synch', 'synch', 'synch', 'synch', 'synch',
['switch', '#tmp_save', '(', 'Expression', ')', '{', 'Case-stmts', 'Default-stmt', '#jp_switch', '}'], 'synch',
'synch', 'synch', 'synch', 'synch', 'synch', '', '', '', 'synch', 'synch', 'synch', '', '', '', '', '', ''],
['Case-stmts', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'epsilon', '', '', '', '',
['Case-stmt', 'Case-stmts'], 'epsilon', '', '', '', '', '', ''],
['Case-stmt', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'synch', '', '', '', '',
['case', '#pnum', 'NUM', '#cmp_save', ':', 'Statement-list', '#jpf'], 'synch', '', '', '', '', '', ''],
['Default-stmt', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'epsilon', '', '', '', '', '',
['default', ':', 'Statement-list'], '', '', '', '', '', ''],
['Expression', '', '', '', '', '', 'synch', '', '', '', '', ['#pid', 'ID', 'B'], ['Simple-expression-zegond'],
['Simple-expression-zegond'], ['Simple-expression-zegond'], ['Simple-expression-zegond'], '', '', 'synch', 'synch',
'', '', '', 'synch', '', '', '', '', ''],
['B', '', '', '', '', '', ['Simple-expression-prime'], '', '', '', '', '', ['Simple-expression-prime'],
['Simple-expression-prime'], ['Simple-expression-prime'], '', '', ['[', 'Expression', ']', '#arr_index', 'H'],
['Simple-expression-prime'], ['Simple-expression-prime'], '', '', '', ['Simple-expression-prime'],
['=', 'Expression', '#assign'], ['Simple-expression-prime'], ['Simple-expression-prime'],
['Simple-expression-prime'], ['Simple-expression-prime']],
['H', '', '', '', '', '', ['G', 'D', 'C'], '', '', '', '', '', ['G', 'D', 'C'], ['G', 'D', 'C'], '', '', '', '',
['G', 'D', 'C'], ['G', 'D', 'C'], '', '', '', ['G', 'D', 'C'], ['=', 'Expression', '#assign'], ['G', 'D', 'C'],
['G', 'D', 'C'], ['G', 'D', 'C'], ''],
['Simple-expression-zegond', '', '', '', '', '', 'synch', '', '', '', '', '', ['Additive-expression-zegond', 'C'],
['Additive-expression-zegond', 'C'], ['Additive-expression-zegond', 'C'], ['Additive-expression-zegond', 'C'], '',
'', 'synch', 'synch', '', '', '', 'synch', '', '', '', '', ''],
['Simple-expression-prime', '', '', '', '', '', ['Additive-expression-prime', 'C'], '', '', '', '', '',
['Additive-expression-prime', 'C'],
['Additive-expression-prime', 'C'], ['Additive-expression-prime', 'C'], '', '', '',
['Additive-expression-prime', 'C'], ['Additive-expression-prime', 'C'], '', '',
'',
['Additive-expression-prime', 'C'], '', ['Additive-expression-prime', 'C'], ['Additive-expression-prime', 'C'],
['Additive-expression-prime', 'C'], ['Additive-expression-prime', 'C']],
['C', '', '', '', '', '', 'epsilon', '', '', '', '', '', '', '', '', '', '', '', 'epsilon', 'epsilon', '', '', '',
'epsilon', '', '', ['#save_addop', 'Relop', 'Additive-expression', '#relop'],
['#save_addop', 'Relop', 'Additive-expression', '#relop'], ''],
['Relop', '', '', '', '', '', '', '', '', '', '', 'synch', 'synch', 'synch', 'synch', 'synch', '', '', '', '', '',
'', '', '', '', '', ['<'], ['=='], ''],
['Additive-expression', '', '', '', '', '', 'synch', '', '', '', '', ['Term', 'D'], ['Term', 'D'], ['Term', 'D'],
['Term', 'D'], ['Term', 'D'], '', '', 'synch', 'synch', '', '', '', 'synch', '', '', '', '', ''],
['Additive-expression-prime', '', '', '', '', '', ['Term-prime', 'D'], '', '', '', '', '', ['Term-prime', 'D'],
['Term-prime', 'D'], ['Term-prime', 'D'], '', '', '', ['Term-prime', 'D'], ['Term-prime', 'D'], '', '', '',
['Term-prime', 'D'], '',
['Term-prime', 'D'], ['Term-prime', 'D'], ['Term-prime', 'D'], ['Term-prime', 'D']],
['Additive-expression-zegond', '', '', '', '', '', 'synch', '', '', '', '', '', ['Term-zegond', 'D'],
['Term-zegond', 'D'], ['Term-zegond', 'D'], ['Term-zegond', 'D'], '', '', 'synch', 'synch', '', '', '', 'synch',
'', '', 'synch', 'synch', ''],
['D', '', '', '', '', '', 'epsilon', '', '', '', '', '', ['#save_addop', 'Addop', 'Term', '#addop', 'D'],
['#save_addop', 'Addop', 'Term', '#addop', 'D'], '', '', '', '', 'epsilon', 'epsilon', '', '', '', 'epsilon', '',
'', 'epsilon', 'epsilon', ''],
['Addop', '', '', '', '', '', '', '', '', '', '', 'synch', ['+'], ['-'], 'synch', 'synch', '', '', '', '', '', '',
'', '', '', '', '', '', ''],
['Term', '', '', '', '', '', 'synch', '', '', '', '', ['Signed-factor', 'G'], ['Signed-factor', 'G'],
['Signed-factor', 'G'], ['Signed-factor', 'G'], ['Signed-factor', 'G'], '', '', 'synch', 'synch', '', '', '',
'synch', '', '', 'synch', 'synch', ''],
['Term-prime', '', '', '', '', '', ['Signed-factor-prime', 'G'], '', '', '', '', '', ['Signed-factor-prime', 'G'],
['Signed-factor-prime', 'G'], ['Signed-factor-prime', 'G'],
'', '', '', ['Signed-factor-prime', 'G'], ['Signed-factor-prime', 'G'], '', '', '', ['Signed-factor-prime', 'G'],
'', ['Signed-factor-prime', 'G'], ['Signed-factor-prime', 'G'], ['Signed-factor-prime', 'G'],
['Signed-factor-prime', 'G']],
['Term-zegond', '', '', '', '', '', 'synch', '', '', '', '', '', ['Signed-factor-zegond', 'G'],
['Signed-factor-zegond', 'G'], ['Signed-factor-zegond', 'G'], ['Signed-factor-zegond', 'G'], '', '', 'synch',
'synch', '', '', '', 'synch', '', '', 'synch', 'synch', ''],
['G', '', '', '', '', '', 'epsilon', '', '', '', '', '', 'epsilon', 'epsilon', '', '', '', '', 'epsilon', 'epsilon',
'', '', '', 'epsilon', '', ['#save_addop', '*', 'Signed-factor', '#mult', 'G'], 'epsilon', 'epsilon', ''],
['Signed-factor', '', '', '', '', '', 'synch', '', '', '', '', ['Factor'],
['#psign', '+', 'Factor', '#correct_signed_factor'], ['#psign', '-', 'Factor', '#correct_signed_factor'],
['Factor'], ['Factor'], '', '', 'synch', 'synch', '', '', '', 'synch', '', 'synch', 'synch', 'synch', ''],
['Signed-factor-prime', '', '', '', '', '', ['Factor-prime'], '', '', '', '', '', ['Factor-prime'],
['Factor-prime'], ['Factor-prime'], '',
'', '', ['Factor-prime'], ['Factor-prime'], '', '', '', ['Factor-prime'], '', ['Factor-prime'], ['Factor-prime'],
['Factor-prime'], ['Factor-prime']],
['Signed-factor-zegond', '', '', '', '', '', 'synch', '', '', '', '', '',
['#psign', '+', 'Factor', '#correct_signed_factor'], ['#psign', '-', 'Factor', '#correct_signed_factor'],
['Factor-zegond'], ['Factor-zegond'], '', '', 'synch', 'synch', '', '', '', 'synch', '', 'synch', 'synch', 'synch',
''],
['Factor', '', '', '', '', '', 'synch', '', '', '', '', ['#pid', 'ID', 'Var-call-prime'], 'synch', 'synch',
['(', 'Expression', ')'], ['#pnum', 'NUM'], '', '', 'synch', 'synch', '', '', '', 'synch', '', 'synch', 'synch',
'synch', ''],
['Var-call-prime', '', '', '', '', '', ['Var-prime'], '', '', '', '', '', ['Var-prime'], ['Var-prime'],
['(', 'Args', ')', '#call_function'], '', '', ['Var-prime'], ['Var-prime'], ['Var-prime'], '', '', '',
['Var-prime'], '', ['Var-prime'], ['Var-prime'], ['Var-prime'], ''],
['Var-prime', '', '', '', '', '', 'epsilon', '', '', '', '', '', 'epsilon', 'epsilon', '', '', '',
['[', 'Expression', ']', '#arr_index'], 'epsilon', 'epsilon', '', '', '', 'epsilon', '', 'epsilon', 'epsilon',
'epsilon', ''],
['Factor-prime', '', '', '', '', '', 'epsilon', '', '', '', '', '', 'epsilon', 'epsilon',
['(', 'Args', ')', '#call_function'], '', '', '', 'epsilon', 'epsilon', '', '', '', 'epsilon', '', 'epsilon',
'epsilon', 'epsilon', ''],
['Factor-zegond', '', '', '', '', '', 'synch', '', '', '', '', '', 'synch', 'synch', ['(', 'Expression', ')'],
['#pnum', 'NUM'], '', '', 'synch', 'synch', '', '', '', 'synch', '', 'synch', 'synch', 'synch', ''],
['Args', '', '', '', '', '', '', '', '', '', '', ['Arg-list'], ['Arg-list'], ['Arg-list'], ['Arg-list'],
['Arg-list'],
'', '', '', 'epsilon', '', '', '', '', '', '', '', '', ''],
['Arg-list', '', '', '', '', '', '', '', '', '', '', ['Expression', 'Arg-list-prime'],
['Expression', 'Arg-list-prime'],
['Expression', 'Arg-list-prime'], ['Expression', 'Arg-list-prime'], ['Expression', 'Arg-list-prime'], '', '', '',
'synch', '', '', '', '', '', '', '', '', ''],
['Arg-list-prime', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '',
[',', 'Expression', 'Arg-list-prime'], 'epsilon', '', '', '', '', '', '', '', '', '']]
parse_table_dim = len(parse_table), len(parse_table[0])
# read input, tokenize it using scanner
with open("input.txt", "r") as file:
s = file.read()
s += '\n'
i = 0
tokens = []
while i < len(s):
t = get_next_token(s, i)
i += len(t[1])
tokens.append(t)
tokens.append(('KEYWORD', '$'))
# main parser program
parser_stack = ['Program']
token_index = 0
def find_in_table(row, col):
ii = 0
jj = 0
for ii in range(1, parse_table_dim[0]):
if row == parse_table[ii][0]:
break
for jj in range(1, parse_table_dim[1]):
if col == parse_table[0][jj]:
break
if ii == parse_table_dim[0] - 1 and parse_table[ii][0] != row:
return ''
return parse_table[ii][jj]
while parser_stack:
t = tokens[token_index]
if t[0] == 'SYMBOL' or t[0] == 'KEYWORD':
next_token = t[1]
else:
next_token = t[0]
if t[0] == "ID":
id_first_occurrence(t[1])
parser_stack_head = parser_stack[-1]
if t[0] in valid_tokens:
if t[0] == 'WHITESPACE' or t[0] == 'COMMENT':
token_index += 1
continue
print(parser_stack_head, next_token)
if parser_stack_head == next_token == '$':
print("Compiled Successfully!")
break
elif parser_stack_head == next_token and next_token != '$':
parser_stack.pop()
token_index += 1
elif parser_stack_head not in parse_table[0]:
M = find_in_table(parser_stack_head, next_token)
print(M)
if isinstance(M, list):
parser_stack.pop()
parser_stack += reversed(M)
elif parser_stack_head in action_symbols:
code_gen(parser_stack_head, t[1])
parser_stack.pop()
elif M == 'epsilon':
non_terminal = parser_stack.pop()
else:
raise Exception("Syntax Error: ", parser_stack, t)
elif parser_stack_head in parse_table[0]:
parser_stack.pop()
else:
raise Exception("Syntax Error: ", parser_stack, t)
print(parser_stack, token_index)
elif t[0] in errors:
raise Exception("Lexical Error: ", t)
else:
raise ValueError(t)
with open("output.txt", "w") as file:
counter = 0
for li in program_block:
if li == '':
break
file.write('%d' % counter + '\t' + li + '\n')
counter += 1