11 #include "type_hash.h"
13 #include "adt/bitfiddle.h"
14 #include "adt/error.h"
15 #include "adt/array.h"
17 //#define PRINT_TOKENS
18 //#define ABORT_ON_ERROR
19 #define MAX_LOOKAHEAD 2
21 struct environment_entry_t {
23 declaration_t *old_declaration;
24 const void *old_context;
28 static token_t lookahead_buffer[MAX_LOOKAHEAD];
29 static int lookahead_bufpos;
30 static struct obstack environment_obstack;
31 static environment_entry_t **environment_stack = NULL;
32 static context_t *context = NULL;
33 static declaration_t *last_declaration = NULL;
34 static struct obstack temp_obst;
36 static type_t *type_int = NULL;
37 static type_t *type_const_char = NULL;
38 static type_t *type_string = NULL;
39 static type_t *type_void = NULL;
40 static type_t *type_size_t = NULL;
42 static statement_t *parse_compound_statement(void);
43 static statement_t *parse_statement(void);
45 static expression_t *parse_sub_expression(unsigned precedence);
46 static expression_t *parse_expression(void);
47 static type_t *parse_typename(void);
49 #define STORAGE_CLASSES \
56 #define TYPE_QUALIFIERS \
62 #ifdef PROVIDE_COMPLEX
63 #define COMPLEX_SPECIFIERS \
66 #define COMPLEX_SPECIFIERS
69 #ifdef PROVIDE_IMAGINARY
70 #define IMAGINARY_SPECIFIERS \
73 #define IMAGINARY_SPECIFIERS
76 #define TYPE_SPECIFIERS \
94 #define DECLARATION_START \
99 #define TYPENAME_START \
103 static inline void *allocate_ast_zero(size_t size)
105 void *res = allocate_ast(size);
106 memset(res, 0, size);
110 static inline void *allocate_type_zero(size_t size)
112 void *res = obstack_alloc(type_obst, size);
113 memset(res, 0, size);
118 * returns the top element of the environment stack
120 static inline size_t environment_top(void)
122 return ARR_LEN(environment_stack);
127 static inline void next_token(void)
129 token = lookahead_buffer[lookahead_bufpos];
130 lookahead_buffer[lookahead_bufpos] = lexer_token;
133 lookahead_bufpos = (lookahead_bufpos+1) % MAX_LOOKAHEAD;
136 print_token(stderr, &token);
137 fprintf(stderr, "\n");
141 static inline const token_t *look_ahead(int num)
143 assert(num > 0 && num <= MAX_LOOKAHEAD);
144 int pos = (lookahead_bufpos+num-1) % MAX_LOOKAHEAD;
145 return & lookahead_buffer[pos];
148 static inline void eat(token_type_t type)
150 assert(token.type == type);
154 void parser_print_error_prefix_pos(const source_position_t source_position)
156 fputs(source_position.input_name, stderr);
158 fprintf(stderr, "%d", source_position.linenr);
159 fputs(": error: ", stderr);
160 #ifdef ABORT_ON_ERROR
165 void parser_print_error_prefix(void)
167 parser_print_error_prefix_pos(token.source_position);
170 static void parse_error(const char *message)
172 parser_print_error_prefix();
173 fprintf(stderr, "parse error: %s\n", message);
176 static void parse_error_expected(const char *message, ...)
181 if(message != NULL) {
182 parser_print_error_prefix();
183 fprintf(stderr, "%s\n", message);
185 parser_print_error_prefix();
186 fputs("Parse error: got ", stderr);
187 print_token(stderr, &token);
188 fputs(", expected ", stderr);
190 va_start(args, message);
191 token_type_t token_type = va_arg(args, token_type_t);
192 while(token_type != 0) {
196 fprintf(stderr, ", ");
198 print_token_type(stderr, token_type);
199 token_type = va_arg(args, token_type_t);
202 fprintf(stderr, "\n");
205 static void eat_block(void)
207 if(token.type == '{')
210 while(token.type != '}') {
211 if(token.type == T_EOF)
213 if(token.type == '{') {
222 static void eat_statement(void)
224 while(token.type != ';') {
225 if(token.type == T_EOF)
227 if(token.type == '}')
229 if(token.type == '{') {
238 static void eat_brace(void)
240 if(token.type == '(')
243 while(token.type != ')') {
244 if(token.type == T_EOF)
246 if(token.type == '{') {
255 #define expect(expected) \
256 if(UNLIKELY(token.type != (expected))) { \
257 parse_error_expected(NULL, (expected), 0); \
263 #define expect_void(expected) \
264 if(UNLIKELY(token.type != (expected))) { \
265 parse_error_expected(NULL, (expected), 0); \
271 static void set_context(context_t *new_context)
273 context = new_context;
275 declaration_t *declaration = new_context->declarations;
276 if(declaration != NULL) {
278 if(declaration->next == NULL)
280 declaration = declaration->next;
284 last_declaration = declaration;
288 * called when we find a 2nd declarator for an identifier we already have a
291 static bool is_compatible_declaration (declaration_t *declaration,
292 declaration_t *previous)
294 /* TODO: not correct yet */
295 return declaration->type == previous->type;
299 * pushs an environment_entry on the environment stack and links the
300 * corresponding symbol to the new entry
302 static inline declaration_t *environment_push(declaration_t *declaration,
305 environment_entry_t *entry
306 = obstack_alloc(&environment_obstack, sizeof(entry[0]));
307 memset(entry, 0, sizeof(entry[0]));
309 int top = ARR_LEN(environment_stack);
310 ARR_RESIZE(environment_stack, top + 1);
311 environment_stack[top] = entry;
313 assert(declaration->source_position.input_name != NULL);
315 symbol_t *symbol = declaration->symbol;
316 assert(declaration != symbol->declaration);
318 if(symbol->context == context) {
319 declaration_t *previous_declaration = symbol->declaration;
320 if(symbol->declaration != NULL) {
321 if(!is_compatible_declaration(declaration, previous_declaration)) {
322 parser_print_error_prefix_pos(declaration->source_position);
323 fprintf(stderr, "definition of symbol '%s' with type ",
324 declaration->symbol->string);
325 print_type(declaration->type);
327 parser_print_error_prefix_pos(
328 previous_declaration->source_position);
329 fprintf(stderr, "is incompatible with previous declaration "
331 print_type(previous_declaration->type);
334 return previous_declaration;
338 entry->old_declaration = symbol->declaration;
339 entry->old_context = symbol->context;
340 entry->symbol = symbol;
341 symbol->declaration = declaration;
342 symbol->context = context;
348 * pops symbols from the environment stack until @p new_top is the top element
350 static inline void environment_pop_to(size_t new_top)
352 environment_entry_t *entry = NULL;
353 size_t top = ARR_LEN(environment_stack);
359 assert(new_top < top);
362 entry = environment_stack[i - 1];
364 symbol_t *symbol = entry->symbol;
366 symbol->declaration = entry->old_declaration;
367 symbol->context = entry->old_context;
370 } while(i != new_top);
371 obstack_free(&environment_obstack, entry);
373 ARR_SHRINKLEN(environment_stack, (int) new_top);
378 static expression_t *parse_constant_expression(void)
380 /* start parsing at precedence 7 (conditional expression) */
381 return parse_sub_expression(7);
384 static expression_t *parse_assignment_expression(void)
386 /* start parsing at precedence 2 (assignment expression) */
387 return parse_sub_expression(2);
390 static void parse_compound_type_entries(void);
391 static void parse_declarator(declaration_t *declaration,
392 storage_class_t storage_class, type_t *type,
393 int may_be_abstract);
394 static declaration_t *record_declaration(declaration_t *declaration);
396 typedef struct declaration_specifiers_t declaration_specifiers_t;
397 struct declaration_specifiers_t {
398 storage_class_t storage_class;
402 static compound_type_t *find_compound_type(compound_type_t *types,
403 const symbol_t *symbol)
405 compound_type_t *type = types;
406 for( ; type != NULL; type = type->next) {
407 if(type->symbol == symbol)
414 static type_t *parse_compound_type_specifier(bool is_struct)
422 symbol_t *symbol = NULL;
423 compound_type_t *compound_type = NULL;
425 if(token.type == T_IDENTIFIER) {
426 symbol = token.v.symbol;
429 if(context != NULL) {
431 compound_type = find_compound_type(context->structs, symbol);
433 compound_type = find_compound_type(context->unions, symbol);
436 } else if(token.type != '{') {
438 parse_error_expected("problem while parsing struct type specifier",
439 T_IDENTIFIER, '{', 0);
441 parse_error_expected("problem while parsing union type specifier",
442 T_IDENTIFIER, '{', 0);
448 if(compound_type == NULL) {
449 compound_type = allocate_type_zero(sizeof(compound_type[0]));
452 compound_type->type.type = TYPE_COMPOUND_STRUCT;
454 compound_type->type.type = TYPE_COMPOUND_UNION;
456 compound_type->source_position = token.source_position;
457 compound_type->symbol = symbol;
460 if(token.type == '{') {
461 if(compound_type->defined) {
462 parser_print_error_prefix();
463 fprintf(stderr, "multiple definition of %s %s\n",
464 is_struct ? "struct" : "union", symbol->string);
465 compound_type->context.declarations = NULL;
467 compound_type->defined = 1;
469 int top = environment_top();
470 context_t *last_context = context;
471 set_context(&compound_type->context);
473 parse_compound_type_entries();
475 assert(context == &compound_type->context);
476 set_context(last_context);
477 environment_pop_to(top);
480 return (type_t*) compound_type;
483 static void parse_enum_entries(void)
487 if(token.type == '}') {
489 parse_error("empty enum not allowed");
494 declaration_t *entry = allocate_ast_zero(sizeof(entry[0]));
496 if(token.type != T_IDENTIFIER) {
497 parse_error_expected("problem while parsing enum entry",
502 entry->storage_class = STORAGE_CLASS_ENUM_ENTRY;
503 entry->symbol = token.v.symbol;
504 entry->source_position = token.source_position;
507 if(token.type == '=') {
509 entry->initializer = parse_constant_expression();
512 record_declaration(entry);
514 if(token.type != ',')
517 } while(token.type != '}');
522 static enum_type_t *find_enum_type(enum_type_t *types, const symbol_t *symbol)
524 enum_type_t *type = types;
525 for( ; type != NULL; type = type->next) {
526 if(type->symbol == symbol)
533 static type_t *parse_enum_specifier(void)
537 symbol_t *symbol = NULL;
538 enum_type_t *enum_type = NULL;
540 if(token.type == T_IDENTIFIER) {
541 symbol = token.v.symbol;
544 if(context != NULL) {
545 enum_type = find_enum_type(context->enums, symbol);
547 } else if(token.type != '{') {
548 parse_error_expected("problem while parsing enum type specifier",
549 T_IDENTIFIER, '{', 0);
553 if(enum_type == NULL) {
554 enum_type = allocate_type_zero(sizeof(enum_type[0]));
555 enum_type->type.type = TYPE_ENUM;
556 enum_type->source_position = token.source_position;
557 enum_type->symbol = symbol;
560 if(token.type == '{') {
561 if(enum_type->defined) {
562 parser_print_error_prefix();
563 fprintf(stderr, "multiple definitions of enum %s\n",
565 enum_type->entries_begin = NULL;
566 enum_type->entries_end = NULL;
568 enum_type->defined = 1;
570 declaration_t *before = last_declaration;
572 parse_enum_entries();
575 enum_type->entries_begin = context->declarations;
577 enum_type->entries_begin = before->next;
579 enum_type->entries_end = last_declaration;
582 return (type_t*) enum_type;
585 static type_t *parse_typeof(void)
593 declaration_t *declaration;
594 expression_t *expression;
598 case T___extension__:
599 /* this can be a prefix to a typename or an expression */
600 /* we simply eat it now. */
603 } while(token.type == T___extension__);
607 declaration = token.v.symbol->declaration;
608 if(declaration != NULL
609 && declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
610 result = parse_typename();
613 expression = parse_expression();
614 result = expression->datatype;
618 result = parse_typename();
622 expression = parse_expression();
623 result = expression->datatype;
632 static const char *parse_string_literals(void)
634 assert(token.type == T_STRING_LITERAL);
635 const char *result = token.v.string;
639 while(token.type == T_STRING_LITERAL) {
640 result = concat_strings(result, token.v.string);
647 static void parse_attributes(void)
651 case T___attribute__:
659 parse_error("EOF while parsing attribute");
677 if(token.type != T_STRING_LITERAL) {
678 parse_error_expected("while parsing assembler attribute",
683 parse_string_literals();
688 goto attributes_finished;
697 SPECIFIER_SIGNED = 1 << 0,
698 SPECIFIER_UNSIGNED = 1 << 1,
699 SPECIFIER_LONG = 1 << 2,
700 SPECIFIER_INT = 1 << 3,
701 SPECIFIER_DOUBLE = 1 << 4,
702 SPECIFIER_CHAR = 1 << 5,
703 SPECIFIER_SHORT = 1 << 6,
704 SPECIFIER_LONG_LONG = 1 << 7,
705 SPECIFIER_FLOAT = 1 << 8,
706 SPECIFIER_BOOL = 1 << 9,
707 SPECIFIER_VOID = 1 << 10,
708 #ifdef PROVIDE_COMPLEX
709 SPECIFIER_COMPLEX = 1 << 11,
711 #ifdef PROVIDE_IMAGINARY
712 SPECIFIER_IMAGINARY = 1 << 12,
716 static type_t *create_builtin_type(symbol_t *symbol)
718 builtin_type_t *type = allocate_type_zero(sizeof(type[0]));
719 type->type.type = TYPE_BUILTIN;
720 type->symbol = symbol;
722 type_t *result = typehash_insert((type_t*) type);
723 if(result != (type_t*) type) {
724 obstack_free(type_obst, type);
730 static void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
732 declaration_t *declaration;
734 unsigned type_qualifiers = 0;
735 unsigned type_specifiers = 0;
742 #define MATCH_STORAGE_CLASS(token, class) \
744 if(specifiers->storage_class != STORAGE_CLASS_NONE) { \
745 parse_error("multiple storage classes in declaration " \
748 specifiers->storage_class = class; \
752 MATCH_STORAGE_CLASS(T_typedef, STORAGE_CLASS_TYPEDEF)
753 MATCH_STORAGE_CLASS(T_extern, STORAGE_CLASS_EXTERN)
754 MATCH_STORAGE_CLASS(T_static, STORAGE_CLASS_STATIC)
755 MATCH_STORAGE_CLASS(T_auto, STORAGE_CLASS_AUTO)
756 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
758 /* type qualifiers */
759 #define MATCH_TYPE_QUALIFIER(token, qualifier) \
761 type_qualifiers |= qualifier; \
765 MATCH_TYPE_QUALIFIER(T_const, TYPE_QUALIFIER_CONST);
766 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
767 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
768 MATCH_TYPE_QUALIFIER(T_inline, TYPE_QUALIFIER_INLINE);
770 case T___extension__:
775 /* type specifiers */
776 #define MATCH_SPECIFIER(token, specifier, name) \
779 if(type_specifiers & specifier) { \
780 parse_error("multiple " name " type specifiers given"); \
782 type_specifiers |= specifier; \
786 MATCH_SPECIFIER(T_void, SPECIFIER_VOID, "void")
787 MATCH_SPECIFIER(T_char, SPECIFIER_CHAR, "char")
788 MATCH_SPECIFIER(T_short, SPECIFIER_SHORT, "short")
789 MATCH_SPECIFIER(T_int, SPECIFIER_INT, "int")
790 MATCH_SPECIFIER(T_float, SPECIFIER_FLOAT, "float")
791 MATCH_SPECIFIER(T_double, SPECIFIER_DOUBLE, "double")
792 MATCH_SPECIFIER(T_signed, SPECIFIER_SIGNED, "signed")
793 MATCH_SPECIFIER(T_unsigned, SPECIFIER_UNSIGNED, "unsigned")
794 MATCH_SPECIFIER(T__Bool, SPECIFIER_BOOL, "_Bool")
795 #ifdef PROVIDE_COMPLEX
796 MATCH_SPECIFIER(T__Complex, SPECIFIER_COMPLEX, "_Complex")
798 #ifdef PROVIDE_IMAGINARY
799 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
803 if(type_specifiers & SPECIFIER_LONG_LONG) {
804 parse_error("multiple type specifiers given");
805 } else if(type_specifiers & SPECIFIER_LONG) {
806 type_specifiers |= SPECIFIER_LONG_LONG;
808 type_specifiers |= SPECIFIER_LONG;
812 /* TODO: if type != NULL for the following rules issue an error */
814 type = parse_compound_type_specifier(true);
817 type = parse_compound_type_specifier(false);
820 type = parse_enum_specifier();
823 type = parse_typeof();
825 case T___builtin_va_list:
826 type = create_builtin_type(token.v.symbol);
830 case T___attribute__:
836 declaration = token.v.symbol->declaration;
837 if(declaration == NULL ||
838 declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
839 goto finish_specifiers;
842 type = declaration->type;
843 assert(type != NULL);
847 /* function specifier */
849 goto finish_specifiers;
856 atomic_type_type_t atomic_type;
858 /* match valid basic types */
859 switch(type_specifiers) {
861 atomic_type = ATOMIC_TYPE_VOID;
864 atomic_type = ATOMIC_TYPE_CHAR;
866 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
867 atomic_type = ATOMIC_TYPE_SCHAR;
869 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
870 atomic_type = ATOMIC_TYPE_UCHAR;
872 case SPECIFIER_SHORT:
873 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
874 case SPECIFIER_SHORT | SPECIFIER_INT:
875 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
876 atomic_type = ATOMIC_TYPE_SHORT;
878 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
879 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
880 atomic_type = ATOMIC_TYPE_USHORT;
883 case SPECIFIER_SIGNED:
884 case SPECIFIER_SIGNED | SPECIFIER_INT:
885 atomic_type = ATOMIC_TYPE_INT;
887 case SPECIFIER_UNSIGNED:
888 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
889 atomic_type = ATOMIC_TYPE_UINT;
892 case SPECIFIER_SIGNED | SPECIFIER_LONG:
893 case SPECIFIER_LONG | SPECIFIER_INT:
894 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
895 atomic_type = ATOMIC_TYPE_LONG;
897 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
898 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
899 atomic_type = ATOMIC_TYPE_ULONG;
901 case SPECIFIER_LONG | SPECIFIER_LONG_LONG:
902 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
903 case SPECIFIER_LONG | SPECIFIER_LONG_LONG | SPECIFIER_INT:
904 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
906 atomic_type = ATOMIC_TYPE_LONGLONG;
908 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
909 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
911 atomic_type = ATOMIC_TYPE_ULONGLONG;
913 case SPECIFIER_FLOAT:
914 atomic_type = ATOMIC_TYPE_FLOAT;
916 case SPECIFIER_DOUBLE:
917 atomic_type = ATOMIC_TYPE_DOUBLE;
919 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
920 atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
923 atomic_type = ATOMIC_TYPE_BOOL;
925 #ifdef PROVIDE_COMPLEX
926 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
927 atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
929 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
930 atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
932 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
933 atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
936 #ifdef PROVIDE_IMAGINARY
937 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
938 atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
940 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
941 atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
943 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
944 atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
948 /* invalid specifier combination, give an error message */
949 if(type_specifiers == 0) {
950 parse_error("no type specifiers given in declaration");
951 } else if((type_specifiers & SPECIFIER_SIGNED) &&
952 (type_specifiers & SPECIFIER_UNSIGNED)) {
953 parse_error("signed and unsigned specifiers gives");
954 } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
955 parse_error("only integer types can be signed or unsigned");
957 parse_error("multiple datatypes in declaration");
959 atomic_type = ATOMIC_TYPE_INVALID;
962 atomic_type_t *atype = allocate_type_zero(sizeof(atype[0]));
963 atype->type.type = TYPE_ATOMIC;
964 atype->atype = atomic_type;
967 type = (type_t*) atype;
969 if(type_specifiers != 0) {
970 parse_error("multiple datatypes in declaration");
974 type->qualifiers = type_qualifiers;
976 type_t *result = typehash_insert(type);
977 if(newtype && result != (type_t*) type) {
978 obstack_free(type_obst, type);
981 specifiers->type = result;
984 static unsigned parse_type_qualifiers(void)
986 unsigned type_qualifiers = 0;
990 /* type qualifiers */
991 MATCH_TYPE_QUALIFIER(T_const, TYPE_QUALIFIER_CONST);
992 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
993 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
994 MATCH_TYPE_QUALIFIER(T_inline, TYPE_QUALIFIER_INLINE);
997 return type_qualifiers;
1002 typedef struct parsed_pointer_t parsed_pointer_t;
1003 struct parsed_pointer_t {
1004 unsigned type_qualifiers;
1005 parsed_pointer_t *next;
1008 static parsed_pointer_t *parse_pointers(void)
1010 parsed_pointer_t *result = NULL;
1011 parsed_pointer_t *last_pointer = NULL;
1013 while(token.type == '*') {
1015 parsed_pointer_t *pointer
1016 = obstack_alloc(&temp_obst, sizeof(pointer[0]));
1017 pointer->type_qualifiers = parse_type_qualifiers();
1019 if(last_pointer != NULL) {
1020 last_pointer->next = pointer;
1024 last_pointer = pointer;
1030 static type_t *make_pointers(type_t *type, parsed_pointer_t *pointer)
1032 for( ; pointer != NULL; pointer = pointer->next) {
1033 pointer_type_t *pointer_type
1034 = allocate_type_zero(sizeof(pointer_type[0]));
1035 pointer_type->type.type = TYPE_POINTER;
1036 pointer_type->points_to = type;
1037 pointer_type->type.qualifiers = pointer->type_qualifiers;
1039 type_t *result = typehash_insert((type_t*) pointer_type);
1040 if(result != (type_t*) pointer_type) {
1041 obstack_free(type_obst, pointer_type);
1050 static void parse_identifier_list(void)
1053 if(token.type != T_IDENTIFIER) {
1054 parse_error_expected("problem while parsing parameter identifier "
1055 "list", T_IDENTIFIER, 0);
1059 if(token.type != ',')
1065 static declaration_t *parse_parameter(void)
1067 declaration_specifiers_t specifiers;
1068 memset(&specifiers, 0, sizeof(specifiers));
1070 parse_declaration_specifiers(&specifiers);
1072 declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
1073 parse_declarator(declaration, specifiers.storage_class,
1074 specifiers.type, 1);
1079 static declaration_t *parse_parameters(method_type_t *type)
1081 if(token.type == T_IDENTIFIER) {
1082 symbol_t *symbol = token.v.symbol;
1083 declaration_t *declaration = symbol->declaration;
1084 if(declaration == NULL
1085 || declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
1087 parse_identifier_list();
1092 if(token.type == ')') {
1093 type->unspecified_parameters = 1;
1096 if(token.type == T_void && look_ahead(1)->type == ')') {
1101 declaration_t *declarations = NULL;
1102 declaration_t *declaration;
1103 declaration_t *last_declaration = NULL;
1104 method_parameter_t *parameter;
1105 method_parameter_t *last_parameter = NULL;
1108 switch(token.type) {
1112 return declarations;
1115 case T___extension__:
1117 declaration = parse_parameter();
1119 parameter = allocate_type_zero(sizeof(parameter[0]));
1120 parameter->type = declaration->type;
1122 if(last_parameter != NULL) {
1123 last_declaration->next = declaration;
1124 last_parameter->next = parameter;
1126 type->parameters = parameter;
1127 declarations = declaration;
1129 last_parameter = parameter;
1130 last_declaration = declaration;
1134 return declarations;
1136 if(token.type != ',')
1137 return declarations;
1142 typedef struct declarator_part declarator_part;
1143 struct declarator_part {
1144 parsed_pointer_t *pointers;
1145 method_type_t *method_type;
1146 declarator_part *inner;
1150 static declarator_part *parse_inner_declarator(declaration_t *declaration,
1151 int may_be_abstract)
1153 declarator_part *part = obstack_alloc(&temp_obst, sizeof(part[0]));
1154 memset(part, 0, sizeof(part[0]));
1156 part->pointers = parse_pointers();
1158 /* TODO: find out if this is correct */
1161 switch(token.type) {
1163 if(declaration == NULL) {
1164 parse_error("no identifier expected in typename");
1166 declaration->symbol = token.v.symbol;
1167 declaration->source_position = token.source_position;
1173 part->inner = parse_inner_declarator(declaration, may_be_abstract);
1179 parse_error_expected("problem while parsing declarator", T_IDENTIFIER,
1184 switch(token.type) {
1188 method_type_t *method_type
1189 = allocate_type_zero(sizeof(method_type[0]));
1190 method_type->type.type = TYPE_METHOD;
1192 declaration_t *parameters = parse_parameters(method_type);
1193 if(declaration != NULL) {
1194 declaration->context.declarations = parameters;
1197 part->method_type = method_type;
1204 if(token.type == T_static) {
1208 unsigned type_qualifiers = parse_type_qualifiers();
1209 if(type_qualifiers != 0) {
1210 if(token.type == T_static) {
1217 if(token.type == '*' && look_ahead(1)->type == ']') {
1219 } else if(token.type != ']') {
1220 parse_assignment_expression();
1226 goto declarator_finished;
1230 declarator_finished:
1236 static type_t *construct_declarator_type(declarator_part *part, type_t *type)
1239 type = make_pointers(type, part->pointers);
1241 method_type_t *method_type = part->method_type;
1242 if(method_type != NULL) {
1243 method_type->result_type = type;
1245 type_t *result = typehash_insert((type_t*) method_type);
1246 if(result != (type_t*) method_type) {
1247 obstack_free(type_obst, method_type);
1253 } while(part != NULL);
1258 static void parse_declarator(declaration_t *declaration,
1259 storage_class_t storage_class, type_t *type,
1260 int may_be_abstract)
1262 declarator_part *part
1263 = parse_inner_declarator(declaration, may_be_abstract);
1266 declaration->type = construct_declarator_type(part, type);
1267 declaration->storage_class = storage_class;
1268 obstack_free(&temp_obst, part);
1272 static type_t *parse_abstract_declarator(type_t *base_type)
1274 declarator_part *part = parse_inner_declarator(NULL, 1);
1279 type_t *result = construct_declarator_type(part, base_type);
1280 obstack_free(&temp_obst, part);
1285 static declaration_t *record_declaration(declaration_t *declaration)
1290 symbol_t *symbol = declaration->symbol;
1291 if(symbol != NULL) {
1292 declaration_t *alias = environment_push(declaration, context);
1293 if(alias != declaration)
1297 if(last_declaration != NULL) {
1298 last_declaration->next = declaration;
1300 context->declarations = declaration;
1302 last_declaration = declaration;
1307 static void parser_error_multiple_definition(declaration_t *previous,
1308 declaration_t *declaration)
1310 parser_print_error_prefix_pos(declaration->source_position);
1311 fprintf(stderr, "multiple definition of symbol '%s'\n",
1312 declaration->symbol->string);
1313 parser_print_error_prefix_pos(previous->source_position);
1314 fprintf(stderr, "this is the location of the previous "
1318 static void parse_init_declarators(const declaration_specifiers_t *specifiers)
1321 declaration_t *ndeclaration
1322 = allocate_ast_zero(sizeof(ndeclaration[0]));
1324 parse_declarator(ndeclaration, specifiers->storage_class,
1325 specifiers->type, 0);
1326 declaration_t *declaration = record_declaration(ndeclaration);
1327 if(token.type == '=') {
1330 /* TODO: check that this is an allowed type (esp. no method type) */
1332 if(declaration->initializer != NULL) {
1333 parser_error_multiple_definition(declaration, ndeclaration);
1336 if(token.type == '{') {
1340 declaration->initializer = parse_assignment_expression();
1342 } else if(token.type == '{') {
1343 if(declaration->type->type != TYPE_METHOD) {
1344 parser_print_error_prefix();
1345 fprintf(stderr, "Declarator ");
1346 print_type_ext(declaration->type, declaration->symbol, NULL);
1347 fprintf(stderr, " is not a method type.\n");
1350 if(declaration->initializer != NULL) {
1351 parser_error_multiple_definition(declaration, ndeclaration);
1353 if(ndeclaration != declaration) {
1354 memcpy(&declaration->context, &ndeclaration->context,
1355 sizeof(declaration->context));
1358 int top = environment_top();
1359 context_t *last_context = context;
1360 set_context(&declaration->context);
1362 /* push function parameters */
1363 declaration_t *parameter = declaration->context.declarations;
1364 for( ; parameter != NULL; parameter = parameter->next) {
1365 environment_push(parameter, context);
1368 statement_t *statement = parse_compound_statement();
1370 assert(context == &declaration->context);
1371 set_context(last_context);
1372 environment_pop_to(top);
1374 declaration->statement = statement;
1378 if(token.type != ',')
1385 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
1388 if(token.type == ':') {
1390 parse_constant_expression();
1391 /* TODO (bitfields) */
1393 declaration_t *declaration
1394 = allocate_ast_zero(sizeof(declaration[0]));
1395 parse_declarator(declaration, specifiers->storage_class,
1396 specifiers->type, 1);
1398 /* TODO: check for doubled fields */
1399 record_declaration(declaration);
1401 if(token.type == ':') {
1403 parse_constant_expression();
1404 /* TODO (bitfields) */
1408 if(token.type != ',')
1415 static void parse_compound_type_entries(void)
1419 while(token.type != '}' && token.type != T_EOF) {
1420 declaration_specifiers_t specifiers;
1421 memset(&specifiers, 0, sizeof(specifiers));
1422 /* TODO not correct as this allows storage class stuff... but only
1423 * specifiers and qualifiers sould be allowed here */
1424 parse_declaration_specifiers(&specifiers);
1426 parse_struct_declarators(&specifiers);
1428 if(token.type == T_EOF) {
1429 parse_error("unexpected error while parsing struct");
1434 static void parse_declaration(void)
1436 declaration_specifiers_t specifiers;
1437 memset(&specifiers, 0, sizeof(specifiers));
1438 parse_declaration_specifiers(&specifiers);
1440 if(token.type == ';') {
1444 parse_init_declarators(&specifiers);
1447 static type_t *parse_typename(void)
1449 declaration_specifiers_t specifiers;
1450 memset(&specifiers, 0, sizeof(specifiers));
1451 parse_declaration_specifiers(&specifiers);
1452 if(specifiers.storage_class != STORAGE_CLASS_NONE) {
1453 /* TODO: improve error message, user does probably not know what a
1454 * storage class is...
1456 parse_error("typename may not have a storage class");
1459 type_t *result = parse_abstract_declarator(specifiers.type);
1467 typedef expression_t* (*parse_expression_function) (unsigned precedence);
1468 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
1469 expression_t *left);
1471 typedef struct expression_parser_function_t expression_parser_function_t;
1472 struct expression_parser_function_t {
1473 unsigned precedence;
1474 parse_expression_function parser;
1475 unsigned infix_precedence;
1476 parse_expression_infix_function infix_parser;
1479 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
1481 static expression_t *expected_expression_error(void)
1483 parser_print_error_prefix();
1484 fprintf(stderr, "expected expression, got token ");
1485 print_token(stderr, & token);
1486 fprintf(stderr, "\n");
1488 expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
1489 expression->type = EXPR_INVALID;
1495 static expression_t *parse_string_const(void)
1497 string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1499 cnst->expression.type = EXPR_STRING_LITERAL;
1500 cnst->expression.datatype = type_string;
1501 cnst->value = parse_string_literals();
1503 return (expression_t*) cnst;
1506 static expression_t *parse_int_const(void)
1508 const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1510 cnst->expression.type = EXPR_CONST;
1511 cnst->expression.datatype = type_int;
1512 cnst->value = token.v.intvalue;
1516 return (expression_t*) cnst;
1519 static expression_t *parse_reference(void)
1521 reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
1523 ref->expression.type = EXPR_REFERENCE;
1524 ref->symbol = token.v.symbol;
1526 if(ref->symbol->declaration == NULL) {
1527 parser_print_error_prefix();
1528 fprintf(stderr, "unknown symbol '%s' found.\n", ref->symbol->string);
1530 ref->declaration = ref->symbol->declaration;
1531 ref->expression.datatype = ref->declaration->type;
1535 return (expression_t*) ref;
1538 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
1542 /* TODO check if cast is allowed and issue warnings/errors */
1545 static expression_t *parse_cast(void)
1547 unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
1549 cast->expression.type = EXPR_UNARY;
1550 cast->type = UNEXPR_CAST;
1551 cast->expression.source_position = token.source_position;
1553 type_t *type = parse_typename();
1556 expression_t *value = parse_sub_expression(20);
1558 check_cast_allowed(value, type);
1560 cast->expression.datatype = type;
1561 cast->value = value;
1563 return (expression_t*) cast;
1566 static expression_t *parse_statement_expression(void)
1568 statement_expression_t *expression
1569 = allocate_ast_zero(sizeof(expression[0]));
1570 expression->expression.type = EXPR_STATEMENT;
1571 expression->statement = parse_compound_statement();
1573 /* find last statement and use it's type */
1574 const statement_t *last_statement = NULL;
1575 const statement_t *statement = expression->statement;
1576 for( ; statement != NULL; statement = statement->next) {
1577 last_statement = statement;
1580 if(last_statement->type == STATEMENT_EXPRESSION) {
1581 const expression_statement_t *expression_statement =
1582 (const expression_statement_t*) last_statement;
1583 expression->expression.datatype
1584 = expression_statement->expression->datatype;
1586 expression->expression.datatype = type_void;
1591 return (expression_t*) expression;
1594 static expression_t *parse_brace_expression(void)
1598 declaration_t *declaration;
1599 switch(token.type) {
1601 /* gcc extension: a stement expression */
1602 return parse_statement_expression();
1606 return parse_cast();
1608 declaration = token.v.symbol->declaration;
1609 if(declaration != NULL &&
1610 (declaration->storage_class == STORAGE_CLASS_TYPEDEF)) {
1611 return parse_cast();
1615 expression_t *result = parse_expression();
1621 static expression_t *parse_function_keyword(void)
1623 eat(T___FUNCTION__);
1626 string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1627 expression->expression.type = EXPR_FUNCTION;
1628 expression->expression.datatype = type_string;
1629 expression->value = "TODO: FUNCTION";
1631 return (expression_t*) expression;
1634 static expression_t *parse_pretty_function_keyword(void)
1636 eat(T___PRETTY_FUNCTION__);
1639 string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1640 expression->expression.type = EXPR_PRETTY_FUNCTION;
1641 expression->expression.datatype = type_string;
1642 expression->value = "TODO: PRETTY FUNCTION";
1644 return (expression_t*) expression;
1647 static member_designator_t *parse_member_designators(void)
1649 member_designator_t *result = allocate_ast_zero(sizeof(result[0]));
1651 if(token.type != T_IDENTIFIER) {
1652 parse_error_expected("problem while parsing member designator",
1657 result->symbol = token.v.symbol;
1660 member_designator_t *last_designator = result;
1662 if(token.type == '.') {
1664 if(token.type != T_IDENTIFIER) {
1665 parse_error_expected("problem while parsing member designator",
1670 member_designator_t *designator
1671 = allocate_ast_zero(sizeof(result[0]));
1672 designator->symbol = token.v.symbol;
1675 last_designator->next = designator;
1676 last_designator = designator;
1679 if(token.type == '[') {
1681 member_designator_t *designator
1682 = allocate_ast_zero(sizeof(result[0]));
1683 designator->array_access = parse_expression();
1684 if(designator->array_access == NULL) {
1690 last_designator->next = designator;
1691 last_designator = designator;
1700 static expression_t *parse_offsetof(void)
1702 eat(T___builtin_offsetof);
1704 offsetof_expression_t *expression
1705 = allocate_ast_zero(sizeof(expression[0]));
1706 expression->expression.type = EXPR_OFFSETOF;
1707 expression->expression.datatype = type_size_t;
1710 expression->type = parse_typename();
1712 expression->member_designators = parse_member_designators();
1715 return (expression_t*) expression;
1718 static expression_t *parse_builtin_symbol(void)
1720 builtin_symbol_expression_t *expression
1721 = allocate_ast_zero(sizeof(expression[0]));
1722 expression->expression.type = EXPR_BUILTIN_SYMBOL;
1724 /* TODO: set datatype */
1726 expression->symbol = token.v.symbol;
1730 return (expression_t*) expression;
1733 static expression_t *parse_primary_expression(void)
1735 switch(token.type) {
1737 return parse_int_const();
1738 case T_STRING_LITERAL:
1739 return parse_string_const();
1741 return parse_reference();
1742 case T___FUNCTION__:
1743 return parse_function_keyword();
1744 case T___PRETTY_FUNCTION__:
1745 return parse_pretty_function_keyword();
1746 case T___builtin_offsetof:
1747 return parse_offsetof();
1748 case T___builtin_expect:
1749 case T___builtin_va_start:
1750 case T___builtin_va_arg:
1751 case T___builtin_va_end:
1752 return parse_builtin_symbol();
1755 return parse_brace_expression();
1758 parser_print_error_prefix();
1759 fprintf(stderr, "unexpected token ");
1760 print_token(stderr, &token);
1761 fprintf(stderr, "\n");
1766 static expression_t *parse_array_expression(unsigned precedence,
1767 expression_t *array_ref)
1773 array_access_expression_t *array_access
1774 = allocate_ast_zero(sizeof(array_access[0]));
1776 array_access->expression.type = EXPR_ARRAY_ACCESS;
1777 array_access->array_ref = array_ref;
1778 array_access->index = parse_expression();
1780 type_t *array_type = array_ref->datatype;
1781 if(array_type != NULL) {
1782 if(array_type->type == TYPE_POINTER) {
1783 pointer_type_t *pointer = (pointer_type_t*) array_type;
1784 array_access->expression.datatype = pointer->points_to;
1786 parse_error("array access on non-pointer type");
1790 if(token.type != ']') {
1791 parse_error_expected("Problem while parsing array access", ']', 0);
1796 return (expression_t*) array_access;
1799 static bool is_declaration_specifier(const token_t *token,
1800 bool only_type_specifiers)
1802 declaration_t *declaration;
1804 switch(token->type) {
1808 declaration = token->v.symbol->declaration;
1809 if(declaration == NULL)
1811 if(declaration->storage_class != STORAGE_CLASS_TYPEDEF)
1816 if(only_type_specifiers)
1825 static expression_t *parse_sizeof(unsigned precedence)
1829 sizeof_expression_t *sizeof_expression
1830 = allocate_ast_zero(sizeof(sizeof_expression[0]));
1831 sizeof_expression->expression.type = EXPR_SIZEOF;
1832 sizeof_expression->expression.datatype = type_size_t;
1834 if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
1836 sizeof_expression->type = parse_typename();
1839 expression_t *expression = parse_sub_expression(precedence);
1840 sizeof_expression->type = expression->datatype;
1841 sizeof_expression->size_expression = expression;
1844 return (expression_t*) sizeof_expression;
1847 static expression_t *parse_select_expression(unsigned precedence,
1848 expression_t *compound)
1852 assert(token.type == '.' || token.type == T_MINUSGREATER);
1855 select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
1857 select->expression.type = EXPR_SELECT;
1858 select->compound = compound;
1860 /* TODO: datatype */
1862 if(token.type != T_IDENTIFIER) {
1863 parse_error_expected("Problem while parsing select", T_IDENTIFIER, 0);
1866 select->symbol = token.v.symbol;
1869 return (expression_t*) select;
1872 static expression_t *parse_call_expression(unsigned precedence,
1873 expression_t *expression)
1876 call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
1878 call->expression.type = EXPR_CALL;
1879 call->method = expression;
1881 /* parse arguments */
1884 if(token.type != ')') {
1885 call_argument_t *last_argument = NULL;
1888 call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
1890 argument->expression = parse_assignment_expression();
1891 if(last_argument == NULL) {
1892 call->arguments = argument;
1894 last_argument->next = argument;
1896 last_argument = argument;
1898 if(token.type != ',')
1905 type_t *type = expression->datatype;
1906 if(type != NULL && type->type != TYPE_METHOD) {
1907 parser_print_error_prefix();
1908 fprintf(stderr, "expected a method type for call but found type ");
1909 print_type(expression->datatype);
1910 fprintf(stderr, "\n");
1912 method_type_t *method_type = (method_type_t*) type;
1913 call->expression.datatype = method_type->result_type;
1916 return (expression_t*) call;
1919 static void type_error(const char *msg, const source_position_t source_position,
1922 parser_print_error_prefix_pos(source_position);
1923 fprintf(stderr, "%s, but found type ", msg);
1925 fputc('\n', stderr);
1928 static void type_error_incompatible(const char *msg,
1929 const source_position_t source_position, const type_t *type1,
1930 const type_t *type2)
1932 parser_print_error_prefix_pos(source_position);
1933 fprintf(stderr, "%s, incompatible types: ", msg);
1935 fprintf(stderr, " - ");
1937 fprintf(stderr, ")\n");
1940 static type_t *get_type_after_conversion(const type_t *type1,
1941 const type_t *type2)
1945 return (type_t*) type1;
1948 static expression_t *parse_conditional_expression(unsigned precedence,
1949 expression_t *expression)
1953 conditional_expression_t *conditional
1954 = allocate_ast_zero(sizeof(conditional[0]));
1955 conditional->expression.type = EXPR_CONDITIONAL;
1956 conditional->condition = expression;
1959 type_t *condition_type = conditional->condition->datatype;
1960 if(condition_type != NULL) {
1961 if(!is_type_scalar(condition_type)) {
1962 type_error("expected a scalar type", expression->source_position,
1967 conditional->true_expression = parse_expression();
1969 conditional->false_expression = parse_sub_expression(precedence);
1971 type_t *true_type = conditional->true_expression->datatype;
1972 if(true_type == NULL)
1973 return (expression_t*) conditional;
1974 type_t *false_type = conditional->false_expression->datatype;
1975 if(false_type == NULL)
1976 return (expression_t*) conditional;
1979 if(true_type == false_type) {
1980 conditional->expression.datatype = true_type;
1981 } else if(is_type_arithmetic(true_type) && is_type_arithmetic(false_type)) {
1982 type_t *result = get_type_after_conversion(true_type, false_type);
1983 /* TODO: create implicit convs if necessary */
1984 conditional->expression.datatype = result;
1985 } else if(true_type->type == TYPE_POINTER &&
1986 false_type->type == TYPE_POINTER &&
1987 true /* TODO compatible points_to types */) {
1989 } else if(/* (is_null_ptr_const(true_type) && false_type->type == TYPE_POINTER)
1990 || (is_null_ptr_const(false_type) &&
1991 true_type->type == TYPE_POINTER) TODO*/ false) {
1993 } else if(/* 1 is pointer to object type, other is void* */ false) {
1996 type_error_incompatible("problem while parsing conditional",
1997 expression->source_position, true_type,
2001 return (expression_t*) conditional;
2004 static expression_t *parse_extension(unsigned precedence)
2006 eat(T___extension__);
2008 /* TODO enable extensions */
2010 return parse_sub_expression(precedence);
2013 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type) \
2015 expression_t *parse_##unexpression_type(unsigned precedence) \
2019 unary_expression_t *unary_expression \
2020 = allocate_ast_zero(sizeof(unary_expression[0])); \
2021 unary_expression->expression.type = EXPR_UNARY; \
2022 unary_expression->type = unexpression_type; \
2023 unary_expression->value = parse_sub_expression(precedence); \
2025 return (expression_t*) unary_expression; \
2028 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE)
2029 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS)
2030 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT)
2031 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE)
2032 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS)
2033 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE)
2034 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_PREFIX_INCREMENT)
2035 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT)
2037 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
2039 expression_t *parse_##unexpression_type(unsigned precedence, \
2040 expression_t *left) \
2042 (void) precedence; \
2045 unary_expression_t *unary_expression \
2046 = allocate_ast_zero(sizeof(unary_expression[0])); \
2047 unary_expression->expression.type = EXPR_UNARY; \
2048 unary_expression->type = unexpression_type; \
2049 unary_expression->value = left; \
2051 return (expression_t*) unary_expression; \
2054 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_POSTFIX_INCREMENT)
2055 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT)
2057 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type) \
2059 expression_t *parse_##binexpression_type(unsigned precedence, \
2060 expression_t *left) \
2064 expression_t *right = parse_sub_expression(precedence); \
2066 binary_expression_t *binexpr \
2067 = allocate_ast_zero(sizeof(binexpr[0])); \
2068 binexpr->expression.type = EXPR_BINARY; \
2069 binexpr->type = binexpression_type; \
2070 binexpr->left = left; \
2071 binexpr->right = right; \
2073 return (expression_t*) binexpr; \
2076 CREATE_BINEXPR_PARSER(',', BINEXPR_COMMA)
2077 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL)
2078 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV)
2079 CREATE_BINEXPR_PARSER('%', BINEXPR_MOD)
2080 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD)
2081 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB)
2082 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS)
2083 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER)
2084 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN)
2085 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL)
2086 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, BINEXPR_NOTEQUAL)
2087 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL)
2088 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL)
2089 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND)
2090 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR)
2091 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR)
2092 CREATE_BINEXPR_PARSER(T_ANDAND, BINEXPR_LOGICAL_AND)
2093 CREATE_BINEXPR_PARSER(T_PIPEPIPE, BINEXPR_LOGICAL_OR)
2094 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT)
2095 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT)
2096 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, BINEXPR_ADD_ASSIGN)
2097 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, BINEXPR_SUB_ASSIGN)
2098 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, BINEXPR_MUL_ASSIGN)
2099 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_DIV_ASSIGN)
2100 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, BINEXPR_MOD_ASSIGN)
2101 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, BINEXPR_SHIFTLEFT_ASSIGN)
2102 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, BINEXPR_SHIFTRIGHT_ASSIGN)
2103 CREATE_BINEXPR_PARSER(T_ANDEQUAL, BINEXPR_BITWISE_AND_ASSIGN)
2104 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, BINEXPR_BITWISE_OR_ASSIGN)
2105 CREATE_BINEXPR_PARSER(T_CARETEQUAL, BINEXPR_BITWISE_XOR_ASSIGN)
2107 static expression_t *parse_sub_expression(unsigned precedence)
2109 if(token.type < 0) {
2110 return expected_expression_error();
2113 expression_parser_function_t *parser
2114 = &expression_parsers[token.type];
2115 source_position_t source_position = token.source_position;
2118 if(parser->parser != NULL) {
2119 left = parser->parser(parser->precedence);
2121 left = parse_primary_expression();
2123 assert(left != NULL);
2124 assert(left->type != EXPR_INVALID);
2125 left->source_position = source_position;
2128 if(token.type < 0) {
2129 return expected_expression_error();
2132 parser = &expression_parsers[token.type];
2133 if(parser->infix_parser == NULL)
2135 if(parser->infix_precedence < precedence)
2138 left = parser->infix_parser(parser->infix_precedence, left);
2140 assert(left != NULL);
2141 assert(left->type != EXPR_INVALID);
2142 left->source_position = source_position;
2148 static expression_t *parse_expression(void)
2150 return parse_sub_expression(1);
2155 void register_expression_parser(parse_expression_function parser,
2156 int token_type, unsigned precedence)
2158 expression_parser_function_t *entry = &expression_parsers[token_type];
2160 if(entry->parser != NULL) {
2161 fprintf(stderr, "for token ");
2162 print_token_type(stderr, token_type);
2163 fprintf(stderr, "\n");
2164 panic("trying to register multiple expression parsers for a token");
2166 entry->parser = parser;
2167 entry->precedence = precedence;
2170 void register_expression_infix_parser(parse_expression_infix_function parser,
2171 int token_type, unsigned precedence)
2173 expression_parser_function_t *entry = &expression_parsers[token_type];
2175 if(entry->infix_parser != NULL) {
2176 fprintf(stderr, "for token ");
2177 print_token_type(stderr, token_type);
2178 fprintf(stderr, "\n");
2179 panic("trying to register multiple infix expression parsers for a "
2182 entry->infix_parser = parser;
2183 entry->infix_precedence = precedence;
2186 static void init_expression_parsers(void)
2188 memset(&expression_parsers, 0, sizeof(expression_parsers));
2190 register_expression_infix_parser(parse_BINEXPR_MUL, '*', 16);
2191 register_expression_infix_parser(parse_BINEXPR_DIV, '/', 16);
2192 register_expression_infix_parser(parse_BINEXPR_MOD, '%', 16);
2193 register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT, T_LESSLESS, 16);
2194 register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
2195 T_GREATERGREATER, 16);
2196 register_expression_infix_parser(parse_BINEXPR_ADD, '+', 15);
2197 register_expression_infix_parser(parse_BINEXPR_SUB, '-', 15);
2198 register_expression_infix_parser(parse_BINEXPR_LESS, '<', 14);
2199 register_expression_infix_parser(parse_BINEXPR_GREATER, '>', 14);
2200 register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL, 14);
2201 register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
2202 T_GREATEREQUAL, 14);
2203 register_expression_infix_parser(parse_BINEXPR_EQUAL, T_EQUALEQUAL, 13);
2204 register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
2205 T_EXCLAMATIONMARKEQUAL, 13);
2206 register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&', 12);
2207 register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^', 11);
2208 register_expression_infix_parser(parse_BINEXPR_BITWISE_OR, '|', 10);
2209 register_expression_infix_parser(parse_BINEXPR_LOGICAL_AND, T_ANDAND, 9);
2210 register_expression_infix_parser(parse_BINEXPR_LOGICAL_OR, T_PIPEPIPE, 8);
2211 register_expression_infix_parser(parse_conditional_expression, '?', 7);
2212 register_expression_infix_parser(parse_BINEXPR_ASSIGN, '=', 2);
2213 register_expression_infix_parser(parse_BINEXPR_ADD_ASSIGN, T_PLUSEQUAL, 2);
2214 register_expression_infix_parser(parse_BINEXPR_SUB_ASSIGN, T_MINUSEQUAL, 2);
2215 register_expression_infix_parser(parse_BINEXPR_MUL_ASSIGN,
2216 T_ASTERISKEQUAL, 2);
2217 register_expression_infix_parser(parse_BINEXPR_DIV_ASSIGN, T_SLASHEQUAL, 2);
2218 register_expression_infix_parser(parse_BINEXPR_MOD_ASSIGN,
2220 register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT_ASSIGN,
2221 T_LESSLESSEQUAL, 2);
2222 register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT_ASSIGN,
2223 T_GREATERGREATEREQUAL, 2);
2224 register_expression_infix_parser(parse_BINEXPR_BITWISE_AND_ASSIGN,
2226 register_expression_infix_parser(parse_BINEXPR_BITWISE_OR_ASSIGN,
2228 register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR_ASSIGN,
2231 register_expression_infix_parser(parse_BINEXPR_COMMA, ',', 1);
2233 register_expression_infix_parser(parse_array_expression, '[', 30);
2234 register_expression_infix_parser(parse_call_expression, '(', 30);
2235 register_expression_infix_parser(parse_select_expression, '.', 30);
2236 register_expression_infix_parser(parse_select_expression,
2237 T_MINUSGREATER, 30);
2238 register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
2240 register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
2243 register_expression_parser(parse_UNEXPR_NEGATE, '-', 25);
2244 register_expression_parser(parse_UNEXPR_PLUS, '+', 25);
2245 register_expression_parser(parse_UNEXPR_NOT, '!', 25);
2246 register_expression_parser(parse_UNEXPR_BITWISE_NEGATE, '~', 25);
2247 register_expression_parser(parse_UNEXPR_DEREFERENCE, '*', 25);
2248 register_expression_parser(parse_UNEXPR_TAKE_ADDRESS, '&', 25);
2249 register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS, 25);
2250 register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
2251 register_expression_parser(parse_sizeof, T_sizeof, 25);
2252 register_expression_parser(parse_extension, T___extension__, 25);
2256 static statement_t *parse_case_statement(void)
2259 case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2260 label->statement.type = STATEMENT_CASE_LABEL;
2261 label->statement.source_position = token.source_position;
2263 label->expression = parse_expression();
2266 label->statement.next = parse_statement();
2268 return (statement_t*) label;
2271 static statement_t *parse_default_statement(void)
2275 case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2276 label->statement.type = STATEMENT_CASE_LABEL;
2277 label->statement.source_position = token.source_position;
2280 label->statement.next = parse_statement();
2282 return (statement_t*) label;
2285 static statement_t *parse_label_statement(void)
2294 static statement_t *parse_if(void)
2298 if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2299 statement->statement.type = STATEMENT_IF;
2300 statement->statement.source_position = token.source_position;
2303 statement->condition = parse_expression();
2306 statement->true_statement = parse_statement();
2307 if(token.type == T_else) {
2309 statement->false_statement = parse_statement();
2312 return (statement_t*) statement;
2315 static statement_t *parse_switch(void)
2319 switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2320 statement->statement.type = STATEMENT_SWITCH;
2321 statement->statement.source_position = token.source_position;
2324 statement->expression = parse_expression();
2326 statement->body = parse_statement();
2328 return (statement_t*) statement;
2331 static statement_t *parse_while(void)
2335 while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2336 statement->statement.type = STATEMENT_WHILE;
2337 statement->statement.source_position = token.source_position;
2340 statement->condition = parse_expression();
2342 statement->body = parse_statement();
2344 return (statement_t*) statement;
2347 static statement_t *parse_do(void)
2351 do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2352 statement->statement.type = STATEMENT_DO_WHILE;
2353 statement->statement.source_position = token.source_position;
2355 statement->body = parse_statement();
2358 statement->condition = parse_expression();
2362 return (statement_t*) statement;
2365 static statement_t *parse_for(void)
2369 for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2370 statement->statement.type = STATEMENT_FOR;
2371 statement->statement.source_position = token.source_position;
2375 int top = environment_top();
2376 context_t *last_context = context;
2377 set_context(&statement->context);
2379 if(token.type != ';') {
2380 if(is_declaration_specifier(&token, false)) {
2381 parse_declaration();
2383 statement->initialisation = parse_expression();
2390 if(token.type != ';') {
2391 statement->condition = parse_expression();
2394 if(token.type != ')') {
2395 statement->step = parse_expression();
2398 statement->body = parse_statement();
2400 assert(context == &statement->context);
2401 set_context(last_context);
2402 environment_pop_to(top);
2404 return (statement_t*) statement;
2407 static statement_t *parse_goto(void)
2410 expect(T_IDENTIFIER);
2416 static statement_t *parse_continue(void)
2421 statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2422 statement->source_position = token.source_position;
2423 statement->type = STATEMENT_CONTINUE;
2428 static statement_t *parse_break(void)
2433 statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2434 statement->source_position = token.source_position;
2435 statement->type = STATEMENT_BREAK;
2440 static statement_t *parse_return(void)
2444 return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2446 statement->statement.type = STATEMENT_RETURN;
2447 statement->statement.source_position = token.source_position;
2448 if(token.type != ';') {
2449 statement->return_value = parse_expression();
2453 return (statement_t*) statement;
2456 static statement_t *parse_declaration_statement(void)
2458 declaration_t *before = last_declaration;
2460 declaration_statement_t *statement
2461 = allocate_ast_zero(sizeof(statement[0]));
2462 statement->statement.type = STATEMENT_DECLARATION;
2463 statement->statement.source_position = token.source_position;
2465 declaration_specifiers_t specifiers;
2466 memset(&specifiers, 0, sizeof(specifiers));
2467 parse_declaration_specifiers(&specifiers);
2469 if(token.type == ';') {
2472 parse_init_declarators(&specifiers);
2475 if(before == NULL) {
2476 statement->declarations_begin = context->declarations;
2478 statement->declarations_begin = before->next;
2480 statement->declarations_end = last_declaration;
2482 return (statement_t*) statement;
2485 static statement_t *parse_expression_statement(void)
2487 expression_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2488 statement->statement.type = STATEMENT_EXPRESSION;
2489 statement->statement.source_position = token.source_position;
2491 statement->expression = parse_expression();
2495 return (statement_t*) statement;
2498 static statement_t *parse_statement(void)
2500 declaration_t *declaration;
2501 statement_t *statement = NULL;
2503 /* declaration or statement */
2504 switch(token.type) {
2506 statement = parse_case_statement();
2510 statement = parse_default_statement();
2514 statement = parse_compound_statement();
2518 statement = parse_if();
2522 statement = parse_switch();
2526 statement = parse_while();
2530 statement = parse_do();
2534 statement = parse_for();
2538 statement = parse_goto();
2542 statement = parse_continue();
2546 statement = parse_break();
2550 statement = parse_return();
2559 if(look_ahead(1)->type == ':') {
2560 statement = parse_label_statement();
2564 declaration = token.v.symbol->declaration;
2565 if(declaration != NULL &&
2566 declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
2567 statement = parse_declaration_statement();
2571 statement = parse_expression_statement();
2574 case T___extension__:
2575 /* this can be a prefix to a declaration or an expression statement */
2576 /* we simply eat it now and parse the rest with tail recursion */
2579 } while(token.type == T___extension__);
2580 statement = parse_statement();
2584 statement = parse_declaration_statement();
2588 statement = parse_expression_statement();
2592 assert(statement == NULL || statement->source_position.input_name != NULL);
2597 static statement_t *parse_compound_statement(void)
2601 compound_statement_t *compound_statement
2602 = allocate_ast_zero(sizeof(compound_statement[0]));
2603 compound_statement->statement.type = STATEMENT_COMPOUND;
2604 compound_statement->statement.source_position = token.source_position;
2606 int top = environment_top();
2607 context_t *last_context = context;
2608 set_context(&compound_statement->context);
2610 statement_t *last_statement = NULL;
2612 while(token.type != '}' && token.type != T_EOF) {
2613 statement_t *statement = parse_statement();
2614 if(statement == NULL)
2617 if(last_statement != NULL) {
2618 last_statement->next = statement;
2620 compound_statement->statements = statement;
2623 while(statement->next != NULL)
2624 statement = statement->next;
2626 last_statement = statement;
2629 assert(context == &compound_statement->context);
2630 set_context(last_context);
2631 environment_pop_to(top);
2635 return (statement_t*) compound_statement;
2638 static translation_unit_t *parse_translation_unit(void)
2640 translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
2642 assert(context == NULL);
2643 set_context(&unit->context);
2645 while(token.type != T_EOF) {
2646 parse_declaration();
2649 assert(context == &unit->context);
2651 last_declaration = NULL;
2656 translation_unit_t *parse(void)
2658 obstack_init(&environment_obstack);
2659 environment_stack = NEW_ARR_F(environment_entry_t*, 0);
2661 type_set_output(stderr);
2663 lookahead_bufpos = 0;
2664 for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
2667 translation_unit_t *unit = parse_translation_unit();
2669 DEL_ARR_F(environment_stack);
2670 obstack_free(&environment_obstack, NULL);
2675 void init_parser(void)
2677 init_expression_parsers();
2678 obstack_init(&temp_obst);
2680 type_int = make_atomic_type(ATOMIC_TYPE_INT, 0);
2681 type_size_t = make_atomic_type(ATOMIC_TYPE_UINT, 0);
2682 type_const_char = make_atomic_type(ATOMIC_TYPE_CHAR, TYPE_QUALIFIER_CONST);
2683 type_void = make_atomic_type(ATOMIC_TYPE_VOID, 0);
2684 type_string = make_pointer_type(type_const_char, 0);
2687 void exit_parser(void)
2689 obstack_free(&temp_obst, NULL);