PROGRAM 2
%{
/**************************************************************************/
/* author: anthony f. ortiz */
/* program: scanner.l */
/* class: cs 6110 theory and design of compilers */
/* date: october 23, 1998 */
/* description: this program implements the scanner and symbol table */
/* part of a compiler. */
/**************************************************************************/
#include "y.tab.h"
#include
#include
int hash_it (char * word);
int add_symtable (char * word);
int lookup_symtable (char * word);
void print_symtable ();
void update_program (char * str);
void update_procedure (char * str);
void update_function (char * str, int type);
void update_parameters (int type, int ref);
void destroy_paramlist ();
void decrement_address ();
void increment_address ();
void start_addressing (int start);
void set_dim0 ();
void increment_dim ();
void update_variables (char * str, int type, int d, int low, int high);
void update_varlist (char * str);
void destroy_varlist ();
void update_variables2 (int type, int d, int low, int high);
int declaring = 0;
%}
%%
"and" {
printf (" ");
return (AND);
}
"array" {
printf (" ");
return (ARRAY);
}
"boolean" {
printf (" ");
return (BOOL);
}
"break" {
printf (" ");
return (BREAK);
}
"continue" {
printf (" ");
return (CONT);
}
"case" {
printf (" ");
return (CASE);
}
"declare" {
declaring = 1;
printf (" ");
return (DECLARE);
}
"div" {
yylval.ival = DIV;
printf (" ");
return (MULTOP);
}
"do" {
printf (" ");
return (DO);
}
"else" {
printf (" ");
return (ELSE);
}
"end" {
if (declaring == 1)
declaring = 0;
printf (" ");
return (END);
}
"function" {
declaring = 1;
printf (" ");
return (FUNCTION);
}
"if" {
printf (" ");
return (IF);
}
"integer" {
printf (" ");
return (INT);
}
"mod" {
yylval.ival = MOD;
printf (" ");
return (MULTOP);
}
"not" {
printf (" ");
return (NOT);
}
"of" {
printf (" ");
return (OF);
}
"or" {
printf (" ");
return (OR);
}
"procedure" {
declaring = 1;
printf (" ");
return (PROCEDURE);
}
"program" {
printf ("\nTOKENS: ");
return (PROGRAM);
}
"read" {
printf (" ");
return (READ);
}
"real" {
printf (" ");
return (REAL);
}
"ref" {
printf (" ");
return (REF);
}
"return" {
printf (" ");
return (RETURN);
}
"returns" {
printf (" ");
return (RETURNS);
}
"then" {
printf (" ");
return (THEN);
}
"while" {
printf (" ");
return (WHILE);
}
"write" {
printf (" ");
return (WRITE);
}
"true" {
yylval.ival = 1;
printf ("", yylval.ival);
return (BCONST);
}
"false" {
yylval.ival = 0;
printf ("", yylval.ival);
return (FALSE);
}
[ \n\t]+ {/* white space */}
"//".*"\n" {/* comments */}
":=" {
printf (" ");
return (ASSGN);
}
":" {
printf (" ");
return (COL);
}
"," {
printf (" ");
return (COMMA);
}
"=" {
yylval.ival = EQ;
printf (" ");
return (RELOP);
}
"/" {
yylval.ival = FDIV;
printf (" ");
return (MULTOP);
}
">=" {
yylval.ival = GEQ;
printf (" ");
return (RELOP);
}
">" {
yylval.ival = GR;
printf (" ");
return (RELOP);
}
[A-Za-z][A-Za-z0-9_]* {
int state;
yylval.cval = strdup (yytext);
state = lookup_symtable (yytext);
if (state == 0 || declaring == 1)
{
add_symtable (yytext);
}
printf (" ", yytext);
return (IDENT);
}
[0-9]+ {
yylval.ival = atoi (yytext);
printf (" ", yylval.ival);
return (INTCONST);
}
"[" {
printf (" ");
return (LBRACK);
}
"{" {
printf ("");
return (LBRACE);
}
"<=" {
yylval.ival = LEQ;
printf (" ");
return (RELOP);
}
"<" {
yylval.ival = LESS;
printf (" ");
return (RELOP);
}
"(" {
printf (" ");
return (LP);
}
"-" {
yylval.ival = MINUS;
printf (" ");
return (ADDOP);
}
"!=" {
yylval.ival = NEQ;
printf (" ");
return (RELOP);
}
"+" {
yylval.ival = PLUS;
printf (" ");
return (ADDOP);
}
".." {
printf (" ");
return (RANGE);
}
"]" {
printf (" ");
return (RBRACK);
}
"}" {
printf (" ");
return (RBRACE);
}
")" {
printf (" ");
return (RP);
}
[0-9]+[/.][0-9]+ {
yylval.rval = (float) (atof (yytext));
printf ("", yylval.rval);
return (REALCONST);
}
";" {
if (declaring == 1)
declaring = 0;
printf (" ");
return (SC);
}
"*" {
yylval.ival = TIMES;
printf (" ");
return (MULTOP);
}
%%
/* my main function is in the parse.y file. */
int scope = 1;
int address = -4;
int dim = 0;
/* define a linked list of variables. */
struct v_struct
{
char * name;
struct v_struct * next;
};
/* define a linked list of parameters. */
struct p_struct
{
int type;
int p_loc;
int isref;
struct p_struct * next;
};
/* define a linked list of symbol table records. */
struct word
{
char * word_name;
int sc_level;
int type;
int dim;
int low;
int high;
int first;
struct p_struct * params;
int ret_type;
struct word * next;
};
struct word * word_list [211]; /* the hash table with open chaining */
struct p_struct * par_type; /* linked list of parameters */
struct v_struct * var_type; /* linked list of variables */
extern void * malloc ();
/* hash word using formula in aho, sethi, and ullman. */
int hash_it (char * word)
{
char * p;
unsigned h = 0;
unsigned g;
for (p = word; * p != '\0'; p = p + 1)
{
h = (h << 4) + (* p);
if (g = h&0xf0000000)
{
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h % 211;
}
/* add identifier to symbol table. */
int add_symtable (char * word)
{
struct word * wp [211];
int h = hash_it (word);
/* word not there, allocate a new entry and link it on the list. */
wp [h] = (struct word *) malloc (sizeof (struct word));
wp [h] -> next = word_list [h];
/* have to copy the word itself as well. */
wp [h] -> word_name = (char *) malloc (strlen (word) + 1);
strcpy (wp [h] -> word_name, word);
word_list [h] = wp [h];
return 1; /* it worked. */
}
/* lookup identifier in symbol table, return 0 if not found,
1 if found. */
int lookup_symtable (char * word)
{
struct word * wp [211];
int h = hash_it (word);
wp [h] = word_list [h];
/* search down the list looking for the word. */
for (; wp [h]; wp [h] = wp [h] -> next)
{
if (strcmp (wp [h] -> word_name, word) == 0)
return 1;
}
return 0; /* not found. */
}
/* print identifiers in symbol table. */
void print_symtable ()
{
struct word * wp [211];
int h;
printf ("\n\nSymbol Table\n\n");
/* print list. */
printf (" name scope type dim low");
printf (" high first return\n\n");
for (h = 0; h < 211; h++)
{
wp [h] = word_list [h];
for (; wp [h]; wp [h] = wp [h] -> next)
{
printf ("%10s %8d %8d", wp [h] -> word_name,
wp [h] -> sc_level,
wp [h] -> type);
if (wp [h] -> type >= 2 && wp [h] -> type <= 4)
{
printf ("%8d %8d %8d %8d\n", wp [h] -> dim,
wp [h] -> low, wp [h] -> high, wp [h] -> first);
}
else if (wp [h] -> type == 5)
{
printf ("%8d %34d\n", wp [h] -> dim, wp [h] -> ret_type);
}
else if (wp [h] -> type == 6)
{
printf ("%8d\n", wp [h] -> dim);
}
else
printf ("\n");
if ((wp [h] -> type == 5 || wp [h] -> type == 6) &&
wp [h] -> params != NULL)
{
for (; wp [h] -> params;
wp [h] -> params = wp [h] -> params -> next)
{
printf ("params, type: %d location: %d ref: %d\n",
wp [h] -> params -> type,
wp [h] -> params -> p_loc,
wp [h] -> params -> isref);
}
}
}
}
printf ("\n");
}
/* increment scope by 1. */
increment_scope ()
{
scope = scope + 1;
}
/* decrement scope by 1. */
decrement_scope ()
{
scope = scope - 1;
}
/* update program. */
void update_program (char * str)
{
struct word * wp [211];
int h = hash_it (str);
wp [h] = word_list [h];
/* search down the list looking for the word. */
for (; wp [h]; wp [h] = wp [h] -> next)
{
if (strcmp (wp [h] -> word_name, str) == 0)
{
wp [h] -> sc_level = scope;
wp [h] -> type = 7;
break;
}
}
}
/* update procedure. */
void update_procedure (char * str)
{
struct word * wp [211];
int h = hash_it (str);
wp [h] = word_list [h];
/* search down the list looking for the word. */
for (; wp [h]; wp [h] = wp [h] -> next)
{
if (strcmp (wp [h] -> word_name, str) == 0)
{
wp [h] -> sc_level = scope;
wp [h] -> type = 6;
wp [h] -> dim = dim;
wp [h] -> params = par_type;
break;
}
}
}
/* update function. */
void update_function (char * str, int type)
{
struct word * wp [211];
int h = hash_it (str);
wp [h] = word_list [h];
/* search down the list looking for the word. */
for (; wp [h]; wp [h] = wp [h] -> next)
{
if (strcmp (wp [h] -> word_name, str) == 0)
{
wp [h] -> sc_level = scope;
wp [h] -> type = 5;
wp [h] -> dim = dim;
wp [h] -> ret_type = type;
wp [h] -> dim = dim;
wp [h] -> params = par_type;
break;
}
}
}
/* update parameters. */
void update_parameters (int type, int ref)
{
struct p_struct * pp;
pp = (struct p_struct *) malloc (sizeof (struct p_struct));
pp -> next = par_type;
/* have to copy it as well. */
pp -> type = type;
pp -> p_loc = address;
pp -> isref = ref;
par_type = pp;
}
/* destroy parameter list. */
void destroy_paramlist ()
{
par_type = NULL;
}
/* decrement address. */
void decrement_address ()
{
address = address - 1;
}
/* increment_address. */
void increment_address ()
{
address = address + 1;
}
/* start address at 1 or -4. */
void start_addressing (int start)
{
address = start;
}
/* start dim at 0. */
void set_dim0 ()
{
dim = 0;
}
/* increment dim for procedures and functions. */
void increment_dim ()
{
dim = dim + 1;
}
/* update variables. */
void update_variables (char * str, int type, int d, int low, int high)
{
struct word * wp [211];
int h = hash_it (str);
wp [h] = word_list [h];
/* search down the list looking for the word. */
for (; wp [h]; wp [h] = wp [h] -> next)
{
if (strcmp (wp [h] -> word_name, str) == 0)
{
wp [h] -> sc_level = scope;
wp [h] -> type = type;
wp [h] -> first = address;
wp [h] -> dim = d;
if (wp [h] -> dim == 1)
{
wp [h] -> low = low;
wp [h] -> high = high;
address = address + high - low + 1;
}
else if (wp [h] -> first < 0)
{
decrement_address ();
}
else if (wp [h] -> first >= 1)
{
increment_address ();
}
break;
}
}
}
/* update variable list. */
void update_varlist (char * str)
{
struct v_struct * vp;
vp = (struct v_struct *) malloc (sizeof (struct v_struct));
vp -> next = var_type;
/* have to copy it as well. */
vp -> name = str;
var_type = vp;
}
/* destroy variable list. */
void destroy_varlist ()
{
var_type = NULL;
}
/* update variables in symbol table. */
void update_variables2 (int type, int d, int low, int high)
{
struct v_struct * vp;
vp = var_type;
/* update each variable in variable list linked list to symbol table. */
for (; vp; vp = vp -> next)
{
update_variables (vp -> name, type, d, low, high);
}
}
/**************************************************************************/
/* author: anthony f. ortiz */
/* program: parser.y */
/* class: cs6110-01 */ /
/* date: october 23, 1998 */
/* description: this program describes and parses a grammer. */
/**************************************************************************/
%{
#include "defs.h"
#include
#include
#include
%}
%token AND
%token ARRAY
%token BOOL /* "boolean" */
%token BREAK
%token CONT /* "continue" */
%token CASE
%token DECLARE
%token DIV
%token DO
%token ELSE
%token END
%token FUNCTION
%token IF
%token INT /* "integer" */
%token MOD
%token NOT
%token OF
%token OR
%token PROCEDURE
%token PROGRAM
%token READ
%token REAL
%token REF
%token RETURN
%token RETURNS
%token THEN
%token WHILE
%token WRITE
%token TRUE
%token FALSE
%token ADDOP
%token ASSGN /* ":=" */
%token BCONST /* boolean constant */
%token COL /* ":" */
%token COMMA /* "," */
%token EQ /* "=" */
%token FDIV /* "/" */
%token GEQ /* ">=" */
%token GR /* ">" */
%token IDENT /* identifier */
%token INTCONST /* integer constant */
%token LBRACK /* "[" */
%token LBRACE /* "{" */
%token LEQ /* "<=" */
%token LESS /* "<" */
%token LP /* "(" */
%token MINUS /* "-" */
%token MULTOP
%token NEQ /* "!=" */
%token PLUS /* "+" */
%token RANGE /* ".." */
%token RBRACK /* "]" */
%token RBRACE /* "}" */
%token RELOP
%token RP /* ")" */
%token REALCONST /* real constant */
%token SC /* ";" */
%token TIMES /* "*" */
%type simpletype
/* yystype structure */
%union {int ival; float rval; char * cval;}
%left OR
%left AND
%nonassoc RELOP
%left ADDOP
%left MULTOP
%right NOT
%right UMINUS
%%
start : program;
program : PROGRAM IDENT SC vardeclar procdeclist LBRACE statlist RBRACE
{update_program ($2);}
;
vardeclar : {start_addressing (1);}
DECLARE vardeclist END SC
| /* empty */
;
vardeclist : decl vardeclist
| /* empty */
;
decl : identlist COL simpletype SC
{update_variables2 ($3, 0, 0, 0); destroy_varlist ();}
| identlist COL arraytype SC
{destroy_varlist ();}
;
identlist : identlist COMMA IDENT
{update_varlist ($3);}
| IDENT
{update_varlist ($1);}
;
simpletype : INT {$$ = 2;}
| REAL {$$ = 3;}
| BOOL {$$ = 4;}
;
arraytype : ARRAY LBRACK INTCONST RANGE INTCONST RBRACK OF simpletype
{update_variables2 ($8, 1, $3, $5);}
;
procdeclist : procdecl procdeclist
| /* empty */
;
procdecl : {increment_scope ();}
procheader vardeclar procdeclist LBRACE statlist RBRACE
{decrement_scope ();}
;
procheader : {start_addressing (-4);}
PROCEDURE IDENT params SC
{update_procedure ($3); destroy_paramlist (); set_dim0 ();}
| {start_addressing (-4);}
FUNCTION IDENT params RETURNS simpletype SC
{update_function ($3, $6); destroy_paramlist (); set_dim0 ();}
;
params : LP paramlist RP
| /* empty */
;
paramlist : parameter
| paramlist COMMA parameter
;
parameter : IDENT COL simpletype
{update_parameters ($3, 0); update_variables ($1, $3, 0, 0, 0);
increment_dim ();}
| REF IDENT COL simpletype
{update_parameters ($4, 1); update_variables ($2, $4, 0, 0, 0);
increment_dim ();}
;
block : {increment_scope ();}
LBRACE vardeclar statlist RBRACE
{decrement_scope ();}
;
statlist : statlist statement
| statement
;
statement : variable ASSGN expression SC
| ifstatement
| WHILE expression DO statlist END
| CASE expression OF caselist END SC
| RETURN expression SC
| BREAK SC
| CONT SC
| READ variable SC
| WRITE expression SC
| procedurecall SC
| block
| SC /* empty */
;
ifstatement : IF expression THEN statlist elsepart
;
elsepart : ELSE statlist END SC
| END SC /* empty */
;
caselist : casebranch caselist
| /* empty */
;
casebranch : labellist COL statement
;
labellist : INTCONST COMMA labellist
| INTCONST
;
procedurecall : IDENT
| callwithparameters
;
callwithparameters : IDENT LP actuals RP
;
actuals : actuals COMMA expression
| expression
;
variable : IDENT LBRACK expression RBRACK
| IDENT
| callwithparameters
;
expression : expression OR expression
| expression AND expression
| expression RELOP expression
| expression ADDOP expression
| expression MULTOP expression
| ADDOP expression %prec UMINUS
| NOT expression
| variable
| BCONST
| INTCONST
| REALCONST
| LP expression RP
;
%%
extern FILE * yyin;
/* read from a file specified by the command line and parse. */
main (int argc, char ** argv)
{
if (argc > 1)
{
FILE *file;
file = fopen (argv [1], "r");
if (!file)
{
fprintf (stderr, "could not open %s\n", argv [1]);
}
yyin = file;
}
yyparse ();
print_symtable ();
}
/* print a error message. */
yyerror (s)
char * s;
{
printf ("%s\n", s);
}
/* filename: defs.h */
/* see program 1. */
/* data file: test1.dat */
program t1;
declare x : integer;
end;
{
x := 12;
write x;
}
/* outfile: prog2.out */
TOKENS:
Symbol Table
name scope type dim low high first return
t1 1 7
x 1 2 0 0 0 1
BACK TO CS6110 PAGE.