<div dir="ltr">Hi Jaro, thanks for the link, having worked with few parsing libs but uu-parsinglib sounds new to me and I'm definitely thinking about having a try.<br>I'm taking a look but haven't yet found any part of code that attempts to factor common prefixes out.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 8, 2017 at 7:48 PM, Jaro <span dir="ltr"><<a href="mailto:noughtmare@openmailbox.org" target="_blank">noughtmare@openmailbox.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>Have you seen uu-parsinglib (<a href="http://foswiki.cs.uu.nl/foswiki/HUT/ParserCombinators" target="_blank">http://foswiki.cs.uu.nl/<wbr>foswiki/HUT/ParserCombinators</a>)<wbr>? It implements a non-backtracking parser that works similarly to what you describe.<div><div class="h5"><br><br><div class="gmail_quote">On 9 March 2017 01:21:09 GMT+01:00, Javran Cheng <<a href="mailto:javran.c@gmail.com" target="_blank">javran.c@gmail.com</a>> 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" target="_blank">https://gist.github.com/<wbr>Javran/<wbr>1cbfe9897d9a5c8fae5d20a33fd838<wbr>13</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="m_6210124524388714078gmail_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></div></div><span class="HOEnZb"><font color="#888888">
-- <br>
Sent from my Android device with K-9 Mail. Please excuse my brevity.</font></span></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Javran (Fang) Cheng<br></div></div>
</div>