Nikolay Orlyuk wrote:
> The problem is that your (<*>) combinator does not really restrict
> the search space. For instance, given an expression
> (p1 <*> p2) <*> (p3 <*> p4)
> you allow for two errors in each of the parsers (p1 <*> p2) and
> (p3 <*> p4) and only cut solutions with more than two error in
> the combined parser, but only after all alternatives for
> (p3 <*> p4) have been tried.
> Why all? Only after error will try to backtrack and in this
> exacmple it will backtrack starting from right to the left (no
> metter how brackets are placed, middle <*> will refer right side
> with partial result).
You are right, not *all* alternatives are tried. If p3 already has
*more* than two errors, p4 will not be tried of course. Yet, my point
remains. If two errors have been detected in (p1 <*> p2), you can
(and should) prune the search space for (p3 <*> p4) by allowing no
error at all in that parser.
>
>
> The only things in which is deffer is just specified order of
> switching within alternatives to be more strict, i.e. (p1 xs) =:=
> (xs',errs1) is unified first and after that it uses (errs1 `plus`
> errs) which results in S(..(S errs2)) where errs2 free until xs''
> or errs2 will be required particularry errs2 =:= Z which will
> result in backtrace for S(S errs3 ) =:= Z without need of
> calulation p3.
You have overlooked another subtle difference in the error case of
the char parser (I forgot to mention that in my previous mail)
char c (S _) xs = (xs,S Z)
This parser can succeed only if an error is still allowed and thus
causes the intended early pruning of the search tree.
Regards
Wolfgang
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mo Feb 25 2008 - 16:46:03 CET