Theory of parsing and live syntax highlighting

Question

I am trying to understand how I should implement live syntax highlight when processing a very big string. I'm quite confused. This is what I know:

(Supposing I have the function parsedString parseString(rawString))

1. Call parseString(entireText) and replace the current string with the returned parsed (and styled, etc.) string on every text change. This seems a bad approach when handling big data.

2. Someone suggested to analyze the edited range, and replace the current raw edited string with the parsed string parseString(editedRange).

Method (1) is clear enough. What I cannot understand is (2). When typing, for each character added to the string, the notification is fired, and a single character is being parsed (and returned as it is).

For example, if I want red selectors when parsing a .css file, how I can understand when there's a completed selector followed by a { that should be colored? I suppose there is some way to delay the parsing until there is a match. How do you implement this?

I'm not looking for a working application. A good explanation would be useful as well.

Thank you in advance.

Answer 1

To re-parse incremental changes, you'll need a lower-level API to your parser.

A parser has a state that changes as it processes the input. For example, first the parser might be skipping spaces, now it might be reading a number, later it might be building an abstract syntax tree for an expression. If you could take a snapshot of all that parser state information at milestone points in the input, then you could reparse an incremental change by starting at the last milestone before the change (and possibly stopping earlier if the state is identical at a milestone beyond that change).

For simple syntax highlighting, like many programmers editors do, this is the approach. Syntax highlighting requires little more than tokenization, so there isn't much state to capture. And many programming languages have plenty of opportunities for milestones, e.g., at the beginning of a new line. In those cases, you might not even need to actually save the parser state, as you might know that it's always the same at the beginning of a line.

So you need an API like:

parsedString parseIncrementally(parserState, rawString);