SYMBOL TABLE

   All Compilers and interpreters must maintain a data structure
   called the SYMBOL TABLE. This is where all the inFormation about
   the Programs symbols are kept. Maintaining a well-organized
   symbol table is a skill all Compiler Writers must master.

   As a Compiler parses a source Program, it relies on the symbol
   table to provide inFormation about each identifier (such as
   Variables and Constants) - it must be able to access and update
   inFormation about each identifier and do so quickly - otherwise
   the process is slowed or produces incorrect results.

   No matter what inFormation is kept, or how the table is organized
   certain operations are fundamental to a symbol tables operation.

   You ENTER inFormation about about an identifier into the table by
   *creating* and entry.

   You SEARCH the table to look up an identifier's entry and make
   available the inFormation in that entry.

   You UPDATE the entry to modify stored inFormation.

   There can be only one entry per identifier in the symbol table,
   so you must first search the table beFore making a new entry.

   TABLE ORGANIZATION

   There are many different ways to handle symbol tables: Arrays,
   linked lists, hash tables...but since the most common operations
   perFormed on a symbol table are searching it For existing entries
   it makes perfect sense to implement it as a BINARY TREE.

   Each NODE in the TREE contains and entry, and points to two other
   nodes. The *values* of the nodes on the subtree to the left are
   always LESS than the parent node, While the subtree to the right
   is always MORE than the parent. This makes searching sorted
   binary trees very efficient.

   Inserting new nodes is as easy as searching the tree: if the
   value you want to insert is LESS than the current node, search
   the node to the left. If it is MORE, search the tree to the right.
   Keep doing this recursively Until an empty node is found, then
   insert the value into that node.

   NITTY-GRITTY

   Now that we've covered some background on the table, here's a
   recap on the symbol table Type defs. For those that missed them
   in the first message, or didn't save them:

Type
   sptr = ^String; { useful For minimum-size allocation }

   DEFN_KEY = (UNDEFINED,
               Const_DEFN, Type_DEFN, Var_DEFN, FIELD_DEFN,
               VALPARM_DEFN, VarPARM_DEFN,
               PROG_DEFN, PROC_DEFN, FUNC_DEFN
              );

   ROUTINE_KEY = (rkDECLARED, rkForWARD,
                  rkREAD, rkREADLN, rkWrite, rkWriteLN,
                  rkABS, rkARCTAN, rkCHR, rkCOS, rkEOF, rkEOLN,
                  rkEXP, rkLN, rkODD, rkORD, rkPRED, rkROUND,
                  rkSIN, rkSQR, rkSQRT, rkSUCC, rkTRUNC
                 );

   RTN_BLOCK = Record               {info about routine declarations}
      key              :ROUTINE_KEY;
      parm_count,
      total_parm_size,
      total_local_size :Word;
      parms, locals,
      local_symtab     :SYMTAB_PTR; {symbol tables of routine}
      code_segment     :sptr;       {interpreter}
   end;

   DTA_BLOCK = Record
      offset     :Word;
      Record_idp :SYMTAB_PTR;
   end;

   INFO_REC = Record
      Case Byte of
        0:(Constant :VALUE);     { literal value }
        1:(routine  :RTN_BLOCK); { identifier is routine }
        2:(data     :DTA_BLOCK); { identifier is data }
   end;

   DEFN_REC = Record
      key  :DEFN_KEY; { what is identifier? }
      info :INFO_REC; { stuff about identifier }
   end;

   SYMTAB_PTR  = ^SYMTAB_NODE;
   SYMTAB_NODE = Record          {actual tree node}
      left, right   :SYMTAB_PTR; {Pointers to left and right subtrees}
      next          :SYMTAB_PTR; {For chaining a node}
      name          :sptr;       {identifier name String}
      level,                     {nesting level}
      co_index      :Integer;    {code Label index}
      defn          :DEFN_REC;   {definition info}
   end; { Record }

   EXCERCISE #1

   Implement a symbol table SEARCH routine, and a symbol table ENTER
   routine. Both routines must accept a Pointer to the root of the
   tree, and the name of the identifier you are working With, and
   must return a Pointer to the node that was found in the search
   routine, or enters in the enter routine. If no node was found, or
   entered, the routines must return NIL.

   The resulting symbol table should be a sorted tree.



