Re: what scanner scheme is efficient?

>Thus the question is simple, how do professionals design their scanners
>and tables, what do they do with keywords, and what is the more effective
>approach?


  > The best approch is to have an rule for 'IDENT' in the lexical
  > scanner and an stage IDENT->RESERVED_WORD after the call to the
  > scanner. This has a few advantages:
  > ...
  > The resword table is an simple hash (O(1) like the scanner


Perhaps someone could give more information on this point.


I recently implemented a scanner for netlist files.


For those who dont work in the VLSI/EDA field netlists are (very
large) files that describe the connectivity of a chip of some sort. It
may be that netlists have a different ratio of keywords to identifiers
from programming languages that would make my data less useful.


I tried the approach of using a single pattern to match both IDENT's
and all keywords followed by a hash table to perform the IDENT-->
keyword transformation. I found this to be _slower_ than just having
all the keywords recognized by the scanner. Note I did not make any
effort to chose some "perfect" hash function that would eliminate
collisions. My hash table had around 25 keywords and I used a table
size of 256 or so.


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.


-Ram
ram@epic.com
--

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