Re: lexing backwards

>Could anyone point me to work and experience on lexing text locally
>and backwards ?
>
>Traditionally lexing is done left-to-right with longest-match regexps.
>But such a lexing system obviously means that if you're in the middle
>of a file and want to know what is the previous lexing token, you end
>up (in the general case) having to lex from the beginning of the file.


Tim A. Wagner had done some work on optimal incremental lexing, which
permits you to start lexing from anywhere in the buffer and re-lexes
as few tokens as possible. His work is described in Chapter 5 of his
dissertation "Practical Algorithms for Incremental Software
Development Environments" [1] and also in an unpublished paper
"General Incremental Lexical Analysis" [2].


Wagner's algorithms were designed for use in an interactive program
development environments (Ensemble/Harmonia [3]) and were also used in
the CodeProcessor editor [4] for per-keystroke lexical analysis.
(This should serve as a testament for their applicability for program
editors.)


Space overhead of Wagner's algorithm is 3 integer fields per lexical
token (flex condition state, lookahead, and lookback). This overhead
could be reduced (or even eliminated) in most programming languages by
noticing that for majority of tokens these fields will have default
values. I have some ideas on how this can be implemented; feel free
to write me for more informations.


Marat.


[1]
http://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-thesis.pdf
[2]
http://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-lexing.pdf
[3]
http://www.cs.berkeley.edu/Research/Projects/harmonia/harmonia/index.html
[4] http://www.cs.berkeley.edu/~maratb/pubs/editor.pdf


--
Marat Boshernitsan
Ph.D. Candidate
Computer Science Division, EECS
University of California, Berkeley

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