Question

CSC 466 Spring 2017
Assignment:: A6
Basic Type System
---------------------------------------------------------------

Your assignment: Build the basic type system
- type set at declaration
- consult sym-tab on var usage
- build type of expression based on parts
- LHS = RHS types should match
** Also make sure vars are declared of course

Note:: we started this in class
-- start with the project you already have from
/tmp/466T/ic0315.tar.gz
that we worked on in class on Wed 3/15

*************************************************************
Kinds of changes you may need to make.....
- scanner for new symbols/keywords
-- regular expressions
- parser for expression operators, ...
-- grammar rules
- symbol table entries
-- calling functions
- type table for new types
-- calling functions
- symbol & type table look-up
-- the code

*************************************************************

Additions: (make these enhancements to the language/project)

floating point literals
** must have . and exactly 2 digits to right
-- such as: 7.23 123.45

Error message for double-declared variables

type system rules
assignment operator:
may only assign
int into int
bool into bool

may assign
float into float
int into float

math operators:
int + int -> int
float + float -> float
float + int -> float
int + float -> float
same for *
Add - with same rules
Add / but result of
any division using int and/or float is float

Add ( ) to expressions

Submission: In your CS directory by
8:00am on Tuesday 3/28

* create Type2Lastname as the directory
containing your solution
- clearly, replace "Lastname" by your name
* be sure your makefile works
* create a README file explaining
- how to run your solution
- sample programs to illustrate correctness
- clean programs; program with errors; ...
* clean the generated files
* tar your solution
% tar -cf type2lastname.tar Type2Lastname
* make sure your tar file is in your home directory
and not some other subdirectory
- don't make me look for it

Here is the makefile:

go: lex.yy.c w.tab.c
gcc w.tab.c lex.yy.c -lfl -ly -o go

lex.yy.c: w.l
flex w.l

w.tab.c: w.y
bison -dv w.y

clean:
rm -f lex.yy.c
rm -f w.output
rm -f w.tab.h
rm -f w.tab.c
rm -f go

Here is the lex code:

%{

typedef struct
{
char thestr[25];
int ival;
int ttype;
}tstruct ;

#define YYSTYPE tstruct

#include "w.tab.h"

%}

DIGIT [0-9]
UC [A-Z]
LC [a-z]
L [A-Za-z]

%%

START { return tstart;}
FINISH { return tfinish;}
BEGIN { return tbegin;}
END { return tend;}
INT { return tint;}
FLOAT { return tfloat;}
BOOL { return tbool;}
PRINT { return tprint;}
PRINTLN { return tprintln;}
IF { return tif;}
WHILE { return twhile;}
LT { return tlt;}
GT { return tgt;}
EQ { return teq;}
":(" { return tfalse;}
":)" { return ttrue;}
":=" { return tassign;}

\"([^"]*)\" { return tstrlit;}
{L}+ { return tid; }
{DIGIT}+ { return tnum; }

@@.*\n {} /* comments */

[ \t] /* ignore whitespace */

\n {}

<<EOF>> yyterminate(); /* signal end of dialogue */

. return yytext[0];

%%

Here is the yacc code:

%{

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
char thestr[25];
int ival;
int ttype;
}tstruct ;

#define YYSTYPE tstruct

int yylex();
void yyerror( char *s );

#include "symtab.c"

%}

%token tstart
%token tfinish
%token tbegin
%token tend
%token tint
%token tfloat
%token tbool
%token tprint
%token tprintln
%token tif
%token twhile
%token tlt
%token tgt
%token teq
%token tfalse
%token ttrue
%token tassign
%token tstrlit
%token tid
%token tnum

%%

p : prog ;

prog : tstart tfinish
| tstart DL SL tfinish {printf("Prog\n");}
;

DL : DL D {printf("declst\n");}
| D {printf("declst\n");}
;

D : tid Dtail { addtab($1.thestr);
addtype($1.thestr, $2.ttype);
}
;

Dtail : ',' tid Dtail { addtab($2.thestr);
addtype($2.thestr, $3.ttype);
$$.ttype = $3.ttype;
}
| ':' type ';' {$$.ttype = $2.ttype;}
;

