Re: Another parser combinator problem

From: Wolfgang Lux <>
Date: Mon, 25 Feb 2008 10:58:28 +0100

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.


curry mailing list
Received on Mo Feb 25 2008 - 16:46:03 CET

This archive was generated by hypermail 2.3.0 : So Sep 20 2020 - 07:15:03 CEST