[Back to FINDREPL SWAG index]  [Back to Main SWAG index]  [Original]

LARRY HADLEY

   Errata: include an "info" Pointer field in the SYMTAB_NODE
   structure in the previous post.

   USING THE SYMBOL TABLE - A CROSS REFERENCER

   A cross-reference is a listing of a Programs identifiers in
   alphabetical order:

Page 1   hello.pas  April 08 1993  19:03
   1 0: Program hello (output);
   2 0: Var i:Integer;
   3 0: begin
   4 0:    For i := 1 to 10 do
   5 0:    begin
   6 0:       WriteLn('Hello world.');
   7 0:    end;
   8 0: end.

Cross Reference
---------------

hello               1

i                   2    4

Integer             2

ouput               1

Writeln             6

  As shown above, alongside each identifier's name are the source
  line numbers that contain the identifier. (This is useful for
  tracking where they're used)

  A cross-referencer reads the source File and looks for
  identifiers, using the scanner you've built previously. The first
  time a particular identifier is found, it is inserted in the
  symbol tree along With it's line number. Subsequent appearances of
  the same identifier update the symbol tree With an additional line
  number appended to the list of line numbers.

  As soon as the Program is completely scanned, all the identifier
  names and their line numbers are printed.

  Use the INFO field of SYMTAB_NODE to point to a LINKED LIST of
  line numbers.

  The main loop should scan For tokens Until it finds a period, or
  Exits With an "Unexpected end of File" error. For each identifier,
  search the symbol table to see if their were any previous
  instances of the identifier. If it is not found, then this must be
  the first time it is used so we can call the "enter" Function to
  create a new node.

  Then, whether a new node was actually created or not, we call a
  Function to add the line number to the queue of line numbers
  attached to the node's "info" field. Finally, when the scanner
  loop terminates, we call a printing Function which traverses the
  tree from left to right to print the sorted tree - and all the
  line numbers in the linked list attached to each node.

  Note that a recursive call to itself is probably the easiest way
  to do this, since _all_ the nodes of the tree are being accessed,
  not just one.

  Types you will need:

Type
  pLINENUMS = ^LINENUM_NODE;
  LINENUM_NODE = Record
     next     :pLINENUMS;
     line     :Integer;
  end;

  pLINE_HEADER = ^LINENUM_HDR;
  LINENUM_HDR = Record
     first, last :pLINENUMS;
  end;

  EXCERCISE #1

  Write a cross referencer, as above. Text it With an assortment of
  pascal sourceFiles.

  ADVANCED EXCERCISE

  Note that the symbol table above converts all identifier names to
  lower case. What would be needed to reWrite the scanner/xref
  Program to preserve case? ReWrite the xref Program to do so. (note
  that Pascal compilers are Case insensitive, so the symbol table -

  For compatibility - must compare lower case)

  "BRAIN TEASERS"

  1. What would be necessary to reWrite the symbol table as a hash
     table?

  2. If an identifier appears more than once in a line, line
     numbers will appear more than once in the listing. Fix xref to
     recognize duplicate occurences of line numbers in node-lists.

  -----------------------------------------------------------------

  Next: Pascal source cruncher.

[Back to FINDREPL SWAG index]  [Back to Main SWAG index]  [Original]