<html><head></head><body>Have you seen uu-parsinglib (<a href="http://foswiki.cs.uu.nl/foswiki/HUT/ParserCombinators">http://foswiki.cs.uu.nl/foswiki/HUT/ParserCombinators</a>)? It implements a non-backtracking parser that works similarly to what you describe.<br><br><div class="gmail_quote">On 9 March 2017 01:21:09 GMT+01:00, Javran Cheng <javran.c@gmail.com> wrote:<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div dir="ltr"><div><div><div><div><div><div><div><div><div>Hi all,<br /><br /></div><div>I come across an idea about parsing a bunch of strings,<br />just want to share this idea and looking for some comments and maybe pointing me to some related articles.<br /><br />The idea is when you have:<br /></div><br /></div>1 <$ string "aabb" <|> 2 <$ string "aacc"<br /><br /></div>you can rewrite it as:<br /><br /></div>string "aa" >> (1 <$ string "bb" <|> 2 <$ string "cc")<br /><br /></div>so that you don't have to deal with the common prefix "aa" twice.<br /><br /></div>Then I further extend this idea: if we have a set of strings (s1, s2, ...), whose element is not a prefix of any other set member,<br /></div>why don't we turn things like (v1 <$ string s1 <|> v2 <$ string s2 <|> ...) into a "tree-structure" so we don't need to deal with<br /></div>any common prefix more than once?<br /><br />So this motivates my little toy implementation at <a href="https://gist.github.com/Javran/1cbfe9897d9a5c8fae5d20a33fd83813">https://gist.github.com/Javran/1cbfe9897d9a5c8fae5d20a33fd83813</a><br /><br /></div>basically given a list [(s1,v1),(s2,v2)...], we want to generate a parser equivalent to (v1 <$ string s1 <|> v2 <$ string s2 <|> ...)<div><div>but perhaps with less backtracking. My code does this by turning the set of strings into a tree structure (see function "compact") and<br />using this "Compact" representation as a driver to generate the parser.<br />I used ReadP to have a concrete parser for testing, but this should work with any parsing library supporting MonadPlus.<br /><br /></div><div><div><div><div><div><div><div><div>I think they are bunch of things that can be improved:<br /></div><div><div><div><div><div><br />- for now every intermediate node of "Compact" contains just a char, so this will end up generating a parser that has branch `char 'f' >> char 'o' >> 'o'` in it<br /> instead of the slightly more efficient version `string "foo"`<br /></div><div>- we could further attach a weight to each string, this allows rearranging (<|>) chains so that a more frequent string parser appears earlier.<br /></div><div>- if the input [(s1,v1),(s2,v2)...] are all known constants at compile time, probably TemplateHaskell can be used for generating the parser at compile time (as a Haskell expression).<br /></div><div> I'm not sure how difficult this would be though, as I have very limited understanding of TH.<br /><br /></div><div>but before I explore further, I want to collect some comments as I said in the beginning.<br /></div><div><br /></div><div>Best,<br /></div><div>-- <br /><div class="gmail_signature"><div dir="ltr">Javran (Fang) Cheng<br /></div></div>
</div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div><br>
-- <br>
Sent from my Android device with K-9 Mail. Please excuse my brevity.</body></html>