PROGRAM 1
/* filename: scan.cpp author: anthony f. ortiz */
/* scanner - turbo c++ version
read characters from textfile 'srcfil' and outputs tokens to textfile
'tokfil'. each token is a pair of lines in this file.
/*
/* include files */
#include
#include
#include
#include
/* constants */
#define RESWORDSIZE 100
int lastcharcode=255;
#define STR_SIZE 10
/* maximum number of characters, not including NULL, in strings of
our standard string type 'str'
*/
char strfield[]="%10s"; /* for input into variables of type str */
int true=1;
int false=0;
char emptystr[]="";
char fwd[]="%5d";
/* control string for output of integers in a standard field width */
char fws[]="5s";
/* control string ... strings ... */
/* types */
typedef char str[STR_SIZE+1];
/* our standard string type. allocates storage. */
typedef char strparam[];
/* type for formal parameter strings. doesn't allocate storage. */
typedef int boolean;
/* variables */
boolean scantrace;
/* determines whether a scanner trace will be produced. */
FILE *srcfilp;
/* pointer to srcfil, the file of characters to be read by scanner. */
int ch;
/* logical head of input queue. procedure get_ch reads into ch from
*srcfilp. get_ch translates an eof into a #.
*/
FILE *tokfilp;
/* pointer to tokfil, the output file of scanner. each token
produced is two lines of this file.
*/
int state; /* state variable of scanner DFA */
str packstr; /* multi-character token values are constructed here. */
int packptr; /* indexes last character, before NULL, in packstr */
enum {letter, digit, specchar, invalidchar, blank, poundsign}
charclass[256];
/* used to quickly determine character class of a character. */
str resword[RESWORDSIZE];
/* table of identifiers that will produce reserved word tokens. */
int numreswords;
/* number of reserved words, which may be smaller than reswordsize.
points to last reserved word in resword array.
*/
int num_lines=0; /* number of trace lines printed since last prompt. */
/* function prototypes */
void cycle(void);
void get_ch(void);
void emit(strparam s1, strparam s2);
void pack_ch(void);
void start_pack_ch(void);
void search_reswords(strparam s, boolean *foundp);
void initialize(void);
void scanpic(void);
void assign_ch(int ch, strparam s);
boolean eqstr(strparam s1, strparam s2);
/*************************************************************************/
void main(void)
{
clrscr(); /* turbo c++ extension to clear user window */
scantrace=true;
initialize();
cycle();
end: puts("scanner done");
puts("push Enter to leave User Window"); /* for turbo c++ */
getchar();
exit(0);
} /* end main. */
/*************************************************************************/
void cycle(void)
/* main loop of scanner. hides definition of lexical structure of source
language expressed as a deterministic finite automation. inputs characters
through get_ch(), which in turn hides definition of input medium, and
outputs token through emit(), which in turn hides definition of output
medium.
*/
{
boolean scanning, found;
str tempstr;
state='s';
get_ch(); /* initialize ch with first character of srcfil. */
scanning=true;
do /* while scanning */
{
if (scantrace) scanpic();
switch (state)
{
case 's':
switch(charclass[ch])
{
case blank:
get_ch(); /* get next source character into ch. */
break;
case poundsign: /* returned by get_ch to signify eof. */
puts("eof read by scanner");
scanning=false;
break;
case invalidchar:
get_ch();
break;
case digit:
start_pack_ch();
get_ch();
state='d';
break;
case letter:
start_pack_ch();
get_ch();
state='l';
break;
case specchar:
assign_ch(ch,tempstr);
emit(tempstr,emptystr);
get_ch();
break;
} /* end switch. */
break; /* end case 's'. */
case 'd':
switch(charclass[ch])
{
case digit:
pack_ch();
get_ch();
break;
default:
emit("$int",packstr);
state='s';
break;
} /* end switch. */
break; /* end case 'd'. */
case 'l':
switch(charclass[ch])
{
case letter:
case digit:
pack_ch();
get_ch();
break;
default:
search_reswords(packstr, (&found));
if (found)
{
strcpy(tempstr,"$");
strcat(tempstr,packstr);
emit(tempstr,emptystr);
/* token name is $ followed by contents of packstr. */
}
else
emit("$id",packstr);
state='s';
break;
} /* end switch. */
break; /* end state 'l'. */
} /* end switch(state). */
}
while(scanning);
} /* end cycle. */
/*************************************************************************/
void get_ch(void)
/* get next character of srcfil into ch, jumping over eol's. if no characters
remain, return the sentinel '#'. don't call get_ch after '#' has been
returned. hide definition of source medium.
*/
{
/* get next non-newline character into ch (may be EOF). */
do
ch=getc(srcfilp);
while (ch=='\n');
/* now "ch==EOF" or some character to pass back verbatim */
if (feof(srcfilp))
ch='#';
} /* end get_ch. */
/*************************************************************************/
void emit(strparam s1, strparam s2)
/* emit s1 and s2 into tokfil as next token. */
{
if (scantrace)
{
printf(">>>>>>>>>>>emitting token. name=%s value=%s\n",s1,s2);
num_lines+=1;
}
fprintf(tokfilp,"%s\n",s1);
fprintf(tokfilp,"%s\n",s2);
} /* end emit. */
/*************************************************************************/
void pack_ch(void)
/* append ch to packstrg. if packstr is already full, then do nothing.
maintain packptr valid.
*/
{
if (packptr']=specchar;
charclass['=']=specchar;
charclass[',']=specchar;
charclass[';']=specchar;
charclass[':']=specchar;
charclass[' ']=blank;
charclass['#']=poundsign;
/* initialize reserved word table. */
strcpy(resword[0],"declare");
strcpy(resword[1],"stop");
strcpy(resword[2],"put");
strcpy(resword[3],"get");
strcpy(resword[4],"goto");
strcpy(resword[5],"if");
strcpy(resword[6],"then");
strcpy(resword[7],"do");
strcpy(resword[8],"end");
numreswords=9;
} /* end initialize. */
/*************************************************************************/
void scanpic(void)
/* write a one line picture showing the scanner configuration. */
{
printf("state=%c ch=%c\n",state,ch);
num_lines+=1;
/* possibly prompt user to continue. */
if (num_lines>=10)
{
printf("push Enter to continue");
getchar();
printf("----------------------------------------");
printf("---------------------------------------\n");
num_lines=0;
}
} /* end scanpic. */
/*************************************************************************/
void assign_ch(int ch, strparam s)
/* s <- ch */
{
s[0]=ch;
s[1]=NULL;
} /* end assign_ch. */
/*************************************************************************/
boolean eqstr(strparam s1, strparam s2)
/* eqstr <- true iff s1=s2 */
{
return(!strcmp(s1,s2));
} /* end eqstr. */
/*************************************************************************/
/* filename: parse.cpp author: anthony f. ortiz */
/* parser - turbo c++ version
when used as a parser:
read terminals from tokfil, which is created either through text editing or
running scanner, and output accept/reject and optionally a derivation.
the parser is based on a cfg whose rule and parse action table are encoded
procedurally in the function 'userule'. there is a restriction on the names
of the alphabet symbols: non-terminals must begin with a letter, actions
with a digit, and terminals with anything else. also, the cfg goal symbol
must be literally 'goal'. the parser is initialized to the following cfg:
goal -> e
e -> t mt
mt -> '+ t mt
mt ->
t -> f mf
mf -> '*' f mf
mf ->
f -> '$id'
f -> '(' e ')'
the subject string to be parsed should be put in tokfil as follows: each
terminal symbol occupies 1 odd-numbered line, left-justified, with
optionally trailing blanks; the even numbered lines following these each
contain blanks or are empty. e.g. to parse $id + $id tokfil should be
$id+$id
this program contains data structures and procedures that will later be
used for translation; they can be ignored when using as a parser.
when used as a translator:
read tokens from tokfil, which is created either through text editing or
running scanner, output accept/reject and optionally a derivation, and
output the corresponding codefil and datafil for later input by simul.cpp .
the translator is based on a translation cfg whose rule and parse action
table are encoded procedurally in the procedure userule and whose action
symbols are defined in the procedure doaction. the same alphabet
restrictions apply as when used as a parser. to emit code for simple
expressions, the cfg above should be changed to:
goal -> e
e -> t mt
mt -> + 1 t mt
mt ->
t -> f mf
mf -> * 2 f mf
mf ->
f -> $id 3
f -> ( e )
the subject string to be translated should be put in tokfil as follows:
each terminal symbol/token name occupies 1 odd numbered line, left-
justified, with optionally trailing blanks; the even numbered lines
following these each contain the corresponding token value, left-justified,
with optionally trailing blanks. e.g. to translate
($id,xmax) (+,empty) ($id,ymax) tokfil should be
$idxmax+$idymax
*/
/* include files */
#include
#include
#include
#include
#include
#include
/* constants */
#define CODE_SIZE 1000
#define DATA_SIZE 100
#define STACK_SIZE 100
#define STR_SIZE 50
/* maximum number of characters, not including NULL, in strings
of our standard string type 'str'
*/
char strfield[]="%50s"; /* for input into variables of type str */
int true=1;
int false=0;
char emptystr[STR_SIZE+1]="";
int fw=5; /* standard field width for output */
int parse_error=1;
/* to be returned by exit when parser hits bug */
/* types */
typedef char str[STR_SIZE+1];
/* our standard string type. allocates storage. */
/* typedef char *strparam; */
typedef char strparam[];
/* type for formal parameter strings. doesn't allocate storage. */
typedef int boolean;
/* variables */
str stack[STACK_SIZE]; /* parse stack. */
int top;
/* always indexes top of stack. top=0 indicates stack is empty. */
FILE *tokfilp;
/* pointer to tokfil, file of tokens to be read by scanner.
each token is two lines of this file.
*/
str tokname,tokvalue;
/* store 'next' token. function gettok reads into these from tokfil. */
str code[CODE_SIZE];
/* image of code memory. will be filled by parser. */
int pc; /* indexes last word emitted into code memory. */
int data[DATA_SIZE]; /* image of data memory. will be filled by parser. */
int dc; /* indexes last word emitted into data memory. */
FILE *codefilp, *datafilp;
/* pointers to codefil and datafil. code and data arrays will be
written to these files at end of parser execution.
*/
boolean parsetrace;
/* determines whether parser will produce a trace. */
/* these are my variables. */
str lasttokenvalue, buffer, variable_name;
str symbol_table [20];
int key, table_ptr, length, save_address;
/* symbol table variables for make_table () and look_up () */
int sign;
/* inequality variables */
/* function prototypes */
void cycle(void);
void userule(boolean *successp);
void doaction(void);
void emit(strparam s);
void initialize(void);
void cleanup(void);
void parsepic(void);
void replace(strparam rightpart);
void pushstring(strparam rightpart);
void pop(void);
void push(strparam s);
boolean ontop(strparam s);
char *topstack(void);
void gettok(void);
boolean athead(strparam s);
char *nextinput(void);
boolean is_action(strparam s);
boolean is_nonterm(strparam s);
boolean eqstr(strparam s1, strparam s2);
void increment_num_lines_printed(int extra_lines);
make_table ();
int look_up ();
/*************************************************************************/
void main(void)
{
clrscr(); /* turbo c++ extension to clear user window */
parsetrace=true;
initialize();
cycle();
cleanup();
end: puts("parser done");
puts("push Enter to leave User Window"); /* for turbo c++ */
getchar();
exit(0);
} /* end main. */
/*************************************************************************/
void cycle(void)
/* main cycle of parser */
{
boolean parsing, success;
if (parsetrace)
puts("starting parser execution");
parsing=true;
do /* while parsing */
{
if (parsetrace)
parsepic();
/* do case on alphabet of stack top. */
if (is_action(topstack()))
{
doaction();
pop();
}
else if (is_nonterm(topstack()))
{
userule(&success); /* to substitute for stack top */
if (!success)
{
puts("reject");
parsing=false;
}
}
else /* topstack is a terminal. */
if (ontop(nextinput()))
{
if (parsetrace)
{
printf("matching:%s\n",tokname);
increment_num_lines_printed(1);
/* and prompt to continue if large enough. */
} /* end if (parsetrace). */
pop();
gettok();
}
else /* topstack != nextinput */
{
parsing=false;
if (ontop("%") && athead("#"))
puts("accept");
else
puts("reject");
}
}
while (parsing); /* end do. */
} /* end cycle. */
/*************************************************************************/
void userule(boolean *successp)
/* use ll(1) parse action table, encoded procedurally, to either:
1) replace stack top with the right part of a rule and return *successp=true
or 2) to return *successp=false.
*/
{
*successp=true; /* will change if necessary. */
/* do case on nonterminal on top of stack. */
if (ontop("goal"))
/* replace topstack with argument "decls states". */
replace("decls states");
else if (ontop("decls"))
{
if (athead("$id") && !strcmp ("DECLARE", tokvalue))
replace("$id dlist ; decls");
else if (athead ("$id") || athead ("#") || athead (":"))
replace (emptystr);
else
*successp=false;
}
else if (ontop("dlist"))
{
if (athead("$id"))
replace("$id 17 ( $int 18 ) dltail");
else
*successp=false;
}
else if (ontop("dltail"))
{
if (athead(","))
replace(", $id 17 ( $int ) dltail");
else if (athead (";"))
replace(emptystr);
else
*successp=false;
}
else if (ontop("states"))
{
if (athead (":") || (athead("$id") && strcmp ("END", tokvalue)))
replace ("label ustate states");
else if (athead("#") || (strcmp ("$id", tokvalue)
&& !strcmp ("END", tokvalue)))
replace(emptystr);
else
*successp=false;
}
else if (ontop("label"))
{
if (athead (":"))
replace(": $id 17 19 :");
else if (athead ("$id") || athead ("#"))
replace (emptystr);
else
*successp=false;
}
else if (ontop("ustate"))
{
if (athead ("$id") && !strcmp ("IF", tokvalue))
replace ("if");
else if (athead ("$id"))
replace ("simple ;");
else
*successp=false;
}
else if (ontop ("simple"))
{
if (athead ("$id") && !strcmp ("STOP", tokvalue))
replace ("stop");
else if (athead ("$id") && !strcmp ("PUT", tokvalue))
replace ("put");
else if (athead ("$id") && !strcmp ("GET", tokvalue))
replace ("get");
else if (athead ("$id") && !strcmp ("GOTO", tokvalue))
replace ("goto");
else if (athead ("$id") && !strcmp ("DO", tokvalue))
replace ("group");
else if (athead ("$id"))
replace ("assign");
else
*successp=false;
}
else if (ontop ("stop"))
{
if (athead ("$id"))
replace ("$id 1");
else
*successp=false;
}
else if (ontop ("put"))
{
if (athead ("$id"))
replace ("$id exprlist 2");
else
*successp=false;
}
else if (ontop ("exprlist"))
{
if (athead ("-") || athead ("$id") || athead ("$int") || athead ("("))
replace ("expr eltail");
else
*successp=false;
}
else if (ontop ("eltail"))
{
if (athead (","))
replace (", expr eltail");
else if (athead (";"))
replace (emptystr);
else
*successp=false;
}
else if (ontop ("get"))
{
if (athead ("$id"))
replace ("$id varlist 3");
else
*successp=false;
}
else if (ontop ("varlist"))
{
if (athead ("$id"))
replace ("var vltail");
else
*successp=false;
}
else if (ontop ("vltail"))
{
if (athead (","))
replace (", var vltail");
else if (athead ("=") || athead (";"))
replace (emptystr);
else
*successp=false;
}
else if (ontop ("assign"))
{
if (athead ("$id"))
replace ("var = expr 4");
else
*successp=false;
}
else if (ontop ("goto"))
{
if (athead ("$id"))
replace ("$id $id 21");
else
*successp=false;
}
else if (ontop ("group"))
{
if (athead ("$id"))
replace ("$id ; states end");
else
*successp=false;
}
else if (ontop ("end"))
{
if (athead ("$id"))
replace ("$id");
else
*successp=false;
}
else if (ontop ("if"))
{
if (athead ("$id"))
replace ("$id logexp then 22 label ustate 24");
else
*successp=false;
}
else if (ontop ("then"))
{
if (athead ("$id"))
replace ("$id");
else
*successp=false;
}
else if (ontop ("logexp"))
{
if (athead ("-") || athead ("$id") || athead ("$int") || athead ("("))
replace ("expr relop");
else
*successp=false;
}
/* sign variable determines lt, gt, eq, le, ge, ne. */
else if (ontop ("relop"))
{
if (athead ("<"))
{
replace ("< mrelop");
sign = 10;
}
else if (athead (">"))
{
replace ("> mrelop");
sign = 11;
}
else if (athead ("="))
{
replace ("< mrelop");
sign = 14;
}
else
*successp=false;
}
else if (ontop ("mrelop"))
{
if (athead ("="))
{
sign = sign + 2;
sprintf (buffer, "= expr %d", sign);
replace (buffer);
}
else if (athead (">"))
{
sign = sign + 4;
sprintf (buffer, "> expr %d", sign);
replace (">");
}
else if (athead ("$id") || athead ("$int") || athead ("(") || athead ("-"))
{
sprintf (buffer, "expr %d", sign);
replace (buffer);
}
else
*successp=false;
sign = 0;
}
else if (ontop ("expr"))
{
if (athead ("$id") || athead ("$int") || athead ("("))
replace ("term mterm");
else if (athead ("-"))
replace ("- term 5 mterm");
else
*successp=false;
}
else if (ontop ("mterm"))
{
if (athead ("+"))
replace ("+ term 6 mterm");
else if (athead ("-"))
replace ("- term 7 mterm");
else if (athead (")") || athead (";")
|| athead ("=") || athead (">") || athead ("<") || athead ("$id"))
replace (emptystr);
else
*successp=false;
}
else if (ontop ("term"))
{
if (athead ("$id") || athead ("$int") || athead ("("))
replace ("fact mfact");
else
*successp=false;
}
else if (ontop ("mfact"))
{
if (athead ("*"))
replace ("* fact 8 mfact");
else if (athead ("/"))
replace ("/ fact 9 mfact");
else if (athead ("+") || athead ("-") || athead (")") || athead (";")
|| athead ("=") || athead (">") || athead ("<") || athead ("$id"))
replace (emptystr);
else
*successp=false;
}
else if (ontop ("fact"))
{
if (athead ("$id"))
replace ("var 23");
else if (athead ("$int"))
replace ("$int 16");
else if (athead ("("))
replace ("( expr )");
else
*successp=false;
}
else if (ontop ("var"))
{
if (athead ("$id"))
replace ("$id 20 subscript");
else
*successp=false;
}
else if (ontop ("subscript"))
{
if (athead ("("))
replace ("( expr 6 ) 25");
else if (athead ("=") || athead (")") || athead ("+") ||
athead ("*") || athead ("/") || athead ("-") || athead (">") ||
athead ("<") || athead (";") | athead ("$id"))
replace (emptystr);
else
*successp=false;
}
else
{
printf("bad nonterminal on stack:%s\n",topstack());
puts("parser done");
puts("push Enter to leave User Window");
getchar();
exit(parse_error); /* stop parser. */
}
} /* end userule. */
/*************************************************************************/
void doaction(void)
/* do the action associated with stack top. */
{
/* strparam topstack(), nextinput(); */
/* do case on particular action on top of stack. */
if (ontop("1"))
emit("quit");
else if (ontop("2"))
emit("out");
else if (ontop("3"))
{
emit("in");
emit ("sti");
}
else if (ontop ("4"))
emit ("sti");
else if (ontop ("5"))
emit ("neg");
else if (ontop ("6"))
emit ("add");
else if (ontop ("7"))
emit ("sub");
else if (ontop ("8"))
emit ("mult");
else if (ontop ("9"))
emit ("div");
else if (ontop ("10"))
emit ("lt");
/* numbers 11, 12, 13, 14, 15, 16 are determined by the sign variable. */
else if (ontop ("11"))
emit ("gt");
else if (ontop ("12"))
emit ("le");
else if (ontop ("13"))
emit ("ge");
else if (ontop ("14"))
emit ("eq");
else if (ontop ("15"))
emit ("ne");
else if (ontop ("16"))
{
emit ("lit");
emit (lasttokenvalue);
}
/* this is used to allocate space in the data memory. */
else if (ontop ("17"))
strcpy (variable_name, lasttokenvalue);
/* this is used to allocate space in the data memory (arrays). */
else if (ontop ("18"))
{
table_ptr = table_ptr + 1;
sprintf (buffer, " %s ", lasttokenvalue + length);
length = atoi (buffer);
make_table ();
}
/* this is used to allocate space in the data memory (labels). */
else if (ontop ("19"))
{
length = length + 1;
make_table ();
data [dc] = pc + 1;
}
/* this is used to allocate space in the data memory (non-array variables)
or look a variable up (non-array variables or arrays).
*/
else if (ontop ("20"))
{
key = look_up ();
if (key != 0)
{
emit ("lit");
sprintf (buffer, "%d", key);
emit (buffer);
}
else
{
strcpy (variable_name, lasttokenvalue);
length = length + 1;
make_table ();
emit ("lit");
sprintf (buffer, "%d", length);
emit (buffer);
}
}
/* this is used to branch to a label unconditionally. */
else if (ontop ("21"))
{
emit ("lit");
key = look_up ();
sprintf (buffer, "%d", key);
emit (buffer);
emit ("ldi");
emit ("br");
}
/* this is used to branch to the end of a if statement on false. */
else if (ontop ("22"))
{
emit ("lit");
strcpy (variable_name, "END");
length = length + 1;
make_table ();
sprintf (buffer, "%d", length);
emit (buffer);
emit ("ldi");
emit ("brf");
save_address = dc;
}
else if (ontop ("23"))
emit ("ldi");
/* this makes sure that the right line value is used for if then statements. */
else if (ontop ("24"))
{
data [save_address] = pc + 1;
}
/* this makes sure that the array indexes start at the right places. */
else if (ontop ("25"))
{
emit ("lit");
emit ("1");
emit ("sub");
}
else
printf("bad action on stack:%s\n",topstack());
} /* end doaction. */
/*************************************************************************/
void emit(strparam s)
/* emit s into next word of code memory image. */
{
if (parsetrace)
{
printf("emitting:%s\n",s);
increment_num_lines_printed(1);
}
++pc;
strcpy(code[pc],s);
} /* end emit. */
/*************************************************************************/
void initialize(void)
/* initialize parser. */
{
/* open files. */
tokfilp=fopen("tokfil","r");
if (tokfilp==NULL)
{
puts("error in trying to open tokfil");
puts("push Enter to leave User Window");
getchar();
exit(1);
}
codefilp=fopen("codefil","w");
if (codefilp==NULL)
{
puts("error in trying to open codefil");
puts("push Enter to leave User Window");
getchar();
exit(1);
}
datafilp=fopen("datafil","w");
if (datafilp==NULL)
{
puts("error in trying to open datafil");
puts("push Enter to leave User Window");
getchar();
exit(1);
}
/* further initialize input queue. */
gettok(); /* initializes tkname and tokvalue. */
/* initialize stack. */
top=0;
push("%");
push("goal");
pc=0; /* causes code to be emitted starting at code[1]. */
dc=0;
} /* end initialize. */
/*************************************************************************/
void cleanup(void)
/* do everything that needs to be done right before exiting parser. */
{
int j;
/* output code memory image to codefil. */
for (j=1;j<=pc;++j)
fprintf(codefilp,"%s\n",code[j]);
/* output data memory image to datafil. */
for (j=1;j<=dc;++j)
fprintf(datafilp,"%d\n",data[j]);
} /* end cleanup. */
/*************************************************************************/
void parsepic(void)
/* produce a short picture of the state of the parser. */
{
int j;
/* show stack. */
printf("stack= ");
for (j=top; j>=1; --j)
printf("%*s ",fw,stack[j]);
puts(""); /* end line. */
/* show next token. */
printf("tokname=%s tokvalue=%s\n",tokname,tokvalue);
puts("");
increment_num_lines_printed(3);
/* and possibly prompt user to continue. */
} /* end parsepic. */
/*************************************************************************/
void replace(strparam rightpart)
/* replace stack top, which should be a nonterminal, with rightpart.
in rightpart, whitespace is interpreted as separating distinct symbols of
the right part string.
*/
{
if (parsetrace)
{
printf("using rule: %s->%s\n", topstack(), rightpart);
increment_num_lines_printed(1);
}
pop();
pushstring(rightpart);
} /* end replace. */
/*************************************************************************/
void pushstring(strparam rightpart)
/* push the symbols in the 'rightpart' string onto the stack, interpreting
according to the replace procedure above. use recursion so as to push
the symbols in lifo order while reading 'rightpart' from left to right.
*/
{
str item, remaining;
/* item <- first symbol in rightpart, remaining <- rest of rightpart. */
strcpy(item, emptystr);
strcpy(remaining, emptystr);
sscanf(rightpart, "%s%[^\0]", item, remaining);
/* rightpart is scanned. initial whitespace is skipped and then the
longest non-whitespace sequence goes into 'item'. then, everything
up to \0 (i.e. the rest of rightpart) goes into 'remaining'.
*/
if (!eqstr(item, emptystr))
{
pushstring(remaining);
push(item); /* i.e. 'item' is pushed *after* the rest of rightpart. */
}
} /* end pushstring. */
/*************************************************************************/
void pop(void)
/* pop parser stack. */
{
--top;
} /* end pop. */
/*************************************************************************/
void push(strparam s)
/* push s onto parser stack. */
{
++top;
strcpy(stack[top],s);
} /* end push. */
/*************************************************************************/
boolean ontop(strparam s)
/* returns true iff s on top of parse stack. */
{
return(eqstr(s,stack[top]));
} /* end ontop(s). */
/*************************************************************************/
char *topstack(void)
/* topstack <- (pointer to) string on top of stack */
{
return(stack[top]);
} /* end topstack. */
/*************************************************************************/
void gettok(void)
/* get next token from tokfil. */
{
fscanf(tokfilp," "); /* try to read eof. */
if (!feof(tokfilp))
{
fscanf(tokfilp,"%[^\n]%*c",tokname);
fscanf(tokfilp,"%[^\n]%*c",tokvalue);
}
else
/* set to artificial value meaning 'end of tokfil'. */
{
strcpy(tokname,"#");
strcpy(tokvalue,"#");
}
/* save the $id and $int values for symbol_table. */
if (strcmp (tokvalue, ""))
if (strcmp (tokvalue, "#"))
if (strcmp (tokvalue, ":"))
if (strcmp (tokvalue, ";"))
if (strcmp (tokvalue, "DO"))
if (strcmp (tokvalue, "END"))
if (strcmp (tokvalue, "IF"))
if (strcmp (tokvalue, "GET"))
if (strcmp (tokvalue, "PUT"))
if (strcmp (tokvalue, "THEN"))
if (strcmp (tokvalue, "GOTO"))
if (strcmp (tokvalue, "STOP"))
strcpy (lasttokenvalue, tokvalue);
#ifdef DEBUG
printf("\ngettok: tokname=%s tokvalue=%s\n\n",tokname,tokvalue);
increment_num_lines_printed(1);
#endif
} /* end gettok. */
/*************************************************************************/
boolean athead(strparam s)
/* returns true iff terminal s is at head of input queue. */
{
return(eqstr(s,tokname));
} /* end athead(s). */
/*************************************************************************/
char *nextinput(void)
/* nextinput <- (pointer to) string at head of input queue */
{
return(tokname);
}
/*************************************************************************/
boolean is_action(strparam s)
/* return true iff s is an action symbol. */
{
return(isdigit(s[0]));
} /* end is_action. */
/*************************************************************************/
boolean is_nonterm(strparam s)
/* return true iff s is a nonterminal symbol. */
{
return(isalpha(s[0]));
} /* end is_nonterm. */
/*************************************************************************/
boolean eqstr(strparam s1, strparam s2)
/* returns true iff s1=s2 as strings. */
{
return(!strcmp(s1,s2));
} /* end eqstr. */
/*************************************************************************/
void increment_num_lines_printed(int extra_lines)
/* add 'extra_lines' to count of number of lines printed since last
prompt. if it has reached some threshold, prompt user to continue.
this is to give the user a chance read the contents of the user window
before it disappears.
*/
{
static int num_lines=0; /* number of trace lines printed since last prompt. */
int max_between_prompts=14;
num_lines+=extra_lines;
static int count;
/* possibly prompt user to continue. */
if (num_lines>=max_between_prompts)
{
printf("push Enter to continue");
getchar();
puts("************************************************************");
puts("");
num_lines=0;
}
} /* end increment_num_lines_printed. */
/*************************************************************************/
/* make the symbol table. */
make_table ()
{
for (table_ptr = table_ptr; table_ptr <= length; table_ptr++)
{
dc++;
data [dc] = 0;
strcpy (symbol_table [table_ptr], variable_name);
}
return (0);
}
/* look up a value in the symbol table. */
int look_up ()
{
for (int i = 1; i <= table_ptr; i++)
{
if (!strcmp (symbol_table [i], lasttokenvalue))
{
return (i);
}
}
return (0);
}
/* filename: simul.cpp author: anthony f. ortiz */
/* simulator
virtual machine simulator that executes intermediate language so as to
be the last module of pl/h interpreter. simulator is initialized from
codefil and datafil, which are created either through text editing or
running parser
*/
/* include files */
#include
#include
#include
#include
#include
/* define array size constants. */
#define CODE_SIZE 1000
#define DATA_SIZE 1000
#define STACK_SIZE 100
/* define miscellaneous constants. */
#define STR_SIZE 10
/* size of our standard string type 'str' */
char strfield[]="%10s"; /* for input into variables of type str */
int true=1;
int false=0;
char fwd[]="%5d";
char fws[]="%5s";
/* define types. */
typedef char str[STR_SIZE+1];
/* our standard string type. allocates storage. */
typedef char strparam[];
/* type for formal parameter strings. doesn't allocate storage. */
typedef int boolean;
/* define variables. */
str code[CODE_SIZE]; /* code memory */
int pc;
/* program counter. during execution phase, points to instruction
being executed.
*/
int data[DATA_SIZE]; /* data memory */
int stack[STACK_SIZE]; /* stack register */
int top;
/* always indexes top of stack. top=0 indicates stack is empty. */
boolean running;
boolean sim_trace;
/* determines whether a simulator trace will be produced. */
/* function prototypes */
void cycle(void);
void push(int);
int immed_op(void);
int pop(void);
void push(int j);
void simpic(void);
void initialize(void);
void read_files(void);
boolean eqstr(strparam s, strparam t);
/********************************************************************/
void main(void)
{
clrscr(); /* turbo c++ extension to clear user window */
sim_trace=true;
initialize();
cycle();
end: puts("simulator done");
puts("push Enter to leave User Window"); /* for turbo c++ */
getchar();
exit(0);
} /* end main. */
/*********************************************************************/
void cycle(void)
/* main cycle of simulator */
{
str opcode;
int top_op;
if (sim_trace)
puts("starting simulator execution");
running=true;
while (running)
{
/* increment pc and fetch next instruction. */
++pc;
strcpy(opcode,code[pc]);
if (sim_trace) simpic();
/* do case on opcode. */
if (eqstr(opcode,"quit"))
{
puts("********** simulator quit instruction executed");
puts("");
running=false;
}
else if (eqstr(opcode,"load"))
push(data[immed_op()]);
else if (eqstr(opcode,"store"))
data[immed_op()]=pop();
else if (eqstr(opcode,"lit"))
push(immed_op());
else if (eqstr(opcode,"ldi"))
push(data[pop()]);
else if (eqstr(opcode,"sti"))
{
top_op=pop();
data[pop()]=top_op;
}
else if (eqstr(opcode,"add"))
push(pop()+pop());
else if (eqstr(opcode,"sub"))
{
top_op=pop();
push(pop()-top_op);
}
else if (eqstr(opcode,"out"))
printf("********** simulator output=%d\n",pop());
/* the new instructions. */
else if (eqstr (opcode, "mult"))
push (pop () * pop ());
else if (eqstr (opcode, "div"))
{
top_op = pop ();
push (pop () / top_op);
}
else if (eqstr (opcode, "neg"))
push (-pop ());
else if (eqstr (opcode, "eq"))
{
top_op = pop ();
if (pop () == top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "lt"))
{
top_op = pop ();
if (pop () < top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "gt"))
{
top_op = pop ();
if (pop () > top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "ne"))
{
top_op = pop ();
if (pop () != top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "le"))
{
top_op = pop ();
if (pop () <= top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "ge"))
{
top_op = pop ();
if (pop () >= top_op)
push (1);
else
push (0);
}
else if (eqstr (opcode, "br"))
{
top_op = pop ();
pc = top_op - 1;
}
else if (eqstr (opcode, "brl"))
{
pc = atoi (code [pc + 1]) - 1;
}
else if (eqstr (opcode, "brf"))
{
top_op = pop ();
if (pop () == 0)
pc = top_op - 1;
}
else if (eqstr (opcode, "in"))
{
printf("********** simulator input= ");
cin >> top_op;
push (top_op);
}
else
printf("invalid opcode=%s\n",opcode);
}
} /* end cycle. */
/************************************************************************/
int immed_op(void)
/* increment pc and return code[pc] as an integer rather than as a string. */
{
++pc;
return(atoi(code[pc]));
} /* end immed_op. */
/***********************************************************************/
int pop(void)
/* pop simulator stack and return value popped. */
{
--top;
return(stack[top+1]);
} /* end pop. */
/************************************************************************/
void push(int j)
/* push j onto simulator stack. */
{
++top;
stack[top]=j;
} /* end push. */
/************************************************************************/
void simpic(void)
/* produce a 3 line picture of the state of the simulator. */
{
int j;
str opcode;
/* separate picture from previous with blank line. */
puts("");
/* show stack. */
printf("stack ");
for (j=top; j>=1; --j)
printf(fwd,stack[j]);
printf("\n");
/* show initial part of data memory. */
printf("data ");
for (j=1; j<=5; ++j)
printf(fwd,data[j]);
printf("\n");
/* show instruction about to be executed. */
strcpy(opcode, code[pc]);
printf("%s",opcode);
if (eqstr(opcode,"load") ||
eqstr(opcode,"store") ||
eqstr(opcode,"lit"))
/* then */
printf(" %s",code[pc+1]);
printf(" at %d\n",pc);
/* prompt user to continue. */
puts("push Enter to continue");
getchar();
} /* end simpic. */
/**********************************************************************/
void initialize(void)
/* initialize simulator. */
{
read_files();
pc=0; /* causes execution to begin with code[1]. */
top=0; /* initializes stack empty. */
} /* end initialize. */
/**********************************************************************/
void read_files(void)
/* read into code and data arrays from text files codefil and datafil. */
{
FILE *codefilp, *datafilp;
/* file pointers for text files from which code and data arrays are
initialized. each line of these files initializes one array
element. */
int j;
#define LINESIZE 80
char linebuf[LINESIZE];
/* read codefil. */
codefilp=fopen("codefil","r");
if (codefilp==NULL)
{
puts("error in trying to open codefil");
puts("push Enter to leave User Window");
getchar();
exit(1);
}
j=0; /* will start initializing with code[0]. */
while (!feof(codefilp))
{
++j;
fscanf(codefilp, strfield, code[j]);
}
fclose(codefilp);
/* read datafil. */
datafilp=fopen("datafil","r");
if (datafilp==NULL)
{
puts("error in trying to open datafil");
puts("push Enter to leave User Window");
getchar();
exit(1);
}
j=0;
while (!feof(datafilp))
{
++j;
fscanf(datafilp, "%d", &data[j]);
}
fclose(datafilp);
} /* end read_files. */
/*************************************************************************/
boolean eqstr(strparam s, strparam t)
/* eqstr <- true iff s=t */
{
return(!strcmp(s,t));
} /* end eqstr. */
/************************************************************************/
/* data file: srcfil.dat */
DECLARE X(5);
NUMTOSORT=5;
I = 1;
:IN:
GET X(I);
I=I+1;
IF I<= NUMTOSORT THEN GOTO IN;
I=1;
:NEXTI:
J=I+1;
:NEXTJ:
IF X(J)
BACK TO CS4110 PAGE.