Link to home
Start Free TrialLog in
Avatar of sam5a1
sam5a1Flag for United States of America

asked on

passing token values from a tree to do type checking

I am writing a compiler but am having trouble "seeing" the values of tokens. I am tring to create a type checking file for the tree that I made from the parser but I can't get the check file to "see" the token types, Real, Integer, Boolean or their values. I have included some of the programs where I think the problems might be, if anyone can see what I'm doing wrong please tell me.
include files are ST.h and tree.h
ST.h file:
        : blocktypedef struct {
        int index;
        int type;
        int scope;
} STentry;

tree.h file:
typedef struct Node {
        int     kind, value;
        float   dval;
        struct  Node *first, *second, *third, *next;
} node;
typedef node    *tree;

tree buildTree (int kind, tree first, tree second, tree third);
tree buildIntTree (int kind, int val);
tree buildFloatTree (int kind, double dval);
void printTree (tree);

void check (tree);

from parse progam:

program
                {;root = $1;}
        ;
block
        :Begin optdecls stmts End
                {$$ = buildTree(Begin, $2, $3, buildTree(End, NULL, NULL, NULL));}
        ;
optdecls
        : /*nothing*/
                {$$ = NULL;}
        | decl Semicol optdecls
        {$$ = buildTree(Semicol,$1, $3, NULL);}
/*{$$ = buildTree(Semicol,$1, NULL, NULL);$$->next = $3;} */
        ;
decl
        :vardecl
                {$$ = $1;}
        |arraydecl
                {$$ = $1;}
        ;
vardecl
        :type idlist
                {$$->next = $2; $$ = $1;}
        ;
type
        :Real
                {$$ = buildTree(Real, NULL, NULL, NULL);}
                /*{$$ = buildFloatTree(Real, $<dval>1);}*/
        |Integer
                {$$ = buildTree(Integer, NULL, NULL, NULL);}
        |Boolean
                {$$ = buildTree(Boolean, NULL, NULL, NULL);}
        ;
idlist
        :Ident
                {$$ = buildIntTree(Ident, $1);}
        |Ident Coma idlist
        {$$ =buildTree(Coma, buildIntTree(Ident, $1), $3, NULL);}
        ;
etc. more productions, more trees

/*Here is where I am really having troubles, I can't "find " the tokens such as Assign, etc to allow me to do type checking or any kind of checking*/


from check.c file:

#include <stdio.h>
#include "tree.h"
#include "y.tab.h"
#include "ST.h"

extern int top;
STentry ST[100] = {0, NoType};

void prST (void)
{
        int i;
        printf ("SYMBOL TABLE\n");
        for (i = 0; i <= top; i++) {
                int     t = ST[i].type;
                printf ("%3d %-10s\t%s\n", i, id_name (i),
                                t == Integer ? "Integer" : t == Boolean ? "Boolean" : t == Real ? "Real" : "<no type>");
                }
}

static void handle_decls (tree t)
{
        for (t; t!= NULL; t = t->next) {
                int     type = t->kind;
                tree    p;
                int i = 0;
                if (type != Integer && type != Boolean && type != Real) {;}/*{
                        fprintf (stderr, "Bad type in decl\n"); return;
                        }*/
               for (p = t->first; p != NULL; p = p->next) {
                        int     pos = p->value;
                        i += 1;
                        ST[pos].type = type; printf("type %d\n",ST[pos].type);
                        ST[pos].index = pos;/*printf("var name %d\n", ST[pos].index);*/
        printf ("Var name and position: %3d %-10s\n", ST[pos].index, id_name (ST[pos].index));
/*prST ();*/
                        }
                }
}

