Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Consuming Rule Based Parsing (Christopher Howard)
2. Re: Consuming Rule Based Parsing (Karl Voelker)
3. Re: Consuming Rule Based Parsing (Christopher Howard)
4. Re: Consuming Rule Based Parsing (Karl Voelker)
----------------------------------------------------------------------
Message: 1
Date: Fri, 16 Nov 2012 16:13:17 -0900
From: Christopher Howard <[email protected]>
Subject: Re: [Haskell-beginners] Consuming Rule Based Parsing
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On 11/16/2012 12:55 AM, Karl Voelker wrote:
>
>
> There is an approach called "parser combinators". The basic idea is this:
>
> type Parser a = String -> [(a, String)]
>
> In other words, a parser of values of type "a" is a function which takes
> a string and returns all possible parses of some prefix of that string
> as an "a"-value, each paired with whatever input was left after parsing.
>
> You can then start writing functions to combine parsers. Thus, you end
> up with "parser combinators".
>
> There is a library called Parsec which is the industrial-strength
> incarnation of the parser combinator concept. But I would recommend that
> you start by getting familiar with a home-grown parser combinator
> library of your own.
>
> -Karl
Thank you for your help. Can you elaborate a little more on your
explanation? So, would "a" be some data type representing the atoms of
the grammar? Or some kind of recursive data type that could represent
any kind of valid structure? Or...?
I'll wait until I'm clear on that point before asking about how I would
combine parsers. (Presumably, two combined parsers would both have to
have the same "a" type.)
--
frigidcode.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 551 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121116/b56054c9/attachment-0001.pgp>
------------------------------
Message: 2
Date: Fri, 16 Nov 2012 19:04:45 -0800
From: Karl Voelker <[email protected]>
Subject: Re: [Haskell-beginners] Consuming Rule Based Parsing
To: Christopher Howard <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CAFfow0zN1tOiMHq=SKXAh4F=rrbpf8mgbehx1mb8wtfm_om...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Fri, Nov 16, 2012 at 5:13 PM, Christopher Howard <
[email protected]> wrote:
> Thank you for your help. Can you elaborate a little more on your
> explanation? So, would "a" be some data type representing the atoms of
> the grammar? Or some kind of recursive data type that could represent
> any kind of valid structure? Or...?
>
The type parameter "a" is the output of that particular parser. So, a
parser for an integer might have type String -> Integer, while a parser for
some complicated data type Foo would have type String -> Foo.
I'll wait until I'm clear on that point before asking about how I would
> combine parsers. (Presumably, two combined parsers would both have to
> have the same "a" type.)
>
Since the parsers in this scheme are just functions, there are endless ways
they could be combined, and the input and output types may or may not match.
Some combinators you will probably want:
andThen :: Parser a -> (a -> Parser b) -> Parser b
orElse :: Parser a -> Parser a -> Parser a
And you might also want:
succeedWith :: a -> Parser a
-Karl
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121116/3b4cdc80/attachment-0001.htm>
------------------------------
Message: 3
Date: Fri, 16 Nov 2012 18:53:50 -0900
From: Christopher Howard <[email protected]>
Subject: Re: [Haskell-beginners] Consuming Rule Based Parsing
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On 11/16/2012 06:04 PM, Karl Voelker wrote:
> On Fri, Nov 16, 2012 at 5:13 PM, Christopher Howard
> <[email protected]
> <mailto:[email protected]>> wrote:
>
> Thank you for your help. Can you elaborate a little more on your
> explanation? So, would "a" be some data type representing the atoms of
> the grammar? Or some kind of recursive data type that could represent
> any kind of valid structure? Or...?
>
>
> The type parameter "a" is the output of that particular parser. So, a
> parser for an integer might have type String -> Integer, while a parser
> for some complicated data type Foo would have type String -> Foo.
>
> I'll wait until I'm clear on that point before asking about how I would
> combine parsers. (Presumably, two combined parsers would both have to
> have the same "a" type.)
>
>
> Since the parsers in this scheme are just functions, there are endless
> ways they could be combined, and the input and output types may or may
> not match.
>
> Some combinators you will probably want:
>
> andThen :: Parser a -> (a -> Parser b) -> Parser b
> orElse :: Parser a -> Parser a -> Parser a
>
> And you might also want:
>
> succeedWith :: a -> Parser a
>
> -Karl
Maybe I'm thinking about this all wrong... But it isn't quite clear to
me how I make a generic function or operator that combines two Parsers
of one (or two) types to make another Parser of a separate type. Say,
for instance, I have a grammar which consists of atomic Nouns, atomic
Verbs, and Sentences which are a combination of the two. So naturally
I'd expect to have something like:
data Noun = Noun String
data Verb = Verb String
data Sentence = Sentence Noun Verb
nounParser :: Parser Noun
nounParser = ...
verbParser :: Parser Verb
verbParser = ...
sentenceParser :: Parser Sentence
sentenceParser = nounParser <+> verbParser
(<+>) :: ?
(<+>) f g = ?
--
frigidcode.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 551 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121116/93fd193f/attachment-0001.pgp>
------------------------------
Message: 4
Date: Fri, 16 Nov 2012 20:03:51 -0800
From: Karl Voelker <[email protected]>
Subject: Re: [Haskell-beginners] Consuming Rule Based Parsing
To: Christopher Howard <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CAFfow0ykVcR7UoKVzzVCv8FyWi=YVCDcZX=sqodqbte7gtn...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Fri, Nov 16, 2012 at 7:53 PM, Christopher Howard <
[email protected]> wrote:
> data Noun = Noun String
> data Verb = Verb String
> data Sentence = Sentence Noun Verb
>
> nounParser :: Parser Noun
> nounParser = ...
>
> verbParser :: Parser Verb
> verbParser = ...
>
This is a good example to start with.
> sentenceParser :: Parser Sentence
> sentenceParser = nounParser <+> verbParser
>
> (<+>) :: ?
> (<+>) f g = ?
Based on the types of nounParser, verbParser, and sentenceParser, we can
infer that:
(<+>) :: Parser Noun -> Parser Verb -> Parser Sentence
But I suspect you were hoping that <+> would be more general-purpose. The
combinator you want is the one I previously called "andThen":
andThen :: Parser a -> (a -> Parser b) -> Parser b
Which you could use like this:
sentenceParser = nounParser `andThen` (\noun -> verbParser `andThen` (\verb
-> succeedWith (Sentence noun verb)))
Notice that the difference between your <+> and my andThen is that andThen
requires the caller to provide the function that combines the two inputs
into one output. This is what keeps it general.
Now for a slight digression:
If this looks frustratingly verbose, that's because it is. But if you make
Parser into a monad (where return is succeedWith and >>= is andThen), you
can use the syntactic sugar that is "do notation":
sentenceParser = do
noun <- nounParser
verb <- verbParser
return (Sentence noun verb)
-Karl
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121116/72ecfd3e/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 21
*****************************************
