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 / pargen.icn < prev    next >
Text File  |  2000-07-29  |  6KB  |  205 lines
  1. ############################################################################
  2. #
  3. #    File:     pargen.icn
  4. #
  5. #    Subject:  Program to generate context-free parser
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     March 31, 1992
  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 parser 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. #     Parentheses can be used for grouping symbols, as in
  32. #
  33. #    <term>::=<element>(|*<term>)
  34. #
  35. #     Note that an empty alternative is allowable.
  36. #
  37. #     The right-hand side metacharacters <, >, (, ), and | are accessible
  38. #  through the built-in symbols <lb>, <rb>, <lp>, <rp>, and <vb>,
  39. #  respectively. There are two other build-in symbols, <empty> and <nl>
  40. #  that match the empty string and a newline, respectively.
  41. #
  42. #     Characters in nonterminal names are limited to letters, digits, and
  43. #  underscores.
  44. #
  45. #     An underscore is appended to the parsing procedure name to avoid
  46. #  possible collisions with Icon function names.
  47. #
  48. #     Lines beginning with an = are passed through unchanged. This allows
  49. #  Icon declarations to be placed in the parser.  Lines beginning with
  50. #  a # are considered to be comments and are ignored.
  51. #
  52. #     If the name of a ucode file is given on the command line, a link
  53. #  declaration for it is provided in the output. Otherwise the main
  54. #  procedure in recog is used.
  55. #
  56. ############################################################################
  57. #
  58. #  Limitations:
  59. #
  60. #     Left recursion in the grammar may cause the parser to loop.
  61. #  There is no check that all nonterminal symbols that are referenced
  62. #  are defined or that there may be duplicate definitions.
  63. #
  64. ############################################################################
  65. #
  66. #  Reference:
  67. #
  68. #     The Icon Programming Language, Second Edition, Ralph E. and Madge T.
  69. #     Griswold, Prentice-Hall, 1990, pp. 180-187.
  70. #
  71. ############################################################################
  72. #
  73. #  Output links recog, matchlib
  74. #
  75. #  See also: recog.icn, matchlib.icn, and parscond.icn
  76. #
  77. ############################################################################
  78.  
  79. global declend            # name suffix and record body
  80. global goal            # nonterminal goal name
  81. global nchars            # characters allowed in a nonterminal name
  82. global procend            # name suffix and parens
  83. global sym            # current nonterminal symbol
  84.  
  85. procedure main(args)
  86.    local line            # a line of input
  87.  
  88.    declend := "__"
  89.    procend := "_()"
  90.    nchars := &letters ++ &digits ++ '_'
  91.  
  92.    while line := read() do {        # process lines of input
  93.       line ? {
  94.          case move(1) of {        # action depends on first character
  95.             "<":  tab(0) ? transprod()    # transform the production
  96.             "=":  write(tab(0))        # pass through
  97.             "#":  &null            # ignore
  98.             default: error()
  99.             }                # end case
  100.          }                # end scan
  101.       }                    # end while
  102.  
  103.    write("link ",args[1] | "recog")    # link main procedure
  104.    write("link matchlib")        # link built-in symbols
  105.    write("global goal\n")        # write out global declaration
  106.    write("procedure init()")        # write out initialization procedure
  107.    write("   goal := ",goal,"_")
  108.    write("   return")
  109.    write("end")
  110.  
  111. end
  112.  
  113. #
  114. #  Transform a production.
  115. #
  116.  
  117. procedure transprod()
  118.  
  119.    {
  120.       sym := tab(many(nchars)) &    # get the nonterminal name
  121.       =">::=" 
  122.       } | error()            # catch syntactic error
  123.    write("record ",sym,declend,"(alts)")# record declaration
  124.    write("procedure ",sym,procend)    # procedure header
  125.    write("   suspend {")        # begin the suspend expression
  126.    writes("      ",sym,declend,"(")    # write indentation
  127.    transalts()                # transform the alternatives
  128.    write(")")
  129.    write("      }")            # end the suspend expression
  130.    write("end")                # end the procedure declaration
  131.    write()                # space between declarations
  132.    /goal := sym                # first symbol is goal
  133.  
  134. end
  135.  
  136. #
  137. #  Transform a sequence of alternatives.
  138. #
  139. procedure transalts()
  140.    local alt                # an alternative
  141.  
  142.    while alt := tab(bal('|') | 0) do {    # process alternatives
  143.       writes("[")        # record for alternative
  144.       alt ? transseq()            # transform the symbols
  145.       if move(1) then writes("] | ")    # if more, close the parentheses
  146.                     # and add the alternation.
  147.       else {
  148.          writes("]")            # no more, so just close the parentheses
  149.          break
  150.          }                # end else
  151.       }                    # end while
  152.  
  153. end
  154.  
  155. #
  156. #  Transform a sequence of symbols.
  157. #
  158. procedure transseq()
  159.  
  160.    repeat {
  161.       transsym()            # process a symbols
  162.       if not pos(0) then writes(" , ")    # if there's more, provide concatenation
  163.       else break            # else get out and return
  164.       }                    # end while
  165.  
  166.    return
  167.  
  168. end
  169.  
  170. #
  171. #  Transform a symbol.
  172. #
  173. procedure transsym()
  174.    local group
  175.  
  176.    if ="<" then {            # if it's a nonterminal
  177.       {                    # write it with suffix.
  178.          writes(tab(many(nchars)),procend) &
  179.          =">"                # get rid of closing bracket
  180.          } | error()            # or catch the error
  181.       }                    # end then
  182.  
  183.    else if ="(" then {            # if it's a parenthesis, pass it
  184.       writes("(")            # along and call transseq()
  185.       group := tab(bal(')')) | error()
  186.       group ? transalts()
  187.       writes(")")
  188.       move(1)
  189.       }
  190.                     # else transform nonterminal string
  191.    else writes("=",image(tab(upto('<') | 0)))
  192.  
  193.    return
  194.  
  195. end
  196.  
  197. #
  198. #  Issue error message and terminate execution.
  199. #
  200. procedure error()
  201.  
  202.    stop("*** malformed definition: ",tab(0))
  203.  
  204. end
  205.