void check (tree t)
{
        for (t; t != NULL; t = t->next)
        /*int i = 0; for scope start a 0 here until Begin is found*/
                switch (t->kind) {
                        case Begin:{printf("%d\n", t->kind);
                                handle_decls (t->first);printf("%d\n", t->kind);
                                check (t->second);
                        check(t->third);
                                printf ("\n");}
                                prST ();
                                break;
                       case Semicol:
                             handle_decls (t->first);
                             check (t->second);
                             check(t->third);
                              printf ("\n");
                              break;
                        case Assign :{
                                int pos = t->first->value;
                                if (ST[pos].index == 0) {
                                        ST[pos].index = pos;
                                        ST[pos].type = Integer;
                                        }
                                if (check_expr (t->second) != ST[pos].type)
                                        fprintf (stderr, "Type error in assignment to identifier %s\n",
                                                                id_name(t->first->value));
                                break;
                                }
Avatar of cwwkie
cwwkie

It would be helpful if you can give an example what it is currently doing.
Avatar of sam5a1

ASKER

Here is the tree printed out. There is a lot more, but this is the start showing where the program begins, the variable types, etc. After this, I will show the output for the check.c. The problem is that I can't get my check.c file to grab the var. types or what  they are.
From the check.c file, I can't get it to "find" the type or value. e.g. the first one shown after Begin is a semicoln, a terminal, the actual input was:

Begin
real x; Boolean z: integer a;1

From printTree:

Begin
  ;
    Real
    Ident  x (1)
    ;
      Boolean
      Ident  z (2)
      ;
        Integer
        ,
          Ident  a (3)
          Ident  b (4)
        ;
          Array
            Real
            [ ]
              Ident  y (5)
              -
                IntConst  1
              IntConst  3
  ;
    :=
      Ident  x (1)
      +
        Realno  3.00000
        *
          Realno  9.00000
  ;
    :=
      Ident  a (3)
      IntConst  12345
  ;
    :=
      Ident  z (2)
      True
etc.

Now from check.c:

SEMICOLIN HAS BEEN FOUND(for debugging)
type 32
Var name and position:    x

SEMICOLIN HAS BEEN FOUND(for debugging)
type 32
Var name and position:    a

SEMICOLIN HAS BEEN FOUND(for debugging)
type 32
Var name and position:    z
         .
         .
         .

SYMBOL TABLE
  0 <no name>   <no type>
  1 x           <no type>
  2 z           <no type>
  3 a           <no type>
  4 b           <no type>
  5 y           <no type>

I can't get my switch command from the check.c file to pickup the Real, Boolean, Integer ot the values that are assigned to them later in the program.
Matter of fact, I can't get my switch{case xxxxxx:  to work for most to the tree. it's like the tree I made only has a couple branches or I'm looking in the wrong place for the nodes.

Avatar of Infinity08
in prST() :
>> t == Integer ? "Integer" : t == Boolean ? "Boolean" : t == Real ? "Real" : "<no type>"

How are Integer, Boolean and Real defined ? As an enum ?

Try to print out t, to see what it really contains ... Also check that the values of Integer, Boolean and Real are what you expect them to be (ie. they are correctly included and visible !).
Avatar of sam5a1

ASKER

I have tried to print the values that are passed back, but so far I have not been able to "see" these.

They are passed as int as defined in the zb.y file. the tree struct is defined in the tree.h fils as:
typedef struct Node {
      int      kind, value;
      struct      Node *first, *second, *third, *next;
} node;
typedef node      *tree;

tree buildTree (int kind, tree first, tree second, tree third);
tree buildIntTree (int kind, int val);
void printTree (tree);

void check (tree);

"...check that the values ..."
That is one of the problems, the values that are eventually assigned to the variables don't seem to be visible so I don't know if they are included. I suspect they are not.
What does it print when you change the prST() function like this :

void prST (void)
{
        int i;
        printf("debug:: Integer = %d\n", Integer);
        printf("debug:: Boolean = %d\n", Boolean);
        printf("debug:: Real = %d\n", Real);
        printf ("SYMBOL TABLE\n");
        for (i = 0; i <= top; i++) {
                int     t = ST[i].type;
                printf ("%3d %-10s\t<%d>:%s\n", i, id_name (i), t,
                                t == Integer ? "Integer" : t == Boolean ? "Boolean" : t == Real ? "Real" : "<no type>");
                }
}
Avatar of sam5a1

ASKER

I'll have to let you know later, I won't be able to do that until I get home tonight (no remote here). If I can get it done sooner, I will.
Avatar of sam5a1

ASKER

Infinity80

Here are the results:

SYMBOL TABLE
debug:: Integer = 17
debug:: Boolean = 56
debug:: Real = 22
  0 <no name>   <3>:<no type>
  1 x           <32>:<no type>
  2 z           <32>:<no type>
  3 a           <32>:<no type>
  4 b           <14>:<no type>
  5 y           <0>:<no type>

if you look at the tokens, you will see that you pulled the type from where the variable was found: ie 32 is an assing statement ,( from input) 14 a For stmt, 3 an if stmt. the tokens are posted below along with the input file. The zero should have been from a do stmt, I see that I need to do something about /t/n's.

%token <i> Ident 1 IntConst 2
%token  RealConst 4 If 3 End 5 Do 7 Else 8 And 9 Array 10
%token <i> Begin 11
%token  Equiv 12 False 13 For 14 Goto 15 Imply 16 Integer 17 Label 18 Not 19
%token  Or 20 Procedure 21 Real 22 Step 23 String 24 Then 25 True 26 Until 27 Value 28 While 29
%token  Own 30 Div 31 Assign 32 Exp 33 Coma 34 Col 35 Semicol 36 Lbrack 37 Rbrack 38 LParen 39
%token  RParen 40 Plus 41 Minus 42 Star 43 Slash 44 Eq 45 Ne 46 Lt 47 Le 48
%token  Gt 49 Ge 50 UPlus 51 UMinus 52 NoType 54
%token <i> Boolean 56
%token <i> Realno 57

begin
real x; Boolean z; integer a, b;
real array y[-1:3];

x := 3.0+4.0*9.0;  a:= 12345;
z := true;
if z and x >= 12.56
then
        begin z := a < 56 or x <= 235.672;
        end
else
        z := not z and x != (if b > 4 then 2.5 else 1.9);
for b := a+3 step -1 until -2034 div a
do
        y[b] := 27 - x * y[b-1];
end
>> if you look at the tokens, you will see that you pulled the type from where the variable was found: ie 32 is an assing statement
So, that's your problem ... you determine the "type of the variable" by checking the "type of where the variable was found". In other words, ST[i].type doesn't contain the type of the variable at position i in the symbol table, but it contains the type of where the variable was found.

The solution is to store the correct type in the symbol table. Check your parser to see what information it stores in the tree for variable types.
Avatar of sam5a1

ASKER

Heres where I'm building my tree. The variables should have been picked up when they were first declared. Also, I still can't figure out why my switch/case statements won't pick up the tokens. any ideas?

code from parser:

 program
        : block
                {;root = $1;}
        ;
block
        :Begin optdecls stmts End
                {$$ = buildTree(Begin, $2, $3, buildTree(End, NULL, NULL, NULL));}
        ;
optdecls
        : /*nothing*/
                {$$ = NULL;}
        | decl Semicol optdecls
        /*{$$ = buildTree(Semicol,$1, $3, NULL);}*/
        {$$ = buildTree(Semicol,$1, NULL, NULL);$$->next = $3;}
        ;
decl
        :vardecl
                {$$ = $1;}
        |arraydecl
                {$$ = $1;}
        ;
vardecl
        :type idlist
                {$1->first = $2;$$ = $1;}
        ;
type
        :Real
                {$$ = buildTree(Real, NULL, NULL, NULL);}
        |Integer
                {$$ = buildTree(Integer, NULL, NULL, NULL);}
        |Boolean
                {$$ = buildTree(Boolean, NULL, NULL, NULL);}
        ;
idlist
        :Ident
                {$$ = buildIntTree(Ident, $1);}
        |Ident Coma idlist
        {$$ =buildTree(Coma, buildIntTree(Ident, $1), $3, NULL);}
        ;
arraydecl
        :Array arraylist
                {$$ = buildTree(Array, $2, NULL, NULL);}
        |type Array arraylist
                {$$ = buildTree(Array, $1, $3, NULL);}
        ;
arraylist
        :arrayseg
                {;$$ = $1;}
        |arrayseg Coma arraylist
                {;$$ = buildTree(Coma, $1, NULL, NULL);$$->next=$3 ;}
        ;
arrayseg
        :Ident Lbrack a_expr Col a_expr Rbrack
                {$$ = buildTree(Lbrack, buildIntTree(Ident, $1), $3, $5);}
        ;
stmts
        :stmt
                {$$ = $1;}
        |stmt Semicol stmts
        /*      {$$ = buildTree(Semicol, $1, $3, NULL);}*/
                {$$ = buildTree(Semicol, $1, NULL, NULL);$$->next=$3 ;}
        ;
stmt
        : u_stmt
                /*{$$ = $1;}*/
        | if_stmt
                /*{$$ = $1;}*/
        | for_stmt
                /*{$$ = $1;}*/
        ;
u_stmt
        :assign
                /*{$$ = $1;}*/
        |dummy
                /*{$$ = $1;}*/
        |block
                /*{;$$ = $1;}*/
        ;
assign
        : var Assign expr
        : var Assign expr
                {$$ = buildTree(Assign, $1, $3, NULL);}
        | var Assign assign
                {$$ = buildTree(Assign, $1, NULL, NULL);$$->next=$3 ;}
        ;
dummy
        : /*nothing*/
                {$$ = NULL;}
        ;
for_stmt
        :For var Assign a_expr Step a_expr Until a_expr Do stmt
                {$$ = buildTree(For, $2, $4, buildTree(Step, $6, $8, $10));}
        ;
if_stmt
        :If expr Then u_stmt
                {$$ = buildTree(If, $2, $4, NULL);}
        |If expr Then u_stmt Else stmt
                {$$ = buildTree(If, $2, $4, $6);}
        |If expr Then u_stmt for_stmt
                {$$ = buildTree(If, $2, $4, $5);}
        ;
var
        : Ident
                {$$ = buildIntTree(Ident, $1);}
        | Ident Lbrack expr Rbrack
                {$$ = buildTree(Lbrack, buildIntTree(Ident, $1), $3, NULL);}
        ;
factor
        :IntConst
        :IntConst
                {$$ = buildIntTree(IntConst, $1);}
        | Realno
                {$$ = buildFloatTree(Realno, $1);}
        |var
                {$$ =$1;}
        |LParen expr RParen
                /*{$$ = buildTree(LParen, $2, NULL, NULL);} */
                {$$ = $2;}
        ;
term
        : factor
                {$$ =$1;}
        | term Star factor
                {$$ = buildTree(Star, $1, $3, NULL);}
        | term Slash factor
                {$$ = buildTree(Slash, $1, $3, NULL);}
        | term Div factor
                {$$ = buildTree(Div, $1, $3, NULL);}........
ASKER CERTIFIED SOLUTION
Avatar of Infinity08
Infinity08
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of sam5a1

ASKER

{two part reply to your post, so please look to the end}

Your right about the tree. I see that now but I would add only one thing to the tree you made, and maybe this is wrong and if it is please correct me BUT after
Real:

....->[Real]-1-> [Coma] - 1-> [Ident, a]
                -2-> [Ident, x]

putting the ident one level even further down.
so getting rid of the link lists might make the tree easier to "read". ie instead of , from your example:

[Begin]  -1-> [Semicol] -1-> [Real] -1-> [Ident , x]
                                                    -2-> NULL
                                                    -3-> NULL
                                   -2-> NULL
                                   -3-> NULL
                                   -next-> ...optdecls...
if I change this:
{$$ = buildTree(Semicol,$1, NULL, NULL);$$->next = $3;}
 
back to this:
{$$ = buildTree(Semicol,$1, $3, NULL);}

the tree would change to this:

[Begin]  -1-> [Semicol] -1-> [Real] -1-> [Ident , x]
                                                    -2-> NULL
                                                    -3-> NULL
                                   -2-> optdecls->[Semicol]-1->[Integer]-1->[Ident, y]
                                   -3-> NULL
                                   

You agree?        

>>>Now, also check that in the Assign part of the switch, you don't update the symbol table ... the symbol table should only updated on variable declaration, not on assignment.<<<

any quick recomendations?

thanks
>> putting the ident one level even further down.
As I said ... I could have been mistaken in interpreting the parser (I didn't compile it, just processed it in my head :)) ... check the actul tree contents (print them out completely) to verify that the nodes DO contain what you expect them to contain.

>> back to this:
>> {$$ = buildTree(Semicol,$1, $3, NULL);}
That does indeed look a bit easier ... I was wondering what the "next" was for ...

>> any quick recomendations?
Not quicker than the one I gave ... the only writes into the symbol table should be done in the handle_decls() function, which should handle all variable declarations. From what I can see, you're also doing changes in the Assign part of the switch in the check() function ... and possibly elsewhere too.

If you make your design as easy as possible (meaning : if you follow simple rules like "change the symbol table in one location only"), your code should be a lot more easy to understand, change, maintain, ...
Avatar of sam5a1

ASKER

Thanks, the only thing more you could do for me is to write the code itself. If you feel like demonstrating you prowness I'll let you. If not, I'm still giving you the points. Thanks for the help
I've got a lot of other projects at the moment, so writing the parser for a compiler is not exactly a task I can just do on the side ... I can however guide you, and answer your questions if you would have any ... whenever i can I'll answer them for you.

I hope that's ok for you ...
Avatar of sam5a1

ASKER

Oops, forgot to give you the points. I appreciate the offer and if I get in trouble again, I'll holler.
OK, one more question if you don't mind, before I close this.
In the case Assign:
                  case Assign :{
                        int pos = t->first->value;
                        if (ST[pos].index == 0) {
                              ST[pos].index = pos;
                              ST[pos].type = Integer;
                              }
                        if (check_expr (t->second) != ST[pos].type)
                              fprintf (stderr, "Type error in assignment to identifier %s\n",
                                                id_name(t->first->value));
                        break;
                        }
how would you change this to do the type check between the value and the variable? (if you don't mind)
Thanks again anyway
An assignment is not a declaration, so, this check :

    if (ST[pos].index == 0)

should never be true.

You can however have a declaration with initialization (immediate assignment), but that should be treated separately, and in the declaration parsing ...
Avatar of sam5a1

ASKER

Given my check.h:
typedef struct {
      int index;
      int type;
      int scope;
} STentry;

extern STentry ST[];

are you saying that the case Assign:, even if I remove this test if (ST[pos].index == 0), won't work?
I'm saying that there's a problem with the parser if test check DOES become true. A normal parser should treat a declaration as a declaration and an assignment as an assignment. When an assignment is found for a variable that hasn't been declared yet, then there's either a problem with the parser, or the parsed code contains an error.
Avatar of sam5a1

ASKER

OK, I get you. Last comment, if you have the time and feel like it. How would you handle this Assign assignment.
Well, look up the id for the variable to assign to in the symbol table. If it's not found, throw an error.
Use this tree :

    [Assign] -1-> variable ID
                 -2-> right-hand side
                 -3-> NULL

ie. pretty much the same way you have it now, except for the fact that you need the variable to be declared earlier.
Avatar of sam5a1

ASKER

Thanks for the pointers :) and help