Dynamic Parsing..

I have the following "dynamic" parsing problem. I would be greatly
obliged if someone could tell me if this problem has been solved, or point
to literature where I can find ways to solve it.


The problem is one of "dynamic" parsing.


Let G be a context free grammar <V,T,P,S>, and let x be a string in T^*
which is in L(G). Let p(x,G) denote the parse of x wrt G.


Define the following binary relation among strings x,y in T^* as follows.


x \approx y if (\exists u,v,w) |v| >= 1, ((( x = uvw) and (y = uw)) or
((x = uw) and (y = uvw))).


Basically I get y from x by either
1. deleting some substring v of x or
2. adding a string v to x somewhere.


The problem I have is, given a grammar G, a string x such that x \in L(G),
p(x,G) being the parse of x, and a string y such that x \approx y, I want
to decide if y is in L(G), and construct the parse of y if y is in L(G).
I want to do this without parsing y "from scratch". I want to just
"modify" those portions of the parse of x which need to be changed to get the
parse of y.


Any pointers would be really welcome. I would guess people working in
incremental compilers would be interested in this problem.


thanks a bunch..


cheers,
Kannan
--

Return to the comp.compilers page.
Search the comp.compilers archives again.