Re: symbol tables and search tries

haberg@math.su.se (Hans Aberg)
3 Feb 2006 18:43:33 -0500

          From comp.compilers

Related articles
[18 earlier articles]
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-02)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-02)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-02-03)
Re: symbol tables and search tries d148f3wg02@sneakemail.com (Karsten Nyblad) (2006-02-03)
Re: symbol tables and search tries henry@spsystems.net (2006-02-03)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-03)
Re: symbol tables and search tries haberg@math.su.se (2006-02-03)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-02-06)
Re: symbol tables and search tries Suif.liyuan@gmail.com (jjyynmb) (2006-02-24)
| List of all articles for this month |

From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:43:33 -0500
Organization: Mathematics
References: 06-01-085 06-01-111 06-01-117 06-01-125 06-01-145
Keywords: symbols, comment

Matthias Blume <blume@tti-c.org> wrote:


> Hans, please, do the calculation!


I find it difficult to carry out any computations before first converting
the problem to a proper model within axiomatic set theory. :-)


> It does /not/ give you logarithmic
> time, it gives you constant time (in the amortized sense).
....
> A hash table does not sort, so this line of reasoning is not
> applicable.


There are apparently two data types in play: one with only equality
(equivalence relation), and one sorted (with total order). The containers
(like the hash table) only doing the equality comparison apparently (if
one should believe the posters here :-)) can do it in O(1) time.
The containers doing the sorting (like the balanced tree) can at best do
it in O(log n) time.


Now, a compiler only needing to identify the tokens would then be best off
with the first type. But a parser of some type that also needs to compare
the tokens, would be best off with the second type.


Roughly.


--
    Hans Aberg
[I think we're all in agreement here. For compiling, all you do with symbols
is look them up, and hashes do that well. In more complex enviroments where
you sort them or use them for name completion, tries have advantages. -John]


Post a followup to this message

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