Hello Steffen!
> Hello,
>
> once again I have a problem with my parser combinators.
> Consider the following code:
> [...]
> 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.
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. The solution, of course, is to make
the upper limit of errors an additional argument of the parsing
combinators, i.e.,
(p1 <*> p2) maxerrs xs | p1 maxerrs xs=:=(xs',errs1) &
p2 (maxerrs `minus` errs1) xs'=:=
(xs'',errs2) =
(xs'', errs1 `plus` errs2)
where xs',errs1,xs'',errs2 free
pSucceed _ xs = (xs,Z)
char c _ (x:xs) | c=:=x = (xs,Z)
char c (S _) xs = (xs,S Z)
Incidentally, in order to avoid just another disappointment, I'd
strongly suggest to use case expressions instead of unification,
i.e.,
(p1 <*> p2) maxerrs xs =
case p1 maxerrs xs of
(xs',errs1) ->
case p2 (maxerrs `minus` errs1) xs' of
(xs'',errs2) -> (xs'', errs1 `plus` errs2)
The problem with unification in this particular example is that
e1=:=e2 is defined to be satisfied only for equal data terms and
therefore both of its arguments are evaluated to normal form.
Unfortunately, this introduces an O(n^2) time complexity in the
parser, where n is the length of the input string, when using
expressions like
p1 maxerrs xs=:=(xs',errs1)
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:45:53 CET