|Lex surrogates lfcs.edinburgh.ac.uk!db@NSS.CS.UCL.AC.UK (Dave Berry) (1989-02-05)|
|Re: Lex surrogates schmidt@ORION.CF.UCI.EDU (Douglas C. Schmidt) (1989-02-05)|
|Re: Lex surrogates firstname.lastname@example.org (Vern Paxson) (1989-02-06)|
|Re: Lex surrogates rsalz@BBN.COM (Rich Salz) (1989-02-07)|
|Re: Lex surrogates wpl@PRC.Unisys.COM (1989-02-06)|
|Re: Lex surrogates email@example.com (Ken Yap) (1989-02-09)|
|Re: Lex surrogates firstname.lastname@example.org (1989-02-09)|
|Re: Lex surrogates tower@bu-cs.BU.EDU (1989-02-10)|
|Re: Lex surrogates email@example.com (1989-02-11)|
|Re: Lex surrogates firstname.lastname@example.org (Henry Spencer) (1989-02-11)|
|Re: Lex surrogates email@example.com (Ric Holt) (1989-02-13)|
|[2 later articles]|
|From:||wpl@PRC.Unisys.COM (William P Loftus)|
|Date:||6 Feb 89 16:55:16 GMT|
Many of the lexical analyzer generators gain their speed from limiting
the specification power of their tools. They are taking advantage of
the fact that most languages don't need a general RE processor. In my
opinion, this limits the use of such tools to traditional language
lexical analyzers (they are not for what Aho et al. call swiss army
knives---see the dragon book). However, there is a full RE lexical
analyzer generator called Flex.
Flex is a lex clone, but much faster.
Here is a file contained in the distribution of flex (which is
freely available from several ftp and uucp sites) that describes
flex vs. lex timings for a C tokenizer which includes keywords:
lex 83.0 secs
flex -cfe 7.1 # uncompressed table, equivalence classes
flex -cf 15.0 # uncompressed table, no equivalence classes
Scanner object file sizes:
lex 41.0K bytes
flex -cfe 49.6K
flex -cf 126.5K
Running times on a 28,088 line input (685K characters):
lex 29.8 secs
flex -cfe 9.0
flex -cf 7.8
The timings were made on a Sun 3/60. All times are user + system CPU time,
and don't include hashing of identifiers.
For about the same sized scanner, you get a factor of 3 in performance.
For a 30% faster scanner, you get a scanner 1/4th the size, and it's
generated in 1/20th the time.
For a scanner that's 3 times larger, you get a factor of 3.8 in
There is a paper by Vern Paxson that describes how he obtains these speeds (I
don't have the paper with me at the moment, so I can't tell you the title).
William P Loftus UUCP: wpl@burdvax.UUCP
Unisys/Paoli Research Center ARPA: firstname.lastname@example.org
PO Box 517 215-354-0614 (home)
Paoli, PA 19301 215-648-7248 (work)
Return to the
Search the comp.compilers archives again.