diff options
| -rw-r--r-- | check/main.p | 34 | ||||
| -rw-r--r-- | check/nesting.p | 69 | ||||
| -rw-r--r-- | main.c | 7 | ||||
| -rw-r--r-- | makefile | 21 | ||||
| -rw-r--r-- | node.c | 17 | ||||
| -rw-r--r-- | node.h | 6 | ||||
| -rw-r--r-- | pc.l | 8 | ||||
| -rw-r--r-- | pc.y | 67 | ||||
| -rw-r--r-- | scope.c | 146 | ||||
| -rw-r--r-- | scope.h | 27 | ||||
| -rw-r--r-- | sem_check.c | 36 | ||||
| -rw-r--r-- | sem_check.h | 8 | ||||
| -rw-r--r-- | tree.c | 7 | ||||
| -rw-r--r-- | tree.h | 3 |
14 files changed, 421 insertions, 35 deletions
diff --git a/check/main.p b/check/main.p new file mode 100644 index 0000000..f05808b --- /dev/null +++ b/check/main.p @@ -0,0 +1,34 @@ +program main ( input, output ); + + var a, b: integer; + var x,y,z: real; + var ai :array [1..10] of integer; + procedure boo (n: integer); + var a,c: integer; + begin + a := n + end; + function bar (a: integer) : real; + var test:integer; + begin + test := 2; + a := 2 + end; + procedure foo; + begin + a := 33333; + x := 1e10; + z := 1e-10; + y := 2.5543e-2 + end; +begin +{ TEST } + + a := 1; + x := 3.14; + b := a + 35; + (* test *) + for c := 0 to 10 do begin + for a:= 10 downto 0 do b := a - c + end +end. diff --git a/check/nesting.p b/check/nesting.p new file mode 100644 index 0000000..6d24b6b --- /dev/null +++ b/check/nesting.p @@ -0,0 +1,69 @@ + +program main ( input, output ); + + var a, b: integer; + var x,y,z: real; + var ai :array [1..10] of integer; + procedure boo (n: integer); + var a,c: integer; + begin + a := n + end; + function bar (a: integer) : real; + var test:integer; + begin + test := 2; + a := 2 + end; + procedure foo; + procedure foo2; + procedure foo13; + procedure foo4; + procedure foo5; + procedure foo6; + procedure foo7; + procedure foo46; + procedure fooaoesut; + procedure foosathst; + procedure foothsth; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; + begin + a := 33333 + end; +begin +{ TEST } + + a := 1; + x := 3.14; + b := a + 35 + (* test *) +end. @@ -2,12 +2,16 @@ #include <stdlib.h> #include <assert.h> +#include "node.h" +#include "scope.h" #include "y.tab.h" #include "pc.h" extern char *yytext; extern int line_num; +scope *cur_scope; + char* pretty_type(t) int t; { @@ -134,6 +138,9 @@ char* msg; int main() { + cur_scope = mkscope(); + assert(cur_scope); + yyparse(); return 0; @@ -1,21 +1,24 @@ -CC = gcc +CC = tcc FLAGS = -g YACC = yacc LEX = lex -mypc: y.tab.o lex.yy.o tree.o node.o pc.o - $(CC) $(FLAGS) -o mypc main.o tree.o node.o y.tab.o lex.yy.o -lfl -ly +mypc: y.tab.o lex.yy.o tree.o scope.o node.o pc.o sem_check.o + $(CC) $(FLAGS) -o mypc main.o tree.o scope.o sem_check.o node.o y.tab.o lex.yy.o -lfl -ly -pc.o: main.c pc.h +pc.o: main.c headers $(CC) $(FLAGS) -c main.c -tree.o: tree.c tree.h +tree.o: tree.c headers $(CC) $(FLAGS) -c tree.c -hash.o: hash.c hash.h - $(CC) $(FLAGS) -c hash.c +sem_check.o: sem_check.c headers + $(CC) $(FLAGS) -c sem_check.c -node.o: node.c node.h +scope.o: scope.c headers + $(CC) $(FLAGS) -c scope.c + +node.o: node.c headers $(CC) $(FLAGS) -c node.c y.tab.o: y.tab.c @@ -30,5 +33,7 @@ y.tab.c: pc.y lex.yy.c: pc.l $(LEX) -l pc.l +headers: pc.h tree.h sem_check.h y.tab.h scope.h node.h y.tab.c + clean: rm -f mypc *.o y.tab.* lex.yy.* @@ -19,7 +19,7 @@ char *str; } /* helpers */ -node* search(root, str) +node* list_search(root, str) node *root; char *str; { @@ -33,7 +33,7 @@ char *str; return NULL; } -node* insert(root, str) /*TODO change to accept double pointer*/ +node* list_insert(root, str) /*TODO change to accept double pointer*/ node *root; char * str; { @@ -41,3 +41,16 @@ char * str; p->next = root; return p; } + +void free_list(n) +node *n; +{ + node *tmp; + + for(tmp = n; tmp;) { + n = tmp->next; + free(tmp); + tmp = NULL; + tmp = n; + } +} @@ -13,7 +13,9 @@ typedef struct node_s { node* mknode(char *); /* helpers */ -node* search(node*, char *); -node* insert(node*, char*); +node* list_search(node*, char *); +node* list_insert(node*, char*); + +void free_list(node*); #endif @@ -1,9 +1,11 @@ %{ - +#include "node.h" +#include "scope.h" #include "y.tab.h" #include "pc.h" int line_num=1; +extern scope *cur_scope; %} @@ -39,13 +41,13 @@ id [A-Za-z][A-Za-z0-9_]* "procedure" { debug_print(PROC, NULL); - /*s = push_scope(s);*/ + push_scope(&cur_scope); return PROC; } "function" { debug_print(FUNC, NULL); - /*s = push_scope(s);*/ + push_scope(&cur_scope); return FUNC; } @@ -3,17 +3,15 @@ #include <stddef.h> #include "node.h" +#include "scope.h" #include "tree.h" #include "y.tab.h" #include "pc.h" -/*#include "sem_check.h"*/ +#include "sem_check.h" -/* -TODO: -- Add checkid() to counter mkid() -*/ extern int yylex(); +extern scope *cur_scope; %} @@ -71,6 +69,8 @@ extern int yylex(); %type <tval> simple_expr %type <tval> id_list +%type <tval> param_list +%type <tval> arguments %type <tval> expr_list %type <tval> statement @@ -98,11 +98,20 @@ program id_list :ID { - $$ = mkid($1); + /*TODO remove check_ids*/ + node *tmp; + check_id(cur_scope, $1); + + tmp = scope_insert(cur_scope, $1); + $$ = mkid(tmp); } |id_list ',' ID { - $$ = mktree(LIST, $1, mkid($3)); + node *tmp; + + check_id(cur_scope, $3); + tmp = scope_insert(cur_scope, $3); + $$ = mktree(LIST, $1, mkid(tmp)); } ; @@ -148,21 +157,31 @@ sub_prog_declaration sub_prog_declarations compound_statement { + pop_scope(&cur_scope); } ; +/*push_scope called in pc.l*/ sub_prog_head :FUNC ID arguments ':' standard_type ';' { + check_id(cur_scope->prev, $2); + scope_insert(cur_scope->prev, $2); + + cur_scope->ret_var = scope_insert(cur_scope, $2); + cur_scope->ret_var->var_type = $5; } |PROC ID arguments ';' { + check_id(cur_scope->prev, $2); + scope_insert(cur_scope->prev, $2); } ; arguments :'(' param_list ')' { + $$ = $2; } |/*empty*/ ; @@ -170,9 +189,11 @@ arguments param_list :id_list ':' type { + $$ = $1; } |param_list ';' id_list ':' type { + $$ = mktree(LIST, $1, $3); } ; @@ -238,22 +259,31 @@ TD: TO | DT; var :ID { - $$ = mkid($1); + $$ = mkid(scope_insert(cur_scope,$1)); } |ID '[' expr ']' { - $$ = mktree(ARRAY_ACCESS, mkid($1), $3); + node* tmp; + tmp = scope_insert(cur_scope, $1); + + $$ = mktree(ARRAY_ACCESS, mkid(tmp), $3); } ; proc_statement :ID { - $$ = mkid($1); + node *tmp; + + tmp = check_exists(cur_scope, $1); + $$ = mktree(PCALL, mkid(tmp), NULL); } |ID '(' expr_list ')' { - $$ = mktree(PCALL, mkid($1), $3); + node *tmp; + + tmp = check_exists(cur_scope, $1); + $$ = mktree(PCALL, mkid(tmp), $3); } ; @@ -304,15 +334,24 @@ term factor :ID { - $$ = mkid($1); + node *tmp; + + tmp = check_exists(cur_scope, $1); + $$ = mkid(tmp); } |ID '[' expr ']' { - $$ = mktree(ARRAY_ACCESS, mkid($1), $3); + node *tmp; + + tmp = check_exists(cur_scope, $1); + $$ = mktree(ARRAY_ACCESS, mkid(tmp), $3); } |ID '(' expr_list ')' { - $$ = mktree(FCALL, mkid($1), $3); + node *tmp; + + tmp = check_exists(cur_scope, $1); + $$ = mktree(FCALL, mkid(tmp), $3); } |INUM { @@ -0,0 +1,146 @@ +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include <string.h> + +#include "node.h" +#include "scope.h" + +scope* mkscope() +{ + int i; + + scope *p = malloc(sizeof(scope)); + assert(p); + + for (i = 0; i < HASH_SIZE; i++) + p->table[i] = NULL; + + p->prev = NULL; + p->ret_var= NULL; + + return p; +} + +void free_scope(s) +scope *s; +{ + int i; + + if (!s) + return; + + for (i = 0; i < HASH_SIZE; i++) { + free_list(s->table[i]); + } + + free(s); + s = NULL; +} + +/*Copied from Compilers, Aho*/ +#define EOS '\0' +int hashpjw(s) +char* s; +{ + char *p; + unsigned h = 0, g; + + for (p = s; *p != EOS; p++) { + h = (h<<4) + *p; + if (g = h & 0xf0000000) { + h^= g>>24; + h^= g; + } + } + + return h % HASH_SIZE; +} + +void push_scope(root) +scope **root; +{ + scope *tmp = mkscope(); + + assert(tmp); + + tmp->prev = *root; + *root = tmp; +} + +void pop_scope(root) +scope **root; +{ + scope *tmp; + + if (!*root) + return; + + tmp = *root; + *root = (*root)->prev; + + free_scope(tmp); +} + +node* scope_insert(root, name) +scope *root; +char *name; +{ + int hash = hashpjw(name); + + node *tmp = root->table[hash]; + return root->table[hash] = list_insert(tmp, name); +} + +node* scope_search(root, name) +scope *root; +char *name; +{ + int hash = hashpjw(name); + + node *tmp = root->table[hash]; + return list_search(tmp, name); +} + +node* scope_search_all(root, name) +scope *root; +char *name; +{ + scope *p; + node *tmp; + + for (p = root; p; p = p->prev) + if (tmp = scope_search(p, name)) + return tmp; + + return NULL; +} + +node* scope_safe_search(root, name) +scope *root; +char *name; +{ + scope *p; + node *tmp; + + for (p = root; p; p = p->prev) { + if (tmp = scope_search(p, name)) + return tmp; + if (p->ret_var) + return NULL; + } + + return NULL; +} + +void print_scope(s) +scope *s; +{ + int i; + node * tmp; + for (i = 0; i < HASH_SIZE; i++) { + for( tmp=s->table[i]; tmp; tmp = tmp->next) { + fprintf(stderr, "\t%s\n", tmp->name); + } + } +} @@ -0,0 +1,27 @@ +#ifndef SCOPE_H +#define SCOPE_H + +#define HASH_SIZE 211 + +typedef struct hash { + node* table[HASH_SIZE]; + struct hash *prev; + node* ret_var; +} scope; + +scope* mkscope(); +void free_scope(scope*); + +/*stack routines*/ +void pop_scope(scope**); +void push_scope(scope**); + +/*helpers*/ +node* scope_insert(scope*, char*); +node* scope_search_all(scope*, char*); +node* scope_search(scope*, char*); +node* scope_safe_search_all(scope*, char*); + +/*hash function*/ +int hashpjw(char*); +#endif diff --git a/sem_check.c b/sem_check.c new file mode 100644 index 0000000..637d044 --- /dev/null +++ b/sem_check.c @@ -0,0 +1,36 @@ +#include <assert.h> +#include <stdio.h> + +#include "node.h" +#include "scope.h" +#include "tree.h" +#include "y.tab.h" +#include "pc.h" +#include "sem_check.h" + +void check_id(s, n) +scope *s; +char *n; +{ + char buf[100]; + + if (scope_search(s, n)) { + snprintf(buf, 100, "\"%s\" already defined in scope...\n", n); + yyerror(buf); + } +} + +node* check_exists(s, n) +scope *s; +char *n; +{ + node *tmp; + char buf[100]; + + if(!(tmp = scope_search(s,n))) { + snprintf(buf, 100, "Cannot find \"%s\"\n", n); + yyerror(buf); + } + + return tmp; +} diff --git a/sem_check.h b/sem_check.h new file mode 100644 index 0000000..eef9e96 --- /dev/null +++ b/sem_check.h @@ -0,0 +1,8 @@ +#ifndef SEMCHECK_H +#define SEMCHECK_H + +void check_id(scope*, char*); + +node* check_exists(scope*, char*); + +#endif @@ -23,12 +23,11 @@ ptree *l, *r; return t; } -ptree* mkid(str) -char *str; +ptree* mkid(n) +node *n; { ptree *p = mktree(ID, NULL, NULL); - p->attr.nval = malloc(sizeof(node)); /*TODO fix hacky node create*/ - p->attr.nval->name = strdup(str); /* memory leak? double strdup*/ + p->attr.nval = n; /* memory leak? double strdup*/ return p; } @@ -6,7 +6,6 @@ typedef struct parse_tree { union { int ival; /* NUM */ float rval; /* RNUM */ - char *sval; /* ID */ node *nval; int opval; /* RELOP: LT LE GT GE EQ NE ADDOP: PLUS MINUS OR @@ -20,7 +19,7 @@ void aux_tree_print(ptree*, int); void print_tree(ptree*); ptree* mktree(int, ptree*, ptree*); -ptree* mkid(char*); +ptree* mkid(node*); ptree* mkinum(int); ptree* mkrnum(float); ptree* mkop(int, int, ptree*, ptree*); |