Re: what scanner scheme is efficient?

peter@peter.bj-ig.de says...
>
>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.


This is irrelevant, because:


1) The sets of typical keywords don't require backtracking. e.g. C++
keywords require no backtracking anywhere. This is not accidental --
the standards people usually think (really!) about this beforehand.
Your example above does not even require backtracking -- a simple
one-character-lookahead lexer like DLG will deal with. An example
that requires backtracking would be like:


        keyword1 = "LET"
        keyword2 = "LETXX"
        input = "LETX "


Just because FLEX supports backtracking does not mean that you have to
use it.


2) Even if backtracking exists, it is usually so rare that the
additional time spent hashing every token outweighs the savings for
rare tokens.


>2. The scanner table is very small. (Every Letter in the Keywords adds 2
>States).


True. For example, the state machine for my DLG-generated C++ lexer
takes about 50-100k, and this might even cause cache misses, which
would slow things down a bit. But when MSVC++ takes 24Mb to compile
one of my files, I think there is considerable slack in the
time/memory tradeoff.


Has anyone actually *tested* the supposed hash-table speedup?


john lilley
--

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