aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ast.c15
-rw-r--r--ast.h2
-rw-r--r--cibic.l4
-rw-r--r--cibic.y56
-rw-r--r--main.c2
-rw-r--r--semantics.c148
-rw-r--r--semantics.h24
-rwxr-xr-xtest_all.sh5
-rw-r--r--testcases/conflict.c4
-rw-r--r--testcases/pass.c15
10 files changed, 235 insertions, 40 deletions
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<intval> INT_CONST
-%type<strval> IDENTIFIER STR_CONST CHAR_CONST
+%type<strval> IDENTIFIER STR_CONST CHAR_CONST USER_TYPE
%type<intval> additive_operator assignment_operator equality_operator multiplicative_operator relational_operator shift_operator struct_or_union unary_operator
-%type<cnode> 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<cnode> 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;