From bbce3104de593c90b10778a379728f982bc3fdcb Mon Sep 17 00:00:00 2001 From: Teddy Date: Sat, 12 Apr 2014 22:24:35 +0800 Subject: typedef now works --- ast.c | 15 ++++++ ast.h | 2 + cibic.l | 4 +- cibic.y | 56 +++++++++++++------ main.c | 2 + semantics.c | 148 ++++++++++++++++++++++++++++++++++++++++++++------- semantics.h | 24 ++++++++- test_all.sh | 5 +- testcases/conflict.c | 4 ++ testcases/pass.c | 15 ++++++ 10 files changed, 235 insertions(+), 40 deletions(-) create mode 100644 testcases/conflict.c diff --git a/ast.c b/ast.c index a126e6b..6057e66 100644 --- a/ast.c +++ b/ast.c @@ -210,6 +210,19 @@ CNode *cnode_create_plain_decl(CNode *type_spec, CNode *declr) { return pdecl; } +CNode *cnode_create_typedef(CNode *type, CNode *declrs) { +#ifdef CIBIC_DEBUG + assert(type->next == NULL); + assert(declrs->next == NULL); +#endif + CNode *def = NEW_CNODE; + def->type = TYPEDEF; + def->next = NULL; + def->chd = declrs; + declrs->next = type; + return def; +} + CNode *cnode_list_wrap(int type, CNode *list) { CNode *wlist = NEW_CNODE; wlist->type = type; @@ -237,6 +250,7 @@ char *cnode_debug_type_repr(CNode *ast) { case INIT_DECLRS: type = "init_declrs"; break; case ARGS: type = "args"; break; case PARAMS: type = "params"; break; + case TYPEDEF: type = "typedef"; break; case ID: type = "id"; aptr += sprintf(abuff, "%s", ast->rec.strval); @@ -320,6 +334,7 @@ char *cnode_debug_type_repr(CNode *ast) { case KW_INT: type = "int"; break; case KW_STRUCT: type = "struct"; break; case KW_UNION: type = "union"; break; + case USER_TYPE: type = "user_type"; break; default: assert(0); } } diff --git a/ast.h b/ast.h index 9831f68..a886c2e 100644 --- a/ast.h +++ b/ast.h @@ -22,6 +22,7 @@ typedef struct CNode { PLAIN_DECL, DECLS, FUNCS, + TYPEDEF, /* Statments */ STMT, @@ -75,6 +76,7 @@ CNode *cnode_create_func(CNode *type, CNode *declr, CNode *stmt); CNode *cnode_create_init_declr(CNode *declr, CNode *initr); CNode *cnode_create_struct_field(CNode *type_spec, CNode *declrs); CNode *cnode_create_plain_decl(CNode *type_spec, CNode *declr); +CNode *cnode_create_typedef(CNode *type, CNode *declrs); CNode *cnode_create_identifier(char *val); CNode *cnode_create_int_const(int val); diff --git a/cibic.l b/cibic.l index e6e449b..e597729 100644 --- a/cibic.l +++ b/cibic.l @@ -1,5 +1,6 @@ %{ #include "cibic.tab.h" +#include "semantics.h" #define MAX_LINEBUFF 1024 int yycolumn = 1; char linebuff[MAX_LINEBUFF], *lptr = linebuff; @@ -69,10 +70,11 @@ char ([^\n'\\]|\\.|\\[0-7]+|\\[xX][0-9a-fA-F]+) "break" { return KW_BREAK; } "return" { return KW_RET; } "sizeof" { return KW_SIZEOF; } +"typedef" { return KW_TYPEDEF; } {letter}({letter}|{digit})* { yylval.strval = strdup(yytext); - return IDENTIFIER; + return is_identifier(yytext) ? IDENTIFIER : USER_TYPE; } ({digit}+)|(0[xX][0-9a-fA-F]+) { diff --git a/cibic.y b/cibic.y index c4e45e2..c3d65ac 100644 --- a/cibic.y +++ b/cibic.y @@ -9,17 +9,17 @@ struct CNode *cnode; } %error-verbose -%token IDENTIFIER "identifier" INT_CONST "integer constant" CHAR_CONST "character constant" STR_CONST "string constant" -%token KW_VOID "void" KW_CHAR "char" KW_INT "int" KW_STRUCT "struct" KW_UNION "union" KW_IF "if" KW_ELSE "else" KW_WHILE "while" +%token IDENTIFIER "identifier" INT_CONST "integer constant" CHAR_CONST "character constant" STR_CONST "string constant" USER_TYPE "typedef name" +%token KW_VOID "void" KW_CHAR "char" KW_INT "int" KW_STRUCT "struct" KW_UNION "union" KW_IF "if" KW_ELSE "else" KW_WHILE "while" KW_TYPEDEF "typedef" %token KW_FOR "for" KW_CONT "continue" KW_BREAK "break" KW_RET "ret" KW_SIZEOF "sizeof" %token OPT_OR "||" OPT_AND "&&" OPT_EQ "==" OPT_NE "!=" OPT_LE "<=" OPT_GE ">=" OPT_SHL "<<" OPT_SHR ">>" OPT_INC "++" OPT_DEC "--" OPT_PTR "->" %token ASS_MUL "*=" ASS_DIV "/=" ASS_MOD "%=" ASS_ADD "+=" ASS_SUB "-=" ASS_SHL "<<=" ASS_SHR ">>=" ASS_AND "&=" ASS_XOR "^=" ASS_OR "|=" %token UNKNOWN "stray character" %token END 0 "end of file" %type INT_CONST -%type IDENTIFIER STR_CONST CHAR_CONST +%type IDENTIFIER STR_CONST CHAR_CONST USER_TYPE %type additive_operator assignment_operator equality_operator multiplicative_operator relational_operator shift_operator struct_or_union unary_operator -%type additive_expression and_expression arguments array_initializer assignment_expression cast_expression comp_decls compound_statement comp_stmts constant_expression declaration declarator declarators equality_expression exclusive_or_expression expression expression_statement function_definition identifier inclusive_or_expression init_declarator init_declarators initializer iteration_statement jump_statement logical_and_expression logical_or_expression multiplicative_expression optional_exp parameters plain_declaration direct_declarator postfix postfix_expression primary_expression prog_list program relational_expression selection_statement shift_expression statement struct_field struct_fields type_name type_specifier unary_expression abstract_declarator direct_abstract_declarator direct_abstract_declarator_opt abstract_declarator_opt +%type additive_expression and_expression arguments array_initializer assignment_expression cast_expression comp_decls compound_statement comp_stmts constant_expression declaration declarator declarators equality_expression exclusive_or_expression expression expression_statement function_definition identifier inclusive_or_expression init_declarator init_declarators initializer iteration_statement jump_statement logical_and_expression logical_or_expression multiplicative_expression optional_exp parameters plain_declaration direct_declarator postfix postfix_expression primary_expression prog_list program relational_expression selection_statement shift_expression statement struct_field struct_fields type_name type_specifier unary_expression abstract_declarator direct_abstract_declarator direct_abstract_declarator_opt abstract_declarator_opt user_type %start program %% program @@ -32,15 +32,22 @@ prog_list | prog_list function_definition { $$ = cnode_list_append($1, $2); } declaration - : type_specifier ';' { + : KW_TYPEDEF type_specifier { enter_typedef(); } declarators ';' { + $$ = cnode_add_loc(cnode_create_typedef( + $2, + cnode_add_loc(cnode_list_wrap(DECLRS, $4), @4)), @$); + exit_declr(); + } + | type_specifier ';' { $$ = cnode_add_loc(cnode_create_decl( $1, cnode_list_wrap(INIT_DECLRS, cnode_create_nop())), @$); } - | type_specifier init_declarators ';' { + | type_specifier init_declarators ';' { $$ = cnode_add_loc(cnode_create_decl( $1, cnode_add_loc(cnode_list_wrap(INIT_DECLRS, $2), @2)), @$); + exit_declr(); } function_definition @@ -75,18 +82,25 @@ array_initializer $$ = cnode_list_append(cnode_add_loc($1, @1), $3); } type_specifier - : KW_VOID { $$ = cnode_add_loc(cnode_create_type_spec(KW_VOID, 0), @$); } - | KW_CHAR { $$ = cnode_add_loc(cnode_create_type_spec(KW_CHAR, 0), @$); } - | KW_INT { $$ = cnode_add_loc(cnode_create_type_spec(KW_INT, 0), @$); } + : KW_VOID { $$ = cnode_add_loc(cnode_create_type_spec(KW_VOID, 0), @$); enter_declr(); } + | KW_CHAR { $$ = cnode_add_loc(cnode_create_type_spec(KW_CHAR, 0), @$); enter_declr(); } + | KW_INT { $$ = cnode_add_loc(cnode_create_type_spec(KW_INT, 0), @$); enter_declr(); } | struct_or_union identifier '{' struct_fields '}' { $$ = cnode_add_loc(cnode_create_type_spec($1, 2, $2, cnode_add_loc(cnode_list_wrap(FIELDS, $4), @4)), @$); + enter_declr(); } | struct_or_union '{' struct_fields '}' { $$ = cnode_add_loc(cnode_create_type_spec($1, 2, cnode_create_nop(), cnode_add_loc(cnode_list_wrap(FIELDS, $3), @3)), @$); + enter_declr(); } | struct_or_union identifier { $$ = cnode_add_loc(cnode_create_type_spec($1, 2, $2, cnode_create_nop()), @$); + enter_declr(); } + | user_type { $$ = cnode_add_loc(cnode_create_type_spec(USER_TYPE, 1, $1), @$); enter_declr(); } + +user_type + : USER_TYPE { $$ = cnode_add_loc(cnode_create_identifier($1), @$); } struct_fields : struct_field @@ -94,8 +108,10 @@ struct_fields struct_field : type_specifier declarators ';' { $$ = cnode_add_loc( - cnode_create_struct_field($1, - cnode_add_loc(cnode_list_wrap(DECLRS, $2), @2)), @$); + cnode_create_struct_field( + $1, + cnode_add_loc(cnode_list_wrap(DECLRS, $2), @2)), @$); + exit_declr(); } struct_or_union @@ -103,10 +119,13 @@ struct_or_union | KW_UNION { $$ = KW_UNION; } plain_declaration - : type_specifier declarator { $$ = cnode_add_loc(cnode_create_plain_decl($1, $2), @$); } + : type_specifier declarator { + $$ = cnode_add_loc(cnode_create_plain_decl($1, $2), @$); + exit_declr(); + } direct_declarator - : identifier + : identifier { push($1->rec.strval); } | '(' declarator ')' { $$ = $2; } | direct_declarator '(' parameters ')' { $$ = cnode_add_loc(cnode_create_declr( @@ -134,10 +153,11 @@ expression_statement | expression ';' { $$ = cnode_add_loc(cnode_create_stmt(STMT_EXP, 1, $1), @$); } compound_statement - : '{' comp_decls comp_stmts '}' { + : { exit_declr(); enter_block(); } '{' comp_decls comp_stmts '}' { $$ = cnode_add_loc( - cnode_create_stmt(STMT_COMP, 2, cnode_add_loc(cnode_list_wrap(COMP_DECLS, $2), @2), - cnode_add_loc(cnode_list_wrap(COMP_STMTS, $3), @3)), @$); + cnode_create_stmt(STMT_COMP, 2, cnode_add_loc(cnode_list_wrap(COMP_DECLS, $3), @3), + cnode_add_loc(cnode_list_wrap(COMP_STMTS, $4), @4)), @$); + exit_block(); } comp_decls @@ -291,7 +311,9 @@ cast_expression type_name : type_specifier abstract_declarator_opt { - $$ = cnode_add_loc(cnode_create_declr(0, 2, $1, $2), @$); } + $$ = cnode_add_loc(cnode_create_declr(0, 2, $1, $2), @$); + exit_declr(); + } abstract_declarator_opt : { $$ = cnode_create_nop(); } diff --git a/main.c b/main.c index dafcf29..df9807a 100644 --- a/main.c +++ b/main.c @@ -39,11 +39,13 @@ void print_ast() { fprintf(stderr, "AST for file: \"%s\"\n", fname); else fprintf(stderr, "AST for stdin\n"); + cibic_init(); yyparse(); cnode_debug_print(ast_root, 1); } void print_sem() { + cibic_init(); yyparse(); semantics_check(ast_root); /* cnode_debug_print(ast_root, 1); */ diff --git a/semantics.c b/semantics.c index ea64905..45571a0 100644 --- a/semantics.c +++ b/semantics.c @@ -69,8 +69,13 @@ static void warning_print(CNode *ast, const char *fmt, ...) { } const char *csymbol_getname(CSymbol_t sym) { - return (sym->kind == CVAR) ? - sym->rec.var->name : sym->rec.type->name; + switch (sym->kind) + { + case CVAR: return sym->rec.var->name; + case CTYPE: return sym->rec.type->name; + case CDEF: return sym->rec.def->name; + } + return NULL; } #ifdef CIBIC_DEBUG @@ -195,6 +200,18 @@ int cscope_push_type(CScope_t cs, CType_t type, int nspace) { return 1; } +int cscope_push_def(CScope_t cs, CDef_t def, int nspace) { + CSymbol_t p = NEW(CSymbol); + p->kind = CDEF; + p->rec.def = def; + if (!cscope_push(cs, p, nspace)) + { + free(p); + return 0; + } + return 1; +} + void cscope_enter(CScope_t cs) { CSNode *np = NEW(CSNode); np->next = cs->top; @@ -273,10 +290,17 @@ unsigned int bkdr_hash(const char *str) { const char *csymbol_print(void *csym) { CSymbol_t p = (CSymbol_t)csym; static char buff[MAX_DEBUG_PRINT_BUFF]; - if (p->kind == CVAR) - sprintf(buff, "%s@%lx", p->rec.var->name, (size_t)p->rec.var); - else - sprintf(buff, "%s@%lx", p->rec.type->name, (size_t)p->rec.type); + switch (p->kind) + { + case CVAR: + sprintf(buff, "%s@%lx", p->rec.var->name, (size_t)p->rec.var); + break; + case CTYPE: + sprintf(buff, "%s@%lx", p->rec.type->name, (size_t)p->rec.type); + break; + case CDEF: + sprintf(buff, "%s@%lx", p->rec.def->name, (size_t)p->rec.def); + } return buff; } @@ -316,6 +340,11 @@ void cvar_print(CVar_t cv) { ctype_print(cv->type); } +void cdef_print(CDef_t cd) { + fprintf(stderr, "[def@%lx:%s]->", (size_t)cd, cd->name); + ctype_print(cd->type); +} + void ctype_print(CType_t ct) { switch (ct->type) { @@ -509,6 +538,14 @@ CType_t semantics_type_spec(CNode *p, CScope_t scope) { type = struct_type_merge(type, scope); } break; + case USER_TYPE: + { + CHECK_TYPE(p->chd, ID); + CSymbol_t lu = cscope_lookup(scope, p->chd->rec.strval, NS_ID); + assert(lu && lu->kind == CDEF); /* parser guarantees this */ + type = lu->rec.def->type; + } + break; default: assert(0); } return type; @@ -724,8 +761,25 @@ void semantics_initr(CNode *p, CScope_t scope, CType_t type) { } } +void semantics_typedef(CNode *p, CType_t type, CScope_t scope) { + CNode *declr = p->chd->next; + for (p = declr->chd; p; p = p->next) + { + CVar_t var = semantics_declr(p, type, scope, 0); + CDef_t def = cdef_create(var->name, var->type, var->ast); + if (!cscope_push_def(scope, def, NS_ID)) + { + CSymbol_t lu = cscope_lookup(scope, def->name, NS_ID); + if (lu->kind != CDEF) + ERROR((def->ast, "'%s' redeclared as different kind of symbol", def->name)); + /* FIXME: `typedef int a()` is different from typedef `int a(int)` */ + if (!is_same_type(lu->rec.type, def->type)) + ERROR((def->ast, "conflicting types of '%s'", def->name)); + } + } +} + CVar_t semantics_decl(CNode *p, CScope_t scope) { - CHECK_TYPE(p, DECL); CNode *declr = p->chd->next; CType_t type = semantics_type_spec(p->chd, scope); CVar_t res = NULL; @@ -736,6 +790,12 @@ CVar_t semantics_decl(CNode *p, CScope_t scope) { cscope_push_type(scope, type, NS_TAG); useful = 1; } + if (p->type == TYPEDEF) + { + semantics_typedef(p, type, scope); + return NULL; + } + CHECK_TYPE(p, DECL); if (declr->chd->type != NOP) { CNode *p; @@ -746,18 +806,19 @@ CVar_t semantics_decl(CNode *p, CScope_t scope) { if (var->type->type == CFUNC) { CType_t func = var->type; + CSymbol_t lu; func->name = var->name; + if (initr->type == INITR) + ERROR((var->ast, "function '%s' is initialized like a variable", func->name)); if (!cscope_push_type(scope, func, NS_ID)) { - CSymbol_t lu = cscope_lookup(scope, func->name, NS_ID); + lu = cscope_lookup(scope, func->name, NS_ID); if (lu->kind != CTYPE) ERROR((func->ast, "'%s' redeclared as different kind of symbol", func->name)); if (!is_same_type(lu->rec.type, func)) ERROR((func->ast, "conflicting types of '%s'", func->name)); type_merge(lu->rec.type, func); } - if (initr->type == INITR) - ERROR((var->ast, "function '%s' is initialized like a variable", func->name)); } else { @@ -1542,7 +1603,7 @@ void semantics_check(CNode *p) { { case FUNC_DEF: semantics_func(p, scope); break; - case DECL: + case DECL: case TYPEDEF: semantics_decl(p, scope); break; default: assert(0); } @@ -1555,22 +1616,71 @@ void semantics_check(CNode *p) { for (p = scope->ids->head[i]; p; p = p->next) { CSymbol_t tp = (CSymbol_t)(p->val); - if (tp->kind == CVAR) - cvar_print(tp->rec.var); - else - ctype_print(tp->rec.type); + switch (tp->kind) + { + case CVAR: cvar_print(tp->rec.var); break; + case CTYPE: ctype_print(tp->rec.type); break; + case CDEF: cdef_print(tp->rec.def); break; + } fprintf(stderr, "\n"); } for (i = 0; i < MAX_TABLE_SIZE; i++) for (p = scope->tags->head[i]; p; p = p->next) { CSymbol_t tp = (CSymbol_t)(p->val); - if (tp->kind == CVAR) - cvar_print(tp->rec.var); - else - ctype_print(tp->rec.type); + switch (tp->kind) + { + case CVAR: cvar_print(tp->rec.var); break; + case CTYPE: ctype_print(tp->rec.type); break; + case CDEF: cdef_print(tp->rec.def); break; + } fprintf(stderr, "\n"); } } cnode_debug_print(ast_root, 1); } + +static CScope_t typedef_scope; +static enum { + NONE, + TYPEDEF_DECLR, + OTHER_DECLR +} typedef_state; + +void cibic_init() { + typedef_scope = cscope_create(); + typedef_state = NONE; +} + +int is_identifier(const char *name) { + CSymbol_t lu; + /* the parser is reading declarators */ + if (typedef_state == OTHER_DECLR) return 1; + /* the parser is reading typedef */ + if (typedef_state == TYPEDEF_DECLR) return 1; + /* no info about name, assume it to be an id by default */ + lu = cscope_lookup(typedef_scope, name, NS_ID); + if (!lu) return 1; + return lu->kind == CVAR; +} + +void push(const char *name) { + if (typedef_state == TYPEDEF_DECLR) + cscope_push_type(typedef_scope, ctype_create(name, 0, NULL), NS_ID); + else + cscope_push_var(typedef_scope, cvar_create(name, NULL, NULL), NS_ID); +} + +CDef_t cdef_create(const char *name, CType_t type, CNode *ast) { + CDef_t cd = NEW(CDef); + cd->name = name; + cd->type = type; + cd->ast = ast; + return cd; +} + +void enter_block() { cscope_enter(typedef_scope); } +void exit_block() { cscope_exit(typedef_scope); } +void enter_typedef() { typedef_state = TYPEDEF_DECLR; } +void enter_declr() { typedef_state = OTHER_DECLR; } +void exit_declr() { typedef_state = NONE; } diff --git a/semantics.h b/semantics.h index bcd8ca8..84dc9dc 100644 --- a/semantics.h +++ b/semantics.h @@ -10,6 +10,8 @@ typedef struct CVar CVar; typedef CVar *CVar_t; typedef struct CSymbol CSymbol; typedef CSymbol *CSymbol_t; +typedef struct CDef CDef; +typedef CDef *CDef_t; struct CVar { const char *name; @@ -121,19 +123,29 @@ typedef struct ExpType { struct CSymbol { enum { CTYPE, - CVAR + CVAR, + CDEF } kind; union { CType_t type; CVar_t var; + CDef_t def; } rec; }; const char *csymbol_print(void *csym); const char *csym_getname(CSymbol_t csym); +struct CDef { + const char *name; + CType_t type; + CNode *ast; +}; +CDef_t cdef_create(const char *name, CType_t type, CNode *ast); + CScope_t cscope_create(); CSymbol_t cscope_lookup(CScope_t cs, const char *name, int nspace); int cscope_push_var(CScope_t cs, CVar_t var, int nspace); +int cscope_push_def(CScope_t cs, CDef_t def, int nspace); int cscope_push_type(CScope_t cs, CType_t type, int nspace); void cscope_enter(CScope_t cs); void cscope_exit(CScope_t cs); @@ -143,4 +155,14 @@ unsigned int bkdr_hash(const char *str); const char *ctable_cvar_print(void *var); void semantics_check(CNode *ast); +int is_identifier(const char *name); +void declr_begin(); +void declr_end(); +void push(const char *name); +void cibic_init(); +void enter_block(); +void exit_block(); +void enter_typedef(); +void exit(); +void enter_declr(); #endif diff --git a/test_all.sh b/test_all.sh index fcf757c..6a9db22 100755 --- a/test_all.sh +++ b/test_all.sh @@ -8,9 +8,10 @@ do gcc $file -o /dev/null &> /dev/null gcc_ret="$?" ./cibic $file &> /dev/null - if [ $? -ne $gcc_ret ]; then + ret=$? + if [ $ret -ne $gcc_ret ]; then echo "Failed on $file" else - echo "ok $file" + echo "ok $file: $ret" fi done diff --git a/testcases/conflict.c b/testcases/conflict.c new file mode 100644 index 0000000..f2798e7 --- /dev/null +++ b/testcases/conflict.c @@ -0,0 +1,4 @@ +int f(int a, char b); +int f(int a); +int main() { +} diff --git a/testcases/pass.c b/testcases/pass.c index bf995ac..e567680 100644 --- a/testcases/pass.c +++ b/testcases/pass.c @@ -109,6 +109,21 @@ struct Node {int x, y;} n; int again; int again; +typedef int def; +int typedef1() { + int def; /* overrides outer typedef */ + def = 1; +} +typedef int *ptr1; +int typedef2() { + typedef int **ptr2; + { + typedef int ***ptr3; + ptr3 ptr2; + ptr3 ptr1; + } +} + int main() { n.x = 1; n.y = 2; -- cgit v1.2.3-70-g09d2