How to do incremental parsing

In general this could be easy to achieve because as I do text parsing (especially in C++) you also may want to store the correct line e.g. index at which the token starts and a length so later in processing you are able to point out error messages more easy. So you could iterate through your token list and determine if a change in range of certain token has happened and then start parsing the stream at the first token's previsous starting index up to the length of token(s) that are (partially) affected by the change.

For your 10000 character comment this is bad but could be difficult to prevent because someone could have changed some content in the middle to */ so your comment token would need to split up there and the rest of the comment is becomming invalid (syntactical).

I (as I'm writing a C++ standard compilant preprocessor at the moment I write this) suggest start validating an expression at the beginning of a line but don't fix to process lines perse. The other question to ask otherwise is (as you already did) how to handle line breaks. In C++ even a single line comment dosen't mean it ends at the same line in case of an \ escaped line break.

What I do over my years of writing different code parser is to set up basic (hard coded) rules in their own functions and build more complex rules out of these functions. Also I work in a pure stream based environment rather than a string or character array environment and have my own specialized stream class to store results in.

My comment rule for example looks like this

bool SingleLineComment(Stream data, TokenStream nodes)
        {
            if (data.Peek() != '/')
                return false;

            data.Get();
            while (!data.Eof())
            {
                if (!EscapedLineBreak(data, nodes))
                {
                    if (!LineBreak(data, nodes))
                        data.Get();
                    else
                        break;
                }
            }
            return true;
        }
        bool MultiLineComment(Stream data, TokenStream nodes)
        {
            if (data.Peek() != '*')
                return false;

            data.Get();
            while (!data.Eof())
            {
                if (!LineBreak(data, nodes) && data.Get() == '*' && data.Peek() == '/')
                {
                    data.Get();
                    return true;
                }
            }
            return false;
        }
        bool Comment(Stream data, TokenStream nodes)
        {
            if (data.Peek() != '/')
                return false;

            long streamPos = data.Position;
            data.Get();

            if (SingleLineComment(data, nodes) ||
                MultiLineComment(data, nodes))
            {
                long length = data.Position - streamPos;
                data.Position -= length;

                for (; length > 0; length--)
                    nodes.Add(data.Get());
                return true;
            }

            data.Position = streamPos;
            return false;
        }

while the 'master' rule for the preprocessor looks like this

bool Any(Stream data, TokenStream nodes)
        {
            bool hasMacro = false;
            while (!LineBreak(data, nodes))
                hasMacro |= AnyWithMacros(data, nodes);

            return hasMacro;
        }
        public bool Master(Stream data, TokenStream nodes)
        {
            if (Direktive(data, nodes))
            { }
            else if (Any(data, nodes))
            {
                Stream stream;
                bool hasMacro;
                do
                {
                    hasMacro = false;
                    stream = new TokenStream(nodes.Buffer);
                    nodes.Buffer.Clear();
                    nodes.Position = 0;

                    while (!stream.Eof())
                        hasMacro |= AnyWithMacros(stream, nodes);
                }
                while (hasMacro);
            }
            return true;
        }

So as you could see here, the Any rule processes until a line break occures from current position of the stream (while the directive rule that covers preprocessor directives does the same as those are bound to a full line in C++). This leads to a line by line tokenizing process but at expression level, not text level.

So taking a look at your comment expression example

/*Lorem ipsum dolor sit amet, consetetur sadipscing 
elitr, sed diam nonumy eirmod tempor invidunt ut 
labore et dolore magna aliquyam erat, sed diam voluptua.
At vero eos et accusam et justo duo dolores et ea rebum. 
Stet clita kasd gubergren*/

starts processing at stream position 0 and verifies a comment character as the first character in the Any expression. Checking all sub rules one by one lets the tokenizer stop at the comment expression that itself reroutes into the single line expression. This fails because the second character is a * character. The multiline comment expression matches and starts processing. It copies any contents to the token stream up to the line where */ occures and returns control back to the Any rule after it has copied the contents of this token into the token stream (I want to keep comments here to process them later)

The Any expression now breaks and continues the while loop until it has found a line break (where line breaks include the EOF state too).

This way you don't have to bother handling the stream line wise while you have full control and access over the position as same as line and column positions of tokens you find (I handle this in the line break expression rule by incrementing a counter for the line and store current stream position as the line index)

13 hours ago, Finalspace said:

I am writing a tokenizer right now to support syntax highlight in my editor, but with a special requirement: Incremental parsing.

Meaning that i get character ranges of text instead of full streams, but use the previous state to continue or replace tokens if needed.

All parser i have written in the past was using a full stream of text always, but this approach does not work for this case and i cannot find much about incremental parsing on the internet.

In compiler construction, the conversion of a text-stream to a token stream is known as scanning or tokenizing. Parsing is the process of converting a token-stream to a parse-tree by matching the grammar of the language against the tokens of the stream.

As such, incremental parsing is likely to point to how to rebuild parts of the tree given a partially changed token-stream, which sounds like a very complicated problem to me. No idea what can be done there and whether it's worth it.

Your problem would be named incremental scanning I think. I pondered about your question some months ago, and in theory, it can be solved by storing the start state of the scanner with a token (which is also the end-state of the scanner at the previous token). You insert your modified characters in the tokens, extending the range to token boundaries (text changes will typically not start at token boundaries but somewhere in the middle). That new piece is labeled "unknown text". The start state of the scanner is known for that piece, so you can set the scanner state, and start processing the piece, breaking up the piece in new tokens. At the end, you simply continue scanning until a) the tokenizer returns a token while the next character is in a next token (ie it ends exactly at an existing token boundary), and b) the state of the scanner at that point matches the start-state stored in the next token.

