home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / hugs101o.zip / Progs / HUGS / Demos / Prolog / Parse < prev    next >
Text File  |  1995-02-14  |  4KB  |  105 lines
  1. --
  2. -- General parsing library, based on Richard Bird's parselib.orw for Orwell
  3. -- (with a number of extensions)
  4. -- Mark P. Jones November 1990, modified for Gofer 20th July 1991
  5. --
  6. -- uses Gofer version 2.28
  7. --
  8.  
  9. infixr 6 `seq`
  10. infixl 5 `do`
  11. infixr 4 `orelse`
  12.  
  13. --- Type definition:
  14.  
  15. type Parser a = [Char] -> [(a,[Char])]
  16.  
  17. -- A parser is a function which maps an input stream of characters into
  18. -- a list of pairs each containing a parsed value and the remainder of the
  19. -- unused input stream.  This approach allows us to use the list of
  20. -- successes technique to detect errors (i.e. empty list ==> syntax error).
  21. -- it also permits the use of ambiguous grammars in which there may be more
  22. -- than one valid parse of an input string.
  23.  
  24. --- Primitive parsers:
  25.  
  26. -- fail     is a parser which always fails.
  27. -- okay v   is a parser which always succeeds without consuming any characters
  28. --          from the input string, with parsed value v.
  29. -- tok w    is a parser which succeeds if the input stream begins with the
  30. --          string (token) w, returning the matching string and the following
  31. --          input.  If the input does not begin with w then the parser fails.
  32. -- sat p    is a parser which succeeds with value c if c is the first input
  33. --          character and c satisfies the predicate p.
  34.  
  35. fail        :: Parser a 
  36. fail is      = []
  37.  
  38. okay        :: a -> Parser a  
  39. okay v is    = [(v,is)]
  40.  
  41. tok         :: [Char] -> Parser [Char]
  42. tok w is     = [(w, drop n is) | w == take n is]
  43.                where n = length w
  44.  
  45. sat         :: (Char -> Bool) -> Parser Char 
  46. sat p []     = []
  47. sat p (c:is) = [ (c,is) | p c ]
  48.  
  49. --- Parser combinators:
  50.  
  51. -- p1 `orelse` p2 is a parser which returns all possible parses of the input
  52. --                string, first using the parser p1, then using parser p2.
  53. -- p1 `seq` p2    is a parser which returns pairs of values (v1,v2) where
  54. --                v1 is the result of parsing the input string using p1 and
  55. --                v2 is the result of parsing the remaining input using p2.
  56. -- p `do` f       is a parser which behaves like the parser p, but returns
  57. --                the value f v wherever p would have returned the value v.
  58. --
  59. -- just p         is a parser which behaves like the parser p, but rejects any
  60. --                parses in which the remaining input string is not blank.
  61. -- sp p           behaves like the parser p, but ignores leading spaces.
  62. -- sptok w        behaves like the parser tok w, but ignores leading spaces.
  63. --
  64. -- many p         returns a list of values, each parsed using the parser p.
  65. -- many1 p        parses a non-empty list of values, each parsed using p.
  66. -- listOf p s     parses a list of input values using the parser p, with
  67. --                separators parsed using the parser s.
  68.  
  69. orelse             :: Parser a -> Parser a -> Parser a 
  70. (p1 `orelse` p2) is = p1 is ++ p2 is
  71.  
  72. seq                :: Parser a -> Parser b -> Parser (a,b)
  73. (p1 `seq` p2) is    = [((v1,v2),is2) | (v1,is1) <- p1 is, (v2,is2) <- p2 is1]
  74.  
  75. do                 :: Parser a -> (a -> b) -> Parser b 
  76. (p `do` f) is       = [(f v, is1) | (v,is1) <- p is]
  77.  
  78. just               :: Parser a -> Parser a
  79. just p is           = [ (v,"") | (v,is')<- p is, dropWhile (' '==) is' == "" ]
  80.  
  81. sp                 :: Parser a -> Parser a
  82. sp p                = p . dropWhile (' '==)
  83.  
  84. sptok              :: [Char] -> Parser [Char]
  85. sptok               =  sp . tok
  86.  
  87. many               :: Parser a  -> Parser [a]
  88. many p              = q
  89.                       where q = ((p `seq` q) `do` makeList) `orelse` (okay [])
  90.  
  91. many1              :: Parser a -> Parser [a]
  92. many1 p             = p `seq` many p `do` makeList
  93.  
  94. listOf             :: Parser a -> Parser b -> Parser [a]
  95. listOf p s          = p `seq` many (s `seq` p) `do` nonempty
  96.                       `orelse` okay []
  97.                       where nonempty (x,xs) = x:(map snd xs)
  98.  
  99. --- Internals:
  100.  
  101. makeList       :: (a,[a]) -> [a]
  102. makeList (x,xs) = x:xs
  103.  
  104. --- End of Parse.hs
  105.