home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / packs / ibpag2 / shrnktbl.icn < prev    next >
Text File  |  2000-08-04  |  4KB  |  132 lines
  1. ############################################################################
  2. #
  3. #    Name:     shrnktbl.icn
  4. #
  5. #    Title:     table shrinker
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    Version: 1.4  (later modified 4-Aug-2000/gmt)
  10. #
  11. ############################################################################
  12. #
  13. #  Action/goto table shrinking routine.
  14. #
  15. #  Entry point: shrink_tables(start_symbol, st, atbl, gtbl), where
  16. #  start_symbol is the start symbol for the grammar whose productions
  17. #  are contained in the list/set st, and where atbl and gtbl are the
  18. #  action and goto tables, respectively.  Returns &null, for lack of
  19. #  anything better.
  20. #  
  21. #  Basically, this routine merges duplicate structures in atbl and
  22. #  gtbl (if there are any), replaces the nonterminal symbols in the
  23. #  action table with integers (including the start symbol), then
  24. #  resets the goto table so that its keys point to these integers,
  25. #  instead of to the original nonterminal symbol strings.
  26. #
  27. ############################################################################
  28. #
  29. #  Links: equiv, lists, sets, tables, outbits
  30. #
  31. ############################################################################
  32. #
  33. #  See also: ibpag2, slrtbls
  34. #
  35. ############################################################################
  36.  
  37. # structs has equiv; outbits is for outputting variable-width integers
  38. # as 8-bit characters
  39. #
  40. link equiv
  41. link lists
  42. link sets
  43. link tables
  44. link outbits
  45.  
  46. #
  47. # shrink_tables
  48. #
  49. procedure shrink_tables(grammar, atbl, gtbl)
  50.  
  51.     local t, k, seen, nontermtbl, r, a, action, state, by_rule,
  52.     rule_len, LHS, keys
  53.  
  54.     # Create a table mapping nonterminal symbols to integers.
  55.     nontermtbl := table()
  56.     every r := !grammar.rules do
  57.     # r is a production; production records have LHS, RHS,...no
  58.     # fields, where the no field contains the rule number; we can
  59.     # use this as an arbitrary representation for that rule's LHS
  60.     # nonterminal
  61.     insert(nontermtbl, r.LHS, r.no)
  62.  
  63.     # Replace old start symbol.
  64.     grammar.start := nontermtbl[grammar.start]
  65.  
  66.     # Re-form the goto table to use the new integer values for
  67.     # nonterminals.
  68.     keys := set()
  69.     every insert(keys, key(gtbl))
  70.     every k := !keys do {
  71.     # first create a column for the new integer-valued nonterminal
  72.     insert(gtbl, string(nontermtbl[k]), gtbl[k])
  73.     # then clobber the old column with a string-valued nonterminal
  74.     gtbl[k] := &null
  75.     }
  76.  
  77.     # Rewrite actions using a fixed field-width format.
  78.     every t := !atbl do {
  79.     every k := key(t) do {
  80.         a := ""
  81.         t[k] ? {
  82.         while action := tab(any('sra')) do {
  83.             case action of {
  84.             "s": {
  85.                 outbits(0, 2)
  86.                 state := integer(tab(find(".")))
  87.                 every a ||:= outbits(state, 11)
  88.                 move(1)
  89.                 by_rule := integer(tab(many(&digits)))
  90.                 every a ||:= outbits(by_rule, 11)
  91.                 outbits()
  92.             }
  93.             "r": {
  94.                 outbits(1, 2)
  95.                 state := integer(tab(find("<")))
  96.                 every a ||:= outbits(state, 11)
  97.                 move(1)
  98.                 LHS := nontermtbl[tab(find(">"))]
  99.                 every a ||:= outbits(LHS, 11)
  100.                 move(1)
  101.                 rule_len := integer(tab(many(&digits)))
  102.                 every a ||:= outbits(rule_len, 8)
  103.                 outbits()
  104.             }
  105.             "a": {
  106.                 outbits(2, 2)
  107.                 a ||:= outbits()
  108.             }
  109.             }
  110.         }
  111.         }
  112.         t[k] := a
  113.     }
  114.     }
  115.  
  116.     #
  117.     # Turn pointers to identical structures into pointers to the same
  118.     # structure.
  119.     #
  120.     seen := set()
  121.     every t := atbl | gtbl do {
  122.     every k := key(t) do {
  123.         if t[k] := equiv(t[k], !seen)
  124.         then next else insert(seen, t[k])
  125.     }
  126.     }
  127.  
  128.     # signal success
  129.     return &null
  130.  
  131. end
  132.