Re: what scanner scheme is efficient?

Peter Brueckner <peter@peter.bj-ig.de>
18 Oct 1996 00:05:06 -0400

          From comp.compilers

Related articles
what scanner scheme is efficient? lloix@star.spb.ru (1996-10-12)
Re: what scanner scheme is efficient? peter@bj-ig.de (1996-10-15)
Re: what scanner scheme is efficient? ramb@primenet.com (Ram Bhamidipaty) (1996-10-16)
Re: what scanner scheme is efficient? peter@peter.bj-ig.de (Peter Brueckner) (1996-10-18)
Re: what scanner scheme is efficient? roth@noel.cs.rice.edu (1996-10-20)
Re: what scanner scheme is efficient? jsgray@acm.org (Jan Gray) (1996-10-20)
Re: what scanner scheme is efficient? clark@quarry.zk3.dec.com (1996-10-24)
Re: what scanner scheme is efficient? james@wgold.demon.co.uk (James Mansion) (1996-10-24)
Re: what scanner scheme is efficient? jlilley@empathy.com (1996-10-30)
Re: what scanner scheme is efficient? vern@daffy.ee.lbl.gov (1996-11-12)
[5 later articles]
| List of all articles for this month |

From: Peter Brueckner <peter@peter.bj-ig.de>
Newsgroups: comp.compilers
Date: 18 Oct 1996 00:05:06 -0400
Organization: Compilers Central
References: 96-10-076
Keywords: lex, performance

>Is scanning/parsing _speed_ ever reason to go toward using a hash
>table for identifying keywords? I would venture to say no: If one's
>scanner has explicit patterns for each keyword then the "minimal"
>amount of work is done to recognize the keyword itself, whereas with
>the hash table approach, not only must the IDENT be recognized, but
>now a hash value must be computed for _every_ word and then the hash
>table probed, probably this last step is very cheap. I think the loss
>in speed comes from having to compute a hash value even when the
>scanner could know, if it had looked at the characters in the
>identifier itself, that the word in question cannot be a keyword.
>
>Does this line of reasoning make sense?
>
>To me then one should use a hash table for kewords when there is some
>other benefit that outweighs the loss in speed from the scanner.


1. The scanner is faster (with an 'IDENT' clause) because it doesn't need to
      'backtrack', example:
              keyword = "LET"
              input = "LETI"
      scanner L->E->T->I->backtrack(4)->L->E->T->I->whitspace->backup(1)->return
      see the flexinfo manpage or flex-infos.
2. The scanner table very small. (Every Letter in the Keywords adds 2 States).


all the other reasons remain.


Peter


--
Peter Brueckner, Brueckner&Jarosch Ing.-GmbH Erfurt, Germany 99084 Erfurt
Andreasstr. 37, TEL +49=361-64318.11, FAX .12, EMail peter@bj-ig.de,-42-
--


Post a followup to this message

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