Re: symbol tables and search tries

haberg@math.su.se (Hans Aberg)
28 Jan 2006 19:18:53 -0500

          From comp.compilers

Related articles
symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-28)
Re: symbol tables and search tries haberg@math.su.se (2006-01-28)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-01-30)
Re: symbol tables and search tries haberg@math.su.se (2006-01-30)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-01-31)
Re: symbol tables and search tries RLake@oxfam.org.uk (2006-01-31)
Re: symbol tables and search tries vmakarov@redhat.com (Vladimir Makarov) (2006-01-31)
Re: symbol tables and search tries clint@0lsen.net (Clint Olsen) (2006-01-31)
[19 later articles]
| List of all articles for this month |

From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 28 Jan 2006 19:18:53 -0500
Organization: Mathematics
References: 06-01-085
Keywords: symbols
Posted-Date: 28 Jan 2006 19:18:53 EST

John Levine wrote:


>... any compiler where symbol lookups are a significant part of
> the compile time has worse problems than which search algorithm it's
> using.


Why not using a balanced tree, like for example the std::map of C++? I
gives the minimum logarithmic search/insertion times without having to
bother about balancing, as in a hash map. Is the overhead too big?


--
    Hans Aberg
[I don't understand what you're proposing. Balanced trees are O(log N)
to search and require rebalancing whenever you insert something. Hash
tables of the sort we usually use for compiler symbol tables are O(1)
and balancing isn't an issue. -John]



Post a followup to this message

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