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