On Fri, Nov 16, 2012 at 12:55 AM, Christopher Howard <span dir="ltr">&lt;<a href="mailto:christopher.howard@frigidcode.com" target="_blank">christopher.howard@frigidcode.com</a>&gt;</span> wrote:<br><div class="gmail_extra">
<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">That is, I&#39;m not parsing a single type of document with a set structure.<br></blockquote><div>
<br></div><div>I think you are. See below.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Rather, the idea is that I have a list of symbols (characters, numbers,<br>
whatever) and pattern match the front part of the list according to some<br>
(grammer) rule (which itself could be a conjunction or disjunction of<br>
rules) in a set of rules. If the match succeeds, then I consume that<br>
part of the list, and then analyze the remaining list, starting again<br>
with the first rule in my rule set. If the match fails, then I try the<br>
next rule in my rule set.</blockquote><div><br></div><div>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:</div><div><br></div><div>S -&gt; (A | B | C)*</div>
<div><br></div><div>So you are still just parsing an S document.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Backtracking would also be cool (to see what<br>

other results I can get).<br></blockquote><div><br></div><div>Unregulated backtracking tends to produce slow parsers. And for a reasonably thought-out grammar, backtracking is not usually necessary. But it can be done.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Is there a particular Haskell abstraction or system suitable for what I<br>
have described?<br></blockquote><div><br></div><div>There is an approach called &quot;parser combinators&quot;. The basic idea is this:</div><div><br></div><div>type Parser a = String -&gt; [(a, String)]</div><div><br></div>
<div>In other words, a parser of values of type &quot;a&quot; is a function which takes a string and returns all possible parses of some prefix of that string as an &quot;a&quot;-value, each paired with whatever input was left after parsing.</div>
<div><br></div><div>You can then start writing functions to combine parsers. Thus, you end up with &quot;parser combinators&quot;.</div><div><br></div><div>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.</div>
<div><br></div><div>-Karl</div></div></div>