Re: Hash specifics

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.
--

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