Re: Keyword implemetation.

Christian Bau <>
2 Jul 2001 00:31:40 -0400

          From comp.compilers

Related articles
Keyword implemetation. (Thomas Fjellstrom) (2001-06-28)
Re: Keyword implemetation. (Christian Bau) (2001-07-02)
| List of all articles for this month |

From: Christian Bau <>
Newsgroups: comp.compilers
Date: 2 Jul 2001 00:31:40 -0400
Organization: Insignia Solutions plc
References: 01-06-079
Keywords: lex, performance
Posted-Date: 02 Jul 2001 00:31:40 EDT

Thomas Fjellstrom wrote:
> In a compiler/translator I've been writing I implemented
> the Reserved/Key words with a sorted table and searched
> using bsearch. I was wondering what every ones preference
> was for implementing keywords? using the symbol table,
> a method just like mine or something else all togeter?

I wouldn't say that I have a preference, but two approaches that I
have seen which try to do it as fast as possible are the following:

1. The brute force method. A switch statement based on the first
character of the identifier, and since you usually have very few
reserved words starting with the same character, you write code
manually that compares the remaining characters. For example, in a C
compiler you could find

switch (ident [0]) {
case 'u':
if (ident [1] == 'n' && ident [2] == 'i'
&& ident [3] == 'o' && ident [4] == 'n'
&& ident [5] == '\0')
token = UNION_TOKEN;
else if (ident [1] == 'n' && ident [2] == 's'
&& ident [3] == 'i' etc.)

The other method which I would prefer uses hashing; for every
identifier you calculate a hashcode; this can come useful anyway if
you use hashing for all the other symbol tables that you need. Then
you have a symbol table for the keywords, and you design your hash
function carefully so that all keywords will have different
hashcodes. Most likely you have to calculate this hashcode once anyway
because whatever the identifier is, you will definitely have to look
it up in some table eventually. So the total cost for looking up
keywords can be as low as indexing into one table.

Post a followup to this message

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