[OT] Partial-reparsing thory?

[Rainer Schuetze]

Nick Sabalausky wrote:
> "spir" <denis.spir at gmail.com> wrote in message 
> news:mailman.3527.1302824019.4748.digitalmars-d at puremagic.com...
>> On 04/15/2011 12:51 AM, Nick Sabalausky wrote:
>>> Is anyone aware of any (formal or informal)
>>> theory/information/research/articles/etc. that's already been done on the
>>> idea of reparsing *part* of an already-parsed source? Either lexing, 
>>> parsing
>>> or both together. Preferably LR, but LL might be helpful, too. (I'd 
>>> imagine
>>> it may be notably more difficult with LR. May need to keep track of all 
>>> the
>>> parsing steps taken the first time around, and may need to continue
>>> re-parsing to the end of the source.)
> 
> I'd imagine lex-only would be a lot easier.
> 

Sure it is. Visual D uses the Visual Studio approach for highlighting, 
keeping a 32-bit integer per line, indicating the state of the lexer. 
This state keeps track of token type, nesting level, etc. The state is 
calculated lazily, so you only have to scan the file until the last 
visible line.

In addition, Visual D has a very simple parser to highlight 
version/debug conditionals, mostly just meant to figure out to what 
conditional an "else" belongs to (simpleparser.d). It keeps track of the 
text span that is covered by a parse tree node. If the text is modified, 
all parse tree nodes after the editing point are discarded, while the 
nodes including the edit point are restored to a state including the 
nodes before the span. The parser stack is reconstructed from the 
remaining parse tree and parsing can restart from a point very close to 
the actual editing point.

As this parser only runs up to the last visible line, it has only a very 
small impact on performance and runs together with the lexer while the 
lines are drawn.

The next version of Visual D will have a D2 parser (currently only used 
to highlight syntax errors), and I was hoping that a similar approach 
would be possible, but the state to keep is way more complicated. So it 
is running in a background thread for now, parsing the complete source.