Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender
From: vern@horse.ee.lbl.gov (Vern Paxson)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design, flex, scanner
Message-ID: <8642@dog.ee.lbl.gov>
Date: 16 Dec 90 22:29:43 GMT
References: <1990Dec12.221425.569@zoo.toronto.edu> <9012122107.aa06454@ICS.UCI.EDU> <1990Dec13.201211.6483@cs.uoregon.edu> <1990Dec14.164415.326@rice.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: vern@horse.ee.lbl.gov (Vern Paxson)
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 29
Approved: compilers@iecc.cambridge.ma.us

In article <1990Dec14.164415.326@rice.edu> roth@resi.rice.edu (Jerry Roth) writes:
> 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....
> ...
> [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]

Right, a finite automaton scanner like flex's looks at each character just
once, regardless of the complexity of the patterns it is matching against (*).
Adding more regular expressions to the rule set makes the scanner tables
bigger but does not change the speed of scanning (except for second-order
effects like page faults).  So if space is not a concern, it's easiest and
fastest to match keywords using a separate rule for each one.

		Vern

	Vern Paxson				vern@helios.ee.lbl.gov
	Real Time Systems			ucbvax!helios.ee.lbl.gov!vern
	Lawrence Berkeley Laboratory		(415) 486-7504

(*) There are some cases when the scanner must rescan text, though they
    don't arise when using individual rules to match keywords plus a
    generic "identifier" rule to match all non-keyword identifiers.
    flex's -b option helps identify and eliminate these cases.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.