Take the 2-minute tour ×

I once implemented an SLR parser generator that generates incremental parsers. The parser can parse a piece of text from beginning to end, but when you delete or insert text it does the minimal amount of work and minimal amount of changes in the token stream and syntax tree, instead of just reparsing everything from the beginning. The problem is I havn't been able to find any use of this? The parser does slightly more work than a normal parser. Is there any use of such a thing? PS. If you want to know how, google 'basics of compiler design diku', it's a free book, then all I had to do was to modify the algorithm a little bit so it stores the state of the parser everywhere, which is the extra work I mentioned above.

share|improve this question
Syntax-checking in editors? –  larsmans Nov 8 '10 at 13:05
"know how, google, its a free book" This phrase doesn't make any sense. Google for a book on SLR parsing? –  Ira Baxter Nov 8 '10 at 15:32
Oops, what I said was google "basics of compiler design diku" but instead of '"' I used the symbols, uhm '<' and '>' and I think they're probably going to disappear again. –  Dude Dawg Homie Nov 8 '10 at 19:37
Next time just edit your question so that the troublesome characters are removed. (I already did that for you). –  Ira Baxter Nov 8 '10 at 23:21
I thought about editing the question, but since someone comented on it it would be less confusing to leave the original that was comented on I thought. It's the funniest sentence of bad english I've accidentaly spoken that, well, that I remember anyway, today... –  Dude Dawg Homie Nov 9 '10 at 12:55

1 Answer 1

The obvious answer is support for a structured editor, in which what the editor holds is the AST rather then the text. This allows the editor to suggest how to continue editing when only a partial input is provided (e.g., after "while" keyword, the editor knows that "(" is necessary and can suggest it; it can put in a full "if" statement after just the keyword is provided, it can complain that entered syntax is wrong as you type, etc.)

There have been lots of such editors built, most of them not successful; people seem to love/hate editors that do this.

THe most advanced current project I know that does this is the Harmonia project at Berkeley. They use the big-brother version of your incremental parser: an incremental GLR parser.

share|improve this answer

Your Answer


