A few thoughts on these topics, which I've been thinking about for a while.
First, let's distinguish two things. One is an _incremental_ system,
such as a parser, which is one which does less work in response to a
small change than it would need to do from scratch. The other is a
system with _error recovery_, which is one where in the presence of
one error, the system can still provide a useful answer and/or
continue on to discover other errors. tree-sitter, for example, aims
to do both of these, but they're quite different.
With that in mind, several points:
1. It would be relatively straightforward to build an incremental
_reader_ -- going from text to s-expressions. You could start from the
grammar here:
https://github.com/racket/parser-tools/blob/master/parser-tools-lib/parser-tools/examples/read.rkt
which is just for Scheme, and the lexer here:
https://github.com/racket/syntax-color/blob/master/syntax-color-lib/syntax-color/racket-lexer.rkt
which is for full Racket, which as Robby says is already
error-tolerant. The read syntax (in the absence of reader extensions)
is definitely context-free and probably LR(1). The code for the reader
is here:
https://github.com/racket/racket/tree/master/racket/src/expander/read
However, just calling `read` from scratch every time isn't a big
bottleneck -- the biggest Racket-syntax file I have around is about
86000 lines and takes 700ms to `read`.
2. As Robby points out, the big challenge is the macro expander, which
is (a) not a grammar, (b) large and complicated (the code is here:
https://github.com/racket/racket/tree/master/racket/src/expander and
it's about 35k lines) and (c) it runs arbitrary Racket code in the
form of macros. I'm definitely interested in thinking about what an
incremental expander would look like, but that's a big research
project and probably would require a different model of macros than
Racket has right now. It would not work to use some existing parsing
toolkit like tree-sitter. You could perhaps write a new macro expander
using an incremental computation framework such as Adapton
[
https://docs.rs/adapton/0.3.31/adapton/] or write something like
Adapton for Racket. How well that would work is an interesting
question. You could also rewrite the macro expander to be incremental
more directly.
3. An error-tolerant macro expander is more plausible, but would again
require substantial changes to the expander. One possible idea is to
use the information the macro stepper already uses to reconstruct the
partial program right before it went wrong, and supply that to the IDE
to use for completion/etc. Another idea would be to replace pieces of
erroneous syntax with something that allows the expander to continue
(this is how error-tolerant parsers work). There are probably lots
more ideas that we could come up with.
4. Compiling to one of the OCaml intermediate languages is an
interesting idea -- I've thought about their flambda language as a
possible target before. The place to start is the `schemify` layer:
https://github.com/racket/racket/tree/master/racket/src/schemify that
turns fully-expanded Racket code into Scheme code for Chez Scheme.
Changing that to produce flambda would be plausible, although there
are a lot of mismatches between the languages that would be tricky to
overcome. Another possibility would be to directly produce JavaScript
from that layer. You might be interested in the RacketScript project:
https://github.com/vishesh/racketscript
If you're interested in thinking more about these topics, or working
on them, I'm happy to offer more advice.
Sam