Re: what scanner scheme is efficient?

John Lilley <jlilley@empathy.com> wrote:
> Just because FLEX supports backtracking does not mean that you have to
> use it.


Let me clarify. Flex doesn't support backtracking in the sense of
trying multiple matches one after the other. It does support
something I call "backing up" (which, confusingly, I called
backtracking in earlier versions of the flex manual). Backing up
means that sometimes when the scanner looks ahead several characters,
it determines that no longer token can match, and must return to the
point of the last match. An example is matching two keywords, "foo"
and "foobar". If 'f', 'o', 'o' have been scanned and the next
characters are 'b' and 'a', the scanner must match them in case what
comes next is 'r'. But if it's not 'r', then it must return to the
point where it had matched "foo". It will later re-scan 'b' and 'a',
when matching the next token.


Most scanners have to do backing-up, though you can sometimes arrange
the scanning rules so it's avoided. Flex has an option for helping
users alter their rules so no backing up is necessary. If it's never
necessary, then flex optimizes the generated scanner by omitting the
backing-up bookkeeping.


Vern
--

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