2008/2/23, Nikolay Orlyuk <virkony_at_gmail.com>:
>
>
>
> 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
>
Sorry now I'm pretty sure thats the reason is:
> > errs `le` S(S Z) & errs =:= errs1 `plus` errs2 where errs,errs1
> ,errs2 free
> {errs = Z, errs1 = Z, errs2 = Z}
> More solutions? [Y(es)/n(o)/a(ll)] a
> {errs = S Z, errs1 = Z, errs2 = S Z} | {errs = S Z, errs1 = S Z, errs2 =
> Z} | {errs = S (S Z), errs1 = Z, errs2 = S (S Z)} | {errs = S (S Z), errs1 =
> S Z, errs2 = S Z} | {errs = S (S Z), errs1 = S (S Z), errs2 = Z}
errs2 is not unknown. Thats causes "p2 xs'=:=(xs'',errs2)" to lose lazyness
earlier than xs'' (when placed after restriction on errors) and refer to p2
too early to say that we didn't maked by errs1.
Try another implementation of curry, because I think that first solution
should look like {errs = Z, errs1 = Z, errs2 = _any }
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:22 CET