type: tint {$$.ttype = 10;} | tfloat {$$.ttype = 20;} | tbool {$$.ttype = 30;} ;

SL : SL S {printf("stmtlst\n");}
| S {printf("stmtlst\n");}
;

S : tprint tstrlit ';' {printf("print lit\n"); }
| tprint tid ';'
{
printf("print id\n");
if ( intab($2.thestr) )
printf("%s is declared %d\n", $2.thestr, @2.first_line);
else
printf("UNDECLARED:: %s \n", $2.thestr);
}
| tprintln ';'
| tid tassign expr ';'
{
printf("assign\n");
if ( intab($1.thestr) )
printf("%s is declared\n", $1.thestr);
else
printf("UNDECLARED:: %s \n", $1.thestr);

$1.ttype = gettype($1.thestr);
if ($1.ttype > 0 )
{
if ($1.ttype == $3.ttype)
;
else
{
printf("Incompatible ASSIGN types %d %d\n", $1.ttype, $3.ttype);
}
}
else
yyerror("Type Error :::");

}
| error ';' {printf("error in statement\n");}
;

expr : expr '+' term
{
if ($1.ttype == 10 && $3.ttype == 10) $$.ttype = 10;
else if ($1.ttype == 20 && $3.ttype == 20) $$.ttype = 20;
else $$.ttype = -1;
}
| term { $$.ttype = $1.ttype; }
;

term : term '*' factor
{
if ($1.ttype == 10 && $3.ttype == 10) $$.ttype = 10;
else if ($1.ttype == 20 && $3.ttype == 20) $$.ttype = 20;
else $$.ttype = -1;
}
| factor { $$.ttype = $1.ttype; }
;

factor : tid
{
if ( intab($1.thestr) )
printf("%s is declared\n", $1.thestr);
else
printf("UNDECLARED:: %s \n", $1.thestr);
$$.ttype = gettype($1.thestr);
if ($$.ttype > 0 )
;
else
yyerror("Type Error :::");
}
| tnum {$$.ttype = 10;}
| ttrue {$$.ttype = 30;}
| tfalse {$$.ttype = 30;}
;

%%

int main()
{
yyparse ();
printf("---------------------\n");
showtab();
}

void yyerror(char *s) /* Called by yyparse on error */
{
printf ("\terror: %s\n", s);
printf ("ERROR: %s at line %d\n", s, 123);
}

Here is the sym.c code

struct stelem
{
char sname[25];
int stype;
};
typedef struct stelem entry;

entry symtab[100];
int nsym;

void addtab( char *s)
{
nsym++;
strcpy( symtab[nsym].sname, s);
symtab[nsym].stype = -1;
}

void showtab()
{
int i;
for (i = 1; i <= nsym; ++i)
printf("%d: %s %d\n", i, symtab[i].sname, symtab[i].stype);
}

int intab( char *s)
{
int i;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
return 1;
}
return 0;

}

int addtype( char *s, int t)
{
int i, loc = -1;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
loc = i;
}
if (loc > 0)
{
printf("Set type %s to %d\n", s, t);
symtab[loc].stype = t;
}
else
{
printf("Unable to set type %s to %d\n", s, t);
}
}

int gettype( char *s)
{
int t = -1;
int i, loc = -1;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
loc = i;
}
if (loc > 0)
{
t = symtab[loc].stype;
printf("Get type for %s to %d\n", s, t);
}
if (loc <= 0)
printf("gettype var %s not found\n", s);
else if (t < 0)
printf("gettype var %s has bad type %d\n", s, t);
else
printf("gettype var %s has type %d\n", s, t);

return t;
}

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
char thestr[25];
int ival;
int ttype;
}tstruct ;

#define YYSTYPE tstruct

int yylex();
void yyerror( char *s );

#include "symtab.c"

%}

%token tstart
%token tfinish
%token tbegin
%token tend
%token tint
%token tfloat
%token tbool
%token tprint
%token tprintln
%token tif
%token twhile
%token tlt
%token tgt
%token teq
%token tfalse
%token ttrue
%token tassign
%token tstrlit
%token tid
%token tnum

%%

p : prog ;

prog : tstart tfinish
| tstart DL SL tfinish {printf("Prog\n");}
;

