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