Another parser combinator problem

From: Steffen Mazanek <>
Date: Sat, 23 Feb 2008 13:44:39 -0500


once again I have a problem with my parser combinators.
Consider the following code:

--peano numbers
data Nat = Z | S Nat

le Z _ = success
le (S x) (S y) = le x y

plus Z y = y
plus (S x) y = S (plus x y)

--given a string, a parser returns the remaining string and the
--number of insertions that had been necessary to succeed
type Parser = String->(String,Nat)

infixl 5 <*>
--sequential composition adds numbers of errors
--and ensures that this number is at most 2
(p1 <*> p2) xs | p1 xs=:=(xs',errs1) & p2 xs'=:=(xs'',errs2) &
                 errs=:=errs1 `plus` errs2 &
                 errs `le` (S (S Z)) = (xs'',errs)
                 where xs',errs1,xs'',errs2,errs free

pSucceed xs = (xs,Z)

--a particular character
char c (x:xs) | c=:=x = (xs,Z)
--can also be "assumed", thereby 1 error occurs
char c xs = (xs,S Z)

--a simple parser for the language (ab)^n
abab = pSucceed
abab = char 'a' <*> char 'b' <*> abab

This code does not work properly. abab returns
some results and then does not terminate anymore
although the search space is restricted such that
no more than two errors are allowed. Reordering of
the constraints in <*> does not help.

Does anybody knows what the problem is? Help is
greatly appreciated.

Thanks again,
curry mailing list
Received on So Feb 24 2008 - 07:59:19 CET

This archive was generated by hypermail 2.3.0 : Sa Dez 09 2023 - 07:15:10 CET