2008/2/23, Steffen Mazanek <steffen.mazanek_at_unibw.de>:
>
> 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.
I think your search space is extended by your restriction space :)
abab starts to generate and generate while receiving error on "abab = ...
<*> pSuccess" resulting in rewriting "abab = ... <*> ( ... <*> pSuccess)",
possibli because of `plus` which requires roll back at this moment to
recalulate errs =:= errs1 `plus` ... `plus` errsN
Thats looks not goode, but I don't see an other way (using MCC) why it
recurse to inifinity.
Thanks again,
> Steffen
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
>
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on So Feb 24 2008 - 07:59:21 CET