<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>