³   Implement a symbol table SEARCH routine, and a symbol table ENTER
³   routine. Both routines must accept a Pointer to the root of the
³   tree, and the name of the identifier you are working with, and
³   must return a Pointer to the node that was found in the search
³   routine, or enters in the enter routine. If no node was found, or
³   entered, the routines must return NIL.
³   The resulting symbol table should be a sorted tree.



Function Enter(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
{ - inserts a new indetifier String PidStr in the symol table. }
{ - nil is returned if duplicate identifier is found.          }
Var
  Ptemp: SymTab_Ptr;
begin
  if (root <> nil) then    { not a terminal node }
    if (PidStr = root^.name) then
      begin
        Enter := nil;
        Exit
      end
    else    { recursive insertion calls to either left or right sub-tree }
      if (PidStr > root^.name) then
        Enter(root^.right, PidStr)
      else
        Enter(root^.left, PidStr)
  else { a terminal node }
    begin
      new(Ptemp);     { create a new tree leaf node }
      Ptemp^.name := PidStr;
      Ptemp^.left := nil;
      Ptemp^.right := nil
    end
end; { Enter }


Function Search(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
{ - search For a certain identifier String PidStr in the symbol table. }
{ - returns nil if search faild.                                       }
begin
  While (root <> nil) and (PidStr <> root^.name) do
    if (PidStr > root^.name) then     { search the right sub-tree }
      root := root^.right
    else
      if (PidStr < root^.name) then
        root := root^.left;           { search the left sub-tree  }
   Search := root                     { return the node           }
end;

{===========================================================================}

Comment:
     What made you choose BINARY trees over AVL trees?  With binary trees,
     the structure may become degenerate (unbalanced) and, the routines for
     searching and insertion becomes inefficient.

>Comment:
>     What made you choose BINARY trees over AVL trees?  With binary trees,
>     the structure may become degenerate (unbalanced) and, the routines for
>     searching and insertion becomes inefficient.

   Glad you could join us!

   I chose a binary tree because it's simple and easy to Write, also
   a degenerate tree isn't much of a concern, simply because it's
   intended to hold only identifiers and Constants, not every
   statement. :)

   As long as it sorts the data as it inserts, it will work. This
   isn't, after all, a graduate "course". The intention is to teach
   people how compilers work and show interested parties how to
   understand and Write their own, if they're interested. This is
   YOUR compiler you're writing, if you want to implement an AVL
   tree, go ahead!

>Function Search(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;

   This works. It's efficient and does the job.

>Function Enter(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;

>    else    { recursive insertion calls to either left or right sub-tree }
>      if (PidStr > root^.name) then
>        Enter(root^.right, PidStr)
>      else
>        Enter(root^.left, PidStr)

   Note: recursive calls shouldn't be necessary in this Function.
   You can search the table the same way you did With Search, and
   you don't run the risk of running out of stack space. Procedure
   calls can also be exensive, slowing down the Program too much
   especially if a lot of symbols are searched.

>  else { a terminal node }
>    begin
>      new(Ptemp);     { create a new tree leaf node }
>      Ptemp^.name := PidStr;
>      Ptemp^.left := nil;
>      Ptemp^.right := nil
>    end
>end; { Enter }

   Please note that there is a lot of data that will be have to
   added to this section over time, as an identifier could be
   ANYTHING from a ConstANT to a Program identifier.

   That isn't too important right now, as we're just getting started
   on the symbol table but suggest you add the following lines, for
   use later:

   Ptemp^.info     := NIL;
   Ptemp^.defn.key := UNDEFINED;
   Ptemp^.level    := 0;     {recursion level}
   Ptemp^.Label_index := 0;  {Label # to be used in code output}