- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

Date: Mon, 25 Feb 2008 09:08:42 +0100

Hello Steffen!

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
*