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 / progs / recgen.icn < prev    next >
Text File  |  2000-07-29  |  5KB  |  170 lines
  1. ############################################################################
  2. #
  3. #    File:     recgen.icn
  4. #
  5. #    Subject:  Program to generate context-free recognizer
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     January 28, 1991
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. #     This program reads a context-free BNF grammar and produces an Icon
  18. #  program that is a recognizer for the corresponding language.
  19. #
  20. #     Nonterminal symbols are are enclosed in angular brackets. Vertical
  21. #  bars separate alternatives.  All other characters are considered to
  22. #  be terminal symbols.  The nonterminal symbol on the first line is
  23. #  taken to be the goal.
  24. #
  25. #     An example is:
  26. #
  27. #    <expression>::=<term>|<term>+<expression>
  28. #    <term>::=<element>|<element>*<term>
  29. #    <element>::=x|y|z|(<expression>)
  30. #
  31. #     Characters in nonterminal names are limited to letters and underscores.
  32. #  An underscore is appended for the recognizing procedure name to avoid
  33. #  possible collisions with Icon function names.
  34. #
  35. #     Lines beginning with an = are passed through unchanged. This allows
  36. #  Icon code to be placed in the recognizer.
  37. #
  38. ############################################################################
  39. #
  40. #  Limitations:
  41. #
  42. #     Left recursion in the grammar may cause the recognizer to loop.
  43. #  There is no check that all nonterminal symbols that are referenced
  44. #  are defined or for duplicate definitions.
  45. #
  46. ############################################################################
  47. #
  48. #  Reference:
  49. #
  50. #     The Icon Programming Language, Second Edition, Ralph E. and Madge T.
  51. #     Griswold, Prentice-Hall, 1990. pp. 180-187.
  52. #
  53. ############################################################################
  54. #
  55. #  See also:  pargen.icn
  56. #
  57. ############################################################################
  58.  
  59. global call            # name suffix and parens
  60. global goal            # nonterminal goal name
  61. global nchars            # characters allowed in a nonterminal name
  62.  
  63. procedure main()
  64.    local line            # a line of input
  65.  
  66.    call := "_()"
  67.    nchars := &letters ++ '_'
  68.  
  69.    while line := read() do {        # process lines of input
  70.       line ? {
  71.          case move(1) of {        # action depends on first character
  72.             "<":  tab(0) ? transprod()    # transform the production
  73.             "=":  write(tab(0))        # pass through
  74.             default: error()
  75.             }                # end case
  76.          }                # end scan
  77.       }                    # end while
  78.  
  79.    write("procedure main()")        # write out the main procedure
  80.    write("   while line := read() do {")
  81.    write("      writes(image(line))")
  82.    write("      if line ? (",goal,call," & pos(0)) then ")
  83.    write("         write(\": accepted\")")
  84.    write("      else write(\": rejected\")")
  85.    write("      }")
  86.    write("end")
  87.  
  88. end
  89.  
  90. #
  91. #  Transform a production.
  92. #
  93.  
  94. procedure transprod()
  95.    local sym                # the symbol being defined
  96.  
  97.    {
  98.                     # begin the procedure declaration
  99.       write("procedure ",sym := tab(many(nchars)),call) &
  100.       =">::="                # skip definition symbols
  101.       } | error()                # catch syntactic error
  102.    write("   suspend {")        # begin the suspend expression
  103.    transalts()                # transform the alternatives
  104.    write("      }")            # end the suspend expression
  105.    write("end")                # end the procedure declaration
  106.    write()                # space between declarations
  107.    /goal := sym                # first symbol is goal
  108.  
  109. end
  110.  
  111. #
  112. #  Transform a sequence of alternatives.
  113. #
  114. procedure transalts()
  115.    local alt                # an alternative
  116.  
  117.    writes("      ")            # write indentation
  118.    while alt := tab(upto('|') | 0) do {    # process alternatives
  119.       writes(" (")            # open parenthesis for alternative
  120.       alt ? transseq()            # transform the symbols
  121.       if move(1) then writes(") |")    # if there's more, close the parentheses
  122.                     # and add the alternation.
  123.       else {
  124.          write(")")            # no more, so just close the parentheses
  125.          break
  126.          }                # end else
  127.       }                    # end while
  128.  
  129. end
  130.  
  131. #
  132. #  Transform a sequence of symbols.
  133. #
  134. procedure transseq()
  135.  
  136.    repeat {
  137.       transsym()            # process a symbols
  138.       if not pos(0) then writes(",")    # if there's more, provide concatenation
  139.       else break            # else get out and return
  140.       }                    # end while
  141.  
  142. end
  143.  
  144. #
  145. #  Transform a symbol.
  146. #
  147. procedure transsym()
  148.  
  149.    if ="<" then {            # if it's a nonterminal
  150.       {                    # write it with suffix.
  151.          writes(tab(many(nchars)),call) &
  152.          =">"                # get rid of closing bracket
  153.          } | error()            # or catch the error
  154.       }                    # end then
  155.                     # otherwise transform nonterminal string
  156.    else writes("=",image(tab(upto('<') | 0)))
  157.  
  158.    return
  159.  
  160. end
  161.  
  162. #
  163. #  Issue error message and terminate execution.
  164. #
  165. procedure error()
  166.  
  167.    stop("*** malformed definition: ",tab(0))
  168.  
  169. end
  170.