At that point the tokenizer is again in sync with the already found tokens, and you can stop scanning.

The problem is of course that you need to store scanner state with each token, which is very costly. For this reason, I now think about storing it at the start of a line only. Most of the edits are in a single line, and most lines are not that long, so scanning the entire line is not that bad. It does mean that you have to force the scanner to always return a token at the end of the line, possibly by having synthetic tokens like "part of a multi-line comment". I don't consider that to be a big problem (the number of tokens that may contain a newline is really small), and an editor needs to know precisely about white space tokens any way (unlike a compiler, so most scanner discard white-space and comments).

14 hours ago, Finalspace said:

- How do i detect to add/insert/delete/continue tokens? 

Don't use "token" as unit, use characters instead. Those are fixed in a line (or in a text stream even) between edits. See tokens as grouping of some characters, you draw boxes around characters that "belong together". Boxes may shift or vary in number or length between scans, characters don't change (much).

14 hours ago, Finalspace said:

- Is it easier when the range always starts at a line and ends at a line?

Not sure, I haven't reached the point I described above. For me it does, but also because I decided to base everything on lines in the editor, so it's a natural boundary to use for scanning.

Even then, I am far from sure this is all worth the trouble. If you think a little further, the next thing you want are the red and yellow squiggles indicating errors and warnings. (Or at least, I do.) To get those, you have to run a parser and a type checker as well (so you get semantic warnings and errors). Since incremental parsing is out, the only way to build a parse tree is to get all tokens from start to end for each type checker run. In other words, you have to walk over all text (or all tokens) very very often anyway, and build parse trees and do type checking computations. If you have to do that, it may be simpler to just make a copy of the token stream between the tokenizer and the parser.

You'd better forget about lines (compilers usually don't care much of lines too). Just process text token by token.

You need a state stack, and let me use "output" to indicate you change the token color for syntax highlighting. An "output" is not a state.

So assume you have the code

if(a == 1 /* comment */)
{
}

Your process may look like,

1. Output "if".

2. State stack: (

3. Output "a". Note if you want to give different color according to the context (such as a == 1 is different with a > 1), you need to add "a" to state stack too.

4. Output "==", "1", etc

5, State stack: (, /*

6, Output anything until "*/" since the stack top is "/*".

7. Get "*/"? Then pop the "/*“。

8. Get ")"? Pop the top "(". If the stack top is not "(", syntax error.

Same of "{" and "}".

You got a basic lexical parser.

There is a reason why i am asking this. I am using scintilla.net and this has a event called StyleNeeded, which gets called automatically when scintilla needs to re-highlight text, but you always get visible ranges.

Initially the first range you get is 0 to xxx, but when you start scroll down you get the next portion which isn´t highlighted yet.

But it gets worse when you random scroll in the editor, then the ranges are random of course.

The good thing about this, changes works the same. You get a range with only the changes plus some extra.

But i think i give up on this one and do full tokenize the entire source when there are any text changes and force to re-highlight everything. This is slow of course (1-2 secs for 70k lines of C-source) in C# but works. Doing all those headaches just for doing highlighting is do costly for me.

If you do the process in the background, and update the screen when it's done, it likely works sufficiently.

On 1/31/2019 at 4:18 PM, Alberth said:

If you do the process in the background, and update the screen when it's done, it likely works sufficiently.

Thats what i am doing right now, when there is text change i fire up a timer (500 msecs). When this timer executes, i start a background thread doing the tokenizing and then force a re-highlight of the entire text area. When i am in the process of typing in characters, the timer restarts. This works reasonably well, 200 msecs for doing full lexing of C (20 k lines) source and 50 msecs to do the highlighing.

Oh and i looked at the C# rosylin lexer code and they dont do "in the middle" parsing as well - so i am fine