Re: what scanner scheme is efficient?

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

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