[Haskell-cafe] Parsing a bunch of strings without backtracking
javran.c at gmail.com
Thu Mar 9 00:21:09 UTC 2017
I come across an idea about parsing a bunch of strings,
just want to share this idea and looking for some comments and maybe
pointing me to some related articles.
The idea is when you have:
1 <$ string "aabb" <|> 2 <$ string "aacc"
you can rewrite it as:
string "aa" >> (1 <$ string "bb" <|> 2 <$ string "cc")
so that you don't have to deal with the common prefix "aa" twice.
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,
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
any common prefix more than once?
So this motivates my little toy implementation at
basically given a list [(s1,v1),(s2,v2)...], we want to generate a parser
equivalent to (v1 <$ string s1 <|> v2 <$ string s2 <|> ...)
but perhaps with less backtracking. My code does this by turning the set of
strings into a tree structure (see function "compact") and
using this "Compact" representation as a driver to generate the parser.
I used ReadP to have a concrete parser for testing, but this should work
with any parsing library supporting MonadPlus.
I think they are bunch of things that can be improved:
- 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
instead of the slightly more efficient version `string "foo"`
- we could further attach a weight to each string, this allows rearranging
(<|>) chains so that a more frequent string parser appears earlier.
- 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).
I'm not sure how difficult this would be though, as I have very limited
understanding of TH.
but before I explore further, I want to collect some comments as I said in
Javran (Fang) Cheng
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe