Non Greedy Parsing

NonGreedy.hs

import Control.Monad
import Text.Parsec

testString = unlines [
                      "foo {",
                      "  contents of foo",
                      "  a stray }",
                      "}",
                      "bar {",
                      "}"
                     ]

naiveP = many $ do
  name <- many alphaNum
  space
  char '{'
  body <- many anyChar
  char '}'
  return (name,body)

naiveTest = parseTest naiveP testString

untilP keepGoing stop = go []
  where
    go accum =
      (try $ do
        e <- stop
        return (accum, e)
      )
      <|>
      (do
        u <- keepGoing
        go (accum ++ [u]))

backtrackingP = do
  name <- many alphaNum
  space
  char '{'
  (body, rest) <- untilP anyChar $ do
                    char '}'
                    endOfLine
                    (<|>) (try backtrackingP)
                          (try $ do
                               eof
                               return [])
  return $ [(name, body)] ++ rest

backtrackingTest = parseTest backtrackingP testString

{-
*Main> naiveTest
parse error at (line 7, column 1):
unexpected end of input
expecting "}"
*Main> backtrackingTest
[("foo","\n  contents of foo\n  a stray }\n"),("bar","\n")]
-}

Here is what I came up with (in applicative interface)

naiveP2 = many $
    (,) <$> (many1 alphaNum) <*> (space *> char '{' *> manyTill anyChar (try ending))
  where
   ending = endOfLine *> char '}' *> endOfLine

block_parser = do
  name <- many alphaNum
  space
  char '{'
  body <- manyTill anyChar $ try next
  return $ (name, body)
  where
    next = do
      char '}'
      endOfLine
      lookAhead (block_parser >> return ()) <|> eof

The tricky part is to permit ending character inside the block. We could use the info from lookAhead to mimic greedy parsing. Hope I get it right.