DL : DL D {printf("declst\n");}
| D {printf("declst\n");}
;

D : tid Dtail { addtab($1.thestr);
addtype($1.thestr, $2.ttype);
}
;

Dtail : ',' tid Dtail { addtab($2.thestr);
addtype($2.thestr, $3.ttype);
$$.ttype = $3.ttype;
}
| ':' type ';' {$$.ttype = $2.ttype;}
;

type: tint {$$.ttype = 10;} | tfloat {$$.ttype = 20;} | tbool {$$.ttype = 30;} ;

SL : SL S {printf("stmtlst\n");}
| S {printf("stmtlst\n");}
;

S : tprint tstrlit ';' {printf("print lit\n"); }
| tprint tid ';'
{
printf("print id\n");
if ( intab($2.thestr) )
printf("%s is declared %d\n", $2.thestr, @2.first_line);
else
printf("UNDECLARED:: %s \n", $2.thestr);
}
| tprintln ';'
| tid tassign expr ';'
{
printf("assign\n");
if ( intab($1.thestr) )
printf("%s is declared\n", $1.thestr);
else
printf("UNDECLARED:: %s \n", $1.thestr);

$1.ttype = gettype($1.thestr);
if ($1.ttype > 0 )
{
if ($1.ttype == $3.ttype)
;
else
{
printf("Incompatible ASSIGN types %d %d\n", $1.ttype, $3.ttype);
}
}
else
yyerror("Type Error :::");

}
| error ';' {printf("error in statement\n");}
;

expr : expr '+' term
{
if ($1.ttype == 10 && $3.ttype == 10) $$.ttype = 10;
else if ($1.ttype == 20 && $3.ttype == 20) $$.ttype = 20;
else $$.ttype = -1;
}
| term { $$.ttype = $1.ttype; }
;

term : term '*' factor
{
if ($1.ttype == 10 && $3.ttype == 10) $$.ttype = 10;
else if ($1.ttype == 20 && $3.ttype == 20) $$.ttype = 20;
else $$.ttype = -1;
}
| factor { $$.ttype = $1.ttype; }
;

factor : tid
{
if ( intab($1.thestr) )
printf("%s is declared\n", $1.thestr);
else
printf("UNDECLARED:: %s \n", $1.thestr);
$$.ttype = gettype($1.thestr);
if ($$.ttype > 0 )
;
else
yyerror("Type Error :::");
}
| tnum {$$.ttype = 10;}
| ttrue {$$.ttype = 30;}
| tfalse {$$.ttype = 30;}
;

%%

int main()
{
yyparse ();
printf("---------------------\n");
showtab();
}

void yyerror(char *s) /* Called by yyparse on error */
{
printf ("\terror: %s\n", s);
printf ("ERROR: %s at line %d\n", s, 123);
}

Here is the sym.c code

struct stelem
{
char sname[25];
int stype;
};
typedef struct stelem entry;

entry symtab[100];
int nsym;

void addtab( char *s)
{
nsym++;
strcpy( symtab[nsym].sname, s);
symtab[nsym].stype = -1;
}

void showtab()
{
int i;
for (i = 1; i <= nsym; ++i)
printf("%d: %s %d\n", i, symtab[i].sname, symtab[i].stype);
}

int intab( char *s)
{
int i;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
return 1;
}
return 0;

}

int addtype( char *s, int t)
{
int i, loc = -1;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
loc = i;
}
if (loc > 0)
{
printf("Set type %s to %d\n", s, t);
symtab[loc].stype = t;
}
else
{
printf("Unable to set type %s to %d\n", s, t);
}
}

int gettype( char *s)
{
int t = -1;
int i, loc = -1;
for ( i = 1; i <= nsym; ++i)
{
if ( strcmp(symtab[i].sname, s) == 0)
loc = i;
}
if (loc > 0)
{
t = symtab[loc].stype;
printf("Get type for %s to %d\n", s, t);
}
if (loc <= 0)
printf("gettype var %s not found\n", s);
else if (t < 0)
printf("gettype var %s has bad type %d\n", s, t);
else
printf("gettype var %s has type %d\n", s, t);

return t;
}