Re: symbol tables and search tries

On 31 Jan 2006 00:33:59 -0500, RLake@oxfam.org.uk wrote:


> Having said that, I don't think that a hash table is the best
> data structure for an IDE, although it probably is for a
> compiler. An IDE will want to be able to do things like
> tab-completion, which would militate for a data structure
> which facilitates prefix searches, such as a trie or
> PATRICIA tree.


I agree. The hash function evaluation time should be counted as well. The
penalty depends on not only n, the table size, but also on m, the token
length.


Further, what hash tables cannot do is parsing the source with an
unknown right bound of the token. I.e. trees don't need a tokenizer to
be run first. A tree (or other ordered structure) can itself act as a
tokenizer, making nice things like closest match, wild-cards etc. This
all boils down to the "native" order of tokens, hash tables lack. It
was already mentioned by some other poster. So it depends...


--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Return to the comp.compilers page.
Search the comp.compilers archives again.