[Haskell-cafe] Parsing workflow

Stephen Tetley stephen.tetley at gmail.com
Sun Oct 31 16:21:37 EDT 2010

On 31 October 2010 16:53, Nils Schweinsberg <ml at n-sch.de> wrote:
> Am 31.10.2010 17:27, schrieb Stephen Tetley:
>> Left factoring! :-)
> Stupid question: Whats that? :)

Actually a good question...

Its a standard grammar transformation - if you have two alternative
productions that share a common prefix

A -> a b
   | a c

Left factoring produces:

A -> A_part (b | c)
A_part -> a

Left factoring can quickly lead to the grammar getting quite
convoluted, but using 'try' can lead to very fragile parsers that stop
working in mysterious ways when you extend them.

Because parser combinators are just functions, you can do questionable
hacks to make left factoring a bit less tedious:

parseA :: Parser A
parseA = do
   a <- a_part
   (parseB a <|> parseC a)

parseB :: a -> Parser A
parseB a = do
  b <- b_part
  return $ B a b

parseC :: b -> Parser A
parseC a = do
  c <- c_part
  return $ C a c

More information about the Haskell-Cafe mailing list