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. Consuming Rule Based Parsing (Christopher Howard)
2. Re: Consuming Rule Based Parsing (Karl Voelker)
----------------------------------------------------------------------
Message: 1
Date: Thu, 15 Nov 2012 23:55:39 -0900
From: Christopher Howard <[email protected]>
Subject: [Haskell-beginners] Consuming Rule Based Parsing
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I haven't learned anything substantive yet regarding Haskell approaches
to parsing, so I would appreciate any pointers towards appropriate
modules, abstractions, tutorials, or such like.
Specifically: For a particular application, I want to play around with a
rules (grammer) based parsing which consumes an incoming data stream.
That is, I'm not parsing a single type of document with a set structure.
Rather, the idea is that I have a list of symbols (characters, numbers,
whatever) and pattern match the front part of the list according to some
(grammer) rule (which itself could be a conjunction or disjunction of
rules) in a set of rules. If the match succeeds, then I consume that
part of the list, and then analyze the remaining list, starting again
with the first rule in my rule set. If the match fails, then I try the
next rule in my rule set. (Sort of like Prolog's context free grammars
and difference lists.) Backtracking would also be cool (to see what
other results I can get).
Is there a particular Haskell abstraction or system suitable for what I
have described?
--
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/20121115/4838762b/attachment-0001.pgp>
------------------------------
Message: 2
Date: Fri, 16 Nov 2012 01:55:12 -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:
<caffow0yrollbf8psmaxcqo7n3s46n5wjrymrvj-0mghy9bg...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Fri, Nov 16, 2012 at 12:55 AM, Christopher Howard <
[email protected]> wrote:
> That is, I'm not parsing a single type of document with a set structure.
>
I think you are. See below.
> Rather, the idea is that I have a list of symbols (characters, numbers,
> whatever) and pattern match the front part of the list according to some
> (grammer) rule (which itself could be a conjunction or disjunction of
> rules) in a set of rules. If the match succeeds, then I consume that
> part of the list, and then analyze the remaining list, starting again
> with the first rule in my rule set. If the match fails, then I try the
> next rule in my rule set.
If the things which can appear on the stream have grammars A, B, and C,
then you can describe the grammar of the stream as a whole by:
S -> (A | B | C)*
So you are still just parsing an S document.
> Backtracking would also be cool (to see what
> other results I can get).
>
Unregulated backtracking tends to produce slow parsers. And for a
reasonably thought-out grammar, backtracking is not usually necessary. But
it can be done.
> Is there a particular Haskell abstraction or system suitable for what I
> have described?
>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121116/69de4a37/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 20
*****************************************
