Re: Hash specifics

vern@horse.ee.lbl.gov (Vern Paxson)
Sun, 16 Dec 90 22:29:43 GMT

          From comp.compilers

Related articles
[7 earlier articles]
Re: Hash specifics rfg@ncd.com (1990-12-13)
Re: Hash specifics rfg@ncd.com (1990-12-13)
Re: Hash specifics bart@cs.uoregon.edu (1990-12-13)
Re: Hash specifics roth@resi.rice.edu (1990-12-14)
Re: Hash specifics oz@nexus.yorku.ca (1990-12-14)
Re: Hash specifics plx!plxsun!evan@Sun.COM (1990-12-15)
Re: Hash specifics vern@horse.ee.lbl.gov (1990-12-16)
Re: Hash specifics schmidt@oberkampf.ICS.UCI.EDU (Doug Schmidt) (1990-12-17)
Re: Hash specifics preston@ariel.rice.edu (1990-12-17)
Re: Hash specifics brain@eos.ncsu.edu (1990-12-18)
Re: Hash specifics rfpfeifl@watcgl.uwaterloo.ca (Ron Pfeifle) (1990-12-21)
| List of all articles for this month |

Newsgroups: comp.compilers
From: vern@horse.ee.lbl.gov (Vern Paxson)
Keywords: design, flex, scanner
Organization: Lawrence Berkeley Laboratory, Berkeley
References: <1990Dec12.221425.569@zoo.toronto.edu> <9012122107.aa06454@ICS.UCI.EDU> <1990Dec13.201211.6483@cs.uoregon.edu> <1990Dec14.164415.326@rice.edu>
Date: Sun, 16 Dec 90 22:29:43 GMT

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


Post a followup to this message

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