[Haskell-cafe] ReadP question

Udo Stenzel u.stenzel at web.de
Thu Aug 31 05:39:03 EDT 2006

Chris Kuklewicz wrote:
> I just tried to mimic regular expression matching with ReadP and got what 
> seems like a non-terminating program.  Is there another way to use ReadP to 
> do this?
> >-- Simulate "(a?|b+|c*)*d" regular expression
> >test = star (choice [quest (c 'a')
> >                    ,plus (c 'b')
> >                    ,star (c 'c')]) +> c 'd'

Indeed, this cannot work.  ReadP delivers parses in order of increasing
length, and your expression produces infinitely many parses of the empty
string, you never get to the interesting matches.  I'd say, the best
solution is to use an equivalent regex which does not contain something
of the form 'many (return x)':

> >-- Simulate "(a?|b+|c*)*d" regular expression
> >test' = star (choice [(c 'a')
> >                     ,plus (c 'b')
> >                     ,plus (c 'c')]) +> c 'd'

f u cn rd ths, u cn gt a gd jb n cmptr prgrmmng.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060831/6e3855be/attachment-0001.bin

More information about the Haskell-Cafe mailing list