home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / findrepl.swg / 0014_SYMTAB1.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  8.7 KB  |  234 lines
  1.    SYMBOL TABLE
  2.  
  3.    All Compilers and interpreters must maintain a data structure
  4.    called the SYMBOL TABLE. This is where all the inFormation about
  5.    the Programs symbols are kept. Maintaining a well-organized
  6.    symbol table is a skill all Compiler Writers must master.
  7.  
  8.    As a Compiler parses a source Program, it relies on the symbol
  9.    table to provide inFormation about each identifier (such as
  10.    Variables and Constants) - it must be able to access and update
  11.    inFormation about each identifier and do so quickly - otherwise
  12.    the process is slowed or produces incorrect results.
  13.  
  14.    No matter what inFormation is kept, or how the table is organized
  15.    certain operations are fundamental to a symbol tables operation.
  16.  
  17.    You ENTER inFormation about about an identifier into the table by
  18.    *creating* and entry.
  19.  
  20.    You SEARCH the table to look up an identifier's entry and make
  21.    available the inFormation in that entry.
  22.  
  23.    You UPDATE the entry to modify stored inFormation.
  24.  
  25.    There can be only one entry per identifier in the symbol table,
  26.    so you must first search the table beFore making a new entry.
  27.  
  28.    TABLE ORGANIZATION
  29.  
  30.    There are many different ways to handle symbol tables: Arrays,
  31.    linked lists, hash tables...but since the most common operations
  32.    perFormed on a symbol table are searching it For existing entries
  33.    it makes perfect sense to implement it as a BINARY TREE.
  34.  
  35.    Each NODE in the TREE contains and entry, and points to two other
  36.    nodes. The *values* of the nodes on the subtree to the left are
  37.    always LESS than the parent node, While the subtree to the right
  38.    is always MORE than the parent. This makes searching sorted
  39.    binary trees very efficient.
  40.  
  41.    Inserting new nodes is as easy as searching the tree: if the
  42.    value you want to insert is LESS than the current node, search
  43.    the node to the left. If it is MORE, search the tree to the right.
  44.    Keep doing this recursively Until an empty node is found, then
  45.    insert the value into that node.
  46.  
  47.    NITTY-GRITTY
  48.  
  49.    Now that we've covered some background on the table, here's a
  50.    recap on the symbol table Type defs. For those that missed them
  51.    in the first message, or didn't save them:
  52.  
  53. Type
  54.    sptr = ^String; { useful For minimum-size allocation }
  55.  
  56.    DEFN_KEY = (UNDEFINED,
  57.                Const_DEFN, Type_DEFN, Var_DEFN, FIELD_DEFN,
  58.                VALPARM_DEFN, VarPARM_DEFN,
  59.                PROG_DEFN, PROC_DEFN, FUNC_DEFN
  60.               );
  61.  
  62.    ROUTINE_KEY = (rkDECLARED, rkForWARD,
  63.                   rkREAD, rkREADLN, rkWrite, rkWriteLN,
  64.                   rkABS, rkARCTAN, rkCHR, rkCOS, rkEOF, rkEOLN,
  65.                   rkEXP, rkLN, rkODD, rkORD, rkPRED, rkROUND,
  66.                   rkSIN, rkSQR, rkSQRT, rkSUCC, rkTRUNC
  67.                  );
  68.  
  69.    RTN_BLOCK = Record               {info about routine declarations}
  70.       key              :ROUTINE_KEY;
  71.       parm_count,
  72.       total_parm_size,
  73.       total_local_size :Word;
  74.       parms, locals,
  75.       local_symtab     :SYMTAB_PTR; {symbol tables of routine}
  76.       code_segment     :sptr;       {interpreter}
  77.    end;
  78.  
  79.    DTA_BLOCK = Record
  80.       offset     :Word;
  81.       Record_idp :SYMTAB_PTR;
  82.    end;
  83.  
  84.    INFO_REC = Record
  85.       Case Byte of
  86.         0:(Constant :VALUE);     { literal value }
  87.         1:(routine  :RTN_BLOCK); { identifier is routine }
  88.         2:(data     :DTA_BLOCK); { identifier is data }
  89.    end;
  90.  
  91.    DEFN_REC = Record
  92.       key  :DEFN_KEY; { what is identifier? }
  93.       info :INFO_REC; { stuff about identifier }
  94.    end;
  95.  
  96.    SYMTAB_PTR  = ^SYMTAB_NODE;
  97.    SYMTAB_NODE = Record          {actual tree node}
  98.       left, right   :SYMTAB_PTR; {Pointers to left and right subtrees}
  99.       next          :SYMTAB_PTR; {For chaining a node}
  100.       name          :sptr;       {identifier name String}
  101.       level,                     {nesting level}
  102.       co_index      :Integer;    {code Label index}
  103.       defn          :DEFN_REC;   {definition info}
  104.    end; { Record }
  105.  
  106.    EXCERCISE #1
  107.  
  108.    Implement a symbol table SEARCH routine, and a symbol table ENTER
  109.    routine. Both routines must accept a Pointer to the root of the
  110.    tree, and the name of the identifier you are working With, and
  111.    must return a Pointer to the node that was found in the search
  112.    routine, or enters in the enter routine. If no node was found, or
  113.    entered, the routines must return NIL.
  114.  
  115.    The resulting symbol table should be a sorted tree.
  116.  
  117.  
  118.  
  119. │   Implement a symbol table SEARCH routine, and a symbol table ENTER
  120. │   routine. Both routines must accept a Pointer to the root of the
  121. │   tree, and the name of the identifier you are working with, and
  122. │   must return a Pointer to the node that was found in the search
  123. │   routine, or enters in the enter routine. If no node was found, or
  124. │   entered, the routines must return NIL.
  125. │   The resulting symbol table should be a sorted tree.
  126.  
  127.  
  128.  
  129. Function Enter(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
  130. { - inserts a new indetifier String PidStr in the symol table. }
  131. { - nil is returned if duplicate identifier is found.          }
  132. Var
  133.   Ptemp: SymTab_Ptr;
  134. begin
  135.   if (root <> nil) then    { not a terminal node }
  136.     if (PidStr = root^.name) then
  137.       begin
  138.         Enter := nil;
  139.         Exit
  140.       end
  141.     else    { recursive insertion calls to either left or right sub-tree }
  142.       if (PidStr > root^.name) then
  143.         Enter(root^.right, PidStr)
  144.       else
  145.         Enter(root^.left, PidStr)
  146.   else { a terminal node }
  147.     begin
  148.       new(Ptemp);     { create a new tree leaf node }
  149.       Ptemp^.name := PidStr;
  150.       Ptemp^.left := nil;
  151.       Ptemp^.right := nil
  152.     end
  153. end; { Enter }
  154.  
  155.  
  156. Function Search(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
  157. { - search For a certain identifier String PidStr in the symbol table. }
  158. { - returns nil if search faild.                                       }
  159. begin
  160.   While (root <> nil) and (PidStr <> root^.name) do
  161.     if (PidStr > root^.name) then     { search the right sub-tree }
  162.       root := root^.right
  163.     else
  164.       if (PidStr < root^.name) then
  165.         root := root^.left;           { search the left sub-tree  }
  166.    Search := root                     { return the node           }
  167. end;
  168.  
  169. {===========================================================================}
  170.  
  171. Comment:
  172.      What made you choose BINARY trees over AVL trees?  With binary trees,
  173.      the structure may become degenerate (unbalanced) and, the routines for
  174.      searching and insertion becomes inefficient.
  175.  
  176. >Comment:
  177. >     What made you choose BINARY trees over AVL trees?  With binary trees,
  178. >     the structure may become degenerate (unbalanced) and, the routines for
  179. >     searching and insertion becomes inefficient.
  180.  
  181.    Glad you could join us!
  182.  
  183.    I chose a binary tree because it's simple and easy to Write, also
  184.    a degenerate tree isn't much of a concern, simply because it's
  185.    intended to hold only identifiers and Constants, not every
  186.    statement. :)
  187.  
  188.    As long as it sorts the data as it inserts, it will work. This
  189.    isn't, after all, a graduate "course". The intention is to teach
  190.    people how compilers work and show interested parties how to
  191.    understand and Write their own, if they're interested. This is
  192.    YOUR compiler you're writing, if you want to implement an AVL
  193.    tree, go ahead!
  194.  
  195. >Function Search(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
  196.  
  197.    This works. It's efficient and does the job.
  198.  
  199. >Function Enter(root: SymTab_Ptr; PidStr: spstr): SymTab_Ptr;
  200.  
  201. >    else    { recursive insertion calls to either left or right sub-tree }
  202. >      if (PidStr > root^.name) then
  203. >        Enter(root^.right, PidStr)
  204. >      else
  205. >        Enter(root^.left, PidStr)
  206.  
  207.    Note: recursive calls shouldn't be necessary in this Function.
  208.    You can search the table the same way you did With Search, and
  209.    you don't run the risk of running out of stack space. Procedure
  210.    calls can also be exensive, slowing down the Program too much
  211.    especially if a lot of symbols are searched.
  212.  
  213. >  else { a terminal node }
  214. >    begin
  215. >      new(Ptemp);     { create a new tree leaf node }
  216. >      Ptemp^.name := PidStr;
  217. >      Ptemp^.left := nil;
  218. >      Ptemp^.right := nil
  219. >    end
  220. >end; { Enter }
  221.  
  222.    Please note that there is a lot of data that will be have to
  223.    added to this section over time, as an identifier could be
  224.    ANYTHING from a ConstANT to a Program identifier.
  225.  
  226.    That isn't too important right now, as we're just getting started
  227.    on the symbol table but suggest you add the following lines, for
  228.    use later:
  229.  
  230.    Ptemp^.info     := NIL;
  231.    Ptemp^.defn.key := UNDEFINED;
  232.    Ptemp^.level    := 0;     {recursion level}
  233.    Ptemp^.Label_index := 0;  {Label # to be used in code output}
  234.