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 symbol_t *symbol = declaration->symbol;
306 assert(declaration != symbol->declaration);
307 assert(declaration->source_position.input_name != NULL);
309 if(symbol->context == context) {
310 declaration_t *previous_declaration = symbol->declaration;
311 if(symbol->declaration != NULL) {
312 if(!is_compatible_declaration(declaration, previous_declaration)) {
313 parser_print_error_prefix_pos(declaration->source_position);
314 fprintf(stderr, "definition of symbol '%s' with type ",
315 declaration->symbol->string);
316 print_type(declaration->type);
318 parser_print_error_prefix_pos(
319 previous_declaration->source_position);
320 fprintf(stderr, "is incompatible with previous declaration "
322 print_type(previous_declaration->type);
325 return previous_declaration;
329 environment_entry_t *entry
330 = obstack_alloc(&environment_obstack, sizeof(entry[0]));
331 memset(entry, 0, sizeof(entry[0]));
333 int top = ARR_LEN(environment_stack);
334 ARR_RESIZE(environment_stack, top + 1);
335 environment_stack[top] = entry;
337 entry->old_declaration = symbol->declaration;
338 entry->old_context = symbol->context;
339 entry->symbol = symbol;
340 symbol->declaration = declaration;
341 symbol->context = context;
347 * pops symbols from the environment stack until @p new_top is the top element
349 static inline void environment_pop_to(size_t new_top)
351 environment_entry_t *entry = NULL;
352 size_t top = ARR_LEN(environment_stack);
358 assert(new_top < top);
361 entry = environment_stack[i - 1];
363 symbol_t *symbol = entry->symbol;
365 symbol->declaration = entry->old_declaration;
366 symbol->context = entry->old_context;
369 } while(i != new_top);
370 obstack_free(&environment_obstack, entry);
372 ARR_SHRINKLEN(environment_stack, (int) new_top);
377 static expression_t *parse_constant_expression(void)
379 /* start parsing at precedence 7 (conditional expression) */
380 return parse_sub_expression(7);
383 static expression_t *parse_assignment_expression(void)
385 /* start parsing at precedence 2 (assignment expression) */
386 return parse_sub_expression(2);
389 static void parse_compound_type_entries(void);
390 static void parse_declarator(declaration_t *declaration,
391 storage_class_t storage_class, type_t *type,
392 int may_be_abstract);
393 static declaration_t *record_declaration(declaration_t *declaration);
395 typedef struct declaration_specifiers_t declaration_specifiers_t;
396 struct declaration_specifiers_t {
397 storage_class_t storage_class;
401 static compound_type_t *find_compound_type(compound_type_t *types,
402 const symbol_t *symbol)
404 compound_type_t *type = types;
405 for( ; type != NULL; type = type->next) {
406 if(type->symbol == symbol)
413 static type_t *parse_compound_type_specifier(bool is_struct)
421 symbol_t *symbol = NULL;
422 compound_type_t *compound_type = NULL;
424 if(token.type == T_IDENTIFIER) {
425 symbol = token.v.symbol;
428 if(context != NULL) {
430 compound_type = find_compound_type(context->structs, symbol);
432 compound_type = find_compound_type(context->unions, symbol);
435 } else if(token.type != '{') {
437 parse_error_expected("problem while parsing struct type specifier",
438 T_IDENTIFIER, '{', 0);
440 parse_error_expected("problem while parsing union type specifier",
441 T_IDENTIFIER, '{', 0);
447 if(compound_type == NULL) {
448 compound_type = allocate_type_zero(sizeof(compound_type[0]));
451 compound_type->type.type = TYPE_COMPOUND_STRUCT;
453 compound_type->type.type = TYPE_COMPOUND_UNION;
455 compound_type->source_position = token.source_position;
456 compound_type->symbol = symbol;
459 if(token.type == '{') {
460 if(compound_type->defined) {
461 parser_print_error_prefix();
462 fprintf(stderr, "multiple definition of %s %s\n",
463 is_struct ? "struct" : "union", symbol->string);
464 compound_type->context.declarations = NULL;
466 compound_type->defined = 1;
468 int top = environment_top();
469 context_t *last_context = context;
470 set_context(&compound_type->context);
472 parse_compound_type_entries();
474 assert(context == &compound_type->context);
475 set_context(last_context);
476 environment_pop_to(top);
479 return (type_t*) compound_type;
482 static void parse_enum_entries(void)
486 if(token.type == '}') {
488 parse_error("empty enum not allowed");
493 declaration_t *entry = allocate_ast_zero(sizeof(entry[0]));
495 if(token.type != T_IDENTIFIER) {
496 parse_error_expected("problem while parsing enum entry",
501 entry->storage_class = STORAGE_CLASS_ENUM_ENTRY;
502 entry->symbol = token.v.symbol;
503 entry->source_position = token.source_position;
506 if(token.type == '=') {
508 entry->initializer = parse_constant_expression();
511 record_declaration(entry);
513 if(token.type != ',')
516 } while(token.type != '}');
521 static enum_type_t *find_enum_type(enum_type_t *types, const symbol_t *symbol)
523 enum_type_t *type = types;
524 for( ; type != NULL; type = type->next) {
525 if(type->symbol == symbol)
532 static type_t *parse_enum_specifier(void)
536 symbol_t *symbol = NULL;
537 enum_type_t *enum_type = NULL;
539 if(token.type == T_IDENTIFIER) {
540 symbol = token.v.symbol;
543 if(context != NULL) {
544 enum_type = find_enum_type(context->enums, symbol);
546 } else if(token.type != '{') {
547 parse_error_expected("problem while parsing enum type specifier",
548 T_IDENTIFIER, '{', 0);
552 if(enum_type == NULL) {
553 enum_type = allocate_type_zero(sizeof(enum_type[0]));
554 enum_type->type.type = TYPE_ENUM;
555 enum_type->source_position = token.source_position;
556 enum_type->symbol = symbol;
559 if(token.type == '{') {
560 if(enum_type->defined) {
561 parser_print_error_prefix();
562 fprintf(stderr, "multiple definitions of enum %s\n",
564 enum_type->entries_begin = NULL;
565 enum_type->entries_end = NULL;
567 enum_type->defined = 1;
569 declaration_t *before = last_declaration;
571 parse_enum_entries();
574 enum_type->entries_begin = context->declarations;
576 enum_type->entries_begin = before->next;
578 enum_type->entries_end = last_declaration;
581 return (type_t*) enum_type;
584 static type_t *parse_typeof(void)
592 declaration_t *declaration;
593 expression_t *expression;
597 case T___extension__:
598 /* this can be a prefix to a typename or an expression */
599 /* we simply eat it now. */
602 } while(token.type == T___extension__);
606 declaration = token.v.symbol->declaration;
607 if(declaration != NULL
608 && declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
609 result = parse_typename();
612 expression = parse_expression();
613 result = expression->datatype;
617 result = parse_typename();
621 expression = parse_expression();
622 result = expression->datatype;
631 static const char *parse_string_literals(void)
633 assert(token.type == T_STRING_LITERAL);
634 const char *result = token.v.string;
638 while(token.type == T_STRING_LITERAL) {
639 result = concat_strings(result, token.v.string);
646 static void parse_attributes(void)
650 case T___attribute__:
658 parse_error("EOF while parsing attribute");
676 if(token.type != T_STRING_LITERAL) {
677 parse_error_expected("while parsing assembler attribute",
682 parse_string_literals();
687 goto attributes_finished;
696 SPECIFIER_SIGNED = 1 << 0,
697 SPECIFIER_UNSIGNED = 1 << 1,
698 SPECIFIER_LONG = 1 << 2,
699 SPECIFIER_INT = 1 << 3,
700 SPECIFIER_DOUBLE = 1 << 4,
701 SPECIFIER_CHAR = 1 << 5,
702 SPECIFIER_SHORT = 1 << 6,
703 SPECIFIER_LONG_LONG = 1 << 7,
704 SPECIFIER_FLOAT = 1 << 8,
705 SPECIFIER_BOOL = 1 << 9,
706 SPECIFIER_VOID = 1 << 10,
707 #ifdef PROVIDE_COMPLEX
708 SPECIFIER_COMPLEX = 1 << 11,
710 #ifdef PROVIDE_IMAGINARY
711 SPECIFIER_IMAGINARY = 1 << 12,
715 static type_t *create_builtin_type(symbol_t *symbol)
717 builtin_type_t *type = allocate_type_zero(sizeof(type[0]));
718 type->type.type = TYPE_BUILTIN;
719 type->symbol = symbol;
721 type_t *result = typehash_insert((type_t*) type);
722 if(result != (type_t*) type) {
723 obstack_free(type_obst, type);
729 static void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
731 declaration_t *declaration;
733 unsigned type_qualifiers = 0;
734 unsigned type_specifiers = 0;
741 #define MATCH_STORAGE_CLASS(token, class) \
743 if(specifiers->storage_class != STORAGE_CLASS_NONE) { \
744 parse_error("multiple storage classes in declaration " \
747 specifiers->storage_class = class; \
751 MATCH_STORAGE_CLASS(T_typedef, STORAGE_CLASS_TYPEDEF)
752 MATCH_STORAGE_CLASS(T_extern, STORAGE_CLASS_EXTERN)
753 MATCH_STORAGE_CLASS(T_static, STORAGE_CLASS_STATIC)
754 MATCH_STORAGE_CLASS(T_auto, STORAGE_CLASS_AUTO)
755 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
757 /* type qualifiers */
758 #define MATCH_TYPE_QUALIFIER(token, qualifier) \
760 type_qualifiers |= qualifier; \
764 MATCH_TYPE_QUALIFIER(T_const, TYPE_QUALIFIER_CONST);
765 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
766 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
767 MATCH_TYPE_QUALIFIER(T_inline, TYPE_QUALIFIER_INLINE);
769 case T___extension__:
774 /* type specifiers */
775 #define MATCH_SPECIFIER(token, specifier, name) \
778 if(type_specifiers & specifier) { \
779 parse_error("multiple " name " type specifiers given"); \
781 type_specifiers |= specifier; \
785 MATCH_SPECIFIER(T_void, SPECIFIER_VOID, "void")
786 MATCH_SPECIFIER(T_char, SPECIFIER_CHAR, "char")
787 MATCH_SPECIFIER(T_short, SPECIFIER_SHORT, "short")
788 MATCH_SPECIFIER(T_int, SPECIFIER_INT, "int")
789 MATCH_SPECIFIER(T_float, SPECIFIER_FLOAT, "float")
790 MATCH_SPECIFIER(T_double, SPECIFIER_DOUBLE, "double")
791 MATCH_SPECIFIER(T_signed, SPECIFIER_SIGNED, "signed")
792 MATCH_SPECIFIER(T_unsigned, SPECIFIER_UNSIGNED, "unsigned")
793 MATCH_SPECIFIER(T__Bool, SPECIFIER_BOOL, "_Bool")
794 #ifdef PROVIDE_COMPLEX
795 MATCH_SPECIFIER(T__Complex, SPECIFIER_COMPLEX, "_Complex")
797 #ifdef PROVIDE_IMAGINARY
798 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
802 if(type_specifiers & SPECIFIER_LONG_LONG) {
803 parse_error("multiple type specifiers given");
804 } else if(type_specifiers & SPECIFIER_LONG) {
805 type_specifiers |= SPECIFIER_LONG_LONG;
807 type_specifiers |= SPECIFIER_LONG;
811 /* TODO: if type != NULL for the following rules issue an error */
813 type = parse_compound_type_specifier(true);
816 type = parse_compound_type_specifier(false);
819 type = parse_enum_specifier();
822 type = parse_typeof();
824 case T___builtin_va_list:
825 type = create_builtin_type(token.v.symbol);
829 case T___attribute__:
835 declaration = token.v.symbol->declaration;
836 if(declaration == NULL ||
837 declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
838 goto finish_specifiers;
841 type = declaration->type;
842 assert(type != NULL);
846 /* function specifier */
848 goto finish_specifiers;
855 atomic_type_type_t atomic_type;
857 /* match valid basic types */
858 switch(type_specifiers) {
860 atomic_type = ATOMIC_TYPE_VOID;
863 atomic_type = ATOMIC_TYPE_CHAR;
865 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
866 atomic_type = ATOMIC_TYPE_SCHAR;
868 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
869 atomic_type = ATOMIC_TYPE_UCHAR;
871 case SPECIFIER_SHORT:
872 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
873 case SPECIFIER_SHORT | SPECIFIER_INT:
874 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
875 atomic_type = ATOMIC_TYPE_SHORT;
877 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
878 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
879 atomic_type = ATOMIC_TYPE_USHORT;
882 case SPECIFIER_SIGNED:
883 case SPECIFIER_SIGNED | SPECIFIER_INT:
884 atomic_type = ATOMIC_TYPE_INT;
886 case SPECIFIER_UNSIGNED:
887 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
888 atomic_type = ATOMIC_TYPE_UINT;
891 case SPECIFIER_SIGNED | SPECIFIER_LONG:
892 case SPECIFIER_LONG | SPECIFIER_INT:
893 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
894 atomic_type = ATOMIC_TYPE_LONG;
896 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
897 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
898 atomic_type = ATOMIC_TYPE_ULONG;
900 case SPECIFIER_LONG | SPECIFIER_LONG_LONG:
901 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
902 case SPECIFIER_LONG | SPECIFIER_LONG_LONG | SPECIFIER_INT:
903 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
905 atomic_type = ATOMIC_TYPE_LONGLONG;
907 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
908 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
910 atomic_type = ATOMIC_TYPE_ULONGLONG;
912 case SPECIFIER_FLOAT:
913 atomic_type = ATOMIC_TYPE_FLOAT;
915 case SPECIFIER_DOUBLE:
916 atomic_type = ATOMIC_TYPE_DOUBLE;
918 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
919 atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
922 atomic_type = ATOMIC_TYPE_BOOL;
924 #ifdef PROVIDE_COMPLEX
925 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
926 atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
928 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
929 atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
931 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
932 atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
935 #ifdef PROVIDE_IMAGINARY
936 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
937 atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
939 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
940 atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
942 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
943 atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
947 /* invalid specifier combination, give an error message */
948 if(type_specifiers == 0) {
949 parse_error("no type specifiers given in declaration");
950 } else if((type_specifiers & SPECIFIER_SIGNED) &&
951 (type_specifiers & SPECIFIER_UNSIGNED)) {
952 parse_error("signed and unsigned specifiers gives");
953 } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
954 parse_error("only integer types can be signed or unsigned");
956 parse_error("multiple datatypes in declaration");
958 atomic_type = ATOMIC_TYPE_INVALID;
961 atomic_type_t *atype = allocate_type_zero(sizeof(atype[0]));
962 atype->type.type = TYPE_ATOMIC;
963 atype->atype = atomic_type;
966 type = (type_t*) atype;
968 if(type_specifiers != 0) {
969 parse_error("multiple datatypes in declaration");
973 type->qualifiers = type_qualifiers;
975 type_t *result = typehash_insert(type);
976 if(newtype && result != (type_t*) type) {
977 obstack_free(type_obst, type);
980 specifiers->type = result;
983 static type_qualifier_t parse_type_qualifiers(void)
985 type_qualifier_t type_qualifiers = 0;
989 /* type qualifiers */
990 MATCH_TYPE_QUALIFIER(T_const, TYPE_QUALIFIER_CONST);
991 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
992 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
993 MATCH_TYPE_QUALIFIER(T_inline, TYPE_QUALIFIER_INLINE);
996 return type_qualifiers;
1001 static void parse_identifier_list(void)
1004 if(token.type != T_IDENTIFIER) {
1005 parse_error_expected("problem while parsing parameter identifier "
1006 "list", T_IDENTIFIER, 0);
1010 if(token.type != ',')
1016 static declaration_t *parse_parameter(void)
1018 declaration_specifiers_t specifiers;
1019 memset(&specifiers, 0, sizeof(specifiers));
1021 parse_declaration_specifiers(&specifiers);
1023 declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
1024 parse_declarator(declaration, specifiers.storage_class,
1025 specifiers.type, 1);
1030 static declaration_t *parse_parameters(method_type_t *type)
1032 if(token.type == T_IDENTIFIER) {
1033 symbol_t *symbol = token.v.symbol;
1034 declaration_t *declaration = symbol->declaration;
1035 if(declaration == NULL
1036 || declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
1038 parse_identifier_list();
1043 if(token.type == ')') {
1044 type->unspecified_parameters = 1;
1047 if(token.type == T_void && look_ahead(1)->type == ')') {
1052 declaration_t *declarations = NULL;
1053 declaration_t *declaration;
1054 declaration_t *last_declaration = NULL;
1055 method_parameter_t *parameter;
1056 method_parameter_t *last_parameter = NULL;
1059 switch(token.type) {
1063 return declarations;
1066 case T___extension__:
1068 declaration = parse_parameter();
1070 parameter = allocate_type_zero(sizeof(parameter[0]));
1071 parameter->type = declaration->type;
1073 if(last_parameter != NULL) {
1074 last_declaration->next = declaration;
1075 last_parameter->next = parameter;
1077 type->parameters = parameter;
1078 declarations = declaration;
1080 last_parameter = parameter;
1081 last_declaration = declaration;
1085 return declarations;
1087 if(token.type != ',')
1088 return declarations;
1097 } construct_type_type_t;
1099 typedef struct construct_type_t construct_type_t;
1100 struct construct_type_t {
1101 construct_type_type_t type;
1102 construct_type_t *next;
1105 typedef struct parsed_pointer_t parsed_pointer_t;
1106 struct parsed_pointer_t {
1107 construct_type_t construct_type;
1108 type_qualifier_t type_qualifiers;
1111 typedef struct construct_method_type_t construct_method_type_t;
1112 struct construct_method_type_t {
1113 construct_type_t construct_type;
1114 method_type_t *method_type;
1117 typedef struct parsed_array_t parsed_array_t;
1118 struct parsed_array_t {
1119 construct_type_t construct_type;
1120 type_qualifier_t type_qualifiers;
1126 typedef struct construct_base_type_t construct_base_type_t;
1127 struct construct_base_type_t {
1128 construct_type_t construct_type;
1132 static construct_type_t *parse_pointer_declarator(void)
1136 parsed_pointer_t *pointer = obstack_alloc(&temp_obst, sizeof(pointer[0]));
1137 memset(pointer, 0, sizeof(pointer[0]));
1138 pointer->type_qualifiers = parse_type_qualifiers();
1140 return (construct_type_t*) pointer;
1143 static construct_type_t *parse_array_declarator(void)
1147 parsed_array_t *array = obstack_alloc(&temp_obst, sizeof(array[0]));
1148 memset(array, 0, sizeof(array[0]));
1150 if(token.type == T_static) {
1151 array->is_static = true;
1155 type_qualifier_t type_qualifiers = parse_type_qualifiers();
1156 if(type_qualifiers != 0) {
1157 if(token.type == T_static) {
1158 array->is_static = true;
1162 array->type_qualifiers = type_qualifiers;
1164 if(token.type == '*' && look_ahead(1)->type == ']') {
1165 array->is_variable = true;
1167 } else if(token.type != ']') {
1168 array->size = parse_assignment_expression();
1173 return (construct_type_t*) array;
1176 static construct_type_t *parse_method_declarator(declaration_t *declaration)
1180 method_type_t *method_type
1181 = allocate_type_zero(sizeof(method_type[0]));
1182 method_type->type.type = TYPE_METHOD;
1184 declaration_t *parameters = parse_parameters(method_type);
1185 if(declaration != NULL) {
1186 declaration->context.declarations = parameters;
1189 construct_method_type_t *construct_method_type =
1190 obstack_alloc(&temp_obst, sizeof(construct_method_type[0]));
1191 memset(construct_method_type, 0, sizeof(construct_method_type[0]));
1192 construct_method_type->construct_type.type = CONSTRUCT_METHOD;
1193 construct_method_type->method_type = method_type;
1197 return (construct_type_t*) construct_method_type;
1200 static construct_type_t *parse_inner_declarator(declaration_t *declaration,
1201 int may_be_abstract)
1203 construct_type_t *result = NULL;
1204 construct_type_t *last = NULL;
1206 while(token.type == '*') {
1207 construct_type_t *type = parse_pointer_declarator();
1216 /* TODO: find out if this is correct */
1219 construct_type_t *inner_types = NULL;
1221 switch(token.type) {
1223 if(declaration == NULL) {
1224 parse_error("no identifier expected in typename");
1226 declaration->symbol = token.v.symbol;
1227 declaration->source_position = token.source_position;
1233 inner_types = parse_inner_declarator(declaration, may_be_abstract);
1239 parse_error_expected("problem while parsing declarator", T_IDENTIFIER,
1244 construct_type_t *type;
1245 switch(token.type) {
1247 type = parse_method_declarator(declaration);
1250 type = parse_array_declarator();
1253 goto declarator_finished;
1264 declarator_finished:
1267 if(inner_types != NULL) {
1269 last->next = inner_types;
1271 result = inner_types;
1280 static type_t *make_pointers(type_t *type, parsed_pointer_t *pointer)
1282 for( ; pointer != NULL; pointer = pointer->next) {
1283 pointer_type_t *pointer_type
1284 = allocate_type_zero(sizeof(pointer_type[0]));
1285 pointer_type->type.type = TYPE_POINTER;
1286 pointer_type->points_to = type;
1287 pointer_type->type.qualifiers = pointer->type_qualifiers;
1289 type_t *result = typehash_insert((type_t*) pointer_type);
1290 if(result != (type_t*) pointer_type) {
1291 obstack_free(type_obst, pointer_type);
1301 static type_t *construct_declarator_type(construct_type_t *construct_list,
1304 construct_type_t *iter = construct_list;
1305 for( ; iter != NULL; iter = iter->next) {
1306 parsed_pointer_t *parsed_pointer;
1307 parsed_array_t *parsed_array;
1308 construct_method_type_t *construct_method_type;
1309 method_type_t *method_type;
1310 pointer_type_t *pointer_type;
1311 array_type_t *array_type;
1313 switch(iter->type) {
1314 case CONSTRUCT_METHOD:
1315 construct_method_type = (construct_method_type_t*) iter;
1316 method_type = construct_method_type->method_type;
1318 method_type->result_type = type;
1319 type = (type_t*) method_type;
1322 case CONSTRUCT_POINTER:
1323 parsed_pointer = (parsed_pointer_t*) iter;
1324 pointer_type = allocate_type_zero(sizeof(pointer_type[0]));
1326 pointer_type->type.type = TYPE_POINTER;
1327 pointer_type->points_to = type;
1328 pointer_type->type.qualifiers = parsed_pointer->type_qualifiers;
1329 type = (type_t*) pointer_type;
1332 case CONSTRUCT_ARRAY:
1333 parsed_array = (parsed_array_t*) iter;
1334 array_type = allocate_type_zero(sizeof(array_type[0]));
1336 array_type->type.type = TYPE_ARRAY;
1337 array_type->element_type = type;
1338 array_type->type.qualifiers = parsed_array->type_qualifiers;
1339 array_type->is_static = parsed_array->is_static;
1340 array_type->is_variable = parsed_array->is_variable;
1341 array_type->size = parsed_array->size;
1342 type = (type_t*) array_type;
1346 type_t *hashed_type = typehash_insert((type_t*) type);
1347 if(hashed_type != type) {
1348 obstack_free(type_obst, type);
1356 static void parse_declarator(declaration_t *declaration,
1357 storage_class_t storage_class, type_t *type,
1358 int may_be_abstract)
1360 construct_type_t *construct_type
1361 = parse_inner_declarator(declaration, may_be_abstract);
1363 declaration->type = construct_declarator_type(construct_type, type);
1364 declaration->storage_class = storage_class;
1365 if(construct_type != NULL) {
1366 obstack_free(&temp_obst, construct_type);
1370 static type_t *parse_abstract_declarator(type_t *base_type)
1372 construct_type_t *construct_type
1373 = parse_inner_declarator(NULL, 1);
1375 if(construct_type == NULL)
1378 type_t *result = construct_declarator_type(construct_type, base_type);
1379 obstack_free(&temp_obst, construct_type);
1384 static declaration_t *record_declaration(declaration_t *declaration)
1389 symbol_t *symbol = declaration->symbol;
1390 if(symbol != NULL) {
1391 declaration_t *alias = environment_push(declaration, context);
1392 if(alias != declaration)
1396 if(last_declaration != NULL) {
1397 last_declaration->next = declaration;
1399 context->declarations = declaration;
1401 last_declaration = declaration;
1406 static void parser_error_multiple_definition(declaration_t *previous,
1407 declaration_t *declaration)
1409 parser_print_error_prefix_pos(declaration->source_position);
1410 fprintf(stderr, "multiple definition of symbol '%s'\n",
1411 declaration->symbol->string);
1412 parser_print_error_prefix_pos(previous->source_position);
1413 fprintf(stderr, "this is the location of the previous "
1417 static void parse_init_declarators(const declaration_specifiers_t *specifiers)
1420 declaration_t *ndeclaration
1421 = allocate_ast_zero(sizeof(ndeclaration[0]));
1423 parse_declarator(ndeclaration, specifiers->storage_class,
1424 specifiers->type, 0);
1425 declaration_t *declaration = record_declaration(ndeclaration);
1426 if(token.type == '=') {
1429 /* TODO: check that this is an allowed type (esp. no method type) */
1431 if(declaration->initializer != NULL) {
1432 parser_error_multiple_definition(declaration, ndeclaration);
1435 if(token.type == '{') {
1439 declaration->initializer = parse_assignment_expression();
1441 } else if(token.type == '{') {
1442 if(declaration->type->type != TYPE_METHOD) {
1443 parser_print_error_prefix();
1444 fprintf(stderr, "Declarator ");
1445 print_type_ext(declaration->type, declaration->symbol, NULL);
1446 fprintf(stderr, " is not a method type.\n");
1449 if(declaration->initializer != NULL) {
1450 parser_error_multiple_definition(declaration, ndeclaration);
1452 if(ndeclaration != declaration) {
1453 memcpy(&declaration->context, &ndeclaration->context,
1454 sizeof(declaration->context));
1457 int top = environment_top();
1458 context_t *last_context = context;
1459 set_context(&declaration->context);
1461 /* push function parameters */
1462 declaration_t *parameter = declaration->context.declarations;
1463 for( ; parameter != NULL; parameter = parameter->next) {
1464 environment_push(parameter, context);
1467 statement_t *statement = parse_compound_statement();
1469 assert(context == &declaration->context);
1470 set_context(last_context);
1471 environment_pop_to(top);
1473 declaration->statement = statement;
1477 if(token.type != ',')
1484 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
1487 if(token.type == ':') {
1489 parse_constant_expression();
1490 /* TODO (bitfields) */
1492 declaration_t *declaration
1493 = allocate_ast_zero(sizeof(declaration[0]));
1494 parse_declarator(declaration, specifiers->storage_class,
1495 specifiers->type, 1);
1497 /* TODO: check for doubled fields */
1498 record_declaration(declaration);
1500 if(token.type == ':') {
1502 parse_constant_expression();
1503 /* TODO (bitfields) */
1507 if(token.type != ',')
1514 static void parse_compound_type_entries(void)
1518 while(token.type != '}' && token.type != T_EOF) {
1519 declaration_specifiers_t specifiers;
1520 memset(&specifiers, 0, sizeof(specifiers));
1521 /* TODO not correct as this allows storage class stuff... but only
1522 * specifiers and qualifiers sould be allowed here */
1523 parse_declaration_specifiers(&specifiers);
1525 parse_struct_declarators(&specifiers);
1527 if(token.type == T_EOF) {
1528 parse_error("unexpected error while parsing struct");
1533 static void parse_declaration(void)
1535 declaration_specifiers_t specifiers;
1536 memset(&specifiers, 0, sizeof(specifiers));
1537 parse_declaration_specifiers(&specifiers);
1539 if(token.type == ';') {
1543 parse_init_declarators(&specifiers);
1546 static type_t *parse_typename(void)
1548 declaration_specifiers_t specifiers;
1549 memset(&specifiers, 0, sizeof(specifiers));
1550 parse_declaration_specifiers(&specifiers);
1551 if(specifiers.storage_class != STORAGE_CLASS_NONE) {
1552 /* TODO: improve error message, user does probably not know what a
1553 * storage class is...
1555 parse_error("typename may not have a storage class");
1558 type_t *result = parse_abstract_declarator(specifiers.type);
1566 typedef expression_t* (*parse_expression_function) (unsigned precedence);
1567 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
1568 expression_t *left);
1570 typedef struct expression_parser_function_t expression_parser_function_t;
1571 struct expression_parser_function_t {
1572 unsigned precedence;
1573 parse_expression_function parser;
1574 unsigned infix_precedence;
1575 parse_expression_infix_function infix_parser;
1578 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
1580 static expression_t *expected_expression_error(void)
1582 parser_print_error_prefix();
1583 fprintf(stderr, "expected expression, got token ");
1584 print_token(stderr, & token);
1585 fprintf(stderr, "\n");
1587 expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
1588 expression->type = EXPR_INVALID;
1594 static expression_t *parse_string_const(void)
1596 string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1598 cnst->expression.type = EXPR_STRING_LITERAL;
1599 cnst->expression.datatype = type_string;
1600 cnst->value = parse_string_literals();
1602 return (expression_t*) cnst;
1605 static expression_t *parse_int_const(void)
1607 const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1609 cnst->expression.type = EXPR_CONST;
1610 cnst->expression.datatype = type_int;
1611 cnst->value = token.v.intvalue;
1615 return (expression_t*) cnst;
1618 static expression_t *parse_reference(void)
1620 reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
1622 ref->expression.type = EXPR_REFERENCE;
1623 ref->symbol = token.v.symbol;
1625 if(ref->symbol->declaration == NULL) {
1626 parser_print_error_prefix();
1627 fprintf(stderr, "unknown symbol '%s' found.\n", ref->symbol->string);
1629 ref->declaration = ref->symbol->declaration;
1630 ref->expression.datatype = ref->declaration->type;
1634 return (expression_t*) ref;
1637 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
1641 /* TODO check if cast is allowed and issue warnings/errors */
1644 static expression_t *parse_cast(void)
1646 unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
1648 cast->expression.type = EXPR_UNARY;
1649 cast->type = UNEXPR_CAST;
1650 cast->expression.source_position = token.source_position;
1652 type_t *type = parse_typename();
1655 expression_t *value = parse_sub_expression(20);
1657 check_cast_allowed(value, type);
1659 cast->expression.datatype = type;
1660 cast->value = value;
1662 return (expression_t*) cast;
1665 static expression_t *parse_statement_expression(void)
1667 statement_expression_t *expression
1668 = allocate_ast_zero(sizeof(expression[0]));
1669 expression->expression.type = EXPR_STATEMENT;
1670 expression->statement = parse_compound_statement();
1672 /* find last statement and use it's type */
1673 const statement_t *last_statement = NULL;
1674 const statement_t *statement = expression->statement;
1675 for( ; statement != NULL; statement = statement->next) {
1676 last_statement = statement;
1679 if(last_statement->type == STATEMENT_EXPRESSION) {
1680 const expression_statement_t *expression_statement =
1681 (const expression_statement_t*) last_statement;
1682 expression->expression.datatype
1683 = expression_statement->expression->datatype;
1685 expression->expression.datatype = type_void;
1690 return (expression_t*) expression;
1693 static expression_t *parse_brace_expression(void)
1697 declaration_t *declaration;
1698 switch(token.type) {
1700 /* gcc extension: a stement expression */
1701 return parse_statement_expression();
1705 return parse_cast();
1707 declaration = token.v.symbol->declaration;
1708 if(declaration != NULL &&
1709 (declaration->storage_class == STORAGE_CLASS_TYPEDEF)) {
1710 return parse_cast();
1714 expression_t *result = parse_expression();
1720 static expression_t *parse_function_keyword(void)
1722 eat(T___FUNCTION__);
1725 string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1726 expression->expression.type = EXPR_FUNCTION;
1727 expression->expression.datatype = type_string;
1728 expression->value = "TODO: FUNCTION";
1730 return (expression_t*) expression;
1733 static expression_t *parse_pretty_function_keyword(void)
1735 eat(T___PRETTY_FUNCTION__);
1738 string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1739 expression->expression.type = EXPR_PRETTY_FUNCTION;
1740 expression->expression.datatype = type_string;
1741 expression->value = "TODO: PRETTY FUNCTION";
1743 return (expression_t*) expression;
1746 static member_designator_t *parse_member_designators(void)
1748 member_designator_t *result = allocate_ast_zero(sizeof(result[0]));
1750 if(token.type != T_IDENTIFIER) {
1751 parse_error_expected("problem while parsing member designator",
1756 result->symbol = token.v.symbol;
1759 member_designator_t *last_designator = result;
1761 if(token.type == '.') {
1763 if(token.type != T_IDENTIFIER) {
1764 parse_error_expected("problem while parsing member designator",
1769 member_designator_t *designator
1770 = allocate_ast_zero(sizeof(result[0]));
1771 designator->symbol = token.v.symbol;
1774 last_designator->next = designator;
1775 last_designator = designator;
1778 if(token.type == '[') {
1780 member_designator_t *designator
1781 = allocate_ast_zero(sizeof(result[0]));
1782 designator->array_access = parse_expression();
1783 if(designator->array_access == NULL) {
1789 last_designator->next = designator;
1790 last_designator = designator;
1799 static expression_t *parse_offsetof(void)
1801 eat(T___builtin_offsetof);
1803 offsetof_expression_t *expression
1804 = allocate_ast_zero(sizeof(expression[0]));
1805 expression->expression.type = EXPR_OFFSETOF;
1806 expression->expression.datatype = type_size_t;
1809 expression->type = parse_typename();
1811 expression->member_designators = parse_member_designators();
1814 return (expression_t*) expression;
1817 static expression_t *parse_builtin_symbol(void)
1819 builtin_symbol_expression_t *expression
1820 = allocate_ast_zero(sizeof(expression[0]));
1821 expression->expression.type = EXPR_BUILTIN_SYMBOL;
1823 /* TODO: set datatype */
1825 expression->symbol = token.v.symbol;
1829 return (expression_t*) expression;
1832 static expression_t *parse_primary_expression(void)
1834 switch(token.type) {
1836 return parse_int_const();
1837 case T_STRING_LITERAL:
1838 return parse_string_const();
1840 return parse_reference();
1841 case T___FUNCTION__:
1842 return parse_function_keyword();
1843 case T___PRETTY_FUNCTION__:
1844 return parse_pretty_function_keyword();
1845 case T___builtin_offsetof:
1846 return parse_offsetof();
1847 case T___builtin_expect:
1848 case T___builtin_va_start:
1849 case T___builtin_va_arg:
1850 case T___builtin_va_end:
1851 return parse_builtin_symbol();
1854 return parse_brace_expression();
1857 parser_print_error_prefix();
1858 fprintf(stderr, "unexpected token ");
1859 print_token(stderr, &token);
1860 fprintf(stderr, "\n");
1865 static expression_t *parse_array_expression(unsigned precedence,
1866 expression_t *array_ref)
1872 array_access_expression_t *array_access
1873 = allocate_ast_zero(sizeof(array_access[0]));
1875 array_access->expression.type = EXPR_ARRAY_ACCESS;
1876 array_access->array_ref = array_ref;
1877 array_access->index = parse_expression();
1879 type_t *array_type = array_ref->datatype;
1880 if(array_type != NULL) {
1881 if(array_type->type == TYPE_POINTER) {
1882 pointer_type_t *pointer = (pointer_type_t*) array_type;
1883 array_access->expression.datatype = pointer->points_to;
1885 parser_print_error_prefix();
1886 fprintf(stderr, "array access on object with non-pointer type ");
1887 print_type(array_type);
1888 fprintf(stderr, "\n");
1892 if(token.type != ']') {
1893 parse_error_expected("Problem while parsing array access", ']', 0);
1898 return (expression_t*) array_access;
1901 static bool is_declaration_specifier(const token_t *token,
1902 bool only_type_specifiers)
1904 declaration_t *declaration;
1906 switch(token->type) {
1910 declaration = token->v.symbol->declaration;
1911 if(declaration == NULL)
1913 if(declaration->storage_class != STORAGE_CLASS_TYPEDEF)
1918 if(only_type_specifiers)
1927 static expression_t *parse_sizeof(unsigned precedence)
1931 sizeof_expression_t *sizeof_expression
1932 = allocate_ast_zero(sizeof(sizeof_expression[0]));
1933 sizeof_expression->expression.type = EXPR_SIZEOF;
1934 sizeof_expression->expression.datatype = type_size_t;
1936 if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
1938 sizeof_expression->type = parse_typename();
1941 expression_t *expression = parse_sub_expression(precedence);
1942 sizeof_expression->type = expression->datatype;
1943 sizeof_expression->size_expression = expression;
1946 return (expression_t*) sizeof_expression;
1949 static expression_t *parse_select_expression(unsigned precedence,
1950 expression_t *compound)
1954 assert(token.type == '.' || token.type == T_MINUSGREATER);
1957 select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
1959 select->expression.type = EXPR_SELECT;
1960 select->compound = compound;
1962 /* TODO: datatype */
1964 if(token.type != T_IDENTIFIER) {
1965 parse_error_expected("Problem while parsing select", T_IDENTIFIER, 0);
1968 select->symbol = token.v.symbol;
1971 return (expression_t*) select;
1974 static expression_t *parse_call_expression(unsigned precedence,
1975 expression_t *expression)
1978 call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
1980 call->expression.type = EXPR_CALL;
1981 call->method = expression;
1983 /* parse arguments */
1986 if(token.type != ')') {
1987 call_argument_t *last_argument = NULL;
1990 call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
1992 argument->expression = parse_assignment_expression();
1993 if(last_argument == NULL) {
1994 call->arguments = argument;
1996 last_argument->next = argument;
1998 last_argument = argument;
2000 if(token.type != ',')
2007 type_t *type = expression->datatype;
2009 /* we can call pointer to function */
2010 if(type->type == TYPE_POINTER) {
2011 pointer_type_t *pointer = (pointer_type_t*) type;
2012 type = pointer->points_to;
2015 if(type == NULL || type->type != TYPE_METHOD) {
2016 parser_print_error_prefix();
2017 fprintf(stderr, "expected a method type for call but found type ");
2018 print_type(expression->datatype);
2019 fprintf(stderr, "\n");
2021 method_type_t *method_type = (method_type_t*) type;
2022 call->expression.datatype = method_type->result_type;
2026 return (expression_t*) call;
2029 static void type_error(const char *msg, const source_position_t source_position,
2032 parser_print_error_prefix_pos(source_position);
2033 fprintf(stderr, "%s, but found type ", msg);
2035 fputc('\n', stderr);
2038 static void type_error_incompatible(const char *msg,
2039 const source_position_t source_position, const type_t *type1,
2040 const type_t *type2)
2042 parser_print_error_prefix_pos(source_position);
2043 fprintf(stderr, "%s, incompatible types: ", msg);
2045 fprintf(stderr, " - ");
2047 fprintf(stderr, ")\n");
2050 static type_t *get_type_after_conversion(const type_t *type1,
2051 const type_t *type2)
2055 return (type_t*) type1;
2058 static expression_t *parse_conditional_expression(unsigned precedence,
2059 expression_t *expression)
2063 conditional_expression_t *conditional
2064 = allocate_ast_zero(sizeof(conditional[0]));
2065 conditional->expression.type = EXPR_CONDITIONAL;
2066 conditional->condition = expression;
2069 type_t *condition_type = conditional->condition->datatype;
2070 if(condition_type != NULL) {
2071 if(!is_type_scalar(condition_type)) {
2072 type_error("expected a scalar type", expression->source_position,
2077 conditional->true_expression = parse_expression();
2079 conditional->false_expression = parse_sub_expression(precedence);
2081 type_t *true_type = conditional->true_expression->datatype;
2082 if(true_type == NULL)
2083 return (expression_t*) conditional;
2084 type_t *false_type = conditional->false_expression->datatype;
2085 if(false_type == NULL)
2086 return (expression_t*) conditional;
2089 if(true_type == false_type) {
2090 conditional->expression.datatype = true_type;
2091 } else if(is_type_arithmetic(true_type) && is_type_arithmetic(false_type)) {
2092 type_t *result = get_type_after_conversion(true_type, false_type);
2093 /* TODO: create implicit convs if necessary */
2094 conditional->expression.datatype = result;
2095 } else if(true_type->type == TYPE_POINTER &&
2096 false_type->type == TYPE_POINTER &&
2097 true /* TODO compatible points_to types */) {
2099 } else if(/* (is_null_ptr_const(true_type) && false_type->type == TYPE_POINTER)
2100 || (is_null_ptr_const(false_type) &&
2101 true_type->type == TYPE_POINTER) TODO*/ false) {
2103 } else if(/* 1 is pointer to object type, other is void* */ false) {
2106 type_error_incompatible("problem while parsing conditional",
2107 expression->source_position, true_type,
2111 return (expression_t*) conditional;
2114 static expression_t *parse_extension(unsigned precedence)
2116 eat(T___extension__);
2118 /* TODO enable extensions */
2120 return parse_sub_expression(precedence);
2123 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type) \
2125 expression_t *parse_##unexpression_type(unsigned precedence) \
2129 unary_expression_t *unary_expression \
2130 = allocate_ast_zero(sizeof(unary_expression[0])); \
2131 unary_expression->expression.type = EXPR_UNARY; \
2132 unary_expression->type = unexpression_type; \
2133 unary_expression->value = parse_sub_expression(precedence); \
2135 return (expression_t*) unary_expression; \
2138 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE)
2139 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS)
2140 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT)
2141 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE)
2142 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS)
2143 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE)
2144 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_PREFIX_INCREMENT)
2145 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT)
2147 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
2149 expression_t *parse_##unexpression_type(unsigned precedence, \
2150 expression_t *left) \
2152 (void) precedence; \
2155 unary_expression_t *unary_expression \
2156 = allocate_ast_zero(sizeof(unary_expression[0])); \
2157 unary_expression->expression.type = EXPR_UNARY; \
2158 unary_expression->type = unexpression_type; \
2159 unary_expression->value = left; \
2161 return (expression_t*) unary_expression; \
2164 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_POSTFIX_INCREMENT)
2165 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT)
2167 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type) \
2169 expression_t *parse_##binexpression_type(unsigned precedence, \
2170 expression_t *left) \
2174 expression_t *right = parse_sub_expression(precedence); \
2176 binary_expression_t *binexpr \
2177 = allocate_ast_zero(sizeof(binexpr[0])); \
2178 binexpr->expression.type = EXPR_BINARY; \
2179 binexpr->type = binexpression_type; \
2180 binexpr->left = left; \
2181 binexpr->right = right; \
2183 return (expression_t*) binexpr; \
2186 CREATE_BINEXPR_PARSER(',', BINEXPR_COMMA)
2187 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL)
2188 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV)
2189 CREATE_BINEXPR_PARSER('%', BINEXPR_MOD)
2190 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD)
2191 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB)
2192 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS)
2193 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER)
2194 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN)
2195 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL)
2196 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, BINEXPR_NOTEQUAL)
2197 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL)
2198 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL)
2199 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND)
2200 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR)
2201 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR)
2202 CREATE_BINEXPR_PARSER(T_ANDAND, BINEXPR_LOGICAL_AND)
2203 CREATE_BINEXPR_PARSER(T_PIPEPIPE, BINEXPR_LOGICAL_OR)
2204 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT)
2205 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT)
2206 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, BINEXPR_ADD_ASSIGN)
2207 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, BINEXPR_SUB_ASSIGN)
2208 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, BINEXPR_MUL_ASSIGN)
2209 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_DIV_ASSIGN)
2210 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, BINEXPR_MOD_ASSIGN)
2211 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, BINEXPR_SHIFTLEFT_ASSIGN)
2212 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, BINEXPR_SHIFTRIGHT_ASSIGN)
2213 CREATE_BINEXPR_PARSER(T_ANDEQUAL, BINEXPR_BITWISE_AND_ASSIGN)
2214 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, BINEXPR_BITWISE_OR_ASSIGN)
2215 CREATE_BINEXPR_PARSER(T_CARETEQUAL, BINEXPR_BITWISE_XOR_ASSIGN)
2217 static expression_t *parse_sub_expression(unsigned precedence)
2219 if(token.type < 0) {
2220 return expected_expression_error();
2223 expression_parser_function_t *parser
2224 = &expression_parsers[token.type];
2225 source_position_t source_position = token.source_position;
2228 if(parser->parser != NULL) {
2229 left = parser->parser(parser->precedence);
2231 left = parse_primary_expression();
2233 assert(left != NULL);
2234 assert(left->type != EXPR_INVALID);
2235 left->source_position = source_position;
2238 if(token.type < 0) {
2239 return expected_expression_error();
2242 parser = &expression_parsers[token.type];
2243 if(parser->infix_parser == NULL)
2245 if(parser->infix_precedence < precedence)
2248 left = parser->infix_parser(parser->infix_precedence, left);
2250 assert(left != NULL);
2251 assert(left->type != EXPR_INVALID);
2252 left->source_position = source_position;
2258 static expression_t *parse_expression(void)
2260 return parse_sub_expression(1);
2265 void register_expression_parser(parse_expression_function parser,
2266 int token_type, unsigned precedence)
2268 expression_parser_function_t *entry = &expression_parsers[token_type];
2270 if(entry->parser != NULL) {
2271 fprintf(stderr, "for token ");
2272 print_token_type(stderr, token_type);
2273 fprintf(stderr, "\n");
2274 panic("trying to register multiple expression parsers for a token");
2276 entry->parser = parser;
2277 entry->precedence = precedence;
2280 void register_expression_infix_parser(parse_expression_infix_function parser,
2281 int token_type, unsigned precedence)
2283 expression_parser_function_t *entry = &expression_parsers[token_type];
2285 if(entry->infix_parser != NULL) {
2286 fprintf(stderr, "for token ");
2287 print_token_type(stderr, token_type);
2288 fprintf(stderr, "\n");
2289 panic("trying to register multiple infix expression parsers for a "
2292 entry->infix_parser = parser;
2293 entry->infix_precedence = precedence;
2296 static void init_expression_parsers(void)
2298 memset(&expression_parsers, 0, sizeof(expression_parsers));
2300 register_expression_infix_parser(parse_BINEXPR_MUL, '*', 16);
2301 register_expression_infix_parser(parse_BINEXPR_DIV, '/', 16);
2302 register_expression_infix_parser(parse_BINEXPR_MOD, '%', 16);
2303 register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT, T_LESSLESS, 16);
2304 register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
2305 T_GREATERGREATER, 16);
2306 register_expression_infix_parser(parse_BINEXPR_ADD, '+', 15);
2307 register_expression_infix_parser(parse_BINEXPR_SUB, '-', 15);
2308 register_expression_infix_parser(parse_BINEXPR_LESS, '<', 14);
2309 register_expression_infix_parser(parse_BINEXPR_GREATER, '>', 14);
2310 register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL, 14);
2311 register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
2312 T_GREATEREQUAL, 14);
2313 register_expression_infix_parser(parse_BINEXPR_EQUAL, T_EQUALEQUAL, 13);
2314 register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
2315 T_EXCLAMATIONMARKEQUAL, 13);
2316 register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&', 12);
2317 register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^', 11);
2318 register_expression_infix_parser(parse_BINEXPR_BITWISE_OR, '|', 10);
2319 register_expression_infix_parser(parse_BINEXPR_LOGICAL_AND, T_ANDAND, 9);
2320 register_expression_infix_parser(parse_BINEXPR_LOGICAL_OR, T_PIPEPIPE, 8);
2321 register_expression_infix_parser(parse_conditional_expression, '?', 7);
2322 register_expression_infix_parser(parse_BINEXPR_ASSIGN, '=', 2);
2323 register_expression_infix_parser(parse_BINEXPR_ADD_ASSIGN, T_PLUSEQUAL, 2);
2324 register_expression_infix_parser(parse_BINEXPR_SUB_ASSIGN, T_MINUSEQUAL, 2);
2325 register_expression_infix_parser(parse_BINEXPR_MUL_ASSIGN,
2326 T_ASTERISKEQUAL, 2);
2327 register_expression_infix_parser(parse_BINEXPR_DIV_ASSIGN, T_SLASHEQUAL, 2);
2328 register_expression_infix_parser(parse_BINEXPR_MOD_ASSIGN,
2330 register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT_ASSIGN,
2331 T_LESSLESSEQUAL, 2);
2332 register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT_ASSIGN,
2333 T_GREATERGREATEREQUAL, 2);
2334 register_expression_infix_parser(parse_BINEXPR_BITWISE_AND_ASSIGN,
2336 register_expression_infix_parser(parse_BINEXPR_BITWISE_OR_ASSIGN,
2338 register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR_ASSIGN,
2341 register_expression_infix_parser(parse_BINEXPR_COMMA, ',', 1);
2343 register_expression_infix_parser(parse_array_expression, '[', 30);
2344 register_expression_infix_parser(parse_call_expression, '(', 30);
2345 register_expression_infix_parser(parse_select_expression, '.', 30);
2346 register_expression_infix_parser(parse_select_expression,
2347 T_MINUSGREATER, 30);
2348 register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
2350 register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
2353 register_expression_parser(parse_UNEXPR_NEGATE, '-', 25);
2354 register_expression_parser(parse_UNEXPR_PLUS, '+', 25);
2355 register_expression_parser(parse_UNEXPR_NOT, '!', 25);
2356 register_expression_parser(parse_UNEXPR_BITWISE_NEGATE, '~', 25);
2357 register_expression_parser(parse_UNEXPR_DEREFERENCE, '*', 25);
2358 register_expression_parser(parse_UNEXPR_TAKE_ADDRESS, '&', 25);
2359 register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS, 25);
2360 register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
2361 register_expression_parser(parse_sizeof, T_sizeof, 25);
2362 register_expression_parser(parse_extension, T___extension__, 25);
2366 static statement_t *parse_case_statement(void)
2369 case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2370 label->statement.type = STATEMENT_CASE_LABEL;
2371 label->statement.source_position = token.source_position;
2373 label->expression = parse_expression();
2376 label->statement.next = parse_statement();
2378 return (statement_t*) label;
2381 static statement_t *parse_default_statement(void)
2385 case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2386 label->statement.type = STATEMENT_CASE_LABEL;
2387 label->statement.source_position = token.source_position;
2390 label->statement.next = parse_statement();
2392 return (statement_t*) label;
2395 static statement_t *parse_label_statement(void)
2404 static statement_t *parse_if(void)
2408 if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2409 statement->statement.type = STATEMENT_IF;
2410 statement->statement.source_position = token.source_position;
2413 statement->condition = parse_expression();
2416 statement->true_statement = parse_statement();
2417 if(token.type == T_else) {
2419 statement->false_statement = parse_statement();
2422 return (statement_t*) statement;
2425 static statement_t *parse_switch(void)
2429 switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2430 statement->statement.type = STATEMENT_SWITCH;
2431 statement->statement.source_position = token.source_position;
2434 statement->expression = parse_expression();
2436 statement->body = parse_statement();
2438 return (statement_t*) statement;
2441 static statement_t *parse_while(void)
2445 while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2446 statement->statement.type = STATEMENT_WHILE;
2447 statement->statement.source_position = token.source_position;
2450 statement->condition = parse_expression();
2452 statement->body = parse_statement();
2454 return (statement_t*) statement;
2457 static statement_t *parse_do(void)
2461 do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2462 statement->statement.type = STATEMENT_DO_WHILE;
2463 statement->statement.source_position = token.source_position;
2465 statement->body = parse_statement();
2468 statement->condition = parse_expression();
2472 return (statement_t*) statement;
2475 static statement_t *parse_for(void)
2479 for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2480 statement->statement.type = STATEMENT_FOR;
2481 statement->statement.source_position = token.source_position;
2485 int top = environment_top();
2486 context_t *last_context = context;
2487 set_context(&statement->context);
2489 if(token.type != ';') {
2490 if(is_declaration_specifier(&token, false)) {
2491 parse_declaration();
2493 statement->initialisation = parse_expression();
2500 if(token.type != ';') {
2501 statement->condition = parse_expression();
2504 if(token.type != ')') {
2505 statement->step = parse_expression();
2508 statement->body = parse_statement();
2510 assert(context == &statement->context);
2511 set_context(last_context);
2512 environment_pop_to(top);
2514 return (statement_t*) statement;
2517 static statement_t *parse_goto(void)
2520 expect(T_IDENTIFIER);
2526 static statement_t *parse_continue(void)
2531 statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2532 statement->source_position = token.source_position;
2533 statement->type = STATEMENT_CONTINUE;
2538 static statement_t *parse_break(void)
2543 statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2544 statement->source_position = token.source_position;
2545 statement->type = STATEMENT_BREAK;
2550 static statement_t *parse_return(void)
2554 return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2556 statement->statement.type = STATEMENT_RETURN;
2557 statement->statement.source_position = token.source_position;
2558 if(token.type != ';') {
2559 statement->return_value = parse_expression();
2563 return (statement_t*) statement;
2566 static statement_t *parse_declaration_statement(void)
2568 declaration_t *before = last_declaration;
2570 declaration_statement_t *statement
2571 = allocate_ast_zero(sizeof(statement[0]));
2572 statement->statement.type = STATEMENT_DECLARATION;
2573 statement->statement.source_position = token.source_position;
2575 declaration_specifiers_t specifiers;
2576 memset(&specifiers, 0, sizeof(specifiers));
2577 parse_declaration_specifiers(&specifiers);
2579 if(token.type == ';') {
2582 parse_init_declarators(&specifiers);
2585 if(before == NULL) {
2586 statement->declarations_begin = context->declarations;
2588 statement->declarations_begin = before->next;
2590 statement->declarations_end = last_declaration;
2592 return (statement_t*) statement;
2595 static statement_t *parse_expression_statement(void)
2597 expression_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2598 statement->statement.type = STATEMENT_EXPRESSION;
2599 statement->statement.source_position = token.source_position;
2601 statement->expression = parse_expression();
2605 return (statement_t*) statement;
2608 static statement_t *parse_statement(void)
2610 declaration_t *declaration;
2611 statement_t *statement = NULL;
2613 /* declaration or statement */
2614 switch(token.type) {
2616 statement = parse_case_statement();
2620 statement = parse_default_statement();
2624 statement = parse_compound_statement();
2628 statement = parse_if();
2632 statement = parse_switch();
2636 statement = parse_while();
2640 statement = parse_do();
2644 statement = parse_for();
2648 statement = parse_goto();
2652 statement = parse_continue();
2656 statement = parse_break();
2660 statement = parse_return();
2669 if(look_ahead(1)->type == ':') {
2670 statement = parse_label_statement();
2674 declaration = token.v.symbol->declaration;
2675 if(declaration != NULL &&
2676 declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
2677 statement = parse_declaration_statement();
2681 statement = parse_expression_statement();
2684 case T___extension__:
2685 /* this can be a prefix to a declaration or an expression statement */
2686 /* we simply eat it now and parse the rest with tail recursion */
2689 } while(token.type == T___extension__);
2690 statement = parse_statement();
2694 statement = parse_declaration_statement();
2698 statement = parse_expression_statement();
2702 assert(statement == NULL || statement->source_position.input_name != NULL);
2707 static statement_t *parse_compound_statement(void)
2711 compound_statement_t *compound_statement
2712 = allocate_ast_zero(sizeof(compound_statement[0]));
2713 compound_statement->statement.type = STATEMENT_COMPOUND;
2714 compound_statement->statement.source_position = token.source_position;
2716 int top = environment_top();
2717 context_t *last_context = context;
2718 set_context(&compound_statement->context);
2720 statement_t *last_statement = NULL;
2722 while(token.type != '}' && token.type != T_EOF) {
2723 statement_t *statement = parse_statement();
2724 if(statement == NULL)
2727 if(last_statement != NULL) {
2728 last_statement->next = statement;
2730 compound_statement->statements = statement;
2733 while(statement->next != NULL)
2734 statement = statement->next;
2736 last_statement = statement;
2739 assert(context == &compound_statement->context);
2740 set_context(last_context);
2741 environment_pop_to(top);
2745 return (statement_t*) compound_statement;
2748 static translation_unit_t *parse_translation_unit(void)
2750 translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
2752 assert(context == NULL);
2753 set_context(&unit->context);
2755 while(token.type != T_EOF) {
2756 parse_declaration();
2759 assert(context == &unit->context);
2761 last_declaration = NULL;
2766 translation_unit_t *parse(void)
2768 obstack_init(&environment_obstack);
2769 environment_stack = NEW_ARR_F(environment_entry_t*, 0);
2771 type_set_output(stderr);
2773 lookahead_bufpos = 0;
2774 for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
2777 translation_unit_t *unit = parse_translation_unit();
2779 DEL_ARR_F(environment_stack);
2780 obstack_free(&environment_obstack, NULL);
2785 void init_parser(void)
2787 init_expression_parsers();
2788 obstack_init(&temp_obst);
2790 type_int = make_atomic_type(ATOMIC_TYPE_INT, 0);
2791 type_size_t = make_atomic_type(ATOMIC_TYPE_UINT, 0);
2792 type_const_char = make_atomic_type(ATOMIC_TYPE_CHAR, TYPE_QUALIFIER_CONST);
2793 type_void = make_atomic_type(ATOMIC_TYPE_VOID, 0);
2794 type_string = make_pointer_type(type_const_char, 0);
2797 void exit_parser(void)
2799 obstack_free(&temp_obst, NULL);