+ type_t *result = parse_abstract_declarator(specifiers.type);
+
+ return result;
+}
+
+
+
+
+typedef expression_t* (*parse_expression_function) (unsigned precedence);
+typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
+ expression_t *left);
+
+typedef struct expression_parser_function_t expression_parser_function_t;
+struct expression_parser_function_t {
+ unsigned precedence;
+ parse_expression_function parser;
+ unsigned infix_precedence;
+ parse_expression_infix_function infix_parser;
+};
+
+expression_parser_function_t expression_parsers[T_LAST_TOKEN];
+
+static
+expression_t *expected_expression_error(void)
+{
+ parser_print_error_prefix();
+ fprintf(stderr, "expected expression, got token ");
+ print_token(stderr, & token);
+ fprintf(stderr, "\n");
+
+ expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
+ expression->type = EXPR_INVALID;
+ next_token();
+
+ return expression;
+}
+
+static
+expression_t *parse_string_const(void)
+{
+ string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
+
+ cnst->expression.type = EXPR_STRING_LITERAL;
+ cnst->value = parse_string_literals();
+
+ return (expression_t*) cnst;
+}
+
+static
+expression_t *parse_int_const(void)
+{
+ const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
+
+ cnst->expression.type = EXPR_CONST;
+ cnst->value = token.v.intvalue;
+
+ next_token();
+
+ return (expression_t*) cnst;
+}
+
+static
+expression_t *parse_reference(void)
+{
+ reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
+
+ ref->expression.type = EXPR_REFERENCE;
+ ref->symbol = token.v.symbol;
+
+ if(ref->symbol->declaration == NULL) {
+ parser_print_error_prefix();
+ fprintf(stderr, "unknown symbol '%s' found.\n", ref->symbol->string);
+ }
+ ref->declaration = ref->symbol->declaration;
+
+ next_token();
+
+ return (expression_t*) ref;
+}
+
+static
+expression_t *parse_cast(void)
+{
+ unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
+
+ cast->expression.type = EXPR_UNARY;
+ cast->type = UNEXPR_CAST;
+ cast->expression.source_position = token.source_position;
+
+ type_t *type = parse_typename();
+
+ expect(')');
+ expression_t *value = parse_sub_expression(20);
+
+ cast->expression.datatype = type;
+ cast->value = value;
+
+ return (expression_t*) cast;
+}
+
+static
+expression_t *parse_brace_expression(void)
+{
+ eat('(');
+
+ declaration_t *declaration;
+ switch(token.type) {
+ TYPE_QUALIFIERS
+ TYPE_SPECIFIERS
+ return parse_cast();
+ case T_IDENTIFIER:
+ declaration = token.v.symbol->declaration;
+ if(declaration != NULL &&
+ (declaration->storage_class & STORAGE_CLASS_TYPEDEF)) {
+ return parse_cast();
+ }
+ }
+
+ expression_t *result = parse_expression();
+ expect(')');
+
+ return result;
+}
+
+static
+expression_t *parse_primary_expression(void)
+{
+ switch(token.type) {
+ case T_INTEGER:
+ return parse_int_const();
+ case T_STRING_LITERAL:
+ return parse_string_const();
+ case T_IDENTIFIER:
+ return parse_reference();
+ case '(':
+ return parse_brace_expression();
+ }
+
+ parser_print_error_prefix();
+ fprintf(stderr, "unexpected token ");
+ print_token(stderr, &token);
+ fprintf(stderr, "\n");
+ eat_statement();
+ return NULL;
+}
+
+static
+expression_t *parse_array_expression(unsigned precedence,
+ expression_t *array_ref)
+{
+ (void) precedence;
+
+ eat('[');
+
+ array_access_expression_t *array_access
+ = allocate_ast_zero(sizeof(array_access[0]));
+
+ array_access->expression.type = EXPR_ARRAY_ACCESS;
+ array_access->array_ref = array_ref;
+ array_access->index = parse_expression();
+
+ if(token.type != ']') {
+ parse_error_expected("Problem while parsing array access", ']', 0);
+ return NULL;
+ }
+ next_token();
+
+ return (expression_t*) array_access;
+}
+
+static
+type_t *get_expression_type(const expression_t *expression)
+{
+ (void) expression;
+ /* TODO */
+ return NULL;
+}
+
+static
+int is_type_specifier(const token_t *token)
+{
+ declaration_t *declaration;
+
+ switch(token->type) {
+ TYPE_SPECIFIERS
+ return 1;
+ case T_IDENTIFIER:
+ declaration = token->v.symbol->declaration;
+ if(declaration == NULL)
+ return 0;
+ if(declaration->storage_class != STORAGE_CLASS_TYPEDEF)
+ return 0;
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+static
+expression_t *parse_sizeof(unsigned precedence)
+{
+ eat(T_sizeof);
+
+ sizeof_expression_t *sizeof_expression
+ = allocate_ast_zero(sizeof(sizeof_expression[0]));
+ sizeof_expression->expression.type = EXPR_SIZEOF;
+
+ if(token.type == '(' && is_type_specifier(look_ahead(1))) {
+ next_token();
+ sizeof_expression->type = parse_typename();
+ expect(')');
+ } else {
+ expression_t *expression = parse_sub_expression(precedence);
+ sizeof_expression->type = get_expression_type(expression);
+ }
+
+ return (expression_t*) sizeof_expression;
+}
+
+static
+expression_t *parse_select_expression(unsigned precedence,
+ expression_t *compound)
+{
+ (void) precedence;
+
+ assert(token.type == '.' || token.type == T_SELECT);
+ next_token();
+
+ select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
+
+ select->expression.type = EXPR_SELECT;
+ select->compound = compound;
+
+ if(token.type != T_IDENTIFIER) {
+ parse_error_expected("Problem while parsing compound select",
+ T_IDENTIFIER, 0);
+ return NULL;
+ }
+ select->symbol = token.v.symbol;
+ next_token();
+
+ return (expression_t*) select;
+}
+
+static
+expression_t *parse_call_expression(unsigned precedence,
+ expression_t *expression)
+{
+ (void) precedence;
+ call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
+
+ call->expression.type = EXPR_CALL;
+ call->method = expression;
+
+ /* parse arguments */
+ eat('(');
+
+ if(token.type != ')') {
+ call_argument_t *last_argument = NULL;
+
+ while(1) {
+ call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
+
+ argument->expression = parse_expression();
+ if(last_argument == NULL) {
+ call->arguments = argument;
+ } else {
+ last_argument->next = argument;
+ }
+ last_argument = argument;
+
+ if(token.type != ',')
+ break;
+ next_token();
+ }
+ }
+ expect(')');
+
+ return (expression_t*) call;
+}
+
+static
+expression_t *parse_conditional_expression(unsigned precedence,
+ expression_t *expression)
+{
+ eat('?');
+
+ conditional_expression_t *conditional
+ = allocate_ast_zero(sizeof(conditional[0]));
+ conditional->condition = expression;
+
+ conditional->true_expression = parse_expression();
+ expect(':');
+ conditional->false_expression = parse_sub_expression(precedence);
+
+ return (expression_t*) conditional;
+}
+
+#define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type) \
+static \
+expression_t *parse_##unexpression_type(unsigned precedence) \
+{ \
+ eat(token_type); \
+ \
+ unary_expression_t *unary_expression \
+ = allocate_ast_zero(sizeof(unary_expression[0])); \
+ unary_expression->expression.type = EXPR_UNARY; \
+ unary_expression->type = unexpression_type; \
+ unary_expression->value = parse_sub_expression(precedence); \
+ \
+ return (expression_t*) unary_expression; \
+}
+
+CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE)
+CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS)
+CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT)
+CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE)
+CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS)
+CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE)
+CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_PREFIX_INCREMENT)
+CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT)
+
+#define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
+static \
+expression_t *parse_##unexpression_type(unsigned precedence, \
+ expression_t *left) \
+{ \
+ (void) precedence; \
+ eat(token_type); \
+ \
+ unary_expression_t *unary_expression \
+ = allocate_ast_zero(sizeof(unary_expression[0])); \
+ unary_expression->expression.type = EXPR_UNARY; \
+ unary_expression->type = unexpression_type; \
+ unary_expression->value = left; \
+ \
+ return (expression_t*) unary_expression; \
+}
+
+CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS, UNEXPR_POSTFIX_INCREMENT)
+CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT)
+
+#define CREATE_BINEXPR_PARSER(token_type, binexpression_type) \
+static \
+expression_t *parse_##binexpression_type(unsigned precedence, \
+ expression_t *left) \
+{ \
+ eat(token_type); \
+ \
+ expression_t *right = parse_sub_expression(precedence); \
+ \
+ binary_expression_t *binexpr \
+ = allocate_ast_zero(sizeof(binexpr[0])); \
+ binexpr->expression.type = EXPR_BINARY; \
+ binexpr->type = binexpression_type; \
+ binexpr->left = left; \
+ binexpr->right = right; \
+ \
+ return (expression_t*) binexpr; \
+}
+
+CREATE_BINEXPR_PARSER('*', BINEXPR_MUL)
+CREATE_BINEXPR_PARSER('/', BINEXPR_DIV)
+CREATE_BINEXPR_PARSER('+', BINEXPR_ADD)
+CREATE_BINEXPR_PARSER('-', BINEXPR_SUB)
+CREATE_BINEXPR_PARSER('<', BINEXPR_LESS)
+CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER)
+CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN)
+CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL)
+CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, BINEXPR_NOTEQUAL)
+CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL)
+CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL)
+CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND)
+CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR)
+CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR)
+CREATE_BINEXPR_PARSER(T_ANDAND, BINEXPR_LOGICAL_AND)
+CREATE_BINEXPR_PARSER(T_PIPEPIPE, BINEXPR_LOGICAL_OR)
+CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT)
+CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT)
+
+static
+expression_t *parse_sub_expression(unsigned precedence)
+{
+ if(token.type < 0) {
+ return expected_expression_error();
+ }
+
+ expression_parser_function_t *parser
+ = &expression_parsers[token.type];
+ source_position_t source_position = token.source_position;
+ expression_t *left;
+
+ if(parser->parser != NULL) {
+ left = parser->parser(parser->precedence);
+ } else {
+ left = parse_primary_expression();
+ }
+ if(left != NULL)
+ left->source_position = source_position;
+
+ while(1) {
+ if(token.type < 0) {
+ return expected_expression_error();
+ }
+
+ parser = &expression_parsers[token.type];
+ if(parser->infix_parser == NULL)
+ break;
+ if(parser->infix_precedence < precedence)
+ break;
+
+ left = parser->infix_parser(parser->infix_precedence, left);
+ if(left != NULL)
+ left->source_position = source_position;
+ }
+
+ return left;
+}
+
+static
+expression_t *parse_expression(void)
+{
+ return parse_sub_expression(1);
+}
+
+
+
+void register_expression_parser(parse_expression_function parser,
+ int token_type, unsigned precedence)
+{
+ expression_parser_function_t *entry = &expression_parsers[token_type];
+
+ if(entry->parser != NULL) {
+ fprintf(stderr, "for token ");
+ print_token_type(stderr, token_type);
+ fprintf(stderr, "\n");
+ panic("trying to register multiple expression parsers for a token");
+ }
+ entry->parser = parser;
+ entry->precedence = precedence;
+}
+
+void register_expression_infix_parser(parse_expression_infix_function parser,
+ int token_type, unsigned precedence)
+{
+ expression_parser_function_t *entry = &expression_parsers[token_type];
+
+ if(entry->infix_parser != NULL) {
+ fprintf(stderr, "for token ");
+ print_token_type(stderr, token_type);
+ fprintf(stderr, "\n");
+ panic("trying to register multiple infix expression parsers for a "
+ "token");
+ }
+ entry->infix_parser = parser;
+ entry->infix_precedence = precedence;
+}
+
+static
+void init_expression_parsers(void)
+{
+ memset(&expression_parsers, 0, sizeof(expression_parsers));
+
+ register_expression_infix_parser(parse_BINEXPR_MUL, '*', 16);
+ register_expression_infix_parser(parse_BINEXPR_DIV, '/', 16);
+ register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT,
+ T_LESSLESS, 16);
+ register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
+ T_GREATERGREATER, 16);
+ register_expression_infix_parser(parse_BINEXPR_ADD, '+', 15);
+ register_expression_infix_parser(parse_BINEXPR_SUB, '-', 15);
+ register_expression_infix_parser(parse_BINEXPR_LESS, '<', 14);
+ register_expression_infix_parser(parse_BINEXPR_GREATER, '>', 14);
+ register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL, 14);
+ register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
+ T_GREATEREQUAL, 14);
+ register_expression_infix_parser(parse_BINEXPR_EQUAL, T_EQUALEQUAL, 13);
+ register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
+ T_EXCLAMATIONMARKEQUAL, 13);
+ register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&', 12);
+ register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^', 11);
+ register_expression_infix_parser(parse_BINEXPR_BITWISE_OR, '|', 10);
+ register_expression_infix_parser(parse_BINEXPR_LOGICAL_AND, T_ANDAND, 9);
+ register_expression_infix_parser(parse_BINEXPR_LOGICAL_OR, T_PIPEPIPE, 8);
+ register_expression_infix_parser(parse_conditional_expression, '?', 7);
+ register_expression_infix_parser(parse_BINEXPR_ASSIGN, T_EQUAL, 2);
+
+ register_expression_infix_parser(parse_array_expression, '[', 30);
+ register_expression_infix_parser(parse_call_expression, '(', 30);
+ register_expression_infix_parser(parse_select_expression, '.', 30);
+ register_expression_infix_parser(parse_select_expression, T_SELECT, 30);
+ register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
+ T_PLUSPLUS, 30);
+ register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
+ T_MINUSMINUS, 30);
+
+ register_expression_parser(parse_UNEXPR_NEGATE, '-', 25);
+ register_expression_parser(parse_UNEXPR_PLUS, '+', 25);
+ register_expression_parser(parse_UNEXPR_NOT, '!', 25);
+ register_expression_parser(parse_UNEXPR_BITWISE_NEGATE, '~', 25);
+ register_expression_parser(parse_UNEXPR_DEREFERENCE, '*', 25);
+ register_expression_parser(parse_UNEXPR_TAKE_ADDRESS, '&', 25);
+ register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS, 25);
+ register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
+ register_expression_parser(parse_sizeof, T_sizeof, 25);
+}
+
+
+static
+statement_t *parse_case_statement(void)
+{
+ eat(T_case);
+ parse_expression();
+ expect(':');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_default_statement(void)
+{
+ eat(T_default);
+ expect(':');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_label_statement(void)
+{
+ eat(T_IDENTIFIER);
+ expect(':');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_if(void)
+{
+ eat(T_if);
+
+ if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
+ statement->statement.type = STATEMENT_IF;
+
+ expect('(');
+ statement->condition = parse_expression();
+ expect(')');
+
+ statement->true_statement = parse_statement();
+ if(token.type == T_else) {
+ next_token();
+ statement->false_statement = parse_statement();
+ }
+
+ return (statement_t*) statement;
+}
+
+static
+statement_t *parse_switch(void)
+{
+ eat(T_switch);
+ expect('(');
+ parse_expression();
+ expect(')');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_while(void)
+{
+ eat(T_while);
+ expect('(');
+ parse_expression();
+ expect(')');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_do(void)
+{
+ eat(T_do);
+ parse_statement();
+ expect(T_while);
+ expect('(');
+ parse_expression();
+ expect(')');
+
+ return NULL;
+}
+
+static
+statement_t *parse_for(void)
+{
+ eat(T_for);
+ expect('(');
+ if(token.type != ';') {
+ /* TODO not correct... this could also be a declaration */
+ parse_expression();
+ }
+ expect(';');
+ if(token.type != ';') {
+ parse_expression();
+ }
+ expect(';');
+ if(token.type != ')') {
+ parse_expression();
+ }
+ expect(')');
+ parse_statement();
+
+ return NULL;
+}
+
+static
+statement_t *parse_goto(void)
+{
+ eat(T_goto);
+ expect(T_IDENTIFIER);
+ expect(';');
+
+ return NULL;
+}
+
+static
+statement_t *parse_continue(void)
+{
+ eat(T_continue);
+ expect(';');
+
+ statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
+ statement->source_position = token.source_position;
+ statement->type = STATEMENT_CONTINUE;
+
+ return statement;
+}
+
+static
+statement_t *parse_break(void)
+{
+ eat(T_break);
+ expect(';');
+
+ return NULL;
+}
+
+static
+statement_t *parse_return(void)
+{
+ eat(T_return);
+
+ return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
+ statement->statement.type = STATEMENT_RETURN;
+ if(token.type != ';') {
+ statement->return_value = parse_expression();
+ }
+ expect(';');
+
+ return (statement_t*) statement;
+}
+
+static
+statement_t *parse_declaration_statement(void)
+{
+ parse_declaration();
+ return NULL;
+}
+
+static
+statement_t *parse_expression_statement(void)
+{
+ parse_expression();
+ return NULL;
+}
+
+static
+statement_t *parse_statement(void)
+{
+ declaration_t *declaration;
+ statement_t *statement = NULL;
+
+ /* declaration or statement */
+ switch(token.type) {
+ case T_case:
+ statement = parse_case_statement();
+ break;
+
+ case T_default:
+ statement = parse_default_statement();
+ break;
+
+ case '{':
+ statement = parse_compound_statement();
+ break;
+
+ case T_if:
+ statement = parse_if();
+ break;
+
+ case T_switch:
+ statement = parse_switch();
+ break;
+
+ case T_while:
+ statement = parse_while();
+ break;
+
+ case T_do:
+ statement = parse_do();
+ break;
+
+ case T_for:
+ statement = parse_for();
+ break;
+
+ case T_goto:
+ statement = parse_goto();
+ break;
+
+ case T_continue:
+ statement = parse_continue();
+ break;
+
+ case T_break:
+ statement = parse_break();
+ break;
+
+ case T_return:
+ statement = parse_return();
+ break;
+
+ case ';':
+ next_token();
+ statement = NULL;
+ break;
+
+ case T_IDENTIFIER:
+ if(look_ahead(1)->type == ':') {
+ statement = parse_label_statement();
+ break;
+ }
+
+ declaration = token.v.symbol->declaration;
+ if(declaration != NULL &&
+ declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
+ statement = parse_declaration_statement();
+ break;
+ }
+
+ statement = parse_expression_statement();
+ break;
+
+ DECLARATION_START
+ statement = parse_declaration_statement();
+ break;
+
+ default:
+ statement = parse_expression_statement();
+ break;
+ }
+
+ return statement;
+}
+
+static
+statement_t *parse_compound_statement(void)
+{
+ eat('{');
+
+ compound_statement_t *compound_statement
+ = allocate_ast_zero(sizeof(compound_statement[0]));
+ compound_statement->statement.type = STATEMENT_COMPOUND;
+
+ int top = environment_top();
+ context_t *last_context = context;
+ set_context(&compound_statement->context);
+
+ statement_t *last_statement = NULL;
+
+ while(token.type != '}' && token.type != T_EOF) {
+ statement_t *statement = parse_statement();
+
+ if(last_statement != NULL) {
+ last_statement->next = statement;
+ } else {
+ compound_statement->statements = statement;
+ }
+ last_statement = statement;
+ }
+
+ assert(context == &compound_statement->context);
+ set_context(last_context);
+ environment_pop_to(top);
+
+ next_token();
+
+ return (statement_t*) compound_statement;
+}
+
+static
+translation_unit_t *parse_translation_unit(void)
+{
+ translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
+
+ assert(context == NULL);
+ set_context(&unit->context);
+
+ while(token.type != T_EOF) {
+ parse_declaration();
+ }
+
+ assert(context == &unit->context);
+ context = NULL;
+ last_declaration = NULL;
+
+ return unit;
+}
+
+translation_unit_t *parse(void)
+{
+ obstack_init(&environment_obstack);
+ environment_stack = NEW_ARR_F(environment_entry_t*, 0);
+
+ type_set_output(stderr);
+
+ lookahead_bufpos = 0;
+ for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
+ next_token();
+ }
+ translation_unit_t *unit = parse_translation_unit();
+
+ DEL_ARR_F(environment_stack);
+ obstack_free(&environment_obstack, NULL);
+
+ return unit;
+}
+
+void init_parser(void)
+{
+ init_expression_parsers();
+ obstack_init(&temp_obst);
+}
+
+void exit_parser(void)
+{
+ obstack_free(&temp_obst, NULL);