polyparse-1.0: docs/haddock/src/Text/ParserCombinators/HuttonMeijer.html
<pre><font color=Blue>-----------------------------------------------------------------------------</font>
<font color=Blue>-- |</font>
<font color=Blue>-- Module : Text.ParserCombinators.HuttonMeijer</font>
<font color=Blue>-- Copyright : Graham Hutton (University of Nottingham), Erik Meijer (University of Utrecht)</font>
<font color=Blue>-- Licence : BSD</font>
<font color=Blue>-- </font>
<font color=Blue>-- Maintainer : Malcolm Wallace <Malcolm.Wallace@cs.york.ac.uk></font>
<font color=Blue>-- Stability : Stable</font>
<font color=Blue>-- Portability : All</font>
<font color=Blue>--</font>
<font color=Blue>-- A LIBRARY OF MONADIC PARSER COMBINATORS</font>
<font color=Blue>-- </font>
<font color=Blue>-- 29th July 1996</font>
<font color=Blue>-- </font>
<font color=Blue>-- Graham Hutton Erik Meijer</font>
<font color=Blue>-- University of Nottingham University of Utrecht</font>
<font color=Blue>-- </font>
<font color=Blue>-- This Haskell script defines a library of parser combinators, and is</font>
<font color=Blue>-- taken from sections 1-6 of our article "Monadic Parser Combinators".</font>
<font color=Blue>-- Some changes to the library have been made in the move from Gofer</font>
<font color=Blue>-- to Haskell:</font>
<font color=Blue>-- </font>
<font color=Blue>-- * Do notation is used in place of monad comprehension notation;</font>
<font color=Blue>-- </font>
<font color=Blue>-- * The parser datatype is defined using "newtype", to avoid the overhead</font>
<font color=Blue>-- of tagging and untagging parsers with the P constructor.</font>
<font color=Blue>-----------------------------------------------------------------------------</font>
<font color=Green><u>module</u></font> Text<font color=Cyan>.</font>ParserCombinators<font color=Cyan>.</font>HuttonMeijer
<font color=Cyan>(</font>Parser<font color=Cyan>(</font><font color=Red>..</font><font color=Cyan>)</font><font color=Cyan>,</font> item<font color=Cyan>,</font> first<font color=Cyan>,</font> papply<font color=Cyan>,</font> <font color=Cyan>(</font><font color=Cyan>+++</font><font color=Cyan>)</font><font color=Cyan>,</font> sat<font color=Cyan>,</font> <font color=Blue>{-tok,-}</font> many<font color=Cyan>,</font> many1<font color=Cyan>,</font>
sepby<font color=Cyan>,</font> sepby1<font color=Cyan>,</font> chainl<font color=Cyan>,</font>
chainl1<font color=Cyan>,</font> chainr<font color=Cyan>,</font> chainr1<font color=Cyan>,</font> ops<font color=Cyan>,</font> bracket<font color=Cyan>,</font> char<font color=Cyan>,</font> digit<font color=Cyan>,</font> lower<font color=Cyan>,</font> upper<font color=Cyan>,</font>
letter<font color=Cyan>,</font> alphanum<font color=Cyan>,</font> string<font color=Cyan>,</font> ident<font color=Cyan>,</font> nat<font color=Cyan>,</font> int<font color=Cyan>,</font> spaces<font color=Cyan>,</font> comment<font color=Cyan>,</font> junk<font color=Cyan>,</font>
skip<font color=Cyan>,</font> token<font color=Cyan>,</font> natural<font color=Cyan>,</font> integer<font color=Cyan>,</font> symbol<font color=Cyan>,</font> identifier<font color=Cyan>)</font> <font color=Green><u>where</u></font>
<font color=Green><u>import</u></font> Char
<font color=Green><u>import</u></font> Monad
<font color=Green><u>infixr</u></font> <font color=Magenta>5</font> <font color=Cyan>+++</font>
<a name="Token"></a><font color=Green><u>type</u></font> Token <font color=Red>=</font> Char
<font color=Blue>---------------------------------------------------------</font>
<font color=Blue>-- | The parser monad</font>
<font color=Green><u>newtype</u></font> Parser a <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>[</font>Token<font color=Red>]</font> <font color=Red>-></font> <font color=Red>[</font><font color=Cyan>(</font>a<font color=Cyan>,</font><font color=Red>[</font>Token<font color=Red>]</font><font color=Cyan>)</font><font color=Red>]</font><font color=Cyan>)</font>
<font color=Green><u>instance</u></font> Functor Parser <font color=Green><u>where</u></font>
<font color=Blue>-- map :: (a -> b) -> (Parser a -> Parser b)</font>
fmap f <font color=Cyan>(</font>P p<font color=Cyan>)</font> <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> <font color=Red>[</font><font color=Cyan>(</font>f v<font color=Cyan>,</font> out<font color=Cyan>)</font> <font color=Red>|</font> <font color=Cyan>(</font>v<font color=Cyan>,</font>out<font color=Cyan>)</font> <font color=Red><-</font> p inp<font color=Red>]</font><font color=Cyan>)</font>
<font color=Green><u>instance</u></font> Monad Parser <font color=Green><u>where</u></font>
<font color=Blue>-- return :: a -> Parser a</font>
return v <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> <font color=Red>[</font><font color=Cyan>(</font>v<font color=Cyan>,</font>inp<font color=Cyan>)</font><font color=Red>]</font><font color=Cyan>)</font>
<font color=Blue>-- >>= :: Parser a -> (a -> Parser b) -> Parser b</font>
<font color=Cyan>(</font>P p<font color=Cyan>)</font> <font color=Cyan>>>=</font> f <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> concat <font color=Red>[</font>papply <font color=Cyan>(</font>f v<font color=Cyan>)</font> out <font color=Red>|</font> <font color=Cyan>(</font>v<font color=Cyan>,</font>out<font color=Cyan>)</font> <font color=Red><-</font> p inp<font color=Red>]</font><font color=Cyan>)</font>
<font color=Blue>-- fail :: String -> Parser a</font>
fail <font color=Green><u>_</u></font> <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font><font color=Green><u>_</u></font> <font color=Red>-></font> <font color=Red>[</font><font color=Red>]</font><font color=Cyan>)</font>
<font color=Green><u>instance</u></font> MonadPlus Parser <font color=Green><u>where</u></font>
<font color=Blue>-- mzero :: Parser a</font>
mzero <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font><font color=Green><u>_</u></font> <font color=Red>-></font> <font color=Red>[</font><font color=Red>]</font><font color=Cyan>)</font>
<font color=Blue>-- mplus :: Parser a -> Parser a -> Parser a</font>
<font color=Cyan>(</font>P p<font color=Cyan>)</font> <font color=Cyan>`mplus`</font> <font color=Cyan>(</font>P q<font color=Cyan>)</font> <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> <font color=Cyan>(</font>p inp <font color=Cyan>++</font> q inp<font color=Cyan>)</font><font color=Cyan>)</font>
<font color=Blue>-- ------------------------------------------------------------</font>
<font color=Blue>-- * Other primitive parser combinators</font>
<font color=Blue>-- ------------------------------------------------------------</font>
item <font color=Red>::</font> Parser Token
<a name="item"></a>item <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> <font color=Green><u>case</u></font> inp <font color=Green><u>of</u></font>
<font color=Red>[</font><font color=Red>]</font> <font color=Red>-></font> <font color=Red>[</font><font color=Red>]</font>
<font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font> <font color=Red>-></font> <font color=Red>[</font><font color=Cyan>(</font>x<font color=Cyan>,</font>xs<font color=Cyan>)</font><font color=Red>]</font><font color=Cyan>)</font>
first <font color=Red>::</font> Parser a <font color=Red>-></font> Parser a
<a name="first"></a>first <font color=Cyan>(</font>P p<font color=Cyan>)</font> <font color=Red>=</font> P <font color=Cyan>(</font><font color=Red>\</font>inp <font color=Red>-></font> <font color=Green><u>case</u></font> p inp <font color=Green><u>of</u></font>
<font color=Red>[</font><font color=Red>]</font> <font color=Red>-></font> <font color=Red>[</font><font color=Red>]</font>
<font color=Cyan>(</font>x<font color=Red><b>:</b></font><font color=Green><u>_</u></font><font color=Cyan>)</font> <font color=Red>-></font> <font color=Red>[</font>x<font color=Red>]</font><font color=Cyan>)</font>
papply <font color=Red>::</font> Parser a <font color=Red>-></font> <font color=Red>[</font>Token<font color=Red>]</font> <font color=Red>-></font> <font color=Red>[</font><font color=Cyan>(</font>a<font color=Cyan>,</font><font color=Red>[</font>Token<font color=Red>]</font><font color=Cyan>)</font><font color=Red>]</font>
<a name="papply"></a>papply <font color=Cyan>(</font>P p<font color=Cyan>)</font> inp <font color=Red>=</font> p inp
<font color=Blue>-- ------------------------------------------------------------</font>
<font color=Blue>-- * Derived combinators</font>
<font color=Blue>-- ------------------------------------------------------------</font>
<a name="+++"></a><font color=Cyan>(</font><font color=Cyan>+++</font><font color=Cyan>)</font> <font color=Red>::</font> Parser a <font color=Red>-></font> Parser a <font color=Red>-></font> Parser a
<a name="p"></a>p <font color=Cyan>+++</font> q <font color=Red>=</font> first <font color=Cyan>(</font>p <font color=Cyan>`mplus`</font> q<font color=Cyan>)</font>
sat <font color=Red>::</font> <font color=Cyan>(</font>Token <font color=Red>-></font> Bool<font color=Cyan>)</font> <font color=Red>-></font> Parser Token
<a name="sat"></a>sat p <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> item<font color=Cyan>;</font> <font color=Green><u>if</u></font> p x <font color=Green><u>then</u></font> return x <font color=Green><u>else</u></font> mzero<font color=Cyan>}</font>
<font color=Blue>--tok :: Token -> Parser Token</font>
<font color=Blue>--tok t = do {x <- item; if t==snd x then return t else mzero}</font>
many <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Red>[</font>a<font color=Red>]</font>
<a name="many"></a>many p <font color=Red>=</font> many1 p <font color=Cyan>+++</font> return <font color=Red>[</font><font color=Red>]</font>
<font color=Blue>--many p = force (many1 p +++ return [])</font>
many1 <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Red>[</font>a<font color=Red>]</font>
<a name="many1"></a>many1 p <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> p<font color=Cyan>;</font> xs <font color=Red><-</font> many p<font color=Cyan>;</font> return <font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font><font color=Cyan>}</font>
sepby <font color=Red>::</font> Parser a <font color=Red>-></font> Parser b <font color=Red>-></font> Parser <font color=Red>[</font>a<font color=Red>]</font>
<a name="sepby"></a>p <font color=Cyan>`sepby`</font> sep <font color=Red>=</font> <font color=Cyan>(</font>p <font color=Cyan>`sepby1`</font> sep<font color=Cyan>)</font> <font color=Cyan>+++</font> return <font color=Red>[</font><font color=Red>]</font>
sepby1 <font color=Red>::</font> Parser a <font color=Red>-></font> Parser b <font color=Red>-></font> Parser <font color=Red>[</font>a<font color=Red>]</font>
<a name="sepby1"></a>p <font color=Cyan>`sepby1`</font> sep <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> p<font color=Cyan>;</font> xs <font color=Red><-</font> many <font color=Cyan>(</font><font color=Green><u>do</u></font> <font color=Cyan>{</font>sep<font color=Cyan>;</font> p<font color=Cyan>}</font><font color=Cyan>)</font><font color=Cyan>;</font> return <font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font><font color=Cyan>}</font>
chainl <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Cyan>(</font>a <font color=Red>-></font> a <font color=Red>-></font> a<font color=Cyan>)</font> <font color=Red>-></font> a <font color=Red>-></font> Parser a
<a name="chainl"></a>chainl p op v <font color=Red>=</font> <font color=Cyan>(</font>p <font color=Cyan>`chainl1`</font> op<font color=Cyan>)</font> <font color=Cyan>+++</font> return v
chainl1 <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Cyan>(</font>a <font color=Red>-></font> a <font color=Red>-></font> a<font color=Cyan>)</font> <font color=Red>-></font> Parser a
<a name="chainl1"></a>p <font color=Cyan>`chainl1`</font> op <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> p<font color=Cyan>;</font> rest x<font color=Cyan>}</font>
<font color=Green><u>where</u></font>
rest x <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>f <font color=Red><-</font> op<font color=Cyan>;</font> y <font color=Red><-</font> p<font color=Cyan>;</font> rest <font color=Cyan>(</font>f x y<font color=Cyan>)</font><font color=Cyan>}</font>
<font color=Cyan>+++</font> return x
chainr <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Cyan>(</font>a <font color=Red>-></font> a <font color=Red>-></font> a<font color=Cyan>)</font> <font color=Red>-></font> a <font color=Red>-></font> Parser a
<a name="chainr"></a>chainr p op v <font color=Red>=</font> <font color=Cyan>(</font>p <font color=Cyan>`chainr1`</font> op<font color=Cyan>)</font> <font color=Cyan>+++</font> return v
chainr1 <font color=Red>::</font> Parser a <font color=Red>-></font> Parser <font color=Cyan>(</font>a <font color=Red>-></font> a <font color=Red>-></font> a<font color=Cyan>)</font> <font color=Red>-></font> Parser a
<a name="chainr1"></a>p <font color=Cyan>`chainr1`</font> op <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> p<font color=Cyan>;</font> rest x<font color=Cyan>}</font>
<font color=Green><u>where</u></font>
rest x <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>f <font color=Red><-</font> op<font color=Cyan>;</font> y <font color=Red><-</font> p <font color=Cyan>`chainr1`</font> op<font color=Cyan>;</font> return <font color=Cyan>(</font>f x y<font color=Cyan>)</font><font color=Cyan>}</font>
<font color=Cyan>+++</font> return x
ops <font color=Red>::</font> <font color=Red>[</font><font color=Cyan>(</font>Parser a<font color=Cyan>,</font> b<font color=Cyan>)</font><font color=Red>]</font> <font color=Red>-></font> Parser b
<a name="ops"></a>ops xs <font color=Red>=</font> foldr1 <font color=Cyan>(</font><font color=Cyan>+++</font><font color=Cyan>)</font> <font color=Red>[</font><font color=Green><u>do</u></font> <font color=Cyan>{</font>p<font color=Cyan>;</font> return op<font color=Cyan>}</font> <font color=Red>|</font> <font color=Cyan>(</font>p<font color=Cyan>,</font>op<font color=Cyan>)</font> <font color=Red><-</font> xs<font color=Red>]</font>
bracket <font color=Red>::</font> Parser a <font color=Red>-></font> Parser b <font color=Red>-></font> Parser c <font color=Red>-></font> Parser b
<a name="bracket"></a>bracket open p close <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>open<font color=Cyan>;</font> x <font color=Red><-</font> p<font color=Cyan>;</font> close<font color=Cyan>;</font> return x<font color=Cyan>}</font>
<font color=Blue>-- ------------------------------------------------------------</font>
<font color=Blue>-- * Useful parsers</font>
<font color=Blue>-- ------------------------------------------------------------</font>
char <font color=Red>::</font> Char <font color=Red>-></font> Parser Char
<a name="char"></a>char x <font color=Red>=</font> sat <font color=Cyan>(</font><font color=Red>\</font>y <font color=Red>-></font> x <font color=Cyan>==</font> y<font color=Cyan>)</font>
digit <font color=Red>::</font> Parser Char
<a name="digit"></a>digit <font color=Red>=</font> sat isDigit
lower <font color=Red>::</font> Parser Char
<a name="lower"></a>lower <font color=Red>=</font> sat isLower
upper <font color=Red>::</font> Parser Char
<a name="upper"></a>upper <font color=Red>=</font> sat isUpper
letter <font color=Red>::</font> Parser Char
<a name="letter"></a>letter <font color=Red>=</font> sat isAlpha
alphanum <font color=Red>::</font> Parser Char
<a name="alphanum"></a>alphanum <font color=Red>=</font> sat isAlphaNum <font color=Cyan>+++</font> char <font color=Magenta>'_'</font>
string <font color=Red>::</font> String <font color=Red>-></font> Parser String
<a name="string"></a>string <font color=Magenta>""</font> <font color=Red>=</font> return <font color=Magenta>""</font>
string <font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font> <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>char x<font color=Cyan>;</font> string xs<font color=Cyan>;</font> return <font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font><font color=Cyan>}</font>
ident <font color=Red>::</font> Parser String
<a name="ident"></a>ident <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> lower<font color=Cyan>;</font> xs <font color=Red><-</font> many alphanum<font color=Cyan>;</font> return <font color=Cyan>(</font>x<font color=Red><b>:</b></font>xs<font color=Cyan>)</font><font color=Cyan>}</font>
nat <font color=Red>::</font> Parser Int
<a name="nat"></a>nat <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> digit<font color=Cyan>;</font> return <font color=Cyan>(</font>fromEnum x <font color=Blue>-</font> fromEnum <font color=Magenta>'0'</font><font color=Cyan>)</font><font color=Cyan>}</font> <font color=Cyan>`chainl1`</font> return op
<font color=Green><u>where</u></font>
m <font color=Cyan>`op`</font> n <font color=Red>=</font> <font color=Magenta>10</font><font color=Cyan>*</font>m <font color=Cyan>+</font> n
int <font color=Red>::</font> Parser Int
<a name="int"></a>int <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>char <font color=Magenta>'-'</font><font color=Cyan>;</font> n <font color=Red><-</font> nat<font color=Cyan>;</font> return <font color=Cyan>(</font><font color=Blue>-</font>n<font color=Cyan>)</font><font color=Cyan>}</font> <font color=Cyan>+++</font> nat
<font color=Blue>-- ------------------------------------------------------------</font>
<font color=Blue>-- * Lexical combinators</font>
<font color=Blue>-- ------------------------------------------------------------</font>
spaces <font color=Red>::</font> Parser <font color=Cyan>(</font><font color=Cyan>)</font>
<a name="spaces"></a>spaces <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>many1 <font color=Cyan>(</font>sat isSpace<font color=Cyan>)</font><font color=Cyan>;</font> return <font color=Cyan>(</font><font color=Cyan>)</font><font color=Cyan>}</font>
comment <font color=Red>::</font> Parser <font color=Cyan>(</font><font color=Cyan>)</font>
<font color=Blue>--comment = do {string "--"; many (sat (\x -> x /= '\n')); return ()}</font>
<font color=Blue>--comment = do </font>
<font color=Blue>-- _ <- string "--"</font>
<font color=Blue>-- _ <- many (sat (\x -> x /= '\n'))</font>
<font color=Blue>-- return ()</font>
<a name="comment"></a>comment <font color=Red>=</font> <font color=Green><u>do</u></font>
bracket <font color=Cyan>(</font>string <font color=Magenta>"/*"</font><font color=Cyan>)</font> <font color=Cyan>(</font>many item<font color=Cyan>)</font> <font color=Cyan>(</font>string <font color=Magenta>"*/"</font><font color=Cyan>)</font>
return <font color=Cyan>(</font><font color=Cyan>)</font>
junk <font color=Red>::</font> Parser <font color=Cyan>(</font><font color=Cyan>)</font>
<a name="junk"></a>junk <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>many <font color=Cyan>(</font>spaces <font color=Cyan>+++</font> comment<font color=Cyan>)</font><font color=Cyan>;</font> return <font color=Cyan>(</font><font color=Cyan>)</font><font color=Cyan>}</font>
skip <font color=Red>::</font> Parser a <font color=Red>-></font> Parser a
<a name="skip"></a>skip p <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>junk<font color=Cyan>;</font> p<font color=Cyan>}</font>
token <font color=Red>::</font> Parser a <font color=Red>-></font> Parser a
<a name="token"></a>token p <font color=Red>=</font> <font color=Green><u>do</u></font> <font color=Cyan>{</font>v <font color=Red><-</font> p<font color=Cyan>;</font> junk<font color=Cyan>;</font> return v<font color=Cyan>}</font>
<font color=Blue>-- ------------------------------------------------------------</font>
<font color=Blue>-- * Token parsers</font>
<font color=Blue>-- ------------------------------------------------------------</font>
natural <font color=Red>::</font> Parser Int
<a name="natural"></a>natural <font color=Red>=</font> token nat
integer <font color=Red>::</font> Parser Int
<a name="integer"></a>integer <font color=Red>=</font> token int
symbol <font color=Red>::</font> String <font color=Red>-></font> Parser String
<a name="symbol"></a>symbol xs <font color=Red>=</font> token <font color=Cyan>(</font>string xs<font color=Cyan>)</font>
identifier <font color=Red>::</font> <font color=Red>[</font>String<font color=Red>]</font> <font color=Red>-></font> Parser String
<a name="identifier"></a>identifier ks <font color=Red>=</font> token <font color=Cyan>(</font><font color=Green><u>do</u></font> <font color=Cyan>{</font>x <font color=Red><-</font> ident<font color=Cyan>;</font>
<font color=Green><u>if</u></font> not <font color=Cyan>(</font>elem x ks<font color=Cyan>)</font> <font color=Green><u>then</u></font> return x
<font color=Green><u>else</u></font> return mzero<font color=Cyan>}</font><font color=Cyan>)</font>
<font color=Blue>------------------------------------------------------------------------------</font>
</pre>