Re: what scanner scheme is efficient?

vern@daffy.ee.lbl.gov (Vern Paxson)
12 Nov 1996 22:02:42 -0500

          From comp.compilers

Related articles
[3 earlier articles]
Re: what scanner scheme is efficient? peter@peter.bj-ig.de (Peter Brueckner) (1996-10-18)
Re: what scanner scheme is efficient? roth@noel.cs.rice.edu (1996-10-20)
Re: what scanner scheme is efficient? jsgray@acm.org (Jan Gray) (1996-10-20)
Re: what scanner scheme is efficient? clark@quarry.zk3.dec.com (1996-10-24)
Re: what scanner scheme is efficient? james@wgold.demon.co.uk (James Mansion) (1996-10-24)
Re: what scanner scheme is efficient? jlilley@empathy.com (1996-10-30)
Re: what scanner scheme is efficient? vern@daffy.ee.lbl.gov (1996-11-12)
Re: what scanner scheme is efficient? jlilley@empathy.com (1996-11-15)
Re: what scanner scheme is efficient? adrian@dcs.rhbnc.ac.uk (1996-11-19)
Re: what scanner scheme is efficient? vern@daffy.ee.lbl.gov (1996-11-21)
Re: what scanner scheme is efficient? adrian@dcs.rhbnc.ac.uk (1996-11-24)
Re: what scanner scheme is efficient? jlilley@empathy.com (1996-12-01)
| List of all articles for this month |

From: vern@daffy.ee.lbl.gov (Vern Paxson)
Newsgroups: comp.compilers
Date: 12 Nov 1996 22:02:42 -0500
Organization: Lawrence Berkeley National Laboratory, Berkeley CA
References: 96-10-076 96-10-081 96-10-149
Keywords: lex, performance

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


Post a followup to this message

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