<html><head></head><body>After thinking about it more (I still don't completely understand uu-parsinglib myself). I think achieves non-backtracking by running the parsers in parallel and then returning the first one that succeeds. So I guess it doesn't really optimize away prefixes. The 'best' function is the function that merges two "sequences" of the intermediate type 'Steps a' and that causes the parsers to be run in parallel. The source is here: <a href="https://hackage.haskell.org/package/uu-parsinglib-2.9.1.1/docs/src/Text-ParserCombinators-UU-Core.html#best.">https://hackage.haskell.org/package/uu-parsinglib-2.9.1.1/docs/src/Text-ParserCombinators-UU-Core.html#best.</a><br><br><div class="gmail_quote">On 9 March 2017 03:41:30 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">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" /></div></blockquote></div><br>
-- <br>
Sent from my Android device with K-9 Mail. Please excuse my brevity.</body></html>