home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / ibpag2 / part03 / slrtbls.icn < prev   
Text File  |  1994-09-25  |  12KB  |  371 lines
  1. ############################################################################
  2. #
  3. #    Name:     slrtbls.icn
  4. #
  5. #    Title:     slr table generation routines
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    $Revision: 1.20 $
  10. #
  11. ############################################################################
  12. #
  13. #  Contains make_slr_tables(grammar, atbl, gtbl, noconflict,
  14. #  like_yacc), where grammar is an ib_grammar record (as returned by
  15. #  ibreader), where atbl and gtbl are initialized (default &null) hash
  16. #  tables, and where noconflict is a switch that, if nonnull, directs
  17. #  the resolver to abort on unresolvable conflicts.  Returns &null if
  18. #  successful in filling out atbl and gtbl.  If likeyacc is nonnull,
  19. #  make_slr_tables will resolve reduce/reduce conflicts by order of
  20. #  occurrence in the grammar, just like YACC.  Shift/reduce conflicts
  21. #  will be resolved in favor of shift.
  22. #
  23. #  The reason for the noconflict switch is that there are parsers that
  24. #  can accept tables with multiple action entries, i.e.  parsers that
  25. #  can use tables generated by ambiguous grammars.
  26. #
  27. #  In this routine's case, success is identified with creating a
  28. #  standard SLR action and goto table.  Note that both tables end up
  29. #  as tables of tables, with symbols being the primary or first key,
  30. #  and state numbers being the second.  This is the reverse of the
  31. #  usual arrangement, but turns out to save a lot of space.  Atbl
  32. #  values are of the form "s2.3", "r4<A>10", "a", etc.  The string
  33. #  "s2.3" means "shift the current lookahead token, and enter state 2
  34. #  via rule 3."  By way of contrast, "r4<A>10" means "reduce by rule
  35. #  number 4, which has A as its LHS symbol and 10 RHS symbols."  A
  36. #  single "a" means "accept."
  37.  
  38. #  Atbl entries may contain more than one action.  The actions are
  39. #  simply concatenated: "s2.3r4<A>10a".  Conflicts may be resolved
  40. #  later by associativity or precedence, if available.  Unresolvable
  41. #  conflicts only cause error termination if the 5th and final
  42. #  argument is nonnull (see above on "noconflict").
  43. #
  44. #  Gtbl entries are simpler than atble entries, consisting of a single
  45. #  integer.
  46. #
  47. ############################################################################
  48. #
  49. #  Links: follow, slritems, iohno
  50. #
  51. ############################################################################
  52.  
  53. # declared in ibreader.icn
  54. # record ib_grammar(start, rules, tbl)
  55.  
  56. #link follow, slritems, iohno#, ximage
  57.  
  58. #
  59. # make_slr_tables
  60. #
  61. procedure make_slr_tables(grammar, atbl, gtbl, noconflict, like_yacc)
  62.  
  63.     local start_symbol, st, C, i, augmented_start_symbol, item,
  64.     symbol, new_item_list, j, action
  65.  
  66.     # Initialize start symbol and rule list/set (either is okay).
  67.     start_symbol := grammar.start
  68.     st := grammar.rules
  69.  
  70.     # Number the rules, and then construct the canonical LR(0) item sets.
  71.     every i := 1 to *st do st[i].no := i
  72.     C := make_slr_item_sets(start_symbol, st)
  73.  
  74.     # Now, go through each item in each item set in C filling out the
  75.     # action (atbl) and goto table (gtbl) as we go.
  76.     #
  77.     augmented_start_symbol := "`_" || start_symbol || "_'"
  78.     every i := 1 to *C do {
  79.         every item := !C[i] do {
  80.         # if the dot's *not* at the end of the production...
  81.         if symbol := item.RHS[item.POS] then {
  82.         # if were looking at a terminal, enter a shift action
  83.         if type(symbol) == "integer" then {
  84.             if symbol = -2 then next   # Never shift epsilon!
  85.             new_item_list := slr_goto(C[i], symbol, st)
  86.             every j := 1 to *C do {
  87.             if equivalent_item_lists(new_item_list, C[j]) then {
  88.                 action := "s" || j || "." || item.no
  89.                 resolve(st, atbl, symbol, i, action,
  90.                     noconflict, like_yacc)
  91.                 break next
  92.             }
  93.             }
  94.         # if we're looking at a nonterminal, add action to gtbl
  95.         } else {
  96.             new_item_list := slr_goto(C[i], symbol, st)
  97.             every j := 1 to *C do {
  98.             if equivalent_item_lists(new_item_list, C[j]) then {
  99.                 /gtbl[symbol] := table()
  100.                 /gtbl[symbol][i] := j |
  101.                 gtbl[symbol][i] =:= j |
  102.                 iohno(80, image(symbol), ".", image(i), ":", j)
  103.                 break next
  104.             }
  105.             }
  106.         }
  107.         # ...else if the dot *is* at the end of the production
  108.         } else {
  109.         if item.LHS == augmented_start_symbol then {
  110.             action := "a"
  111.             # 0 = EOF 
  112.             resolve(st, atbl, 0, i, action, noconflict, like_yacc)
  113.         } else {
  114.             # add a reduce for every symbol in FOLLOW(item.LHS)
  115.             every symbol := !FOLLOW(start_symbol, st, item.LHS) do {
  116.             # RHS size is 0 for epsilon.
  117.             if item.RHS[1] === -2 then {
  118.                 action := "r" || item.no || "<" || item.LHS ||
  119.                 ">0"
  120.             } else
  121.                 action := "r" || item.no || "<" || item.LHS ||
  122.                     ">" || *item.RHS
  123.             resolve(st, atbl, symbol, i, action,
  124.                 noconflict, like_yacc)
  125.             }
  126.         }
  127.         }
  128.     }
  129.     }
  130.  
  131.     return
  132.  
  133. end
  134.  
  135.  
  136. #
  137. # resolve: list|set x table x string|integer, integer, anything, anything
  138. #                                  -> string
  139. #          (st, tbl, symbol, state, action, noconflict, like_yacc)
  140. #                            -> new_action_list
  141. #
  142. #     Add action to action table, resolving conflicts by precedence
  143. #     and associativity, if need be.  If noconflict is nonnull, abort
  144. #     on unresolvable conflicts.  Fails on shift/shift "conflicts," or
  145. #     if an identical action is already present in the table entry to
  146. #     be modified.  If like_yacc is nonnull, resolve reduce/reduce
  147. #     conflicts by their order of occurrence in the grammar; resolve
  148. #     shift/reduce conflicts in favor of shift.
  149. #
  150. procedure resolve(st, tbl, symbol, state, action, noconflict, like_yacc)
  151.  
  152.     local actions, chr, a, ruleno, p, newp
  153.  
  154.     /tbl[symbol] := table()
  155.     /tbl[symbol][state] := ""
  156.     
  157.     # If this action is already present, then don't re-enter it.  Just
  158.     # fail.
  159.     #
  160.     tbl[symbol][state] ? {
  161.     while a := tab(any('sra')) do {
  162.         a ||:= tab(upto('.<'))
  163.         a ||:= { (="<" || tab(find(">")+1)) | ="." }
  164.         a ||:= tab(many(&digits))
  165.         if a == action then fail
  166.     }
  167.     }
  168.  
  169.     # Get rule number for the new action specified as arg 5, and
  170.     # fetch its source production.
  171.     action ? {
  172.     case move(1) of {
  173.         "s": ruleno := (tab(find(".")+1), tab(many(&digits)))
  174.         "r": ruleno := 1(tab(find("<")), move(1))
  175.         "a": return tbl[symbol][state] := action || tbl[symbol][state]
  176.     } | iohno(70, tbl[symbol][state])
  177.     (newp := !st).no = ruleno |
  178.         iohno(72, tbl[symbol][state])
  179.     }
  180.  
  181.     # Resolve any conflicts that might be present.
  182.     #
  183.     actions := ""
  184.     tbl[symbol][state] ? {
  185.     while a := tab(any('sra')) do {
  186.         # Snip out the old action, and put it into a.
  187.         a ||:= tab(upto('.<'))
  188.         a ||:= { (="<" || tab(find(">")+1)) | ="." }
  189.         a ||:= tab(many(&digits))
  190.         #
  191.         # Get the old action's rule number, and use it to fetch
  192.         # the full production that it is keyed to.
  193.         #
  194.         a ? {
  195.         case move(1) of {
  196.             "s": ruleno := (tab(find(".")+1), tab(many(&digits)))
  197.             "r": ruleno := 1(tab(find("<")), move(1))
  198.             "a": return tbl[symbol][state] := a || actions || action
  199.         } | iohno(70, tbl[symbol][state])
  200.         # Go through rule list; find the one whose number is ruleno.
  201.         (p := !st).no = ruleno |
  202.             iohno(71, tbl[symbol][state])
  203.         }
  204.  
  205.         # Check precedences to see if we can resolve the conflict
  206.         # this way.
  207.         #
  208.         if \newp.prec > \p.prec then
  209.         # discard the old action, a
  210.         return tbl[symbol][state] := actions || action || tab(0)
  211.         else if \newp.prec < \p.prec then
  212.         # discard the new action, action
  213.         return tbl[symbol][state] := actions || a || tab(0)
  214.         else {
  215.         #
  216.         # If, however, both precedences are the same (i.e.
  217.         # newp.prec === p.prec), then we must check the
  218.         # associativities.  Right implies shift; left, reduce.
  219.         # If there is no associativity, then we have a
  220.         # conflict.  Nonassociative ("n") implies error.
  221.         #
  222.         case action[1] of {
  223.             default: iohno(70, tbl[symbol][state])    
  224.             # case "a" is handled above; look for "s" & "r"
  225.             "s" : {
  226.             if a[1] == "s" then fail  # no shift/shift "conflict"
  227.             else if a[1] == "r" then {
  228.                 newp.assoc === p.assoc | {
  229.                 iohno(40, "state " || state || "; token " ||
  230.                       symbol || "; rules " || newp.no ||
  231.                       "," || p.no)
  232.                 }
  233.                 case newp.assoc of {
  234.                 "n"  : iohno(41, production_2_string(newp))
  235.                 &null: { # no associativity given
  236.                     if \noconflict & /like_yacc then
  237.                     iohno(46, "state " || state ||
  238.                           "; token " || symbol ||
  239.                           "; rules " || newp.no ||
  240.                           "," || p.no)
  241.                     else {
  242.                     write(&errout, "warning: shift/reduce",
  243.                           " conflict in state " || state ||
  244.                           "; token " || symbol ||
  245.                           "; rules " || newp.no ||
  246.                           "," || p.no)
  247.                     if \like_yacc then {
  248.                         write(&errout, "resolving in _
  249.                                     favor of shift.")
  250.                         return tbl[symbol][state] :=
  251.                            actions || action || tab(0)
  252.                     } else {
  253.                         write(&errout, "creating multi-_
  254.                             action table entry")
  255.                         return tbl[symbol][state] :=
  256.                            actions || action || a || tab(0)
  257.                     }
  258.                     }
  259.                 }
  260.                 "l"  : { # left associative
  261.                     # discard new action, action
  262.                     return tbl[symbol][state] := 
  263.                     actions || a || tab(0)
  264.                 }
  265.                 "r"  : { # right associative
  266.                     # remove old action, a
  267.                     return tbl[symbol][state] := 
  268.                     actions || action || tab(0)
  269.                 }
  270.                 }
  271.             }
  272.             }
  273.             "r" : {
  274.             if a[1] == "r" then {
  275.                 #
  276.                 # If conflicts in general, and reduce-reduce
  277.                 # conflicts in specific are not okay...
  278.                 #
  279.                 if \noconflict & /like_yacc then {
  280.                 # ...abort, otherwise...
  281.                 iohno(42, "state " || state || "; token " ||
  282.                       symbol || "; " || "; rules " ||
  283.                       newp.no || "," || p.no)
  284.                 } else {
  285.                 #
  286.                 # ...flag reduce-reduce conficts, and
  287.                 # then resolve them by their order of
  288.                 # occurrence in the grammar.
  289.                 #
  290.                 write(&errout, "warning: reduce/reduce",
  291.                       " conflict in state ", state,
  292.                       "; token ", symbol, "; rules ",
  293.                       newp.no, ",", p.no)
  294.                 if \like_yacc then {
  295.                     write(&errout, "resolving by order of _
  296.                           occurrence in the grammar")
  297.                     if newp.no > p.no
  298.                     # discard later production (newp)
  299.                     then return return tbl[symbol][state] := 
  300.                     actions || a || tab(0)
  301.                     # discard later production (old p)
  302.                     else return tbl[symbol][state] := 
  303.                     actions || action || tab(0)
  304.                 } else {
  305.                     #
  306.                     # If conflicts ok, but we aren't supposed
  307.                     # to resolve reduce-reduce conflicts by
  308.                     # order of rule occurrence:
  309.                     #
  310.                     write(&errout, "creating multi-action _
  311.                     table entry")
  312.                     return tbl[symbol][state] :=
  313.                     actions || action || a || tab(0)
  314.                 }
  315.                 }
  316.             } else {
  317.                 # associativities must be the same for both rules:
  318.                 newp.assoc === p.assoc | {
  319.                 iohno(40, "state " || state || "; token " ||
  320.                       symbol || "; rules " || newp.no ||
  321.                       "," || p.no)
  322.                 }
  323.                 case newp.assoc of {
  324.                 "n"  : iohno(41, production_2_string(newp))
  325.                 &null: {
  326.                     if \noconflict & /like_yacc then
  327.                     iohno(46, "state " || state ||
  328.                           "; token " || symbol ||
  329.                           "; rules " || newp.no ||
  330.                           "," || p.no)
  331.                     else {
  332.                     write(&errout, "warning: shift/reduce",
  333.                           " conflict in state " || state ||
  334.                           "; token " || symbol ||
  335.                           "; rules " || newp.no ||
  336.                           "," || p.no)
  337.                     if \like_yacc then {
  338.                         write(&errout, "resolving in _
  339.                                     favor of shift.")
  340.                         return tbl[symbol][state] :=
  341.                            actions || a || tab(0)
  342.                     } else {
  343.                         write(&errout, "creating multi-_
  344.                             action table entry")
  345.                         return tbl[symbol][state] :=
  346.                            actions || action || a || tab(0)
  347.                     }
  348.                     }
  349.                 }
  350.                 "r"  : {
  351.                     # discard new action, action
  352.                     return tbl[symbol][state] :=
  353.                     actions || a || tab(0)
  354.                 }
  355.                 "l"  : {
  356.                     # remove old action, a
  357.                     return tbl[symbol][state] :=
  358.                     actions || action || tab(0)
  359.                 }
  360.                 }
  361.             }
  362.             }
  363.         }
  364.         }
  365.     }
  366.     }
  367.  
  368.     return tbl[symbol][state] ||:= action
  369.  
  370. end
  371.