Parsec question: attempted 'notMatching' combinator
I've attempted to define a Parsec combinator thus: [[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = try ( do { a <- p ; unexpected (show a) } <|> return () ) ]] It's modelled on the Parsec-provided combinator 'notFollowedBy', but is less fussy about the type of parser allowed. It is an attempt to do a look-ahead. It compiles OK, but it doesn't work as I might expect, e.g. as in: [[ relativeUri :: UriParser URI relativeUri = do { notMatching uscheme ; ua <- option "" ( do { try (string "//") ; uauthority } ) ; up <- upath ; uq <- option "" ( do { string "?" ; uquery } ) ; uf <- option "" ( do { string "#" ; ufragment } ) ; return $ URI { scheme = "" , authority = ua , path = up , query = uq , fragment = uf } } ]] It has the effect of causing several otherwise valid parses to fail. Notably, it is cases that do not match the 'uscheme' parser that fail when they should be matched overall. I *suspect* that the 'try' logic is not interacting cleanly with the case that uscheme parser does not succeed, but I don't have any hard evidence. Can anyone see anything obviously wrong with this? (I have a work-around to the problem, but one that sometimes involves parsing an entire URI twice when trying to isolate relative URIs. I could restructure the code in other ways, but that would defeat my goal of keeping the code very close to the work-in-progress URI specification.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Tue, Feb 17, 2004 at 06:42:39PM +0000, Graham Klyne wrote:
I've attempted to define a Parsec combinator thus:
[[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = try ( do { a <- p ; unexpected (show a) } <|> return () ) ]]
If p fails but consumes some input, return () won't be tried, thus the whole notMatching will have failed. The try means that it will not have consumed any input, but that's no consolation, because notMatching should have succeeded! How about: notMatching p = try ( do { a <- p ; unexpected (show a) } ) <|> return () In fact, I think notFollowedBy can be considered to be buggy in the same way. notFollowedBy p = try (do{ c <- p; unexpected (show [c]) } <|> return () ) It doesn't usually bite, because notFollowedBy takes a parser that returns a token, and such a parser normally only looks at one token. But it could look at more: aNoBC = do char 'a' notFollowedBy $ do char 'b' char 'c' Intutively, (aNoBC >> char 'b') should match "abe", but *Main> parseTest (aNoBC >> char 'b') "abe" parse error at (line 1, column 2): unexpected "e" expecting "c" If you instead put the try around the do, it works as expected. So I conclude that the try simply got put in the wrong place by mistake. Andrew
Thanks! That got me going, though not with quite what you suggested. I ended up with this: [[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = do { a <- try p ; unexpected (show a) } <|> return () ]] which does the required job for me. Using your version caused the notMatching parser to be equivalent to: return () presumably, because the failure was protected by the try combinator? #g -- At 14:29 17/02/04 -0500, Andrew Pimlott wrote:
On Tue, Feb 17, 2004 at 06:42:39PM +0000, Graham Klyne wrote:
I've attempted to define a Parsec combinator thus:
[[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = try ( do { a <- p ; unexpected (show a) } <|> return () ) ]]
If p fails but consumes some input, return () won't be tried, thus the whole notMatching will have failed. The try means that it will not have consumed any input, but that's no consolation, because notMatching should have succeeded! How about:
notMatching p = try ( do { a <- p ; unexpected (show a) } ) <|> return ()
In fact, I think notFollowedBy can be considered to be buggy in the same way.
notFollowedBy p = try (do{ c <- p; unexpected (show [c]) } <|> return () )
It doesn't usually bite, because notFollowedBy takes a parser that returns a token, and such a parser normally only looks at one token. But it could look at more:
aNoBC = do char 'a' notFollowedBy $ do char 'b' char 'c'
Intutively, (aNoBC >> char 'b') should match "abe", but
*Main> parseTest (aNoBC >> char 'b') "abe" parse error at (line 1, column 2): unexpected "e" expecting "c"
If you instead put the try around the do, it works as expected. So I conclude that the try simply got put in the wrong place by mistake.
Andrew
------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Tue, Feb 17, 2004 at 07:48:52PM +0000, Graham Klyne wrote:
Thanks! That got me going, though not with quite what you suggested.
I ended up with this: [[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = do { a <- try p ; unexpected (show a) } <|> return () ]] which does the required job for me.
Oops, that does look better. I knew the try had to go somewhere. :-) The only remaining problem is when p succeeds but does not consume any input, eg eof. In this case, the <|> return () cannot distinguish it from p failing. I didn't realize at first what a dirty trick this function uses: It distinguishes success or failure of p by whether any input from the first part (before <|> return ()) was consumed. I don't think it is possible (or desirable!) to get this approach 100% right: By "erasing" the success of p, you lose the information you need. What about a more prosaic implementation: notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = do res <- do a <- try p; return $ Just a <|> return Nothing case res of Just a -> unexpected (show a) Nothing -> return () This works for the tests I've tried, but there's one little quirk with error reporting: aNoBC = do char 'a' notFollowedBy' $ do char 'b'; char 'c' *Main> parseTest (aNoBC >> char 'e') "abe" parse error at (line 1, column 2): unexpected "e" expecting "c" or "e" It seems that parsec both misreports which token is unexpected (should be "b", and thinks that the failure to match "c" is a problem, even though notFollowedBy' succeeded.
Using your version caused the notMatching parser to be equivalent to: return () presumably, because the failure was protected by the try combinator?
Or perhaps more accurately, the success (of p) was protected by the try! Ie, the unexpected and the try together undid the tell-tale token consumption of p. Andrew
On Tue, Feb 17, 2004 at 04:57:34PM -0500, Andrew Pimlott wrote:
What about a more prosaic implementation:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = do res <- do a <- try p; return $ Just a <|> return Nothing case res of Just a -> unexpected (show a) Nothing -> return ()
After some pondering and fiddling, a version I like: notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = join $ do a <- try p; return (unexpected (show a)) <|> return (return ()) Andrew
On Wed, 18 Feb 2004 01:11:31 -0500, Andrew Pimlott <andrew@pimlott.net> wrote:
After some pondering and fiddling, a version I like:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = join $ do a <- try p; return (unexpected (show a)) <|> return (return ())
Great work. Do you think that the library function should be fixed with this version? (or can you check it in yourself?) -- Daan.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Wed, Feb 18, 2004 at 02:45:15PM +0100, Daan Leijen wrote:
On Wed, 18 Feb 2004 01:11:31 -0500, Andrew Pimlott <andrew@pimlott.net> wrote:
After some pondering and fiddling, a version I like:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = join $ do a <- try p; return (unexpected (show a)) <|> return (return ())
Great work. Do you think that the library function should be fixed with this version? (or can you check it in yourself?)
Thanks! There is one catch: I followed Graham's idea of generalizing the signature (which is orthogonal to my fix). As per earlier mails, the signature of the current notFollowedBy notFollowedBy :: Show tok => GenParser tok st tok -> GenParser tok st () notFollowedBy p = try (do{ c <- p; unexpected (show [c]) } <|> return () ) is rather curious--<TV lawyer>as if the author knew about the problem, and required a parser returning tok so no-one would notice</TV lawyer>. Actually, maybe the reason is error reporting. Graham's "show a" might be confusing (who knows whether a is anything like a representation of the input?). It seems you'd like to grab the Expect message out of p, but I'm not sure if this is possible. Also, in the tok case, there is a small change in the error message (c vs [c]). Even if these are not fixible, they seem to me minor problems compared with the benefit of a more general type. So I'm happy with my version as written. I'm not set up to check it in, so you should probably do it. Don't forget that there is a copy of the code in the documentation. Andrew
On Wed, Feb 18, 2004 at 02:45:15PM +0100, Daan Leijen wrote:
On Wed, 18 Feb 2004 01:11:31 -0500, Andrew Pimlott <andrew@pimlott.net> wrote:
After some pondering and fiddling, a version I like:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = join $ do a <- try p; return (unexpected (show a)) <|> return (return ())
Argh, there is still a problem! When notFollowedBy' fails, it will have consumed whatever p consumed. Stupid example: ab = do char 'a' (notFollowedBy' $ do char 'b'; char 'c') <|> do char 'b'; return () *Main> parseTest ab "abcd" parse error at (line 1, column 4): unexpected 'c' Last version: notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = try $ join $ do a <- try p return (unexpected (show a)) <|> return (return ()) Try, try again, Andrew
Hi, In a local copy of Parsec.Prim I've added a primitive, that may be of help for your problem as well. consumeNothing :: GenParser tok st () consumeNothing = Parser (\state -> Consumed (Ok () state (unknownError state))) With this I've implemented: checkWith :: (Show a) => GenParser tok st a -> (a -> Bool) -> GenParser tok st a p `checkWith` f = do x <- p if f x then return x else consumeNothing >> unexpected (show x) I can't remember, how I've implemented the more general notFollowedBy with this (possibly also wrong). consumeNothing simply pretends to consume something, which may be dangerous when repeated. You might also like: bind :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c bind f p q = do { x <- p; y <- q; return (f x y) } infixl << (<<) :: (Monad m) => m a -> m b -> m a (<<) = bind const followedWith :: GenParser tok st a -> GenParser tok st b -> GenParser tok st a p `followedWith` q = try (p << lookAhead q) Christian Andrew Pimlott wrote:
On Wed, Feb 18, 2004 at 02:45:15PM +0100, Daan Leijen wrote:
On Wed, 18 Feb 2004 01:11:31 -0500, Andrew Pimlott <andrew@pimlott.net> wrote:
After some pondering and fiddling, a version I like:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = join $ do a <- try p; return (unexpected (show a)) <|> return (return ())
Argh, there is still a problem! When notFollowedBy' fails, it will have consumed whatever p consumed. Stupid example:
ab = do char 'a' (notFollowedBy' $ do char 'b'; char 'c') <|> do char 'b'; return ()
*Main> parseTest ab "abcd" parse error at (line 1, column 4): unexpected 'c'
Last version:
notFollowedBy' :: Show a => GenParser tok st a -> GenParser tok st () notFollowedBy' p = try $ join $ do a <- try p return (unexpected (show a)) <|> return (return ())
Try, try again, Andrew _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (4)
-
Andrew Pimlott -
Christian Maeder -
Daan Leijen -
Graham Klyne