Implementing try (look-ahead) and untilStop with parser combinators

Question

I am following this tutorial for implementing Parser Combinators (a la parsec) in Haskell. I implemented everything of the NanoParsec mentioned throught this post.

For some hours now, I am struggeling to implement

-- try p. If p fails continue without consuming anything
try :: Parser a -> Parser a
try p = ...

-- Parser for everything, until the character-sequence stop appears. 
-- If stop does not appear at all: fail
untilStop :: String -> Parser String
untilStop stop = ...

My best attempt to implement untilStop looks like somewhat like this and does not quite work

untilStop :: String -> Parser String
untilStop (c : cs) = do
  s <- some $ satisfy (/= d)
  string (c : cs) <|> do
    i <- item
    untilStop (d : ds)
  -- maybe use msum from MonadPlus to combine?

I could not figure out how to combine s, i and the recursive call without failing everthing because of string are not getting everything together.

I think once I have try, untilStop should be straightforward. Can someone point me in the right direction or implement it (try) for me?

Right now I am still learning about Monads, Applicative and related stuff so trying to understand the sourcecode of parsec was impossible for me.

You don't need try for this simple parser library. p <|> q already behaves like try p <|> q. Am I right? — Euge
Well <|> :: Parser a -> Parser a -> Parser a needs an alternative to my tried option. I was hoping for something I can just try and if it fails, do nothing and just move onto the next statement in my do notation. — elfeck

Euge Euge · Accepted Answer · 2017-01-01T15:21:52

As I said in a comment, I think you don't need to have a Parsec-like try.

For the untilStop, check this:

untilStop :: String -> Parser String
untilStop [] = everything
untilStop (c:cs) = item >>= fun
  where fun i = do { s <- untilStop cs;
                     if i == c && s == "" then return "" else failure } <|> do
                     s <- untilStop (c : cs)
                     return (i : s)

First, if the stop string is empty, you parse everything. Where everything is:

everything :: Parser String
everything = Parser (\inp -> [(inp,"")])

Otherwise, if it is of the form c:cs, then parse a character i and consider two cases:

The stop string is right in the front of the parsing stream (because c == i and parsing with the rest of the string cs gives an empty result), then return "". Or,
It is somewhere in the stream, so you look for it further.

Note that the <|> operator is used to backtrack. If untilStop cs fails to be what we want, we need to reparse, using untilStop (c:cs) instead.

Implementing try (look-ahead) and untilStop with parser combinators

1 Answers