1# -----------------------------------------------------------------------------
2# cparse.py
3#
4# Simple parser for ANSI C.  Based on the grammar in K&R, 2nd Ed.
5# -----------------------------------------------------------------------------
6
7import sys
8import clex
9import ply.yacc as yacc
10
11# Get the token map
12tokens = clex.tokens
13
14# translation-unit:
15
16def p_translation_unit_1(t):
17    'translation_unit : external_declaration'
18    pass
19
20def p_translation_unit_2(t):
21    'translation_unit : translation_unit external_declaration'
22    pass
23
24# external-declaration:
25
26def p_external_declaration_1(t):
27    'external_declaration : function_definition'
28    pass
29
30def p_external_declaration_2(t):
31    'external_declaration : declaration'
32    pass
33
34# function-definition:
35
36def p_function_definition_1(t):
37    'function_definition : declaration_specifiers declarator declaration_list compound_statement'
38    pass
39
40def p_function_definition_2(t):
41    'function_definition : declarator declaration_list compound_statement'
42    pass
43
44def p_function_definition_3(t):
45    'function_definition : declarator compound_statement'
46    pass
47
48def p_function_definition_4(t):
49    'function_definition : declaration_specifiers declarator compound_statement'
50    pass
51
52# declaration:
53
54def p_declaration_1(t):
55    'declaration : declaration_specifiers init_declarator_list SEMI'
56    pass
57
58def p_declaration_2(t):
59    'declaration : declaration_specifiers SEMI'
60    pass
61
62# declaration-list:
63
64def p_declaration_list_1(t):
65    'declaration_list : declaration'
66    pass
67
68def p_declaration_list_2(t):
69    'declaration_list : declaration_list declaration '
70    pass
71
72# declaration-specifiers
73def p_declaration_specifiers_1(t):
74    'declaration_specifiers : storage_class_specifier declaration_specifiers'
75    pass
76
77def p_declaration_specifiers_2(t):
78    'declaration_specifiers : type_specifier declaration_specifiers'
79    pass
80
81def p_declaration_specifiers_3(t):
82    'declaration_specifiers : type_qualifier declaration_specifiers'
83    pass
84
85def p_declaration_specifiers_4(t):
86    'declaration_specifiers : storage_class_specifier'
87    pass
88
89def p_declaration_specifiers_5(t):
90    'declaration_specifiers : type_specifier'
91    pass
92
93def p_declaration_specifiers_6(t):
94    'declaration_specifiers : type_qualifier'
95    pass
96
97# storage-class-specifier
98def p_storage_class_specifier(t):
99    '''storage_class_specifier : AUTO
100                               | REGISTER
101                               | STATIC
102                               | EXTERN
103                               | TYPEDEF
104                               '''
105    pass
106
107# type-specifier:
108def p_type_specifier(t):
109    '''type_specifier : VOID
110                      | CHAR
111                      | SHORT
112                      | INT
113                      | LONG
114                      | FLOAT
115                      | DOUBLE
116                      | SIGNED
117                      | UNSIGNED
118                      | struct_or_union_specifier
119                      | enum_specifier
120                      | TYPEID
121                      '''
122    pass
123
124# type-qualifier:
125def p_type_qualifier(t):
126    '''type_qualifier : CONST
127                      | VOLATILE'''
128    pass
129
130# struct-or-union-specifier
131
132def p_struct_or_union_specifier_1(t):
133    'struct_or_union_specifier : struct_or_union ID LBRACE struct_declaration_list RBRACE'
134    pass
135
136def p_struct_or_union_specifier_2(t):
137    'struct_or_union_specifier : struct_or_union LBRACE struct_declaration_list RBRACE'
138    pass
139
140def p_struct_or_union_specifier_3(t):
141    'struct_or_union_specifier : struct_or_union ID'
142    pass
143
144# struct-or-union:
145def p_struct_or_union(t):
146    '''struct_or_union : STRUCT
147                       | UNION
148                       '''
149    pass
150
151# struct-declaration-list:
152
153def p_struct_declaration_list_1(t):
154    'struct_declaration_list : struct_declaration'
155    pass
156
157def p_struct_declaration_list_2(t):
158    'struct_declaration_list : struct_declaration_list struct_declaration'
159    pass
160
161# init-declarator-list:
162
163def p_init_declarator_list_1(t):
164    'init_declarator_list : init_declarator'
165    pass
166
167def p_init_declarator_list_2(t):
168    'init_declarator_list : init_declarator_list COMMA init_declarator'
169    pass
170
171# init-declarator
172
173def p_init_declarator_1(t):
174    'init_declarator : declarator'
175    pass
176
177def p_init_declarator_2(t):
178    'init_declarator : declarator EQUALS initializer'
179    pass
180
181# struct-declaration:
182
183def p_struct_declaration(t):
184    'struct_declaration : specifier_qualifier_list struct_declarator_list SEMI'
185    pass
186
187# specifier-qualifier-list:
188
189def p_specifier_qualifier_list_1(t):
190    'specifier_qualifier_list : type_specifier specifier_qualifier_list'
191    pass
192
193def p_specifier_qualifier_list_2(t):
194    'specifier_qualifier_list : type_specifier'
195    pass
196
197def p_specifier_qualifier_list_3(t):
198    'specifier_qualifier_list : type_qualifier specifier_qualifier_list'
199    pass
200
201def p_specifier_qualifier_list_4(t):
202    'specifier_qualifier_list : type_qualifier'
203    pass
204
205# struct-declarator-list:
206
207def p_struct_declarator_list_1(t):
208    'struct_declarator_list : struct_declarator'
209    pass
210
211def p_struct_declarator_list_2(t):
212    'struct_declarator_list : struct_declarator_list COMMA struct_declarator'
213    pass
214
215# struct-declarator:
216
217def p_struct_declarator_1(t):
218    'struct_declarator : declarator'
219    pass
220
221def p_struct_declarator_2(t):
222    'struct_declarator : declarator COLON constant_expression'
223    pass
224
225def p_struct_declarator_3(t):
226    'struct_declarator : COLON constant_expression'
227    pass
228
229# enum-specifier:
230
231def p_enum_specifier_1(t):
232    'enum_specifier : ENUM ID LBRACE enumerator_list RBRACE'
233    pass
234
235def p_enum_specifier_2(t):
236    'enum_specifier : ENUM LBRACE enumerator_list RBRACE'
237    pass
238
239def p_enum_specifier_3(t):
240    'enum_specifier : ENUM ID'
241    pass
242
243# enumerator_list:
244def p_enumerator_list_1(t):
245    'enumerator_list : enumerator'
246    pass
247
248def p_enumerator_list_2(t):
249    'enumerator_list : enumerator_list COMMA enumerator'
250    pass
251
252# enumerator:
253def p_enumerator_1(t):
254    'enumerator : ID'
255    pass
256
257def p_enumerator_2(t):
258    'enumerator : ID EQUALS constant_expression'
259    pass
260
261# declarator:
262
263def p_declarator_1(t):
264    'declarator : pointer direct_declarator'
265    pass
266
267def p_declarator_2(t):
268    'declarator : direct_declarator'
269    pass
270
271# direct-declarator:
272
273def p_direct_declarator_1(t):
274    'direct_declarator : ID'
275    pass
276
277def p_direct_declarator_2(t):
278    'direct_declarator : LPAREN declarator RPAREN'
279    pass
280
281def p_direct_declarator_3(t):
282    'direct_declarator : direct_declarator LBRACKET constant_expression_opt RBRACKET'
283    pass
284
285def p_direct_declarator_4(t):
286    'direct_declarator : direct_declarator LPAREN parameter_type_list RPAREN '
287    pass
288
289def p_direct_declarator_5(t):
290    'direct_declarator : direct_declarator LPAREN identifier_list RPAREN '
291    pass
292
293def p_direct_declarator_6(t):
294    'direct_declarator : direct_declarator LPAREN RPAREN '
295    pass
296
297# pointer:
298def p_pointer_1(t):
299    'pointer : TIMES type_qualifier_list'
300    pass
301
302def p_pointer_2(t):
303    'pointer : TIMES'
304    pass
305
306def p_pointer_3(t):
307    'pointer : TIMES type_qualifier_list pointer'
308    pass
309
310def p_pointer_4(t):
311    'pointer : TIMES pointer'
312    pass
313
314# type-qualifier-list:
315
316def p_type_qualifier_list_1(t):
317    'type_qualifier_list : type_qualifier'
318    pass
319
320def p_type_qualifier_list_2(t):
321    'type_qualifier_list : type_qualifier_list type_qualifier'
322    pass
323
324# parameter-type-list:
325
326def p_parameter_type_list_1(t):
327    'parameter_type_list : parameter_list'
328    pass
329
330def p_parameter_type_list_2(t):
331    'parameter_type_list : parameter_list COMMA ELLIPSIS'
332    pass
333
334# parameter-list:
335
336def p_parameter_list_1(t):
337    'parameter_list : parameter_declaration'
338    pass
339
340def p_parameter_list_2(t):
341    'parameter_list : parameter_list COMMA parameter_declaration'
342    pass
343
344# parameter-declaration:
345def p_parameter_declaration_1(t):
346    'parameter_declaration : declaration_specifiers declarator'
347    pass
348
349def p_parameter_declaration_2(t):
350    'parameter_declaration : declaration_specifiers abstract_declarator_opt'
351    pass
352
353# identifier-list:
354def p_identifier_list_1(t):
355    'identifier_list : ID'
356    pass
357
358def p_identifier_list_2(t):
359    'identifier_list : identifier_list COMMA ID'
360    pass
361
362# initializer:
363
364def p_initializer_1(t):
365    'initializer : assignment_expression'
366    pass
367
368def p_initializer_2(t):
369    '''initializer : LBRACE initializer_list RBRACE
370                   | LBRACE initializer_list COMMA RBRACE'''
371    pass
372
373# initializer-list:
374
375def p_initializer_list_1(t):
376    'initializer_list : initializer'
377    pass
378
379def p_initializer_list_2(t):
380    'initializer_list : initializer_list COMMA initializer'
381    pass
382
383# type-name:
384
385def p_type_name(t):
386    'type_name : specifier_qualifier_list abstract_declarator_opt'
387    pass
388
389def p_abstract_declarator_opt_1(t):
390    'abstract_declarator_opt : empty'
391    pass
392
393def p_abstract_declarator_opt_2(t):
394    'abstract_declarator_opt : abstract_declarator'
395    pass
396
397# abstract-declarator:
398
399def p_abstract_declarator_1(t):
400    'abstract_declarator : pointer '
401    pass
402
403def p_abstract_declarator_2(t):
404    'abstract_declarator : pointer direct_abstract_declarator'
405    pass
406
407def p_abstract_declarator_3(t):
408    'abstract_declarator : direct_abstract_declarator'
409    pass
410
411# direct-abstract-declarator:
412
413def p_direct_abstract_declarator_1(t):
414    'direct_abstract_declarator : LPAREN abstract_declarator RPAREN'
415    pass
416
417def p_direct_abstract_declarator_2(t):
418    'direct_abstract_declarator : direct_abstract_declarator LBRACKET constant_expression_opt RBRACKET'
419    pass
420
421def p_direct_abstract_declarator_3(t):
422    'direct_abstract_declarator : LBRACKET constant_expression_opt RBRACKET'
423    pass
424
425def p_direct_abstract_declarator_4(t):
426    'direct_abstract_declarator : direct_abstract_declarator LPAREN parameter_type_list_opt RPAREN'
427    pass
428
429def p_direct_abstract_declarator_5(t):
430    'direct_abstract_declarator : LPAREN parameter_type_list_opt RPAREN'
431    pass
432
433# Optional fields in abstract declarators
434
435def p_constant_expression_opt_1(t):
436    'constant_expression_opt : empty'
437    pass
438
439def p_constant_expression_opt_2(t):
440    'constant_expression_opt : constant_expression'
441    pass
442
443def p_parameter_type_list_opt_1(t):
444    'parameter_type_list_opt : empty'
445    pass
446
447def p_parameter_type_list_opt_2(t):
448    'parameter_type_list_opt : parameter_type_list'
449    pass
450
451# statement:
452
453def p_statement(t):
454    '''
455    statement : labeled_statement
456              | expression_statement
457              | compound_statement
458              | selection_statement
459              | iteration_statement
460              | jump_statement
461              '''
462    pass
463
464# labeled-statement:
465
466def p_labeled_statement_1(t):
467    'labeled_statement : ID COLON statement'
468    pass
469
470def p_labeled_statement_2(t):
471    'labeled_statement : CASE constant_expression COLON statement'
472    pass
473
474def p_labeled_statement_3(t):
475    'labeled_statement : DEFAULT COLON statement'
476    pass
477
478# expression-statement:
479def p_expression_statement(t):
480    'expression_statement : expression_opt SEMI'
481    pass
482
483# compound-statement:
484
485def p_compound_statement_1(t):
486    'compound_statement : LBRACE declaration_list statement_list RBRACE'
487    pass
488
489def p_compound_statement_2(t):
490    'compound_statement : LBRACE statement_list RBRACE'
491    pass
492
493def p_compound_statement_3(t):
494    'compound_statement : LBRACE declaration_list RBRACE'
495    pass
496
497def p_compound_statement_4(t):
498    'compound_statement : LBRACE RBRACE'
499    pass
500
501# statement-list:
502
503def p_statement_list_1(t):
504    'statement_list : statement'
505    pass
506
507def p_statement_list_2(t):
508    'statement_list : statement_list statement'
509    pass
510
511# selection-statement
512
513def p_selection_statement_1(t):
514    'selection_statement : IF LPAREN expression RPAREN statement'
515    pass
516
517def p_selection_statement_2(t):
518    'selection_statement : IF LPAREN expression RPAREN statement ELSE statement '
519    pass
520
521def p_selection_statement_3(t):
522    'selection_statement : SWITCH LPAREN expression RPAREN statement '
523    pass
524
525# iteration_statement:
526
527def p_iteration_statement_1(t):
528    'iteration_statement : WHILE LPAREN expression RPAREN statement'
529    pass
530
531def p_iteration_statement_2(t):
532    'iteration_statement : FOR LPAREN expression_opt SEMI expression_opt SEMI expression_opt RPAREN statement '
533    pass
534
535def p_iteration_statement_3(t):
536    'iteration_statement : DO statement WHILE LPAREN expression RPAREN SEMI'
537    pass
538
539# jump_statement:
540
541def p_jump_statement_1(t):
542    'jump_statement : GOTO ID SEMI'
543    pass
544
545def p_jump_statement_2(t):
546    'jump_statement : CONTINUE SEMI'
547    pass
548
549def p_jump_statement_3(t):
550    'jump_statement : BREAK SEMI'
551    pass
552
553def p_jump_statement_4(t):
554    'jump_statement : RETURN expression_opt SEMI'
555    pass
556
557def p_expression_opt_1(t):
558    'expression_opt : empty'
559    pass
560
561def p_expression_opt_2(t):
562    'expression_opt : expression'
563    pass
564
565# expression:
566def p_expression_1(t):
567    'expression : assignment_expression'
568    pass
569
570def p_expression_2(t):
571    'expression : expression COMMA assignment_expression'
572    pass
573
574# assigment_expression:
575def p_assignment_expression_1(t):
576    'assignment_expression : conditional_expression'
577    pass
578
579def p_assignment_expression_2(t):
580    'assignment_expression : unary_expression assignment_operator assignment_expression'
581    pass
582
583# assignment_operator:
584def p_assignment_operator(t):
585    '''
586    assignment_operator : EQUALS
587                        | TIMESEQUAL
588                        | DIVEQUAL
589                        | MODEQUAL
590                        | PLUSEQUAL
591                        | MINUSEQUAL
592                        | LSHIFTEQUAL
593                        | RSHIFTEQUAL
594                        | ANDEQUAL
595                        | OREQUAL
596                        | XOREQUAL
597                        '''
598    pass
599
600# conditional-expression
601def p_conditional_expression_1(t):
602    'conditional_expression : logical_or_expression'
603    pass
604
605def p_conditional_expression_2(t):
606    'conditional_expression : logical_or_expression CONDOP expression COLON conditional_expression '
607    pass
608
609# constant-expression
610
611def p_constant_expression(t):
612    'constant_expression : conditional_expression'
613    pass
614
615# logical-or-expression
616
617def p_logical_or_expression_1(t):
618    'logical_or_expression : logical_and_expression'
619    pass
620
621def p_logical_or_expression_2(t):
622    'logical_or_expression : logical_or_expression LOR logical_and_expression'
623    pass
624
625# logical-and-expression
626
627def p_logical_and_expression_1(t):
628    'logical_and_expression : inclusive_or_expression'
629    pass
630
631def p_logical_and_expression_2(t):
632    'logical_and_expression : logical_and_expression LAND inclusive_or_expression'
633    pass
634
635# inclusive-or-expression:
636
637def p_inclusive_or_expression_1(t):
638    'inclusive_or_expression : exclusive_or_expression'
639    pass
640
641def p_inclusive_or_expression_2(t):
642    'inclusive_or_expression : inclusive_or_expression OR exclusive_or_expression'
643    pass
644
645# exclusive-or-expression:
646
647def p_exclusive_or_expression_1(t):
648    'exclusive_or_expression :  and_expression'
649    pass
650
651def p_exclusive_or_expression_2(t):
652    'exclusive_or_expression :  exclusive_or_expression XOR and_expression'
653    pass
654
655# AND-expression
656
657def p_and_expression_1(t):
658    'and_expression : equality_expression'
659    pass
660
661def p_and_expression_2(t):
662    'and_expression : and_expression AND equality_expression'
663    pass
664
665
666# equality-expression:
667def p_equality_expression_1(t):
668    'equality_expression : relational_expression'
669    pass
670
671def p_equality_expression_2(t):
672    'equality_expression : equality_expression EQ relational_expression'
673    pass
674
675def p_equality_expression_3(t):
676    'equality_expression : equality_expression NE relational_expression'
677    pass
678
679
680# relational-expression:
681def p_relational_expression_1(t):
682    'relational_expression : shift_expression'
683    pass
684
685def p_relational_expression_2(t):
686    'relational_expression : relational_expression LT shift_expression'
687    pass
688
689def p_relational_expression_3(t):
690    'relational_expression : relational_expression GT shift_expression'
691    pass
692
693def p_relational_expression_4(t):
694    'relational_expression : relational_expression LE shift_expression'
695    pass
696
697def p_relational_expression_5(t):
698    'relational_expression : relational_expression GE shift_expression'
699    pass
700
701# shift-expression
702
703def p_shift_expression_1(t):
704    'shift_expression : additive_expression'
705    pass
706
707def p_shift_expression_2(t):
708    'shift_expression : shift_expression LSHIFT additive_expression'
709    pass
710
711def p_shift_expression_3(t):
712    'shift_expression : shift_expression RSHIFT additive_expression'
713    pass
714
715# additive-expression
716
717def p_additive_expression_1(t):
718    'additive_expression : multiplicative_expression'
719    pass
720
721def p_additive_expression_2(t):
722    'additive_expression : additive_expression PLUS multiplicative_expression'
723    pass
724
725def p_additive_expression_3(t):
726    'additive_expression : additive_expression MINUS multiplicative_expression'
727    pass
728
729# multiplicative-expression
730
731def p_multiplicative_expression_1(t):
732    'multiplicative_expression : cast_expression'
733    pass
734
735def p_multiplicative_expression_2(t):
736    'multiplicative_expression : multiplicative_expression TIMES cast_expression'
737    pass
738
739def p_multiplicative_expression_3(t):
740    'multiplicative_expression : multiplicative_expression DIVIDE cast_expression'
741    pass
742
743def p_multiplicative_expression_4(t):
744    'multiplicative_expression : multiplicative_expression MOD cast_expression'
745    pass
746
747# cast-expression:
748
749def p_cast_expression_1(t):
750    'cast_expression : unary_expression'
751    pass
752
753def p_cast_expression_2(t):
754    'cast_expression : LPAREN type_name RPAREN cast_expression'
755    pass
756
757# unary-expression:
758def p_unary_expression_1(t):
759    'unary_expression : postfix_expression'
760    pass
761
762def p_unary_expression_2(t):
763    'unary_expression : PLUSPLUS unary_expression'
764    pass
765
766def p_unary_expression_3(t):
767    'unary_expression : MINUSMINUS unary_expression'
768    pass
769
770def p_unary_expression_4(t):
771    'unary_expression : unary_operator cast_expression'
772    pass
773
774def p_unary_expression_5(t):
775    'unary_expression : SIZEOF unary_expression'
776    pass
777
778def p_unary_expression_6(t):
779    'unary_expression : SIZEOF LPAREN type_name RPAREN'
780    pass
781
782#unary-operator
783def p_unary_operator(t):
784    '''unary_operator : AND
785                    | TIMES
786                    | PLUS
787                    | MINUS
788                    | NOT
789                    | LNOT '''
790    pass
791
792# postfix-expression:
793def p_postfix_expression_1(t):
794    'postfix_expression : primary_expression'
795    pass
796
797def p_postfix_expression_2(t):
798    'postfix_expression : postfix_expression LBRACKET expression RBRACKET'
799    pass
800
801def p_postfix_expression_3(t):
802    'postfix_expression : postfix_expression LPAREN argument_expression_list RPAREN'
803    pass
804
805def p_postfix_expression_4(t):
806    'postfix_expression : postfix_expression LPAREN RPAREN'
807    pass
808
809def p_postfix_expression_5(t):
810    'postfix_expression : postfix_expression PERIOD ID'
811    pass
812
813def p_postfix_expression_6(t):
814    'postfix_expression : postfix_expression ARROW ID'
815    pass
816
817def p_postfix_expression_7(t):
818    'postfix_expression : postfix_expression PLUSPLUS'
819    pass
820
821def p_postfix_expression_8(t):
822    'postfix_expression : postfix_expression MINUSMINUS'
823    pass
824
825# primary-expression:
826def p_primary_expression(t):
827    '''primary_expression :  ID
828                        |  constant
829                        |  SCONST
830                        |  LPAREN expression RPAREN'''
831    pass
832
833# argument-expression-list:
834def p_argument_expression_list(t):
835    '''argument_expression_list :  assignment_expression
836                              |  argument_expression_list COMMA assignment_expression'''
837    pass
838
839# constant:
840def p_constant(t):
841   '''constant : ICONST
842              | FCONST
843              | CCONST'''
844   pass
845
846
847def p_empty(t):
848    'empty : '
849    pass
850
851def p_error(t):
852    print("Whoa. We're hosed")
853
854import profile
855# Build the grammar
856
857yacc.yacc(method='LALR')
858
859#profile.run("yacc.yacc(method='LALR')")
860
861
862
863
864