ANTLR 3 to have inbuilt Incremental Parsing functionality
Friday, February 17, 2006
Havent blogged in a while, have I? Well here goes then.
Lets talk a little about ANTLR 3. I guess a lot of people use ANTLR generated parsers in IDEs. And as we all know, you can make an IDE go real fast if you have an incremental parser instead of the regular one.
For those who dont know, an incremental parser parses only those parts of the file which have changed since the last time it was edited. This is a huge advantage in IDEs, especially when you have large files open, cause you dont want to parse the entire file from top to bottom every time a user types a single key.
But making an incremental parser out of the one generated by ANTLR is pretty tough. As a matter of fact there were no known algorithms for making an incremental parser out of a recursive descent parser (which is what ANTLR generates). You notice the word 'were', instead of 'are'. Yes, there is an algorithm for doing so now. Actually it was stumbled upon by yours truly, when I was designing ANTLR Studio's editor.
The algorithm is already implemented in ANTLR Studio. It is what makes all the cool stuff like TypeOnce in the editor possible.
So I had a talk with Terence and guess what, we are implementing this functionality in ANTLR 3. So in ANTLR 3 all you will have to do is put in an option like '
For those who cant wait till the release of ANTLR 3 (which is still a long way away), I will be publishing a paper on the algorithm along with Terence in a few weeks. So you will be able to implement an incremental parser with ANTLR 2 too.
Lets talk a little about ANTLR 3. I guess a lot of people use ANTLR generated parsers in IDEs. And as we all know, you can make an IDE go real fast if you have an incremental parser instead of the regular one.
For those who dont know, an incremental parser parses only those parts of the file which have changed since the last time it was edited. This is a huge advantage in IDEs, especially when you have large files open, cause you dont want to parse the entire file from top to bottom every time a user types a single key.
But making an incremental parser out of the one generated by ANTLR is pretty tough. As a matter of fact there were no known algorithms for making an incremental parser out of a recursive descent parser (which is what ANTLR generates). You notice the word 'were', instead of 'are'. Yes, there is an algorithm for doing so now. Actually it was stumbled upon by yours truly, when I was designing ANTLR Studio's editor.
The algorithm is already implemented in ANTLR Studio. It is what makes all the cool stuff like TypeOnce in the editor possible.
So I had a talk with Terence and guess what, we are implementing this functionality in ANTLR 3. So in ANTLR 3 all you will have to do is put in an option like '
incremental=true' in the grammar file and voila, it will generate a full fledged incremental parser for you!For those who cant wait till the release of ANTLR 3 (which is still a long way away), I will be publishing a paper on the algorithm along with Terence in a few weeks. So you will be able to implement an incremental parser with ANTLR 2 too.
3 Comments:
commented by Anonymous, 7:55 PM, February 22, 2006
Great work on the ANTLR eclipse plugin Prashant, and especially on the incremental compilation.
And I'll go ahead and comment on your two previous blog entries two. Swing still sucks and most likely always will and yes, Half-life 2 activation bites.
commented by , 6:15 AM, February 23, 2006
Hello,
Is there any description of used algorithm?
(Algorithm for making an incremental parser I mean)
happy
(excuse my poor english)
commented by , 9:55 PM, March 14, 2006
Be sure to announce it on you blog, and not only on antlr.org