Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!iecc!compilers-sender
From: roth@resi.rice.edu (Jerry Roth)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design, lex, scanner
Message-ID: <1990Dec14.164415.326@rice.edu>
Date: 14 Dec 90 16:44:15 GMT
References: <1990Dec12.221425.569@zoo.toronto.edu> <9012122107.aa06454@ICS.UCI.EDU> <1990Dec13.201211.6483@cs.uoregon.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: roth@resi.rice.edu (Jerry Roth)
Organization: Rice University, Houston
Lines: 35
Approved: compilers@iecc.cambridge.ma.us

In article <1990Dec13.201211.6483@cs.uoregon.edu> bart@cs.uoregon.edu (Barton Christopher Massey) writes:
>You can very efficiently decide whether the next input belongs to a given
>set of keywords or is an identifier as you read it in using a DFA or some
>similar recognizer.  Given the wide availability of FLEX, this is the
>approach I almost always use -- dodges both the problems of efficient
>keyword hashing and separating identifiers from keywords.

I have always wondered which method is truly more efficient. The two
methods are:

(a) Preload all keywords into the hash table and have the lexer distinguish
identifiers from keywords via lookup. Keywords and identifiers are then
treated the same until after the lookup.

(b) Add a regular expression for each keyword to the lexer followed by a
regular expression to catch identifiers. Keywords are then handled directly
while only the identifiers get hashed.

It seems method (a) has the advantage of keeping the lexer simple in that it
has fewer expressions to attempt to match.  While method (b) avoids hashing
keywords.

Can anyone tell me if adding more expressions to my lexer (one per keyword)
causes it to execute less efficiently, assuming that I am using LEX/FLEX to
create it. If so, is it less efficient than hashing each keyword when
encountered.

Thanks,
Jerry Roth
[It is my impression that the speed at which a flex parser does what it does
is unrelated to the complexity of the state machine, although its size goes
up, but I'd be glad to hear from someone who knows definitively. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.