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