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 / follow.icn < prev    next >
Text File  |  2000-07-29  |  11KB  |  333 lines
  1. ############################################################################
  2. #
  3. #    Name:     follow.icn
  4. #
  5. #    Title:     compute follow sets for grammar
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    Version: 1.15
  10. #
  11. ############################################################################
  12. #
  13. #  This file contains FIRST(st, symbol...) and FOLLOW(start_symbol,
  14. #  st, symbol).  For FIRST(), arg1 is a list of productions.  Arg 2 is
  15. #  a string (nonterminal) or an integer (terminal).  FIRST may take
  16. #  more than one symbol argument.  FOLLOW takes a string as its first
  17. #  argument, a list of productions as its second, and a symbol as its
  18. #  third.  There is never any need to call FOLLOW with any more than
  19. #  one symbol.  The return values for FIRST() and FOLLOW() may be
  20. #  described as follows:
  21. #
  22. #  FIRST returns the set of all terminal symbols that begin valid
  23. #  prefixes of the first symbol argument, or, if this contains
  24. #  epsilon, of the first symbol -- <epsilon> ++ the set of terminals
  25. #  beginning valid prefixes of the second symbol, etc....  The first
  26. #  argument, st, contains the production list over which FIRST is to
  27. #  be computed.
  28. #
  29. #  FOLLOW is similar, except that it accepts only one symbol argument,
  30. #  and returns the set of nonterminals that begin valid prefixes of
  31. #  symbols that may follow symbol in the grammar defined by the
  32. #  productions in st.
  33. #
  34. #  Both FIRST() and FOLLOW() are optimized.  When called for the first
  35. #  time with a specific production list (st), both FIRST() and
  36. #  FOLLOW() create the necessary data structures to calculate their
  37. #  respective return values.  Once created, these data structures are
  38. #  saved, and re-used for subsequent calls with the same st argument.
  39. #  The implications for the user are two: 1) The first call to FOLLOW
  40. #  or FIRST for a given production list will take a while to return,
  41. #  but 2) subsequent calls will return much faster.  Naturally, you
  42. #  can call both FIRST() and FOLLOW() with various st arguments
  43. #  throughout the life of a given program.
  44. #
  45. ############################################################################
  46. #
  47. #  Links: none
  48. #
  49. ############################################################################
  50.  
  51.  
  52. #
  53. # FIRST:  list|set x string|integer...   -> set
  54. #         (st, symbols...)               -> FIRST_set
  55. #
  56. #     Where symbols are strings or integers (nonterminal or terminal
  57. #     symbols in a production in the list or set of productions, st),
  58. #     and where FIRST_set is a set of integers corresponding to
  59. #     terminal symbols that begin valid prefixes of symbols[1], or if
  60. #     that derives epsilon, of symbols[1] -- epsilon ++ symbols[2],
  61. #     unless that derives epsilon, etc...
  62. #
  63. procedure FIRST(st, symbols[])
  64.  
  65.     local   i, result, FIRST_tbl
  66.     static  FIRST_tbl_tbl
  67.     initial FIRST_tbl_tbl := table()
  68.  
  69.     /FIRST_tbl_tbl[st] := make_FIRST_sets(st)
  70.     FIRST_tbl := FIRST_tbl_tbl[st]
  71.  
  72.     result := set()
  73.     i := 0
  74.     while *symbols >= (i +:= 1) do {
  75.     /FIRST_tbl[symbols[i]] & iohno(90, image(symbols[i]))
  76.     if not member(FIRST_tbl[symbols[i]], -2) then {
  77.         # We're done if no epsilons.
  78.         result ++:= FIRST_tbl[symbols[i]]
  79.         break
  80.     } else {
  81.         # Remove the epsilon & try the next symbol in p.RHS.
  82.         result ++:= FIRST_tbl[symbols[i]] -- FIRST_tbl[-2]
  83.     }
  84.     }
  85.     # If we get to here without finding a symbol that doesn't derive
  86.     # epsilon, then give up and insert <epsilon> into result.
  87.     if i > *symbols then
  88.     result ++:= FIRST_tbl[-2]
  89.  
  90.     return result
  91.  
  92. end
  93.  
  94.  
  95. #
  96. # FOLLOW: list|set x string|integer -> set
  97. #         (st,       symbol)        -> FOLLOW_set
  98. #
  99. procedure FOLLOW(start_symbol, st, symbol)
  100.  
  101.     static  FOLLOW_tbl_tbl
  102.     initial FOLLOW_tbl_tbl := table()
  103.  
  104.     /FOLLOW_tbl_tbl[st] := make_slr_FOLLOW_sets(start_symbol, st) 
  105.     return FOLLOW_tbl_tbl[st][symbol]
  106.  
  107. end
  108.  
  109.  
  110. #
  111. #  Below is the procedure make_slr_FOLLOW_sets(start_symbol, st),
  112. #  which accepts a string, a set, and a table as its arguments and
  113. #  returns another table.  The first argument must contain the start
  114. #  symbol for the set (or list) of productions contained in the second
  115. #  argument.  Returns a table of FOLLOW sets, where keys = symbols and
  116. #  values = follow sets for those symbols.
  117. #
  118. #  The algorithm - somewhat inefficiently implemented here - works out
  119. #  as follows:
  120. #
  121. #      1. Place $ (internal 0) in FOLLOW_tbl[start_symbol].
  122. #      2. Initialize FOLLOW_tbl[symbol] to { } for every other symbol.
  123. #      3. For each production A -> aBb do FOLLOW_tbl[B] ++:= FIRST(b) --
  124. #         FIRST(<epsilon>).
  125. #      4. For each production A -> aBb where FIRST(b) contains
  126. #         <epsilon> and for each production A -> aB, do FOLLOW_tbl[B] ++:=
  127. #         FOLLOW_tbl[A].
  128. #
  129. #  Repeat steps 3 and 4 until no FOLLOW set can be expanded, at which
  130. #  point return the FOLLOW table.
  131. #
  132. #  Note that <epsilon> is represented internally by -2.
  133. #
  134.  
  135.  
  136. #
  137. # make_slr_FOLLOW_sets: string x set/list  -> table
  138. #                       (start_symbol, st) -> FOLLOW_tbl
  139. #
  140. #     Where start_symbol is the start symbol for the grammar defined
  141. #     by the set/list of productions in st, and where FOLLOW_tbl is a
  142. #     table of follow sets (keys = symbols, values = follow sets for
  143. #     the symbols).
  144. #
  145. procedure make_slr_FOLLOW_sets(start_symbol, st)
  146.  
  147.     local FOLLOW_tbl, k, size, old_size, p, i, j
  148.  
  149.     FOLLOW_tbl := table()
  150.     # step 1 above; note that 0 = EOF
  151.     FOLLOW_tbl[start_symbol] := set([0])
  152.  
  153.     # step 2
  154.     every k := (!st).LHS do
  155.     /FOLLOW_tbl[k] := set()
  156.  
  157.     # steps 3 and 4
  158.     size := 0
  159.     #
  160.     # When the old size of the FOLLOW sets equals the new size, we are
  161.     # done because nothing was added to the FOLLOW sets on the last
  162.     # pass.
  163.     #
  164.     while old_size ~===:= size do {
  165.     size := 0
  166.     every p := !st do {
  167.         every i := 1 to *p.RHS-1 do {
  168.         type(p.RHS[i]) == "string" | next
  169.         /FOLLOW_tbl[p.RHS[i]] & iohno(90, image(p.RHS[i]))
  170.         # Go through every RHS symbol until we get a FIRST set
  171.         # without an epsilon move.
  172.         every j := i+1 to *p.RHS do {
  173.             if member(FIRST(st, p.RHS[j]), -2) then {
  174.             FOLLOW_tbl[p.RHS[i]] ++:=
  175.                 FIRST(st, p.RHS[j]) -- FIRST(st, -2)
  176.             } else {
  177.             FOLLOW_tbl[p.RHS[i]] ++:= FIRST(st, p.RHS[j])
  178.             size +:= *FOLLOW_tbl[p.RHS[i]]
  179.             break next
  180.             }
  181.         }
  182.         # If we get past "break next" then b in A -> aBb =>*
  183.         # <epsilon>; add FOLLOW_tbl[A] to FOLLOW_tbl[B].
  184.         FOLLOW_tbl[p.RHS[i]] ++:= FOLLOW_tbl[p.LHS]
  185.         size +:= *FOLLOW_tbl[p.RHS[i]]
  186.         }
  187.         # Add FOLLOW_tbl[A] to FOLLOW_tbl[B] for the last symbol in the
  188.         # RHS of every rule.
  189.         type(p.RHS[*p.RHS]) == "string" | next
  190.         /FOLLOW_tbl[p.RHS[*p.RHS]] & iohno(90, image(p.RHS[*p.RHS]))
  191.         FOLLOW_tbl[p.RHS[*p.RHS]] ++:= FOLLOW_tbl[p.LHS]
  192.         size +:= *FOLLOW_tbl[p.RHS[*p.RHS]]
  193.     }
  194.     }
  195.  
  196.     # Print human-readable version of FOLLOW_tbl if instructed to do so.
  197.     if \DEBUG then
  198.     print_follow_sets(FOLLOW_tbl)
  199.  
  200.     # check for useless nonterminal symbols
  201.     every k := (!st).LHS do
  202.     *FOLLOW_tbl[k] = 0 & iohno(91, k)
  203.  
  204.     return FOLLOW_tbl
  205.  
  206. end
  207.  
  208.  
  209. #
  210. #  Below is the routine make_FIRST_sets(st), which accepts as its one
  211. #  argument a list or set of production records, and which returns a
  212. #  table t, where t's keys are symbols from the grammar defined by the
  213. #  productions in st, and where the values assocated with each of
  214. #  these keys is the FIRST set for that key.
  215. #
  216. #  Production records are structures where the first two fields, LHS
  217. #  and RHS, contain the left-hand and right-hand side of each rule in
  218. #  a given grammar.  The right-hand side is a linked list of integers
  219. #  (used for terminals) and strings (used for nonterminals). LHS must
  220. #  contain a string.  Terminals below 1 are reserved.  Currently three
  221. #  are actually used:
  222. #
  223. #      0    EOF
  224. #      -1   error
  225. #      -2   epsilon
  226. #
  227. #  For a description of the FIRST() construction algorithm, see Alfred
  228. #  Aho, Ravi Sethi, and Jeffrey D. Ullman _Compilers_ (Reading,
  229. #  Massachusetts: Addison & Wesley, 1986), section 4.4, page 189.
  230. #  Their algorithm is not strictly suitable, as is, for use here.  I
  231. #  thank Dave Schaumann of the University of Arizona at Tuscon for
  232. #  explaining to me the iterative construction algorithm that in fact
  233. #  *is* suitable.
  234. #  
  235. #  FIRST is computed on an iterative basis as follows:
  236. #
  237. #      1. For every terminal symbol a, FIRST(a) = { a }
  238. #      2. For every non-terminal symbol A, initialize FIRST(A) = { }
  239. #      3. For every production A -> <epsilon>, add <epsilon> to FIRST(A)
  240. #      4. For each production of the grammar having the form X -> Y1
  241. #         Y2 ... Yn, perform the following procedure:
  242. #          i := 1
  243. #          while i <= number-of-RHS-symbols do {
  244. #              if <epsilon> is not in FIRST(Y[i]) then {
  245. #                  FIRST(X) ++:= FIRST(Y[i])
  246. #                  break
  247. #              } else {
  248. #                  FIRST(X) ++:= FIRST(Y[i]) -- FIRST[<epsilon>]
  249. #                  i +:= 1
  250. #              }
  251. #          }
  252. #          if i > number-of-RHS-symbols then
  253. #              # <epsilon> is in FIRST(Y[i])
  254. #              FIRST(X) ++:= FIRST[epsilon]
  255. #      5. Repeat step 3 until no new symbols or <epsilon> can be added
  256. #         to any FIRST set
  257. #
  258.  
  259.  
  260. #
  261. # make_FIRST_sets:  set/list -> table
  262. #                   st       -> t
  263. #
  264. #     Where st is a set or list of production records, and t is a
  265. #     table of FIRST sets, where the keys = terminal or nonterminal
  266. #     symbols and the values = sets of terminal symbols.
  267. #
  268. #     Epsilon move is -2; terminals are positive integers;
  269. #     nonterminals are strings.  Error is -1; EOF is 0.
  270. #
  271. procedure make_FIRST_sets(st)
  272.  
  273.     local FIRST_tbl, symbol, p, old_size, size, i
  274.  
  275.     FIRST_tbl    := table()
  276.     FIRST_tbl[0] := set([0])
  277.  
  278.     # steps 1, 2, and 3 above
  279.     every p := !st do {
  280.     # check for empty RHS (an error)
  281.     *p.RHS = 0 & iohno(11, production_2_string(p))
  282.     # step 1
  283.     every symbol := !p.RHS do {
  284.         if type(symbol) == "integer"
  285.         then FIRST_tbl[symbol] := set([symbol])
  286.     }
  287.     # step 2
  288.     /FIRST_tbl[p.LHS] := set() &
  289.     # step 3
  290.     if *p.RHS = 1 then {
  291.         if p.RHS[1] === -2    # -2 is epsilon
  292.         then insert(FIRST_tbl[p.LHS], -2)
  293.     }
  294.     }
  295.  
  296.     # steps 4 and 5 above
  297.     size := 0
  298.     #
  299.     # When the old size of the FIRST sets equals the new size, we are
  300.     # done.  As long as they're unequal, set old_size to size and try
  301.     # to add to the FIRST sets.
  302.     #
  303.     while old_size ~===:= size do {
  304.     size := 0
  305.     every p := !st do {
  306.         every i := 1 to *p.RHS do {
  307.         \FIRST_tbl[p.RHS[i]] | iohno(90, image(p.RHS[i]))
  308.         if not member(FIRST_tbl[p.RHS[i]], -2) then {
  309.             # We're done with this pass if no epsilons.
  310.             FIRST_tbl[p.LHS] ++:= FIRST_tbl[p.RHS[i]]
  311.             size +:= *FIRST_tbl[p.LHS]
  312.             break next
  313.         } else {
  314.             # Remove the epsilon & try the next symbol in p.RHS.
  315.             FIRST_tbl[p.LHS] ++:= FIRST_tbl[p.RHS[i]] -- FIRST_tbl[-2]
  316.         }
  317.         }
  318.         # If we get past the every...do structure without
  319.         # break+next-ing, then we are still finding epsilons.  In
  320.         # this case, add epsilon to FIRST_tbl[p.LHS].
  321.         FIRST_tbl[p.LHS] ++:= FIRST_tbl[-2]
  322.         size +:= *FIRST_tbl[p.LHS]
  323.     }
  324.     }
  325.  
  326.     # Print human-readable version of FIRST_tbl if instructed to do so.
  327.     if \DEBUG then
  328.     print_first_sets(FIRST_tbl)
  329.  
  330.     return FIRST_tbl
  331.  
  332. end
  333.