Re: State-machine based syntax highlighting

[Stefan Monnier]

> A much better strategy is to start parsing at point in each file and only
> parse a screenful at a time, doing this with an external parser would be
> very hard.

Starting the parse "at point" can be terribly difficult since you don't know
the state of the parser at that point.  You can infer the state by parsing
backward (this is what the indentation code does typically), or by jumping
to some previous spot assumed to have some known parsing state and then
parse forward.

If all you care about is indentation, then parsing backward gives the best
results in terms of being robust in the face of partially incorrect code
(because it only parses just as far back as necessary to determine
indentation, so the resulting indentation behavior has some kind of
locality quality to it).

If you really need the full state because you're going to keep parsing
forward some arbitrary distance, then you're better off jumping back to
a "safe spot" and parsing forward from there.  In some languages it's not so
easy to figure out what are such safe spots other than the beginning of
the file.  But maybe with enough parse-state caching (à la syntax-ppss in
Emacs-22, although beefed up to keep the state of a real parser), and with
a fast enough forward parsing code, you can get away with always parsing
"from the beginning of the buffer", although it then suffers from problems
when faced with invalid/misunderstood source code.

Of note: parsing backward can be fiendishly difficult because languages are
designed without paying any attention to it.

> There are other problems.  What if a part of the code is incorrect?
> Imagine, in C for example, if a function were written "foo (;" on line
> 10.  The effect of the error would propagate down far away from where
> it occurs, even line 300 might be treated wrongly.  The parser would
> have to cope with this eventuality.

What if it's correct, but only after passing through some special
purpose preprocessor?

> Also, in many languages there are bits of the meaning that depend on
> the names used.  In C for example the code " (foo) (bar)" means
> something different if foo is a type than it does if it's an
> identifier.  The C compiler can cope with this because it tracks all
> typedefs and identifiers through not only the current file but those
> included in it with #include.   The only way for a font-lock system
> based on a normal parser to deal with this situation would be for it to
> read all the include files, which may not even be present.

> Compiler parsers and font-locking/navigating code have different
> intentions.  Compiler parsers must be fast when handling a whole file,
> and they must generate accurate error messages.  Font-locking code must
> be fast when starting at any arbitrary part of the code, and it must
> tolerate incomplete information and errors.

Note that this last point can be seen as an advantage: we don't have to
detect invalid code.

I believe there are two alternatives: one is the way taken by things like
Visual Haskell where you integrate the editor and the build system, so the
editor can run the parser with the exact same args as the compiler
would/will.  I think this is a very workable solution and I hope it will be
developped in Emacs as well.

If you decide not to integrate the editor so closely with the build system
(i.e. follow the way Emacs currently works), then you really can't reliably
parse the buffer and thus can't reuse existing parsers.  So you end up
having to design a new parser for every language.  For a real programming
language, writing its grammar is a non-trivial task, so it can be
a problem.  The only thing that would save us is that we can be as
permissive as we want: we don't have to reject invalid programs.  Better: we
can presume that the code is valid, and if it isn't we can anything we
please.  I hope Emacs will also develop in this direction.  One good step in
that direction would be to spice up syntax-table so that the basic syntactic
elements can be bigger than a single-char (e.g. so as to handle
begin...end).  I've recently experimented with the use of an
infix-precedence system where each infix "operator" can have a different
left and right precedence, and then to try and use that to parse things like
if/then/else (where `then' and `else' are seen as "infix" operators).
It doesn't seem quite powerful enough for what I want (to indent Coq code
in this case), but sufficiently close that maybe some minor extension will
get me there.


        Stefan