Parser Combinators FAQ
I am not interested in error correction, and want to stop parsing as soon as I encounter an error.
The parser produces a list of error messages; if you only print the first message on this list and do not force the evaluation of the parser in some other way (e.g. by asking how many errors there are in total), your parser will just stop at this first error, and hopefully with a good suggestion.
My parsing times are getting very large
Most likely you have an ambiguous grammar. For each ambiguous element the parsing time for the rest of the program doubles, quickly leading to exponential parsing times. Experience has shown that it is not always a trivial transformation to make your original grammar one that is not left-recursive. It is easy to make a mistake here. (see also the next question)
How can I choose one of the alternatives in case a grammar is ambiguous
It may be the case that you have several alternatives that are overlapping, and in that case you want to give preference to one of them. There is a function pCost
that can be of help here. A typical example is if you use the combinators to define a scanner and you want to parse an identifier, but some of those identifiers are to be interpreted as keywords. The trick now is to append a small step with low cost to the end of the identifier, that makes that alternative a bit more expensive, and thus gives preference to the other alternative. In order to be more robust if we have an erroneaous input immediately after we have added costs to both alternatives in the example.
In the contenxt of:
pChar = 'a' <..> 'z'
pIdent = pList pChar
if_as_ident = ((("This is the identifier: ") ++) <$> pIdent)
if_as_keyword = ((("This is the keyword: ") ++) <$> pToks "if")
*Examples> test (if_as_ident <* pCost 2 <|> if_as_keyword <* pCost 1) "if"
"This is the keyword: if"
How can I debug my parser
The parser maintains an input state. probably the easiest way to find out what your parser is actually doing is to change the functions splitInput
, which construct the next token from the input. If you do not have a problem you will see each token being asked for twice.
module Test where
data Tracing s = Tracing [s]
instance Show s => InputState (Tracing s) s (Maybe s) where
splitStateE (Tracing ) = Right' (Tracing )
splitStateE (Tracing (s:ss)) = trace ("Inspecting " ++ show s ++ "\n") (Left' s (Tracing ss))
splitState (Tracing (s:ss)) = trace ("Inspecting " ++ show s ++ "\n") ( s, Tracing ss)
getPosition (Tracing ) = Nothing
getPosition (Tracing (s:ss)) = Just s
-- parseIO' :: (Eq s, Show s, Symbol s) => Parser s a -> Tracing s -> IO a
parseIO' = parseIOMessage showMessage
where showMessage (Msg expecting position action)
= let pos = case position of
Nothing -> "at end of file"
Just s -> case action of
Insert _ -> "before " ++ show s
Delete t -> "at " ++ show t
in "\n?? Error : " ++ pos ++
"\n?? Expecting : " ++ show expecting ++
"\n?? Repaired by: " ++ show action ++ "\n"
a = pSym 'a'
b = pSym 'b'
c = pSym 'c'
ab = (\ a b -> [a,b]) <$> a <*> b
bc = (\ b c -> [b,c]) <$> b <*> c
abc = (:) <$> a <*> bc
abc' = (\ ab c -> ab ++ [c]) <$> ab <*> c
test = parseIO' (abc <|> abc') (Tracing "abc")
As you can see every character (except the 'a'
on which the parser forks) shows up 4 times now, indicating that you have two alternative parses:
- 19 Jan 2007