PROGRAM 5
%{
/**************************************************************************/
/* author: anthony f. ortiz */
/* program: scanner.l */
/* class: cs 6110 theory and design of compilers */
/* date: december 2, 1998 */
/* description: this program implements the scanner and symbol table */
/* part of a compiler. */
/**************************************************************************/
#include "defs.h"
#include "y.tab.h"
#include
#include
#include
int hash_it (char * word);
struct word * add_symtable (char * word);
struct word * lookup_symtable (char * word);
void cleanup_symtable ();
void print_symtable ();
void update_program (char * str);
void update_procedure (char * str);
void update_procedure2 (char * str);
void update_function (char * str, type_t type);
void update_parameters (type_t 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, type_t type, int d, int low, int high);
void update_varlist (char * str);
void destroy_varlist ();
void update_variables2 (type_t type, int d, int low, int high);
void write_file(void);
void print_quad (quad_t qq);
void print_prog(void);
int start_program ();
void quit_program (int top);
void handle_integers (type_t type, int value);
void handle_reals (type_t type, double value);
void handle_variables (type_t type, int first, int index);
void handle_assignments (type_t type, int first, int index, type_t type2,
int first2);
void handle_writes (type_t type, int first);
void handle_reads (type_t type, int first, int index);
void handle_calculations (type_t type, int first, int sign, type_t type2,
int first2);
void handle_inequalities (type_t type, int first, int sign, type_t
type2, int first2);
void handle_bool (type_t type, int first, int sign, type_t type2, int first2);
int handle_then (int first);
int handle_else (int instr);
void handle_end (int instr);
int save_loc ();
int start_while (int first);
int end_while (int start, int end);
void handle_procedures (int scope2, type_t type, int return_addr, int ct_params);
int start_procedure ();
void end_procedure (int top);
void handle_return (int first);
void save_offsets ();
int start_block ();
int handle_blocks ();
void end_block (int top, int return_addr);
void handle_scope (type_t type, int first, int index, int scope2);
void handle_params (int ct_params, struct p_struct * params, struct
info actuals);
int handle_escapes ();
void end_escapes (int first, int end, int brk, int cont);
int start_case ();
void end_case (int start);
int end_branch ();
void handle_case (int first, struct case_info branches);
void backpatch_case (struct case_info branches);
int declaring = 0;
%}
%%
"and" {
yylval.ival = 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" {
yylval.ival = NOT;
printf (" ");
return (NOT);
}
"of" {
printf (" ");
return (OF);
}
"or" {
yylval.ival = 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 = TRUE;
printf ("", yylval.ival);
return (BCONST);
}
"false" {
yylval.ival = FALSE;
printf ("", yylval.ival);
return (BCONST);
}
[ \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_]* {
yylval.pval = lookup_symtable (yytext);
if (yylval.pval == NULL || declaring == 1)
{
yylval.pval = 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]*\.[0-9]+)([eE][-+]?[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. */
/* my structures and enumerations are in defs.h. */
int scope = 1;
int address = 1;
int dim = 0;
int next_instr = 2;
char * op_name [] = {"add", "sub", "mult", "idiv", "neg", "less", "equ",
"fadd", "fsub", "fmult", "fdiv", "fneg", "fless",
"fequ", "itor", "mov", "inxld", "inxst", "movim",
"movad", "movabs", "bnot", "band", "bor", "bequ", "gto",
"jmp", "iread", "rread", "iwrite", "rwrite", "call",
"ret", "halt"};
mem_t mem [MAXMEM]; /* main memory */
mem_t * p; /* working pointer */
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 */
struct actual_info * actuals; /* linked list of actuals */
int offsets [10]; /* beginning address for proc and func */
int while_scope; /* this is used for break/continue out of blocks/while. */
/* 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. */
struct word * add_symtable (char * word)
{
struct word * wp;
int h = hash_it (word);
/* word not there, allocate a new entry and link it on the list. */
wp = (struct word *) malloc (sizeof (struct word));
wp -> next = word_list [h];
/* have to copy the word itself as well. */
wp -> word_name = (char *) malloc (strlen (word) + 1);
strcpy (wp -> word_name, word);
word_list [h] = wp;
return wp; /* it worked. */
}
/* lookup identifier in symbol table, return 0 if not found,
1 if found. */
struct word * lookup_symtable (char * word)
{
struct word * wp;
int h = hash_it (word);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, word) == 0)
return wp;
}
return NULL; /* not found. */
}
/* clean up table. */
void cleanup_symtable ()
{
int i;
struct word * wp;
/* remove current scope idents (not really). */
for (i = 0; i < 211; i++)
{
wp = word_list [i];
for (; wp; wp = wp -> next)
{
if (wp -> sc_level == scope && (wp -> type == int_t ||
wp -> type == real_t || wp -> type == bool_t))
strcpy (wp -> word_name, "removed ");
}
}
}
/* print identifiers in symbol table. */
void print_symtable ()
{
struct word * wp;
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 = word_list [h];
for (; wp; wp = wp -> next)
{
printf ("%10s %8d %8d", wp -> word_name,
wp -> sc_level,
wp -> type);
if (wp -> type >= 1 && wp -> type <= 3)
{
printf ("%8d %8d %8d %8d\n", wp -> dim,
wp -> low, wp -> high, wp -> first);
}
else if (wp -> type == 4)
{
printf ("%8d %26d %8d\n", wp -> dim, wp -> first,
wp -> ret_type);
}
else if (wp -> type == 5)
{
printf ("%8d %26d\n", wp -> dim, wp -> first);
}
else
printf ("\n");
if ((wp -> type == 4 || wp -> type == 5) &&
wp -> params != NULL)
{
for (; wp -> params;
wp -> params = wp -> params -> next)
{
printf ("params, type: %d location: %d ref: %d\n",
wp -> params -> type,
wp -> params -> p_loc,
wp -> 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;
int h = hash_it (str);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, str) == 0)
{
wp -> sc_level = scope;
wp -> type = program_t;
break;
}
}
}
/* update procedure. */
void update_procedure (char * str)
{
struct word * wp;
int h = hash_it (str);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, str) == 0)
{
wp -> sc_level = scope;
wp -> type = proc_t;
wp -> dim = dim;
wp -> first = next_instr;
wp -> params = par_type;
break;
}
}
}
/* update procedure2. */
void update_procedure2 (char * str)
{
struct word * wp;
int h = hash_it (str);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, str) == 0)
{
wp -> first = next_instr;
break;
}
}
}
/* update function. */
void update_function (char * str, type_t type)
{
struct word * wp;
int h = hash_it (str);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, str) == 0)
{
wp -> sc_level = scope;
wp -> type = funct_t;
wp -> dim = dim;
wp -> ret_type = type;
wp -> dim = dim;
wp -> first = next_instr;
wp -> params = par_type;
break;
}
}
}
/* update parameters. */
void update_parameters (type_t 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, type_t type, int d, int low, int high)
{
struct word * wp;
int h = hash_it (str);
wp = word_list [h];
/* search down the list looking for the word. */
for (; wp; wp = wp -> next)
{
if (strcmp (wp -> word_name, str) == 0)
{
wp -> sc_level = scope;
wp -> type = type;
wp -> first = address - low;
wp -> dim = d;
if (wp -> dim == 1)
{
wp -> low = low;
wp -> high = high;
address = address + high - low + 1;
}
else if (wp -> first < 0)
{
decrement_address ();
}
else if (wp -> 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 (type_t 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);
}
}
/* next 4 procedures were created by dr. nico. */
/* this simply generates the next quad and updates a global counter,
which i have called "next_instr" and kept pointing to the next
free mem space. */
void put_quad (op_t operator, int operand1, int operand2, int destination)
{
/* this generates the next quad in the array mem and
increments the next_instr index, which is kept pointing
to the next free space. */
mem_t *p;
p = &(mem[next_instr++]); /* get address and increment index. */
p->op = operator;
p->opd1 = operand1;
p->opd2 = operand2;
p->dest = destination;
}
/* this is my utility to dump the quad array (mem) to a file. it
requires that you #include in order to get the
definitions for the constants o_wronly, etc. this version
has a default filename "hard coded", but that, of course,
could be changed. */
void write_file(void)
{
int ofd;
int n;
if((ofd = open("outfile.exec", O_WRONLY | O_TRUNC |O_CREAT, 0600)) <= 0)
{
perror(" Can't write outfile");
exit(1);
}
n = write(ofd, mem, next_instr * sizeof(mem_t));
fprintf(stderr, "Wrote out %d instructions\n", n / sizeof(mem_t));
}
/* this will print out a single quad. */
void print_quad(quad_t qq)
{
printf("(%7s, %4d, %4d, %4d)\n", op_name[qq._op], qq._opd1,qq._opd2,
qq._dest);
}
/* this can be used to print out the quads you have generated while they
are still in memory. it is what i have called at the end of
my compiler in order to produce the output i have included on
class handouts. */
void print_prog(void)
{
int n;
printf("PC = %d\n", mem[0].ival);
printf("SP = %d\n", mem[1].ival);
for(n=2; n < next_instr; n++)
{
printf("%4d: ", n);
print_quad(mem[n].quad);
if(mem[n].op == movim)
{
++n;
printf("%4d: (** %8d // %e **)\n", n, mem[n].ival, mem[n].rval);
}
}
}
/* start program. */
int start_program ()
{
address = offsets [scope - 1];
put_quad (movim, 0, 0, -1);
next_instr++; /* skip the constant top and fill it in at end. */
return (next_instr - 1);
}
/* quit program. */
void quit_program (int top)
{
put_quad (halt, 0, 0, 0);
PC = top - 1;
SP = next_instr + 4;
mem [top].ival = address;
}
/* handle integers. */
void handle_integers (type_t type, int value)
{
i.type = type;
i.first = address;
i.index = 0;
put_quad (movim, 0, 0, address);
if (type == int_t)
{
mem [next_instr].ival = value;
}
else if (type == bool_t && value == TRUE)
{
mem [next_instr].ival = true;
}
else if (type == bool_t && value == FALSE)
{
mem [next_instr].bval = false;
}
next_instr = next_instr + 1;
address = address + 1;
}
/* handle reals. */
void handle_reals (type_t type, double value)
{
i.type = type;
i.first = address;
i.index = 0;
put_quad (movim, 0, 0, address);
if (type == real_t)
{
mem [next_instr].rval = value;
}
next_instr = next_instr + 1;
address = address + 1;
}
/* handle variables. */
void handle_variables (type_t type, int first, int index)
{
if (index == 0)
{
i.type = type;
i.first = first;
i.index = index;
}
else if (index != 0)
{
i.type = type;
i.first = address;
i.index = 0;
put_quad (inxld, first , index , address);
address = address + 1;
}
else if (index <= -4)
{
i.type = type;
i.first = address;
i.index = 0;
put_quad (inxld, first, index, address);
address = address + 1;
}
}
/* handle assignments. */
void handle_assignments (type_t type, int first, int index, type_t type2,
int first2)
{
if (type == real_t && type2 == int_t)
{
put_quad (itor, first2, 0, address);
first2 = address;
type2 = real_t;
address++;
}
if (index == 0 && type == type2)
{
put_quad (mov, first2, 0, first);
}
else if (type == type2)
{
put_quad (inxst, first2, index, first);
}
}
/* handle writes. */
void handle_writes (type_t type, int first)
{
if (type == int_t)
{
put_quad (iwrite, first, 0, 0);
}
else if (type == real_t)
{
put_quad (rwrite, first, 0, 0);
}
}
/* handle reads. */
void handle_reads (type_t type, int first, int index)
{
if (type == int_t && index == 0)
{
put_quad (iread, 0, 0, first);
}
else if (type == real_t && index == 0)
{
put_quad (rread, 0, 0, first);
}
else if (type == int_t && index != 0)
{
put_quad (iread, 0, 0, address);
put_quad (inxst, address, index, first);
address++;
}
else if (type == real_t && index != 0)
{
put_quad (rread, 0, 0, address);
put_quad (inxst, address, index, first);
address++;
}
}
/* handle calculations. */
void handle_calculations (type_t type, int first, int sign, type_t type2,
int first2)
{
if (type == int_t && type2 == real_t)
{
put_quad (itor, first, 0, address);
first = address;
type = real_t;
address++;
}
else if (type == real_t && type2 == int_t)
{
put_quad (itor, first2, 0, address);
first2 = address;
type2 = real_t;
address++;
}
else if (sign == FDIV && type == int_t && type2 == int_t)
{
put_quad (itor, first, 0, address);
first = address;
type = real_t;
address++;
put_quad (itor, first2, 0, address);
first2 = address;
type2 = real_t;
address++;
}
if (sign == MOD && type == int_t && type2 == int_t)
{
int temp;
put_quad (idiv, first, first2, address);
temp = address;
address++;
put_quad (mult, temp, first2, address);
temp = address;
address++;
put_quad (sub, first, temp, address);
}
else if (sign == PLUS && type == int_t && type2 == int_t)
{
put_quad (add, first, first2, address);
}
else if (sign == PLUS && type == real_t && type2 == real_t)
{
put_quad (fadd, first, first2, address);
}
else if (sign == MINUS && type == int_t && type2 == int_t)
{
put_quad (sub, first, first2, address);
}
else if (sign == MINUS && type == real_t && type2 == real_t)
{
put_quad (fsub, first, first2, address);
}
else if (sign == TIMES && type == int_t && type2 == int_t)
{
put_quad (mult, first, first2, address);
}
else if (sign == TIMES && type == real_t && type2 == real_t)
{
put_quad (fmult, first, first2, address);
}
else if ((sign == FDIV || sign == DIV) && type == int_t && type2 == int_t)
{
put_quad (idiv, first, first2, address);
}
else if (sign == FDIV && type == real_t && type2 == real_t)
{
put_quad (fdiv, first, first2, address);
}
else if (sign == MINUS && type == int_t)
{
put_quad (neg, first, 0, address);
}
else if (sign == MINUS && type == real_t)
{
put_quad (fneg, first, 0, address);
}
if ((type == type2 || type2 == 0) && (type == real_t || type == int_t))
{
i.type = type;
i.first = address;
i.index = 0;
address++;
}
}
/* handle inequalities. */
void handle_inequalities (type_t type, int first, int sign, type_t
type2, int first2)
{
if (type == int_t && type2 == real_t)
{
put_quad (itor, first, 0, address);
first = address;
type = real_t;
address++;
}
else if (type == real_t && type2 == int_t)
{
put_quad (itor, first2, 0, address);
first2 = address;
type2 = real_t;
address++;
}
if (sign == LESS && type == int_t && type2 == int_t)
{
put_quad (less, first, first2, address);
}
else if (sign == LESS && type == real_t && type2 == real_t)
{
put_quad (fless, first, first2, address);
}
else if (sign == GR && type == int_t && type2 == int_t)
{
put_quad (less, first2, first, address);
}
else if (sign == GR && type == real_t && type2 == real_t)
{
put_quad (fless, first2, first, address);
}
else if (sign == EQ && type == bool_t && type2 == bool_t)
{
put_quad (bequ, first, first2, address);
}
else if (sign == EQ && type == int_t && type2 == int_t)
{
put_quad (equ, first, first2, address);
}
else if (sign == EQ && type == real_t && type2 == real_t)
{
put_quad (fequ, first, first2, address);
}
else if (sign == NEQ && type == int_t && type2 == int_t)
{
int temp;
put_quad (equ, first, first2, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
else if (sign == NEQ && type == real_t && type2 == real_t)
{
int temp;
put_quad (fequ, first, first2, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
else if (sign == LEQ && type == int_t && type2 == int_t)
{
int temp;
put_quad (less, first2, first, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
else if (sign == LEQ && type == real_t && type2 == real_t)
{
int temp;
put_quad (fless, first2, first, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
else if (sign == GEQ && type == int_t && type2 == int_t)
{
int temp;
put_quad (less, first, first2, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
else if (sign == GEQ && type == real_t && type2 == real_t)
{
int temp;
put_quad (fless, first, first2, address);
temp = address;
address++;
put_quad (bnot, temp, 0, address);
}
if (type == type2 && (type == int_t || type == real_t || type == bool_t))
{
i.type = bool_t;
i.first = address;
i.index = 0;
address++;
}
}
/* handle boolean algebra. */
void handle_bool (type_t type, int first, int sign, type_t type2, int first2)
{
if (sign == AND && type == bool_t && type2 == bool_t)
{
put_quad (band, first, first2, address);
}
else if (sign == OR && type == bool_t && type2 == bool_t)
{
put_quad (bor, first, first2, address);
}
else if (sign == NOT && type == bool_t)
{
put_quad (bnot, first, 0, address);
}
if ((type == type2 || type2 == 0) && type == bool_t)
{
i.type = type;
i.first = address;
i.index = 0;
address++;
}
}
/* handle then. */
int handle_then (int first)
{
put_quad (bnot, first, 0, address);
put_quad (jmp, address, 0, 0);
address++;
return next_instr - 1;
}
/* handle else. */
int handle_else (int instr)
{
int i;
put_quad (gto, 0, 0, 0);
mem [instr].quad._dest = next_instr;
return next_instr - 1;
}
/* handle end. */
void handle_end (int instr)
{
mem [instr].quad._dest = next_instr;
}
/* save location of beginning while. */
int save_loc ()
{
return next_instr;
}
/* start while. */
int start_while (int first)
{
while_scope = scope;
put_quad (bnot, first, 0, address);
put_quad (jmp, address, 0, 0);
address++;
return next_instr - 1;
}
/* end while. */
int end_while (int begin, int end)
{
while_scope = 0;
put_quad (gto, 0, 0, begin);
mem [end].quad._dest = next_instr;
return next_instr;
}
/* handle procedures. */
void handle_procedures (int scope2, type_t type, int return_addr,
int ct_params)
{
int temp;
if (scope2 - scope >= 2)
{
/* do nothing. */
}
else
{
if (scope >= scope2)
{
int i;
put_quad (mov, -2, 0, address);
temp = address;
address++;
for (i = scope2; i <= scope; i++)
{
put_quad (inxld, -2, temp, address);
put_quad (add, temp, address, temp);
}
put_quad (movim, 0, 0, address);
mem [next_instr].ival = 4 + ct_params;
next_instr++;
put_quad (sub, temp, address, temp);
put_quad (mov, -1, 0, address);
}
else
{
put_quad (mov, -1, 0, address);
put_quad (neg, address, 0, address);
temp = address;
address++;
put_quad (movim, 0, 0, address);
mem [next_instr].ival = 4 + ct_params;
next_instr++;
}
put_quad (sub, temp, address, temp);
address++;
put_quad (inxst, temp, -1, 2 + ct_params);
put_quad (movabs, 1, 0, address);
put_quad (inxst, address, -1, 4 + ct_params);
address++;
put_quad (movim, 0, 0, address);
mem [next_instr].ival = next_instr + 3;
next_instr++;
put_quad (inxst, address, -1, 1 + ct_params);
address++;
put_quad (call, return_addr, ct_params, 0);
if (type == funct_t)
{
put_quad (inxld, 0, -1, address);
i.first = address;
i.index = 0;
address++;
}
}
}
/* start procedure. */
int start_procedure ()
{
address = offsets [scope - 1];
put_quad (movim, 0, 0, -1);
next_instr++;
return (next_instr - 1);
}
/* end procedure. */
void end_procedure (int top)
{
put_quad (ret, 0, 0, 0);
mem [top].ival = address;
}
/* handle return. find the # of params in the function. have to find
the function using scope. */
void handle_return (int first)
{
struct word * wp;
int h, temp, params;
temp = 0;
for (h = 0; h < 211; h++)
{
wp = word_list [h];
for (; wp; wp = wp -> next)
{
if (scope == wp -> sc_level && funct_t == wp -> type)
if (temp == 0 ||
((next_instr - wp -> first) < (next_instr - temp) &&
(next_instr - wp -> first > 0)))
{
params = wp -> dim;
temp = wp -> first;
}
}
}
put_quad (mov, first, 0, -4 - params);
}
/* save offsets. */
void save_offsets ()
{
offsets [scope - 1] = address;
}
/* start block. */
int start_block ()
{
address = offsets [scope - 1];
put_quad (movim, 0, 0, -1);
next_instr++;
return (next_instr - 1);
}
/* handle blocks. */
int handle_blocks ()
{
int temp, return_addr;
put_quad (mov, -1, 0, address);
put_quad (neg, address, 0, address);
temp = address;
address++;
put_quad (movim, 0, 0, address);
mem [next_instr].ival = 4;
next_instr++;
put_quad (sub, temp, address, temp);
address++;
put_quad (inxst, temp, -1, 2);
put_quad (movabs, 1, 0, address);
put_quad (inxst, address, -1, 4);
address++;
put_quad (movim, 0, 0, address);
next_instr++;
return_addr = next_instr - 1;
put_quad (inxst, address, -1, 1);
address++;
offsets [scope - 1] = address;
put_quad (call, next_instr + 1, 0, 0);
return return_addr;
}
/* end block. */
void end_block (int top, int return_addr)
{
put_quad (ret, 0, 0, 0);
mem [top].ival = address;
mem [return_addr].ival = next_instr;
address = offsets [scope - 1];
}
/* handle scope to find non-locals. */
void handle_scope (type_t type, int first, int index, int scope2)
{
if (index == 2)
{
index = first;
first = 0;
}
if ((scope - scope2) == 0)
{
i.type = type;
i.first = first;
i.index = index;
}
else if ((scope - scope2) == 1)
{
if (index != 0)
{
put_quad (add, index, -2, address);
i.index = address;
address++;
}
else
{
i.index = -2;
}
i.type = type;
i.first = first;
}
else if ((scope - scope2) > 1)
{
int j, temp, temp2;
put_quad (mov, -2, 0, address);
temp = address;
address++;
temp2 = address;
for (j = 1; j < (scope - scope2); j++)
{
put_quad (inxld, -2, temp, address);
put_quad (add, address, temp, temp);
if (index != 0)
{
int temp2;
put_quad (add, index, temp, address);
temp2 = temp;
temp = address;
address = temp2;
}
}
i.type = type;
i.first = first;
i.index = temp;
address = temp2 + 1;
}
}
/* handle parameters. */
void handle_params (int ct_params, struct p_struct * params,
struct info actuals)
{
struct info * ap = actuals.next;
struct info * ap2;
struct info * ap3;
struct p_struct * pp = params;
int ct = 0;
/* reverse order of actuals so they correspond with params. */
ap2 = (struct info *) malloc (sizeof (struct info));
ap2 -> first = actuals.first;
ap3 = ap2;
for (; ap; ap = ap -> next)
{
ap2 = (struct info *) malloc (sizeof (struct info));
ap2 -> next = ap3;
ap2 -> first = ap -> first;
ap3 = ap2;
} ap = ap3;
/* put params in their procedures stack frame. */
for (; ap; ap = ap -> next)
{
ct = ct + 1;
if (pp -> isref == 1)
{
int temp;
put_quad (movad, ap -> first, 0, address);
put_quad (sub, address, -1, address);
temp = address + 1;
put_quad (movim, 0, 0, temp);
mem [next_instr].ival = 4 + ct_params;
next_instr++;
put_quad (sub, address, temp, address);
put_quad (inxst, address, -1, ct);
}
else
{
put_quad (inxst, ap -> first, -1, ct);
}
if (ct >= 1)
{
pp = pp -> next;
}
}
}
/* handle breaks and escapes. */
int handle_escapes ()
{
if (scope > while_scope)
{
int i;
for (i = while_scope; i < scope; i++) {
put_quad (movim, 0, 0, -3);
mem [next_instr].ival = next_instr + 2;
next_instr++;
put_quad (ret, 0, 0, 0);
}
}
put_quad (gto, 0, 0, 0);
return next_instr - 1;
}
/* backpatch break and continue. */
void end_escapes (int first, int end, int brk, int cont)
{
if (first != 0 && cont != 0)
{
mem [cont].quad._dest = first;
}
if (end != 0 && brk != 0)
{
mem [brk].quad._dest = end;
}
}
/* goto the instruction where the equality testing will take place. */
int start_case ()
{
put_quad (gto, 0, 0, 0);
return next_instr - 1;
}
/* backpatch the goto which will lead to the case testing. */
void end_case (int start)
{
mem [start].quad._dest = next_instr;
}
/* goto the end of the case. */
int end_branch ()
{
put_quad (gto, 0, 0, 0);
return next_instr - 1;
}
/* jump to the case statements if equality is true. */
void handle_case (int first, struct case_info branches)
{
struct case_info * cp = branches.next;
int temp;
put_quad (movim, 0, 0, address);
mem [next_instr].ival = branches.label;
next_instr++;
temp = address;
address++;
put_quad (equ, temp, first, address);
put_quad (jmp, address, 0, branches.s_loc);
address++;
for (; cp; cp = cp -> next)
{
put_quad (movim, 0, 0, address);
mem [next_instr].ival = cp -> label;
next_instr++;
temp = address;
address++;
put_quad (equ, temp, first, address);
put_quad (jmp, address, 0, cp -> s_loc);
}
}
/* backpatch the gotos after every possible case which will lead out
of case structure. */
void backpatch_case (struct case_info branches)
{
struct case_info * cp = branches.next;
mem [branches.e_loc].quad._dest = next_instr;
for (; cp; cp = cp -> next)
{
mem [cp -> e_loc].quad._dest = next_instr;
}
}
/**************************************************************************/
/* author: anthony f. ortiz */
/* program: parser.y */
/* class: cs6110-01 */
/* date: october 28, 1998 */
/* date: december 2, 1998 */
/* description: this program describes and parses a grammar. */
/**************************************************************************/
%{
#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
%type variable
%type expression
%type ifstatement
%type elsepart
%type statement
%type program
%type procdecl
%type block
%type procheader
%type callwithparameters
%type statlist
%type labellist
%type casebranch
%type caselist
%type actuals
/* yystype structure */
%union {int ival; float rval; bool bval; type_t tval; struct info infoval;
struct do_info dval; char * cval; struct word * pval;
struct case_info sval;}
%left OR
%left AND
%nonassoc RELOP
%left ADDOP
%left MULTOP
%right NOT
%right UMINUS
%%
start : program;
program : PROGRAM IDENT SC vardeclar procdeclist LBRACE
{$$ = start_program ();}
statlist RBRACE
{update_program ($2 -> word_name); quit_program ($7);}
;
vardeclar : {start_addressing (1);}
DECLARE vardeclist END SC
| {start_addressing (1); save_offsets ();} /* empty */
;
vardeclist : decl vardeclist {save_offsets ();}
| /* 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 -> word_name);}
| IDENT
{update_varlist ($1 -> word_name);}
;
simpletype : INT {$$ = int_t;}
| REAL {$$ = real_t;}
| BOOL {$$ = bool_t;}
;
arraytype : ARRAY LBRACK INTCONST RANGE INTCONST RBRACK OF simpletype
{update_variables2 ($8, 1, $3, $5);}
;
procdeclist : procdecl procdeclist
| /* empty */
;
procdecl : procheader vardeclar procdeclist LBRACE
{update_procedure2 ($1); $$ = start_procedure ();}
statlist RBRACE {cleanup_symtable ();
end_procedure ($5); decrement_scope ();}
;
procheader : {set_dim0 (); increment_scope (); start_addressing (-4);}
PROCEDURE IDENT params SC
{update_procedure ($3 -> word_name); destroy_paramlist ();
$$ = $3 -> word_name;}
| {set_dim0 (); increment_scope (); start_addressing (-4);}
FUNCTION IDENT params RETURNS simpletype SC
{update_function ($3 -> word_name, $6); destroy_paramlist ();
$$ = $3 -> word_name;}
;
params : LP paramlist RP
| /* empty */
;
paramlist : parameter
| paramlist COMMA parameter
;
parameter : IDENT COL simpletype
{update_parameters ($3, 0);
update_variables ($1 -> word_name, $3, 0, 0, 0);
increment_dim ();}
| REF IDENT COL simpletype
{update_parameters ($4, 1);
update_variables ($2 -> word_name, $4, 2, 0, 0);
increment_dim ();}
;
block : {$$.start = handle_blocks (); increment_scope ();}
LBRACE vardeclar
{$$.start = start_block ();}
statlist RBRACE
{decrement_scope (); end_block ($4.start,
$1.start);
$$.brk = $5.brk; $$.cont = $5.cont;}
;
statlist : statlist statement {if ($2.brk != 0) $$.brk = $2.brk;
if ($1.brk != 0) $$.brk = $1.brk;
if ($2.cont != 0) $$.cont = $2.cont;
if ($1.cont != 0) $$.cont = $1.cont;}
| statement {if ($1.brk != 0) $$.brk = $1.brk;
if ($1.cont != 0) $$.cont = $1.cont;}
;
statement : variable ASSGN expression SC
{handle_assignments ($1.type, $1.first, $1.index, $3.type, $3.first);}
| ifstatement {$$.brk = $1.brk; $$.cont = $1.cont;}
| WHILE {$$.start = save_loc ();} expression
DO {$$.middle = start_while ($3.first);}
statlist END
{$$.end = end_while ($2.start, $5.middle);
end_escapes ($2.start, $$.end, $6.brk, $6.cont);
$6.brk = 0; $6.cont = 0;}
| CASE expression OF {$$.start = start_case ();}
caselist {end_case ($4.start);} END SC
{handle_case ($2.first, $5); backpatch_case ($5);}
| RETURN expression SC {handle_return ($2.first);}
| BREAK SC {$$.brk = handle_escapes ();}
| CONT SC {$$.cont = handle_escapes ();}
| READ variable SC
{handle_reads ($2.type, $2.first, $2.index);}
| WRITE expression SC
{handle_writes ($2.type, $2.first);}
| procedurecall SC {}
| block {$$.brk = $1.brk; $$.cont = $1.cont;}
| SC /* empty */ {}
;
ifstatement : IF expression THEN
{$$.start = handle_then ($2.first);} statlist
{$$.end = handle_else ($4.start);} elsepart
{handle_end ($6.end);
if ($5.brk != 0) $$.brk = $5.brk;
if ($5.cont != 0) $$.cont = $5.cont;
if ($7.brk != 0) $$.brk = $7.brk;
if ($7.cont != 0) $$.cont = $7.cont;}
;
elsepart : ELSE statlist END SC {$$.brk = $2.brk; $$.cont = $2.cont;}
| END SC /* empty */ {}
;
caselist : casebranch caselist {$$ = $1; $$.next = &$2;}
| /* empty */ {}
;
casebranch : labellist COL {$1.s_loc = save_loc ();}
statement {$$ = $1; $$.e_loc = end_branch ();}
;
labellist : INTCONST {$$.label = $1;} COMMA labellist {}
| INTCONST {$$.label = $1;}
;
procedurecall : IDENT {handle_procedures ($1 -> sc_level, $1 -> type,
$1 -> first, $1 -> dim);}
| callwithparameters
;
callwithparameters : IDENT LP actuals RP {handle_params ($1 -> dim,
$1 -> params, $3);
if ($1 -> type == proc_t)
{
handle_procedures (
$1 -> sc_level, $1 -> type,
$1 -> first, $1 -> dim);
$$ = $1;
}
}
;
actuals : expression COMMA actuals
{$$ = $1; $$.next = & $3;}
| expression
{$$.first = $1.first;}
;
variable : IDENT LBRACK expression RBRACK
{handle_scope ($1 -> type, $1 -> first, $3.first,
$1 -> sc_level); $$ = i;}
| IDENT
{if ($1 -> type == funct_t)
{
handle_procedures ($1 -> sc_level, $1 -> type,
$1 -> first, $1 -> dim);
$$.type = $1 -> ret_type;
$$.first = i.first;
$$.index = i.index;
}
else
{
handle_scope ($1 -> type, $1 -> first, $1 -> dim,
$1 -> sc_level);
$$ = i;
}
}
| callwithparameters
{
if ($1 -> type == funct_t)
{
handle_procedures ($1 -> sc_level, $1 -> type,
$1 -> first, $1 -> dim);
$$.type = $1 -> ret_type;
$$.first = i.first;
$$.index = i.index;
}
}
;
expression : expression OR expression
{handle_bool ($1.type, $1.first, $2, $3.type, $3.first);
$$ = i;}
| expression AND expression
{handle_bool ($1.type, $1.first, $2, $3.type, $3.first);
$$ = i;}
| expression RELOP expression
{handle_inequalities ($1.type, $1.first, $2, $3.type, $3.first);
$$ = i;}
| expression ADDOP expression
{handle_calculations ($1.type, $1.first, $2, $3.type, $3.first);
$$ = i;}
| expression MULTOP expression
{handle_calculations ($1.type, $1.first, $2, $3.type, $3.first);
$$ = i;}
| ADDOP expression %prec UMINUS
{handle_calculations ($2.type, $2.first, $1, 0, 0);
$$ = i;}
| NOT expression
{handle_bool ($2.type, $2.first, $1, 0, 0);
$$ = i;}
| variable
{handle_variables ($1.type, $1.first, $1.index);
$$ = i;}
| BCONST
{handle_integers (bool_t, $1);
$$ = i;}
| INTCONST
{handle_integers (int_t, $1);
$$ = i;}
| REALCONST
{handle_reals (real_t, $1);
$$ = i;}
| LP expression RP
{$$ = $2;}
;
%%
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 ();
write_file ();
}
/* print a error message. */
yyerror (s)
char * s;
{
printf ("%s\n", s);
}
/* data file: test1.dat */
// A typical program might look something like the following.
program test13;
declare x, y, z : integer;
a: array[4..9]of integer;
u : real;
end;
function f returns integer;
declare z: array[7..12]of real;
myarry: array[3..5] of integer;
end;
{
return 22;
}
procedure pp ( s : integer , ref t: real, u : integer);
declare tmp : integer; end;
procedure qq (ref x : integer);
{
x := 5*x;
}
{
qq(u);
t := s+ t + u;
}
{ // main block begins here
// this is just another sample comment.
x := 42; y := 4; z := f;
u := 3.14;
{
declare tmp : integer; end;
tmp := x; x := y; y := tmp;
};
pp(z, u, x + z);
write x;
write y;
write z;
write u;
}
// and thus ends the program.
/* outfile: prog5.out */
TOKENS: