Re: Another parser combinator problem

From: Wolfgang Lux <wlux_at_uni-muenster.de>
Date: Mon, 25 Feb 2008 09:08:42 +0100

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 Mon Feb 25 2008 - 16:45:53 CET

This archive was generated by hypermail 2.3.0 : Mon Sep 16 2019 - 07:15:06 CEST