[antlr-interest] Incremental Parsing

mrosgood mrosgood at yahoo.com
Wed Oct 9 17:48:33 PDT 2002

Hi Brian Smith-

You wrote:

> Not coincidently, tonight I am researching incremental GLR, 
> LR(k), and LL(k) incremental parsers. Most research in 
> this area seems to be on LR(k) and in particular LALR(1) 
> grammars, but I'm interested in learning whether it is 
> possible to use top-down recursive decent predicated LL(k) 
> parsers (a.k.a ANTLR) for incremental parsing.
> So if anybody has any more links or references in this 
> area...

Yea, an algorithm for incremental LL(k) parsing would be most cool.  
Then I wouldn't have to scrap my ANTLR grammars! <grin>

Below are the references I found (all LR, sorry).  

This exercise has been frustrating in a couple of ways.  There's no 
source code to be found.  I get the impression that there's duplicate 
research effort (there's few cross-citations).  Few academic papers 
have the good sense to contain publications dates.  Groups tend to 
use different words for the same thing (e.g. structure editors, 
language-based editors, syntax-aware editors, incremental parsing, 
etc.).  Some of the papers aren't available online.  And, the worst 
offense of all, authors aren't taking advantage of CiteSeer.


Hey, good luck with your efforts.  Holler if you need help.  (I'm in 
way over my head with this stuff.)

Cheers, Jason Osgood


Incremental LR Parsing (1996)
Wuu Yang

Incremental Attribute Evaluation of LR-attributed grammars Using 
Space-Efficient Data Structure (2000)
Hisashi Kakai, Masataka Sassa, Kiroaki Kameyama, Ikuo Nakata
3rd Workshop on Attribute Grammars and their Applications WAGA2000
(can't find link)

Incremental attribute evaluation without parse trees
Hiroaki Kameyama Hisashi Nakai, Masataka Sassa and Ikuo Nakata. 

A new approach to incremental LR parsing (1997)
Warren X. Li (Software Verification Research Centre)

An Incremental Lr Parse Strategy for Language-Based Editors
Phil Cook, Jim Welsh (Software Verification Research Centre)

Incremental Parsing in language-based editors: user needs and how to 
meet them
Phil Cook, Jim Welsh (Software Verification Research Centre)
Software - Practice & Experience, Vol 21 Dec 2001
(not available online)

This site has all the familiar publications by Tim A. Wagner, Susan 
L. Graham, and Marat Boshernitsan:


Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

More information about the antlr-interest mailing list