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.


Peter Brueckner <peter@peter.bj-ig.de> wrote:
>1. The scanner is faster (with an 'IDENT' clause) because it doesn't need to
> 'backtrack', example:


Flex/lex based scanners do not backtrack.


I posed a question to this news group when I was a TA for a compiler
class that was almost identical to the original question. The response
then was that if *speed* is the issue it is better to put your
keywords into your grammar and have the scanner recognize them than it
is to use a hash table. Of course other issues besides speed
(ie, maintainability or table size) may dictate a different approach.


Interested readers should retrieve articles 90-12-040 and 90-12-044
from the comp.compilers archive (http://iecc.com/compilers/).


Jerry Roth
roth@cs.rice.edu
http://www.cs.rice.edu/~roth/
--

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