[Haskell-cafe] Alternative instance for non-backtracking parsers
Paul
aquagnu at gmail.com
Fri Aug 24 12:31:29 UTC 2018
> behaviours are surprising, it's because there is a lack of
understanding of the tool, and not an issue with the tool itself.
Hello, Issac. Yes, it will be the most correct statement :)
>
> Also, trifecta has the same backtracking semantics as megaparsec.
>
> On Fri, Aug 24, 2018 at 8:10 PM Paul <aquagnu at gmail.com
> <mailto:aquagnu at gmail.com>> wrote:
>
> may be because I always hit similar problems and needs different
> tricks
> with them, so I an not sure that parser combinators are good
> solution.
> Btw, usually I use standard parser combinator which is related to GHC
> itself (in the 'base' package), so I'm not sure how all those P.C.
> libraries are similar (may be MegaParsec has different behavior). But
> it's my IMHO: I'm not sure that P.C. libraries are good for serious
> parsing tasks: you should be concentrated on the task and not to
> spend
> time in solving of such surprises like that.
>
> Btw, some time ago I found this list of libs
> https://www.reddit.com/r/haskell/comments/46u45o/what_is_the_current_state_of_parser_libraries_in/
>
> and Trifecta looks interesting but I did not try it
>
>
> 24.08.2018 12:44, Doaitse Swierstra wrote:
> >
> >> Op 24 aug. 2018, om 7:33 heeft Paul <aquagnu at gmail.com
> <mailto:aquagnu at gmail.com>> het volgende geschreven:
> >>
> >>> Of course the example above can be mitigated by moving the
> char '-' outside the alternative.
> >> Right, this works fine:
> >>
> >> pq :: Parsec Void String Bool
> >> pq = do
> >> char '-'
> >> (q <|> p)
> >>
> >> which for me, means that Haskell has not real backtracking.
> > You are confusing the language “Haskell” with the library
> “Parsec”. Parsec is just one of the many parser combinator libraries.
> >
> >> Btw, `Alternative` is not backtracking (as well as List
> permutations).
> > The class “Alternative” does in no way specify how parsers
> should behave; it defines an interface. One might expect <|> to be
> associative, but even that is in no way guaranteed.
> >
> >> After "do" should happen context saving. I think it's possible
> to be implemented manually... As workaround, may be to pick char
> '-', but don't consume it (and to fail if it is not expecting '-')
> ? Or to switch to another parser libs: arrow based, happy,
> bindings to good known libs... For me, parsers combinators
> absolutely ever are big problem: a lot of tricks, low performance,
> may be it's typical for any "elegant" approach.
> > - Some libraries do not need “try” constructs to set backtrack
> points, but may be a bit slower; other libraries are more greedy
> and a bit faster.
> > - Some parsers keep track of where you are in the input at
> some cost, others just parse as fast as possible without having to
> update line and position counters (handy when you know the input
> is correct since it was machine-generated).
> > - Some libraries provide nice error messages about what was
> expected at some cost, other libraries just report that they did
> not find a parse.
> > - Some libraries try to “repair” the input and continue
> parsing when they cannot proceed otherwise, some others just stop
> when they get stuck.
> > - Some libraries hang on to the input so they may backtrack to
> a point far back, some libraries work in an online way and pursue
> all parses “in parallel”, i.e. they perform a breadth first search
> for a successful parse.
> > - Some libraries analyse the grammar before parsing starts and
> warn for non-sensical parsers, others just do not.
> > - Some libraries already return part of the computed result
> during the parsing process -and thus exhibit online behaviour-,
> other libraries (usually the monadic ones) construct a huge
> closure describing the result, which only becomes available when a
> succesful parse was found.
> > - Some libraries analyse a grammar for left-recursion and
> transform them into an equivalent non-left-recusrive one at some
> costs.
> > - Some libraries memoise the parsing, and may be faster, but
> in return cannot handle real monadic constructs.
> > - Etc., Etc.
> >
> > My impression is that with respect to parser combinators you
> just jump a bit too fast to a conclusion.
> >
> > Doaitse
> >
> >
> >>
> >> 23.08.2018 22:41, Olaf Klinke wrote:
> >>> Dear Cafe,
> >>>
> >>> can anyone explain the use of an Alternative instance for a
> parser monad where the parser (p <|> q) does not backtrack
> automatically when p fails?
> >>> Consider megaparsec for example. When p is a parser that does
> not backtrack automatically, then (p <|> q) never succeeds with q.
> While I do understand that fine-grained control of backtracking is
> desirable for performance reasons in general, it escapes me why
> such an Alternative instance could be useful. See also "A note on
> backtracking" in the parser-combinators package documentation [1].
> >>>
> >>> Minimal code example and context below.
> >>>
> >>> Thanks,
> >>> Olaf
> >>>
> >>> [1]
> http://hackage.haskell.org/package/parser-combinators-1.0.0/docs/Control-Applicative-Combinators.html
> >>>
> >>> import Text.Megaparsec
> >>> import Text.Megaparsec.Char
> >>> import Data.Void
> >>>
> >>> p :: Parsec Void String Bool
> >>> p = do
> >>> char '-'
> >>> string "True"
> >>> return True
> >>> q :: Parsec Void String Bool
> >>> q = do
> >>> char '-'
> >>> string "False"
> >>> return False
> >>>
> >>>>>> parseTest (p <|> q) "-True"
> >>> True
> >>>>>> parseTest (p <|> q) "-False"
> >>> 1:2:
> >>> unexpected "Fals"
> >>> expecting "True"
> >>> -- Since q can parse "-False", I would expect (p <|> q) to
> parse "-False", too.
> >>>
> >>> Context:
> >>> Of course the example above can be mitigated by moving the
> char '-' outside the alternative. But we might not have control
> over whether the two parsers share a common prefix. I am trying to
> write some code generic in the parser monad and I am having
> difficulties making my code work for both backtracking and
> non-backtracking parsers. If possible, I'd like to keep my parser
> type class devoid of a 'try' combinator, which would be the
> identity function for parser monads that always backtrack.
> >>> _______________________________________________
> >>> Haskell-Cafe mailing list
> >>> To (un)subscribe, modify options or view archives go to:
> >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> >>> Only members subscribed via the mailman list are allowed to post.
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> To (un)subscribe, modify options or view archives go to:
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> >> Only members subscribed via the mailman list are allowed to post.
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180824/b4898126/attachment.html>
More information about the Haskell-Cafe
mailing list