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

From: Steffen Mazanek <steffen.mazanek_at_unibw.de>

Date: Sun, 24 Feb 2008 13:45:58 +0100

Nikolay,

thanks for answering! I have also tried PAKCS with sicstus and the

same problem occurred. So, I think we cannot blame MCC :-)

In a string setting error correcting parser combinators are well-studied.

For instance, the Utrecht parser combinators incorporate very

sophisticated error handling. However, I deal with graphs (the example

was just a simplification of my problem). I feel that powerful error

correction by edge insertion is in reach and I am quite excited about

this.

Previously I have simply added free variables to my graph to correct errors.

This works, but has several disadvantages:

1. the number of edges that have to be inserted must be known in advance

2. inserting more than 1 free variable results in redundant permutations, i.e.,

given a solution e1=edge1 and e2=edge2 I am not interested in the solution

e1=edge2 and e2=edge1.

Assuming edges if necessary and collecting inserted edges bottom up should

solve this permutation problem. However, without the possibility to

restrict their

number this approach is also doomed to failure.

So, help with this problem is greatly appreciated.

Regards,

Steffen

2008/2/24, Nikolay Orlyuk <virkony_at_gmail.com>:

*>
*

*>
*

*> 2008/2/23, Nikolay Orlyuk <virkony_at_gmail.com>:
*

*> >
*

*> >
*

*> >
*

*> > 2008/2/23, Steffen Mazanek <steffen.mazanek_at_unibw.de>:
*

*> >
*

*> > > Hello,
*

*> > >
*

*> > > once again I have a problem with my parser combinators.
*

*> > > Consider the following code:
*

*> > >
*

*> > > --peano numbers
*

*> > > data Nat = Z | S Nat
*

*> > >
*

*> > > le::Nat->Nat->Success
*

*> > > le Z _ = success
*

*> > > le (S x) (S y) = le x y
*

*> > >
*

*> > > plus::Nat->Nat->Nat
*

*> > > plus Z y = y
*

*> > > plus (S x) y = S (plus x y)
*

*> > >
*

*> > > --given a string, a parser returns the remaining string and the
*

*> > > --number of insertions that had been necessary to succeed
*

*> > > type Parser = String->(String,Nat)
*

*> > >
*

*> > > infixl 5 <*>
*

*> > > --sequential composition adds numbers of errors
*

*> > > --and ensures that this number is at most 2
*

*> > > (<*>)::Parser->Parser->Parser
*

*> > > (p1 <*> p2) xs | p1 xs=:=(xs',errs1) & p2 xs'=:=(xs'',errs2) &
*

*> > > errs=:=errs1 `plus` errs2 &
*

*> > > errs `le` (S (S Z)) = (xs'',errs)
*

*> > > where xs',errs1,xs'',errs2,errs free
*

*> > >
*

*> > > pSucceed xs = (xs,Z)
*

*> > >
*

*> > > --a particular character
*

*> > > char::Char->Parser
*

*> > > char c (x:xs) | c=:=x = (xs,Z)
*

*> > > --can also be "assumed", thereby 1 error occurs
*

*> > > char c xs = (xs,S Z)
*

*> > >
*

*> > > --a simple parser for the language (ab)^n
*

*> > > abab::Parser
*

*> > > abab = pSucceed
*

*> > > abab = char 'a' <*> char 'b' <*> abab
*

*> > >
*

*> > > 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.
*

*> >
*

*> >
*

*> > I think your search space is extended by your restriction space :)
*

*> > abab starts to generate and generate while receiving error on "abab = ...
*

*> <*> pSuccess" resulting in rewriting "abab = ... <*> ( ... <*> pSuccess)",
*

*> possibli because of `plus` which requires roll back at this moment to
*

*> recalulate errs =:= errs1 `plus` ... `plus` errsN
*

*>
*

*> Sorry now I'm pretty sure thats the reason is:
*

*> > > errs `le` S(S Z) & errs =:= errs1 `plus` errs2 where errs,errs1
*

*> > ,errs2 free
*

*> > {errs = Z, errs1 = Z, errs2 = Z}
*

*> > More solutions? [Y(es)/n(o)/a(ll)] a
*

*> > {errs = S Z, errs1 = Z, errs2 = S Z} | {errs = S Z, errs1 = S Z, errs2 =
*

*> Z} | {errs = S (S Z), errs1 = Z, errs2 = S (S Z)} | {errs = S (S Z), errs1 =
*

*> S Z, errs2 = S Z} | {errs = S (S Z), errs1 = S (S Z), errs2 = Z}
*

*>
*

*>
*

*> errs2 is not unknown. Thats causes "p2 xs'=:=(xs'',errs2)" to lose lazyness
*

*> earlier than xs'' (when placed after restriction on errors) and refer to p2
*

*> too early to say that we didn't maked by errs1.
*

*>
*

*> Try another implementation of curry, because I think that first solution
*

*> should look like {errs = Z, errs1 = Z, errs2 = _any }
*

*>
*

*> >
*

*> >
*

*> > Thats looks not goode, but I don't see an other way (using MCC) why it
*

*> recurse to inifinity.
*

*> >
*

*> >
*

*> > > Thanks again,
*

*> > > Steffen
*

*> > > _______________________________________________
*

*> > > curry mailing list
*

*> > > curry_at_lists.RWTH-Aachen.DE
*

*> > > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
*

*> > >
*

*> >
*

*> >
*

*>
*

*>
*

Date: Sun, 24 Feb 2008 13:45:58 +0100

Nikolay,

thanks for answering! I have also tried PAKCS with sicstus and the

same problem occurred. So, I think we cannot blame MCC :-)

In a string setting error correcting parser combinators are well-studied.

For instance, the Utrecht parser combinators incorporate very

sophisticated error handling. However, I deal with graphs (the example

was just a simplification of my problem). I feel that powerful error

correction by edge insertion is in reach and I am quite excited about

this.

Previously I have simply added free variables to my graph to correct errors.

This works, but has several disadvantages:

1. the number of edges that have to be inserted must be known in advance

2. inserting more than 1 free variable results in redundant permutations, i.e.,

given a solution e1=edge1 and e2=edge2 I am not interested in the solution

e1=edge2 and e2=edge1.

Assuming edges if necessary and collecting inserted edges bottom up should

solve this permutation problem. However, without the possibility to

restrict their

number this approach is also doomed to failure.

So, help with this problem is greatly appreciated.

Regards,

Steffen

2008/2/24, Nikolay Orlyuk <virkony_at_gmail.com>:

-- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek_at_unibw.de _______________________________________________ curry mailing list curry_at_lists.RWTH-Aachen.DE http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curryReceived on So Feb 24 2008 - 17:32:21 CET

*
This archive was generated by hypermail 2.3.0
: Do Jun 20 2024 - 07:15:09 CEST
*