uu-parsinglib parsing with conditional fail

Question

EDITED for more complete problem:

I'd like to create a parser (I'm using uu-parsinglib) that takes the result of a previous parser, and conditionally fails if the result contains a certain constructor:

I now realise this must be a monadic parser.

I have a grammar which contains non-direct left recursive. Below illustrates the problem, the reality is slightly more convoluted:

data Field = 
       Field_A  A
       Field_B  B
       Field_C  C
       Field_D  String

data A =
       A Prefix String

data B =
       B Prefix String

data C =
       C Prefix String

data Prefix = 
       Prefix Field

Most of the time I'm only interested in Field, and in the interests of minimising backtracking, its best to focus on that case.

I've defined an operator to help

(<..>) :: IsParser p => p (a -> b) -> p (b -> c) -> p (a -> c)
g <..> f = (.) <$> f <*> g

And I approach the problem as:

pField :: Parser Field 
pField =  
   ( Field_D <$> pString ) <??>
   pChainl' ( pReturn (helper) <*> pPrefix' ) ( pA' <<|> pB' <<|> pC' )
   where pChainl' :: IsParser p =>  p (f -> (pre -> f) -> f) -> 
                                       p (pre -> f) -> 
                                       p (f -> f)
         pChainl' op x = must_be_non_empties "pChainl'" op x (
                            flip f <$> pList1 (flip <$> op <*> x)
                         )
         f x [] = x
         f x (func:rest) = f (func x) rest
         helper :: (Field -> Prefix) -> 
                      Field -> 
                      (Prefix -> Field) -> 
                      Field
         helper p i n = n $ p i

Note I've defined a variant of pChainl that allows the initial field to be passed in, whilst keeping left association.

pA' :: Parser (Prefix -> Field)
pA' = ( (flip A) <$> pString ) <..> pReturn Field_A

pB' :: Parser (Prefix -> Field)
pB' = ( (flip B) <$> pString ) <..> pReturn Field_B

pC' :: Parser (Prefix -> Field)
pC' = ( (flip C) <$> pString ) <..> pReturn Field_C

-- This consumes no input
pPrefix' :: Parser (Field -> Prefix)
pPrefix' = pReturn Prefix

The question I'd like to define

pA :: Parser A

in terms of pField, with a post filter to fail if the rightmost Field constructor is not Field_A. As has rightly been pointed out, this is a monadic parse. I can't find any compelling examples of using uu-parsinglib as a monadic parser, so what would your suggested approach be?

If I'm barking up the wrong tree, please let me know also.

Answer 1

It seems like you could make a generalized conditional parser that only succeeds if the value returned by the parser passes some test. This uses the monad capabilities of course. I am not sure if this is a good thing to do with uu-parsinglib however. It seems to work fine in my testing, with one exception: when the conditional fails and no other parsers are available to consume input, the library throws an exception. (something along the lines of no correcting steps given...)

pConditional :: Parser a -> (a -> Bool) -> Parser a
pConditional p test = p >>= (\result -> case (test result) of
    True -> pure result
    False -> empty)

I would also like to know of other pitfalls that would arise from liberal use of such a conditional parser. (if any.)

Answer 2

I think I've found a solution. I'm still interested in hearing thoughts on the best way to parse such indirect left recursion.

The proposed solution is

pA :: Parser A
pA = do
   a <- pField
   case a of 
      (Field_A r) -> return r
      otherwise   -> pFail