-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.py
1579 lines (1462 loc) · 69.7 KB
/
main.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
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
'''
A Simple C-Compiler based in Python
For Help:
python main.py -h
For Lexical Result:
python main.py -s source.c -p
'''
import re
import sys
import getopt
# Classifications of Token
from sqlalchemy import true
TOKEN_STYLE = ['KEY_WORD', 'IDENTIFIER', 'DIGIT_CONSTANT',
'OPERATOR', 'SEPARATOR', 'STRING_CONSTANT']
# Detail Classificitaion
DETAIL_TOKEN_STYLE = {
'include': 'INCLUDE', 'int': 'INT', 'float': 'FLOAT', 'char': 'CHAR', 'double': 'DOUBLE', 'for': 'FOR', 'if': 'IF', 'else': 'ELSE',
'while': 'WHILE', 'do': 'DO', 'return': 'RETURN', '=': 'ASSIGN', '&': 'ADDRESS',
'<': 'LT', '>': 'GT', '++': 'SELF_PLUS', '--': 'SELF_MINUS', '+': 'PLUS', '-': 'MINUS', '*': 'MUL', '/': 'DIV', '>=': 'GET', '<=': 'LET', '(': 'LL_BRACKET',
')': 'RL_BRACKET', '{': 'LB_BRACKET', '}': 'RB_BRACKET', '[': 'LM_BRACKET', ']': 'RM_BRACKET', ',': 'COMMA', '\"': 'DOUBLE_QUOTE',
';': 'SEMICOLON', '#': 'SHARP'}
#KeyWords
keywords = [['int', 'float', 'double', 'char', 'void'],
['if', 'for', 'while', 'do', 'else'], ['include', 'return']]
#Operators
operators = ['=', '&', '<', '>', '++', '--',
'+', '-', '*', '/', '>=', '<=', '!=']
#delimiters
delimiters = ['(', ')', '{', '}', '[', ']', ',', '\"', ';']
file_name = None
content = None
class Token:
'''Analyze the Tokens'''
def __init__(self, type_index, value):
self.type = DETAIL_TOKEN_STYLE[
value] if type_index == 0 or type_index == 3 or type_index == 4 else TOKEN_STYLE[type_index]
self.value = value
class Lexer(object):
'''Lexical Analyzer'''
tokens = []
def __init__(self):
self.tokens = []
# Blank String
def is_blank(self, index):
return content[index] == ' ' or content[index] == '\t' or content[index] == '\n' or content[index] == '\r'
# Skip Blank String
def skip_blank(self, index):
while index < len(content) and self.is_blank(index):
index += 1
return index
# Print
def print_log(self, style, value):
print ('(%s, %s)' % (style, value))
# Judge Keyword
def is_keyword(self, value):
for item in keywords:
if value in item:
return True
return False
# Lexer Main
def main(self):
i = 0
while i < len(content):
i = self.skip_blank(i)
# include file
if content[i] == '#':
self.tokens.append(Token(4, content[i]))
i = self.skip_blank(i + 1)
# analyze
while i < len(content):
# find "include"
if re.match('include', content[i:]):
self.tokens.append(Token(0, 'include'))
i = self.skip_blank(i + 7)
# find " or <
elif content[i] == '\"' or content[i] == '<':
self.tokens.append(Token(4, content[i]))
i = self.skip_blank(i + 1)
close_flag = '\"' if content[i] == '\"' else '>'
# find include file
lib = ''
while content[i] != close_flag:
lib += content[i]
i += 1
self.tokens.append(Token(1, lib))
self.tokens.append(Token(4, close_flag))
i = self.skip_blank(i + 1)
break
else:
print ('include error!')
exit()
elif content[i].isalpha() or content[i] == '_':
# find string
temp = ''
while i < len(content) and (content[i].isalpha() or content[i] == '_' or content[i].isdigit()):
temp += content[i]
i += 1
# analyze string
if self.is_keyword(temp):
self.tokens.append(Token(0, temp))
else:
self.tokens.append(Token(1, temp))
i = self.skip_blank(i)
# if digits
elif content[i].isdigit():
temp = ''
while i < len(content):
if content[i].isdigit() or (content[i] == '.' and content[i + 1].isdigit()):
temp += content[i]
i += 1
elif not content[i].isdigit():
if content[i] == '.':
print ('float number error!')
exit()
else:
break
self.tokens.append(Token(2, temp))
i = self.skip_blank(i)
# delimiters
elif content[i] in delimiters:
self.tokens.append(Token(4, content[i]))
if content[i] == '\"':
i += 1
temp = ''
while i < len(content):
if content[i] != '\"':
temp += content[i]
i += 1
else:
break
else:
print ('error:lack of \"')
exit()
self.tokens.append(Token(5, temp))
self.tokens.append(Token(4, '\"'))
i = self.skip_blank(i + 1)
elif content[i] in operators:
if (content[i] == '+' or content[i] == '-') and content[i + 1] == content[i]:
self.tokens.append(Token(3, content[i] * 2))
i = self.skip_blank(i + 2)
# if >= or <=
elif (content[i] == '>' or content[i] == '<') and content[i + 1] == '=':
self.tokens.append(Token(3, content[i] + '='))
i = self.skip_blank(i + 2)
# else
else:
self.tokens.append(Token(3, content[i]))
i = self.skip_blank(i + 1)
for token in self.tokens:
print ('(%s, %s)' % (token.type, token.value))
class SyntaxTreeNode(object):
def __init__(self, value = None, _type = None, extra_info = None):
#record value
self.value = value
#record token type
self.type = _type
#record key info
self.extra_info = extra_info
self.father = None
self.left = None
self.right = None
self.first_son = None
def set_value(self,value):
self.value = value
def set_type(self, _type):
self.type = _type
def set_extra_info(self, extra_info):
self.extra_info = extra_info
class SyntaxTree(object):
def __init__(self):
# root of the tree
self.root = None
# current node of the tree
self.current = None
#add a child node, to make sure father is in the tree
def add_child_node(self, new_node, father=None):
if not father:
father = self.current
new_node.father = father
if not father.first_son:
father.first_son = new_node
else:
current_node = father.first_son
while current_node.right:
current_node = current_node.right
current_node.right = new_node
new_node.left = current_node
self.current = new_node
#exchange the brother tree
def switch(self, left, right):
left_left = left.left
right_right = right.right
left.left = right
left.right = right_right
right.left = left_left
right.right = left
if left_left:
left_left.right = right
if right_right:
right_right.left = left
class Parser(object):
def __init__(self):
lexer = Lexer()
lexer.main()
# tokens to be analyzed
self.tokens = lexer.tokens
# tokens index is 0
self.index = 0
# final syntax tree
self.tree = SyntaxTree()
#the parts in block
def _block(self, father_tree):
self.index += 1
sentence_tree = SyntaxTree()
sentence_tree.current = sentence_tree.root = SyntaxTreeNode('Sentence')
father_tree.add_child_node(sentence_tree.root, father_tree.root)
while True:
sentence_pattern = self._judge_sentence_pattern()
#statement
if sentence_pattern = 'STATEMENT':
self._statement(sentence_tree.root)
#assignment
if sentence_pattern = 'ASSIGNMENT':
self._assignment(sentence_tree.root)
#call function
if sentence_pattern = 'FUNCTION_CALL':
self._function_call(sentence_tree.root)
#control
if sentence_pattern = 'CONTROL':
self._control(sentence_tree.root)
# return
elif sentence_pattern == 'RETURN':
self._return(sentence_tree.root)
# Bracket
elif sentence_pattern == 'RB_BRACKET':
break
else:
print 'block error!'
exit()
def _include(self, father=None):
if not father:
father = self.tree.root
include_tree = SyntaxTree()
include_tree.current = include_tree.root = SyntaxTreeNode('Include')
self.tree.add_child_node(include_tree.root, father)
# include语句中双引号的个数
cnt = 0
# include语句是否结束
flag = True
while flag:
if self.tokens[self.index] == '\"':
cnt += 1
if self.index >= len(self.tokens) or cnt >= 2 or self.tokens[self.index].value == '>':
flag = False
include_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value), include_tree.root)
self.index += 1
# 函数声明
def _function_statement(self, father=None):
if not father:
father = self.tree.root
func_statement_tree = SyntaxTree()
func_statement_tree.current = func_statement_tree.root = SyntaxTreeNode(
'FunctionStatement')
self.tree.add_child_node(func_statement_tree.root, father)
# 函数声明语句什么时候结束
flag = True
while flag and self.index < len(self.tokens):
# 如果是函数返回类型
if self.tokens[self.index].value in keywords[0]:
return_type = SyntaxTreeNode('Type')
func_statement_tree.add_child_node(return_type)
func_statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'FIELD_TYPE',
{'type': self.tokens[self.index].value}))
self.index += 1
# 如果是函数名
elif self.tokens[self.index].type == 'IDENTIFIER':
func_name = SyntaxTreeNode('FunctionName')
func_statement_tree.add_child_node(
func_name, func_statement_tree.root)
# extra_info
func_statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'IDENTIFIER', {'type': 'FUNCTION_NAME'}))
self.index += 1
# 如果是参数序列
elif self.tokens[self.index].type == 'LL_BRACKET':
params_list = SyntaxTreeNode('StateParameterList')
func_statement_tree.add_child_node(
params_list, func_statement_tree.root)
self.index += 1
while self.tokens[self.index].type != 'RL_BRACKET':
if self.tokens[self.index].value in keywords[0]:
param = SyntaxTreeNode('Parameter')
func_statement_tree.add_child_node(param, params_list)
# extra_info
func_statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'FIELD_TYPE',
{'type': self.tokens[self.index].value}), param)
if self.tokens[self.index + 1].type == 'IDENTIFIER':
# extra_info
func_statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index + 1].value, 'IDENTIFIER', {
'type': 'VARIABLE', 'variable_type': self.tokens[self.index].value}),
param)
else:
print
'函数定义参数错误!'
exit()
self.index += 1
self.index += 1
self.index += 1
# 如果是遇见了左大括号
elif self.tokens[self.index].type == 'LB_BRACKET':
self._block(func_statement_tree)
#judge the pattern of the sentence
def _statement(self, father=None):
if not father:
father = self.tree.root
statement_tree = SyntaxTree()
statement_tree.current = statement_tree.root = SyntaxTreeNode(
'Statement')
self.tree.add_child_node(statement_tree.root, father)
# 暂时用来保存当前声明语句的类型,以便于识别多个变量的声明
tmp_variable_type = None
while self.tokens[self.index].type != 'SEMICOLON':
# 变量类型
if self.tokens[self.index].value in keywords[0]:
tmp_variable_type = self.tokens[self.index].value
variable_type = SyntaxTreeNode('Type')
statement_tree.add_child_node(variable_type)
# extra_info
statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'FIELD_TYPE',
{'type': self.tokens[self.index].value}))
# 变量名
elif self.tokens[self.index].type == 'IDENTIFIER':
# extra_info
statement_tree.add_child_node(SyntaxTreeNode(self.tokens[self.index].value, 'IDENTIFIER', {
'type': 'VARIABLE', 'variable_type': tmp_variable_type}), statement_tree.root)
# 数组大小
elif self.tokens[self.index].type == 'DIGIT_CONSTANT':
statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'DIGIT_CONSTANT'), statement_tree.root)
statement_tree.current.left.set_extra_info(
{'type': 'LIST', 'list_type': tmp_variable_type})
# 数组元素
elif self.tokens[self.index].type == 'LB_BRACKET':
self.index += 1
constant_list = SyntaxTreeNode('ConstantList')
statement_tree.add_child_node(
constant_list, statement_tree.root)
while self.tokens[self.index].type != 'RB_BRACKET':
if self.tokens[self.index].type == 'DIGIT_CONSTANT':
statement_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'DIGIT_CONSTANT'), constant_list)
self.index += 1
# 多个变量声明
elif self.tokens[self.index].type == 'COMMA':
while self.tokens[self.index].type != 'SEMICOLON':
if self.tokens[self.index].type == 'IDENTIFIER':
tree = SyntaxTree()
tree.current = tree.root = SyntaxTreeNode('Statement')
self.tree.add_child_node(tree.root, father)
# 类型
variable_type = SyntaxTreeNode('Type')
tree.add_child_node(variable_type)
# extra_info
# 类型
tree.add_child_node(
SyntaxTreeNode(tmp_variable_type, 'FIELD_TYPE', {'type': tmp_variable_type}))
# 变量名
tree.add_child_node(SyntaxTreeNode(self.tokens[self.index].value, 'IDENTIFIER', {
'type': 'VARIABLE', 'variable_type': tmp_variable_type}), tree.root)
self.index += 1
break
self.index += 1
self.index += 1
# assignment - TO DO
def _assignment(self, father=None):
if not father:
father = self.tree.root
assign_tree = SyntaxTree()
assign_tree.current = assign_tree.root = SyntaxTreeNode('Assignment')
self.tree.add_child_node(assign_tree.root, father)
while self.tokens[self.index].type != 'SEMICOLON':
# 被赋值的变量
if self.tokens[self.index].type == 'IDENTIFIER':
assign_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'IDENTIFIER'))
self.index += 1
elif self.tokens[self.index].type == 'ASSIGN':
self.index += 1
self._expression(assign_tree.root)
self.index += 1
# while语句,没处理do-while的情况,只处理了while
def _while(self, father=None):
while_tree = SyntaxTree()
while_tree.current = while_tree.root = SyntaxTreeNode(
'Control', 'WhileControl')
self.tree.add_child_node(while_tree.root, father)
self.index += 1
if self.tokens[self.index].type == 'LL_BRACKET':
tmp_index = self.index
while self.tokens[tmp_index].type != 'RL_BRACKET':
tmp_index += 1
self._expression(while_tree.root, tmp_index)
if self.tokens[self.index].type == 'LB_BRACKET':
self._block(while_tree)
# for语句
def _for(self, father=None):
for_tree = SyntaxTree()
for_tree.current = for_tree.root = SyntaxTreeNode(
'Control', 'ForControl')
self.tree.add_child_node(for_tree.root, father)
# 标记for语句是否结束
while True:
token_type = self.tokens[self.index].type
# for标记
if token_type == 'FOR':
self.index += 1
# 左小括号
elif token_type == 'LL_BRACKET':
self.index += 1
# 首先找到右小括号的位置
tmp_index = self.index
while self.tokens[tmp_index].type != 'RL_BRACKET':
tmp_index += 1
# for语句中的第一个分号前的部分
self._assignment(for_tree.root)
# 两个分号中间的部分
self._expression(for_tree.root)
self.index += 1
# 第二个分号后的部分
self._expression(for_tree.root, tmp_index)
self.index += 1
# 如果为左大括号
elif token_type == 'LB_BRACKET':
self._block(for_tree)
break
# 交换for语句下第三个子节点和第四个子节点
current_node = for_tree.root.first_son.right.right
next_node = current_node.right
for_tree.switch(current_node, next_node)
# if语句
def _if_else(self, father=None):
if_else_tree = SyntaxTree()
if_else_tree.current = if_else_tree.root = SyntaxTreeNode(
'Control', 'IfElseControl')
self.tree.add_child_node(if_else_tree.root, father)
if_tree = SyntaxTree()
if_tree.current = if_tree.root = SyntaxTreeNode('IfControl')
if_else_tree.add_child_node(if_tree.root)
# if标志
if self.tokens[self.index].type == 'IF':
self.index += 1
# 左小括号
if self.tokens[self.index].type == 'LL_BRACKET':
self.index += 1
# 右小括号位置
tmp_index = self.index
while self.tokens[tmp_index].type != 'RL_BRACKET':
tmp_index += 1
self._expression(if_tree.root, tmp_index)
self.index += 1
else:
print
'error: lack of left bracket!'
exit()
# 左大括号
if self.tokens[self.index].type == 'LB_BRACKET':
self._block(if_tree)
# 如果是else关键字
if self.tokens[self.index].type == 'ELSE':
self.index += 1
else_tree = SyntaxTree()
else_tree.current = else_tree.root = SyntaxTreeNode('ElseControl')
if_else_tree.add_child_node(else_tree.root, if_else_tree.root)
# 左大括号
if self.tokens[self.index].type == 'LB_BRACKET':
self._block(else_tree)
def _control(self, father=None):
token_type = self.tokens[self.index].type
if token_type == 'WHILE' or token_type == 'DO':
self._while(father)
elif token_type == 'IF':
self._if_else(father)
elif token_type == 'FOR':
self._for(father)
else:
print
'error: control style not supported!'
exit()
# 表达式-->TODO
def _expression(self, father=None, index=None):
if not father:
father = self.tree.root
# 运算符优先级
operator_priority = {'>': 0, '<': 0, '>=': 0, '<=': 0,
'+': 1, '-': 1, '*': 2, '/': 2, '++': 3, '--': 3, '!': 3}
# 运算符栈
operator_stack = []
# 转换成的逆波兰表达式结果
reverse_polish_expression = []
# 中缀表达式转为后缀表达式,即逆波兰表达式
while self.tokens[self.index].type != 'SEMICOLON':
if index and self.index >= index:
break
# 如果是常量
if self.tokens[self.index].type == 'DIGIT_CONSTANT':
tree = SyntaxTree()
tree.current = tree.root = SyntaxTreeNode(
'Expression', 'Constant')
tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, '_Constant'))
reverse_polish_expression.append(tree)
# 如果是变量或者数组的某元素
elif self.tokens[self.index].type == 'IDENTIFIER':
# 变量
if self.tokens[self.index + 1].value in operators or self.tokens[
self.index + 1].type == 'SEMICOLON':
tree = SyntaxTree()
tree.current = tree.root = SyntaxTreeNode(
'Expression', 'Variable')
tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, '_Variable'))
reverse_polish_expression.append(tree)
# 数组的某一个元素ID[i]
elif self.tokens[self.index + 1].type == 'LM_BRACKET':
tree = SyntaxTree()
tree.current = tree.root = SyntaxTreeNode(
'Expression', 'ArrayItem')
# 数组的名字
tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, '_ArrayName'))
self.index += 2
if self.tokens[self.index].type != 'DIGIT_CONSTANT' and self.tokens[
self.index].type != 'IDENTIFIER':
print
'error: 数组下表必须为常量或标识符'
print
self.tokens[self.index].type
exit()
else:
# 数组下标
tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, '_ArrayIndex'), tree.root)
reverse_polish_expression.append(tree)
# 如果是运算符
elif self.tokens[self.index].value in operators or self.tokens[self.index].type == 'LL_BRACKET' or
self.tokens[self.index].type == 'RL_BRACKET':
tree = SyntaxTree()
tree.current = tree.root = SyntaxTreeNode(
'Operator', 'Operator')
tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, '_Operator'))
# 如果是左括号,直接压栈
if self.tokens[self.index].type == 'LL_BRACKET':
operator_stack.append(tree.root)
# 如果是右括号,弹栈直到遇到左括号为止
elif self.tokens[self.index].type == 'RL_BRACKET':
while operator_stack and operator_stack[-1].current.type != 'LL_BRACKET':
reverse_polish_expression.append(operator_stack.pop())
# 将左括号弹出来
if operator_stack:
operator_stack.pop()
# 其他只能是运算符
else:
while operator_stack and operator_priority[tree.current.value] < operator_priority[
operator_stack[-1].current.value]:
reverse_polish_expression.append(operator_stack.pop())
operator_stack.append(tree)
self.index += 1
# 最后将符号栈清空,最终得到逆波兰表达式reverse_polish_expression
while operator_stack:
reverse_polish_expression.append(operator_stack.pop())
# 打印
# for item in reverse_polish_expression:
# print item.current.value,
# print
# 操作数栈
operand_stack = []
child_operators = [['!', '++', '--'], [
'+', '-', '*', '/', '>', '<', '>=', '<=']]
for item in reverse_polish_expression:
if item.root.type != 'Operator':
operand_stack.append(item)
else:
# 处理单目运算符
if item.current.value in child_operators[0]:
a = operand_stack.pop()
new_tree = SyntaxTree()
new_tree.current = new_tree.root = SyntaxTreeNode(
'Expression', 'SingleOperand')
# 添加操作符
new_tree.add_child_node(item.root)
# 添加操作数
new_tree.add_child_node(a.root, new_tree.root)
operand_stack.append(new_tree)
# 双目运算符
elif item.current.value in child_operators[1]:
b = operand_stack.pop()
a = operand_stack.pop()
new_tree = SyntaxTree()
new_tree.current = new_tree.root = SyntaxTreeNode(
'Expression', 'DoubleOperand')
# 第一个操作数
new_tree.add_child_node(a.root)
# 操作符
new_tree.add_child_node(item.root, new_tree.root)
# 第二个操作数
new_tree.add_child_node(b.root, new_tree.root)
operand_stack.append(new_tree)
else:
print
'operator %s not supported!' % item.current.value
exit()
self.tree.add_child_node(operand_stack[0].root, father)
# 函数调用
def _function_call(self, father=None):
if not father:
father = self.tree.root
func_call_tree = SyntaxTree()
func_call_tree.current = func_call_tree.root = SyntaxTreeNode(
'FunctionCall')
self.tree.add_child_node(func_call_tree.root, father)
while self.tokens[self.index].type != 'SEMICOLON':
# 函数名
if self.tokens[self.index].type == 'IDENTIFIER':
func_call_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'FUNCTION_NAME'))
# 左小括号
elif self.tokens[self.index].type == 'LL_BRACKET':
self.index += 1
params_list = SyntaxTreeNode('CallParameterList')
func_call_tree.add_child_node(params_list, func_call_tree.root)
while self.tokens[self.index].type != 'RL_BRACKET':
if self.tokens[self.index].type == 'IDENTIFIER' or self.tokens[
self.index].type == 'DIGIT_CONSTANT' or self.tokens[self.index].type == 'STRING_CONSTANT':
func_call_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, self.tokens[self.index].type),
params_list)
elif self.tokens[self.index].type == 'DOUBLE_QUOTE':
self.index += 1
func_call_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, self.tokens[self.index].type),
params_list)
self.index += 1
elif self.tokens[self.index].type == 'ADDRESS':
func_call_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value, 'ADDRESS'), params_list)
self.index += 1
else:
print
'function call error!'
exit()
self.index += 1
self.index += 1
# return语句 -->TODO
def _return(self, father=None):
if not father:
father = self.tree.root
return_tree = SyntaxTree()
return_tree.current = return_tree.root = SyntaxTreeNode('Return')
self.tree.add_child_node(return_tree.root, father)
while self.tokens[self.index].type != 'SEMICOLON':
# 被赋值的变量
if self.tokens[self.index].type == 'RETURN':
return_tree.add_child_node(
SyntaxTreeNode(self.tokens[self.index].value))
self.index += 1
else:
self._expression(return_tree.root)
self.index += 1
# 根据一个句型的句首判断句型
def _judge_sentence_pattern(self):
token_value = self.tokens[self.index].value
token_type = self.tokens[self.index].type
# include句型
if token_type == 'SHARP' and self.tokens[self.index + 1].type == 'INCLUDE':
return 'INCLUDE'
# 控制句型
elif token_value in keywords[1]:
return 'CONTROL'
# 有可能是声明语句或者函数声明语句
elif token_value in keywords[0] and self.tokens[self.index + 1].type == 'IDENTIFIER':
index_2_token_type = self.tokens[self.index + 2].type
if index_2_token_type == 'LL_BRACKET':
return 'FUNCTION_STATEMENT'
elif index_2_token_type == 'SEMICOLON' or index_2_token_type == 'LM_BRACKET' or index_2_token_type == 'COMMA':
return 'STATEMENT'
else:
return 'ERROR'
# 可能为函数调用或者赋值语句
elif token_type == 'IDENTIFIER':
index_1_token_type = self.tokens[self.index + 1].type
if index_1_token_type == 'LL_BRACKET':
return 'FUNCTION_CALL'
elif index_1_token_type == 'ASSIGN':
return 'ASSIGNMENT'
else:
return 'ERROR'
# return语句
elif token_type == 'RETURN':
return 'RETURN'
# 右大括号,表明函数的结束
elif token_type == 'RB_BRACKET':
self.index += 1
return 'RB_BRACKET'
else:
return 'ERROR'
# 主程序
def main(self):
# 根节点
self.tree.current = self.tree.root = SyntaxTreeNode('Sentence')
while self.index < len(self.tokens):
# 句型
sentence_pattern = self._judge_sentence_pattern()
# 如果是include句型
if sentence_pattern == 'INCLUDE':
self._include()
# 函数声明语句
elif sentence_pattern == 'FUNCTION_STATEMENT':
self._function_statement()
break
# 声明语句
elif sentence_pattern == 'STATEMENT':
self._statement()
# 函数调用
elif sentence_pattern == 'FUNCTION_CALL':
self._function_call()
else:
print
'main error!'
exit()
# DFS遍历语法树
def display(self, node):
if not node:
return
print
'( self: %s %s, father: %s, left: %s, right: %s )' % (
node.value, node.type, node.father.value if node.father else None, node.left.value if node.left else None,
node.right.value if node.right else None)
child = node.first_son
while child:
self.display(child)
child = child.right
class AssemblerFileHandler(object):
'''维护生成的汇编文件'''
def __init__(self):
self.result = ['.data', '.bss', '.lcomm bss_tmp, 4', '.text']
self.data_pointer = 1
self.bss_pointer = 3
self.text_pointer = 4
def insert(self, value, _type):
# 插入到data域
if _type == 'DATA':
self.result.insert(self.data_pointer, value)
self.data_pointer += 1
self.bss_pointer += 1
self.text_pointer += 1
# 插入到bss域
elif _type == 'BSS':
self.result.insert(self.bss_pointer, value)
self.bss_pointer += 1
self.text_pointer += 1
# 插入到代码段
elif _type == 'TEXT':
self.result.insert(self.text_pointer, value)
self.text_pointer += 1
else:
print
'error!'
exit()
# 将结果保存到文件中
def generate_ass_file(self):
self.file = open(file_name + '.S', 'w+')
self.file.write('\n'.join(self.result) + '\n')
self.file.close()
class Assembler(object):
'''编译成汇编语言'''
def __init__(self):
self.parser = Parser()
self.parser.main()
# 生成的语法树
self.tree = self.parser.tree
# 要生成的汇编文件管理器
self.ass_file_handler = AssemblerFileHandler()
# 符号表
self.symbol_table = {}
# 语法类型
self.sentence_type = ['Sentence', 'Include', 'FunctionStatement',
'Statement', 'FunctionCall', 'Assignment', 'Control', 'Expression', 'Return']
# 表达式中的符号栈
self.operator_stack = []
# 表达式中的操作符栈
self.operand_stack = []
# 已经声明了多少个label
self.label_cnt = 0
# ifelse中的标签
self.labels_ifelse = {}
# include句型
def _include(self, node=None):
pass
# 函数定义句型
def _function_statement(self, node=None):
# 第一个儿子
current_node = node.first_son
while current_node:
if current_node.value == 'FunctionName':
if current_node.first_son.value != 'main':
print
'other function statement except for main is not supported!'
exit()
else:
self.ass_file_handler.insert('.globl main', 'TEXT')
self.ass_file_handler.insert('main:', 'TEXT')
self.ass_file_handler.insert('finit', 'TEXT')
elif current_node.value == 'Sentence':
self.traverse(current_node.first_son)
current_node = current_node.right
# 简单的sizeof
def _sizeof(self, _type):
size = -1
if _type == 'int' or _type == 'float' or _type == 'long':
size = 4
elif _type == 'char':
size = 1
elif _type == 'double':
size = 8
return str(size)
# 声明语句
def _statement(self, node=None):
# 对应的汇编代码中的声明语句
line = None
# 1:初始化的,0:没有初始化
flag = 0
# 变量数据类型
variable_field_type = None
# 变量类型,是数组还是单个变量
variable_type = None
# 变量名
variable_name = None
current_node = node.first_son
while current_node:
# 类型
if current_node.value == 'Type':
variable_field_type = current_node.first_son.value
# 变量名
elif current_node.type == 'IDENTIFIER':
variable_name = current_node.value
variable_type = current_node.extra_info['type']
line = '.lcomm ' + variable_name + \
', ' + self._sizeof(variable_field_type)
# 数组元素
elif current_node.value == 'ConstantList':
line = variable_name + ': .' + variable_field_type + ' '
tmp_node = current_node.first_son
# 保存该数组
array = []
while tmp_node:
array.append(tmp_node.value)
tmp_node = tmp_node.right
line += ', '.join(array)
current_node = current_node.right
self.ass_file_handler.insert(
line, 'BSS' if variable_type == 'VARIABLE' else 'DATA')
# 将该变量存入符号表
self.symbol_table[variable_name] = {
'type': variable_type, 'field_type': variable_field_type}
# 函数调用
def _function_call(self, node=None):
current_node = node.first_son
func_name = None
parameter_list = []
while current_node:
# 函数名字
if current_node.type == 'FUNCTION_NAME':
func_name = current_node.value
if func_name != 'scanf' and func_name != 'printf':
print
'function call except scanf and printf not supported yet!'
exit()
# 函数参数
elif current_node.value == 'CallParameterList':
tmp_node = current_node.first_son
while tmp_node:
# 是常数
if tmp_node.type == 'DIGIT_CONSTANT' or tmp_node.type == 'STRING_CONSTANT':
# 汇编中该参数的名称
label = 'label_' + str(self.label_cnt)
self.label_cnt += 1
if tmp_node.type == 'STRING_CONSTANT':
# 添加数据段中该参数定义
line = label + ': .asciz "' + tmp_node.value + '"'
self.ass_file_handler.insert(line, 'DATA')
else:
print
'in functionc_call digital constant parameter is not supported yet!'
exit()
self.symbol_table[label] = {
'type': 'STRING_CONSTANT', 'value': tmp_node.value}
parameter_list.append(label)
# 是某个变量
elif tmp_node.type == 'IDENTIFIER':
parameter_list.append(tmp_node.value)
elif tmp_node.type == 'ADDRESS':
pass
else:
print
tmp_node.value
print
tmp_node.type
print
'parameter type is not supported yet!'
exit()
tmp_node = tmp_node.right
current_node = current_node.right
# 添加到代码段
if func_name == 'printf':