Another parser combinator problem

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

Hello,

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

--peano numbers
data Nat = Z | S Nat

le::Nat->Nat->Success
le Z _ = success
le (S x) (S y) = le x y

plus::Nat->Nat->Nat
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
(<*>)::Parser->Parser->Parser
(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::Char->Parser
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::Parser
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,
Steffen
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Sun Feb 24 2008 - 07:59:19 CET

This archive was generated by hypermail 2.3.0 : Fri Sep 20 2019 - 07:15:07 CEST