scc

Simple C99 Compiler
Log | Files | Refs | README | LICENSE

commit b95cc0c19c628ad8cf1f0e99548dadaff35a786f
parent 3ebea5faa5010e59f17ad4df846d0b5440c5f82c
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Fri,  8 Jun 2012 15:34:01 +0200

Added symbol table

The symbol table is a hash table, where collation area is implemented like a
double linked list with a dummy header. All the item presents in the table
are stored in a single linked list, so it is easy run over the last symbols
and remove all of them each time a block ends.

Diffstat:
decl.c | 8++++++--
expr.c | 2++
flow.c | 9+++++----
lex.c | 2++
main.c | 2++
symbol.c | 114+++++++++++++++++++++++++++++++++++--------------------------------------------
symbol.h | 15+++++++++++----
tokens.h | 4++--
8 files changed, 81 insertions(+), 75 deletions(-)

diff --git a/decl.c b/decl.c @@ -6,6 +6,7 @@ #include "tokens.h" #include "types.h" #include "syntax.h" +#include "symbol.h" char parser_out_home; @@ -20,8 +21,11 @@ static void dirdcl(void) if (accept('(')) { declarator(); expect(')'); - } else if (accept(IDENTIFIER)) { - ; + } else if (yytoken == IDENTIFIER) { + if (yyval.sym && yyval.sym->level == nested_level) + error("redeclaration of '%s'", yytext); + addsym(yytext, yyhash); + next(); } else { error("expected '(' or identifier before of '%s'", yytext); } diff --git a/expr.c b/expr.c @@ -14,6 +14,8 @@ static void primary(void) puts("primary"); switch (yytoken) { case IDENTIFIER: + if (!yyval.sym) + error("'%s' undeclared", yytext); case CONSTANT: case STRING_LITERAL: next(); diff --git a/flow.c b/flow.c @@ -1,12 +1,10 @@ #include <stdio.h> +#include "symbol.h" #include "tokens.h" #include "syntax.h" - -unsigned char nested_level; - void stmt(void); static void do_goto(void) @@ -131,11 +129,14 @@ void compound(void) { puts("compound"); if (accept('{')) { - ++nested_level; + struct symctx ctx; + + new_ctx(&ctx); while (decl()) /* nothing */; while (!accept('}')) stmt(); + del_ctx(); } puts("leaving compound"); } diff --git a/lex.c b/lex.c @@ -55,6 +55,7 @@ static struct keyword { static struct keyword *khash[NR_KWD_HASH]; static FILE *yyin; +union yyval yyval; unsigned char yytoken; unsigned char yyhash; char yytext[TOKSIZ_MAX + 1]; @@ -200,6 +201,7 @@ static unsigned char iden(void) if (!strcmp(kwp->str, yytext)) return kwp->tok; } + yyval.sym = lookupsym(yytext, yyhash); return IDENTIFIER; } diff --git a/main.c b/main.c @@ -7,6 +7,7 @@ extern void open_file(const char *file); extern void init_lex(); +extern void init_symbol(); struct user_opt user_opt; @@ -15,6 +16,7 @@ struct user_opt user_opt; int main(int argc, char *argv[]) { init_lex(); + init_symbol(); open_file(NULL); for (next(); yytoken != EOFTOK; decl()) /* nothing */; diff --git a/symbol.c b/symbol.c @@ -1,99 +1,87 @@ - +#include <stdlib.h> #include <string.h> #include "symbol.h" +#define xmalloc malloc +#define xstrdup strdup #define NR_SYM_HASH 32 struct symhash { - struct symbol *buf[NR_SYM_HASH]; + struct symbol buf[NR_SYM_HASH]; struct symbol *top; }; -struct symctx { - struct symbol *siden; - struct symbol *sstruct; - struct symbol *sgoto; - struct symctx *next; -}; - - - -static struct symctx global_ctx; -static struct symctx *ctxp = &global_ctx; -struct symhash *siden = (struct symhash *) {0}; -struct symhash *sgoto = (struct symhash *) {0}; - -struct symhash *sstruct = (struct symhash *) {0}; - - +unsigned char nested_level; +static struct symhash iden_hash; +static struct symctx ctx_base; +static struct symctx *ctx_head = &ctx_base; - - -void new_ctx(struct symctx *ctx) +static void del_hash_ctx(struct symhash *htable, struct symbol *lim) { - ctx->siden = siden->top; - ctx->sstruct = sstruct->top; - ctx->sgoto = sgoto->top; - ctx->next = ctxp; - ctxp = ctx; -} - + register struct symbol *bp; -/* - * WARNING: This function is not portable and waits that incremental calls - * to alloca return decremented address - */ -static void del_hash_ctx(struct symhash *h, struct symbol *const top) -{ - register struct symbol **bp; - static struct symbol **lim; - - lim = h->buf + NR_SYM_HASH; - for (bp = h->buf; bp < lim; bp++) { - register struct symbol *aux; - for (aux = *bp; aux < top; *bp = aux = aux->next) { - if (aux == h->top) - h->top = aux; - } + for (bp = htable->top; bp && bp != lim; bp = bp->next) { + register struct symbol *next = bp->h_next, *prev = bp->h_prev; + prev->h_next = next; + next->h_prev = prev; + free(bp->str); + free(bp); } } +void new_ctx(struct symctx *ctx) +{ + ++nested_level; + ctx->next = ctx_head; + ctx_head = ctx; + ctx->iden = iden_hash.top; +} void del_ctx(void) { - del_hash_ctx(siden, ctxp->siden); - del_hash_ctx(sstruct, ctxp->sstruct); - del_hash_ctx(sgoto, ctxp->sgoto); /* TODO: correct handling in goto */ + --nested_level; + del_hash_ctx(&iden_hash, ctx_head->next->iden); } - - - -struct symbol *addsym(struct symhash *h, - struct symbol *sym, unsigned char hash) - +struct symbol *addsym(const char *s, unsigned char key) { - static unsigned char key; + static struct symbol *head; + register struct symbol *sym, *next; - key = hash % NR_SYM_HASH; - h->top = sym; - sym->next = h->buf[key]; - return h->buf[key] = sym; -} + sym = xmalloc(sizeof(*sym)); + sym->str = xstrdup(s); + sym->next = iden_hash.top; + iden_hash.top = sym; + head = &iden_hash.buf[key], next = head->h_next; + sym->h_next = next; + sym->h_prev = next->h_prev; + head->h_next = sym; + next->h_prev = sym; + return sym; +} -struct symbol *findsym(struct symhash *h, char *s, unsigned char hash) +struct symbol *lookupsym(char *s, unsigned char key) { - register struct symbol *bp; + register struct symbol *bp, *head; - for (bp = h->buf[hash % NR_SYM_HASH]; bp; bp = bp->next) { + head = &iden_hash.buf[key]; + for (bp = head->h_next; bp != head; bp = bp->next) { if (!strcmp(bp->str, s)) return bp; } return NULL; } + +void init_symbol(void) +{ + struct symbol *bp; + + for (bp = iden_hash.buf; bp < &iden_hash.buf[NR_SYM_HASH]; ++bp) + bp->h_next = bp->h_prev = bp; +} diff --git a/symbol.h b/symbol.h @@ -8,15 +8,22 @@ struct type; struct symbol { char *str; + unsigned char level; struct type *type; struct symbol *next; + struct symbol *h_next, *h_prev; }; -struct symhash; -extern struct symhash *siden, *sgoto, *sstruct; +struct symctx { + struct symbol *iden; + struct symctx *next; +}; + -struct symbol * -addsym(struct symhash *h, struct symbol *sym, unsigned char hash); +extern void new_ctx(struct symctx *ctx); +extern void del_ctx(void); +extern struct symbol *addsym(const char *s, unsigned char key); +extern struct symbol *lookupsym(char *s, unsigned char key); #endif diff --git a/tokens.h b/tokens.h @@ -37,10 +37,10 @@ enum { union yyval { struct symbol *sym; -} yyval; - +}; +extern union yyval yyval; extern char yytext[]; extern unsigned char yyhash; extern size_t yylen;