Hashing for Keywords? (was: Minimal Perfect Hashing and Cichelli's algorithm)

Hi!


taj@vanbc.wimsey.com (Taj Khattra) wrote:


> For "large" keyword sets (certainly larger than the keyword sets of most
> programming languages) it may be worthwhile to explore the algorithm
> described in [CHM92] which is a probabilistic method using random graphs
> that works very fast in practice. It also has the benefit of being order
> preserving.


      Reading through the mails leading up to the one quoted above I
found myself wondering whether this really is an issue at all when
dealing with keywords.


      In fact a lot of Oberon-2 compilers use the following approach
which is *very* simple and apparently not causing a "bottleneck" for
the compiler (Oberon-2 compilers are usually very fast compared to
other compilers, see [1] for an objective comparison):


      VAR buffer: ARRAY 256 OF CHAR; token: INTEGER;
      (* ... *)
      CASE buffer[0] OF
          (* ... *)
          "A": IF buffer = "ARRAY" THEN
                        token := array;
                    ELSE
                        token := identifier;
                    END;
        |"B": IF buffer = "BEGIN" THEN
                        token := begin;
                    ELSIF buffer = "BY" THEN
                        token := by;
                    ELSE
                        token := identifier;
                    END;
          (* ... *)
      ELSE
          token := identifier;
      END;


I can't guarantee for correct syntax here. :-/


      I understand the problem for syntax tables where a large number of
varying objects (identifiers) must be expected, but for keywords? Is
it worth the pain to deal with them in a more complex way than the one
outlined above?


----------
[1] Henderson, Zorn: A Comparison of Four Object-Oriented Programming
Languages. Technical Report CU-CS-641-93, University of Colorado at
Boulder, 1993. (availiable through ftp)


By(T)e...
                  Peter...
--

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