home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / ibpag2 / part04 / slritems.icn < prev    next >
Encoding:
Text File  |  1994-09-25  |  8.0 KB  |  245 lines
  1. ############################################################################
  2. #
  3. #    Name:     slritems.icn
  4. #
  5. #    Title:     compute item sets for a grammar
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    $Revision: 1.10 $
  10. #
  11. ############################################################################
  12. #
  13. #  Contains make_slr_item_sets(start_symbol, st), slr_goto(l, symbol,
  14. #  st), slr_closure(l, st).  The user need only worry about
  15. #  make_slr_item_sets() initially.  The slr_goto() routine may be
  16. #  useful later when constructing action and goto tables.
  17. #
  18. #  Slr_closure(l, st) accepts a list of items as its first argument, a
  19. #  list or set of the productions in the grammar as its second, and
  20. #  returns the closure of item list l, in the form of another item
  21. #  list.
  22. #
  23. #  Note also that the production record structure (LHS, RHS, POS,
  24. #  LOOK...) has a POS field, and therefore can serve also as an item.
  25. #  In fact, any structure can be used, as long as its first three
  26. #  fields are LHS, RHS, and POS.
  27. #
  28. #  See the "Dragon Book" (cited in first.icn) p. 222 ff.
  29. #
  30. #  Slr_goto(l, symbol, st) accepts a list as its first argument, a
  31. #  string or integer as its second (string = nonterminal, integer =
  32. #  terminal), and a list or set for its third, returning another list.
  33. #  Arg 1 must be an item list, as generated either by another call to
  34. #  slr_goto() or by closure of the start production of the augmented
  35. #  grammar.  Arg 2, symbol, is some terminal or nonterminal symbol.
  36. #  Arg 3 is the list or set of all productions in the current grammar.
  37. #  The return value is the closure of the set of all items [A -> aX.b]
  38. #  such that [A -> a.Xb] is in l (arg 1).
  39. #
  40. #  make_slr_item_sets(start_sym, st) takes a string, start_sym, as its
  41. #  first argument, and a list or set of productions as its second.
  42. #  Returns a list of canonical LR(0) item sets or states.  It returns,
  43. #  in other words, a list of lists of items.  Items can be any record
  44. #  type that has LHS, RHS, and POS as its first three fields.
  45. #
  46. #  See the "Dragon Book," example 4.35 (p. 224).
  47. #
  48. ############################################################################
  49. #
  50. #  Links: ibutil
  51. #
  52. ############################################################################
  53.  
  54. # link ibutil
  55.  
  56. #
  57. # slr_closure:  list x list/set -> list
  58. #               (l2,    st)      -> l2
  59. #
  60. #     Where l is a list of items, where st is a list/set of all
  61. #     productions in the grammar from which l was derived, and where
  62. #     l(2) is the SLR closure of l, as constructed using the standard
  63. #     SLR closure operation.
  64. #
  65. #     Ignore the third to fifth arguments, len to added.  They are
  66. #     used internally by recursive calls to slr_closure().
  67. #
  68. procedure slr_closure(l, st, len, LHS_tbl, added)
  69.  
  70.     local   p, i, new_p, symbol
  71.     static  LHS_tbl_tbl
  72.     initial LHS_tbl_tbl := table()
  73.  
  74.     if /LHS_tbl then {
  75.     if /LHS_tbl_tbl[st] := table() then {
  76.         # makes looking up all rules with a given LHS easier
  77.         every p := !st do {
  78.         /LHS_tbl_tbl[st][p.LHS] := list()
  79.         put(LHS_tbl_tbl[st][p.LHS], p)
  80.         }
  81.     }
  82.     LHS_tbl := LHS_tbl_tbl[st]
  83.     }
  84.  
  85.     /len := 0
  86.     /added := set()
  87.  
  88.     # Len tells us where the elements in l start that we haven't yet
  89.     # tried to generate more items from.  These elements are basically
  90.     # the items added on the last recursive call (or the "core," if
  91.     # there has not yet been a recursive call).
  92.     #
  93.     every i := len+1 to *l do {
  94.     /l[i].POS := 1
  95.     # Fails if dot (i.e. l[i].POS) is at the end of the RHS;
  96.     # also fails if the current symbol (i.e. l[i].RHS[l[i].POS])
  97.     # is a nonterminal.
  98.     symbol := l[i].RHS[l[i].POS]
  99.     # No need to add productions having symbol as their LHS if
  100.     # we've already done so for this particular l.
  101.     member(added, symbol) & next
  102.     every p := !\LHS_tbl[symbol] do {
  103.         # Make a copy of p, but with dot set to position 1.
  104.         new_p := copy(p)
  105.         # Set POS to 1 for non-epsilon productions; otherwise to 2.
  106.         if *new_p.RHS = 1 & new_p.RHS[1] === -2 then
  107.         new_p.POS := 2
  108.         else new_p.POS := 1
  109.         # if new_p isn't in l, add it to the end of l
  110.         if not equivalent_items(new_p, !l) then
  111.         put(l, new_p)
  112.     }
  113.     insert(added, symbol)
  114.     }
  115.     return {
  116.     # If nothing new has been added, sort the result and return...
  117.     if *l = i then sortff(l, 1, 2, 3)
  118.     # ...otherwise, try to add more items to l.
  119.     else slr_closure(l, st, i, LHS_tbl, added)
  120.     }
  121.     
  122. end
  123.  
  124.     
  125. #
  126. # slr_goto: list x string|integer x list|set -> list
  127. #           (l,    symbol,          st)      -> l2
  128. #
  129. #     Where l is an item set previously returned by slr_goto or (for
  130. #     the start symbol of the augmented grammar) by slr_closure(),
  131. #     where symbol is a string (nonterminal) or integer (terminal),
  132. #     where st is a list or set of all productions in the current
  133. #     grammar, and where l2 is the SLR closure of the set of all items
  134. #     [A -> aX.b] such that [A -> a.Xb] is in l.
  135. #
  136. #     The idea is just to move the dots for all productions where the
  137. #     dots precede "symbol," creating a new item list for the "moved"
  138. #     items, and then performing a slr_closure() on that new item list.
  139. #     Note that items can be represented by any structure where fields
  140. #     1, 2, and 3 are LHS, RHS, and POS.
  141. #
  142. #     Note that slr_goto(l, symbol, st) may yield a result that's
  143. #     structurally equivalent to one already in the sets of items thus
  144. #     far generated.  This won't normally happen, because slr_goto()
  145. #     saves old results, never re-calcing for the same l x symbol
  146. #     combination.  Still, a duplicate result could theoretically
  147. #     happen.
  148. #
  149. procedure slr_goto(l, symbol, st)
  150.  
  151.     local    item, item2, l2, iteml_symbol_table
  152.     static   iteml_symbol_table_table
  153.     initial  iteml_symbol_table_table := table()
  154.  
  155.     # Keep old results for this grammar (st) in a table of tables of
  156.     # tables!
  157.     #
  158.     /iteml_symbol_table_table[st] := table()
  159.     iteml_symbol_table := iteml_symbol_table_table[st]
  160.  
  161.     # See if we've already performed this same calculation.
  162.     #
  163.     if l2 := \(\iteml_symbol_table[l])[symbol]
  164.     then return l2
  165.  
  166.     l2 := list()
  167.     every item := !l do {
  168.     # Subscripting operation fails if the dot's at end.
  169.         if item.RHS[item.POS] === symbol
  170.     then {
  171.         item2 := copy(item)    # copy is nonrecursive
  172.         item2.POS +:= 1
  173.         put(l2, item2)
  174.     }
  175.     }
  176.     if *l2 = 0 then fail
  177.     else l2 := slr_closure(l2, st)
  178.     #
  179.     # Keep track of item lists and symbols we've already seen.
  180.     #
  181.     /iteml_symbol_table[l] := table()
  182.     /iteml_symbol_table[l][symbol] := l2
  183.  
  184.     if *l2 > 0 then
  185.     return l2
  186.     else fail
  187.  
  188. end
  189.  
  190.  
  191. #
  192. # make_slr_item_sets: string x list|set -> list
  193. #                     (start_sym, st)   -> l
  194. #
  195. #     Where start_sym is the start symbol for the grammar defined by
  196. #     the productions contained in st, and where l is the list of item
  197. #     lists generated by the standard LR(0) set-of-items construction
  198. #     algorithm.
  199. #
  200. #     Ignore the third and fourth arguments.  They are used internally
  201. #     by recursive calls.
  202. #
  203. procedure make_slr_item_sets(start_sym, st, C, len)
  204.  
  205.     local i, next_items, item_list, new_list, item, symbol
  206.  
  207.     #
  208.     # First extend the old start symbol and use the result as the new
  209.     # start symbol for the augmented grammar to which the set-of-items
  210.     # construction will be applied.
  211.     #
  212.     # &trace := -1
  213.     /C := [slr_closure(
  214.         [production("`_" || start_sym || "_'", [start_sym], 1)],st)]
  215.     /len := 0
  216.  
  217.     # Iterate through C (the list of item-lists), doing gotos, and adding
  218.     # new states, until no more states can be added to C.
  219.     #
  220.     every item_list := C[i := len+1 to *C] do {
  221.     if \DEBUG then
  222.         print_item_list(C, i)
  223.     # collect all symbols after the dot for the the items in C[i]...
  224.     next_items := set()
  225.     every item := !item_list do
  226.         insert(next_items, item.RHS[item.POS])
  227.     # ...now, try to do a slr_goto() for every collected symbol.
  228.     every symbol := !next_items do {
  229.         new_list := slr_goto(item_list, symbol, st) | next
  230.         if not equivalent_item_lists(new_list, !C)
  231.         then put(C, new_list)
  232.     }
  233.     }
  234.     # If nothing has been inserted, return C and quit; otherwise, call
  235.     # recursively and try again.
  236.     #
  237.     return {
  238.     if i = *C then C
  239.     else make_slr_item_sets(&null, st, C, i)
  240.     }
  241.  
  242. end
  243.  
  244.  
  245.