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 / csgen.icn < prev    next >
Text File  |  2000-07-29  |  4KB  |  154 lines
  1. ############################################################################
  2. #
  3. #    File:     csgen.icn
  4. #
  5. #    Subject:  Program to generate context-sensitive sentences
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     November 19, 1997
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #  
  17. #     This program accepts a context-sensitive production grammar
  18. #  and generates randomly selected sentences from the corresponding
  19. #  language.
  20. #  
  21. #     Uppercase letters stand for nonterminal symbols and -> indi-
  22. #  cates the lefthand side can be rewritten by the righthand side.
  23. #  Other characters are considered to be terminal symbols. Lines
  24. #  beginning with # are considered to be comments and are ignored.
  25. #  A line consisting of a nonterminal symbol followed by a colon and
  26. #  a nonnegative integer i is a generation specification for i
  27. #  instances of sentences for the language defined by the nontermi-
  28. #  nal (goal) symbol.  An example of input to csgen is:
  29. #  
  30. #          #   a(n)b(n)c(n)
  31. #          #   Salomaa, p. 11.
  32. #          #   Attributed to M. Soittola.
  33. #          #
  34. #          X->abc
  35. #          X->aYbc
  36. #          Yb->bY
  37. #          Yc->Zbcc
  38. #          bZ->Zb
  39. #          aZ->aaY
  40. #          aZ->aa
  41. #          X:10
  42. #  
  43. #  The output of csgen for this example is
  44. #  
  45. #          aaabbbccc
  46. #          aaaaaaaaabbbbbbbbbccccccccc
  47. #          abc
  48. #          aabbcc
  49. #          aabbcc
  50. #          aaabbbccc
  51. #          aabbcc
  52. #          abc
  53. #          aaaabbbbcccc
  54. #          aaabbbccc
  55. #  
  56. #  
  57. #     A positive integer followed by a colon can be prefixed to a
  58. #  production to replicate that production, making its selection
  59. #  more likely. For example,
  60. #  
  61. #          3:X->abc
  62. #  
  63. #  is equivalent to
  64. #  
  65. #          X->abc
  66. #          X->abc
  67. #          X->abc
  68. #  
  69. #  One option is supported:
  70. #
  71. #    -g i    number of derivations; overrides the number specified
  72. #        in the grammar
  73. #  
  74. #  Limitations: Nonterminal symbols can only be represented by sin-
  75. #  gle uppercase letters, and there is no way to represent uppercase
  76. #  letters as terminal symbols.
  77. #  
  78. #     There can be only one generation specification and it must
  79. #  appear as the last line of input.
  80. #  
  81. #  Comments: Generation of context-sensitive strings is a slow pro-
  82. #  cess. It may not terminate, either because of a loop in the
  83. #  rewriting rules or because of the progressive accumulation of
  84. #  nonterminal symbols.  The program avoids deadlock, in which there
  85. #  are no possible rewrites for a string in the derivation.
  86. #  
  87. #     This program would be improved if the specification of nonter-
  88. #  minal symbols were more general, as in rsg.
  89. #  
  90. ############################################################################
  91. #
  92. #  Links: options, random
  93. #
  94. ############################################################################
  95.  
  96. link options
  97. link random
  98.  
  99. global xlist
  100.  
  101. procedure main(args)
  102.    local line, goal, count, s, opts
  103.  
  104.    opts := options(args, "g+")
  105.  
  106.    randomize()
  107.  
  108.    while line := read() do        #  read in grammar
  109.       if line[1] == "#" then next
  110.       else if xpairs(line) then next
  111.       else {
  112.          line ? (goal := move(1),move(1),count := (1 < integer(tab(0))))
  113.          break
  114.          }
  115.  
  116.    if /count then stop("no goal specification")
  117.  
  118.    count := \opts["g"]
  119.    if count < 1 then stop("*** invalid number of derivations specified")
  120.  
  121.    every 1 to count do {        #  generate sentences
  122.       s := goal
  123.       repeat {
  124.          if not upto(&ucase,s) then break    # text for nonterminal
  125.                     #  quit on deadlock
  126.          if not(s ? subst(!xlist)) then break next
  127.          until s ?:= subst(?xlist)    #  make replacement
  128.          }
  129.       write(s)
  130.       }
  131. end
  132.  
  133. #  replace left hand side by right hand side
  134. #
  135. procedure subst(a)
  136.    suspend tab(find(a[1])) || (move(*a[1]),a[2]) || tab(0)
  137. end
  138.  
  139. #  enter rewriting rule
  140. #
  141. procedure xpairs(s)
  142.    local i, a
  143.    initial xlist := []
  144.    if s ? {
  145.                 #  handle optional replication factor
  146.       i := 1(0 < integer(tab(upto(':'))),move(1)) | 1 &
  147.       a := [tab(find("->")),(move(2),tab(0))]
  148.       }
  149.    then {
  150.       every 1 to i do put(xlist,a)
  151.       return
  152.       }
  153. end
  154.