more code completion fun!

[Richard Moore]

Eva Brucherseifer wrote:
> 
> Hi all,
> 
> I don't know the ANTLR thing or what LL(k) is, but here is my contribution to
> this, maybe it is of help:
> 
> this morning I talked to our professor here at the TU Darmstadt about this
> problem and I got some interesting hints.
> 
> There is an algorithm by Donald Knuth (yes, the latex guy) that uses a finite
> state machine, which is widely used for problems of this type.
> You either can test for matches while the user writes and complete as soon as
> there is a unique match, or you can give choices before. For both cases you
> need a dictionary of valid words.

I assume you mean the Knuth-Morris-Pratt algorithm? This is useful for
this sort of thing, but I would guess tree would work better. You can
descend a level of the tree for each letter the user types, so the
searches would get progressively faster too. The trouble with KMP is
that the state machine is rebuilt each time a new name is added. You
could probably optimise it by using the existing state machine to
find the minimum set of changes to create the new one, but a tree
would be a lot easier to code.

Rich.
-- 
     Richard Moore		rich at ipso-facto.freeserve.co.uk
http://developer.kde.org/	rich at kde.org


-
to unsubscribe from this list send an email to kdevelop-request at kdevelop.org with the following body:
unsubscribe »your-email-address«