Tue, 14 Dec 1993 14:54:51 GMT

Related articles |
---|

Dynamic Parsing.. govin-k@cs.Buffalo.EDU (Kannan Govindarajan) (1993-12-14) |

Re: Dynamic Parsing.. mauney@adm.csc.ncsu.edu (1993-12-15) |

re: Dynamic Parsing.. bdarr@atr-2s.hac.com (1993-12-16) |

Newsgroups: | comp.compilers |

From: | Kannan Govindarajan <govin-k@cs.Buffalo.EDU> |

Keywords: | parse, question |

Organization: | Compilers Central |

Date: | Tue, 14 Dec 1993 14:54:51 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.