re: Dynamic Parsing..

>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.


          Interesting. Well, just off the cuff...
It seems like you could have attributes for each nonterminal (in V),
call them 'begin' and 'end' for example, that point to positions in
the input string, x, where the beginning and end of each symbol
occurr. An SDD to compute these attributes should be fairly
straightforword. Then, when a modification is made to x to produce
y, you would know that symbols which end before the modification
point, or begin after the modification point do not need to be
reparsed. Simply reparse the parts of the tree that do not meet this
condition. This even works for translation schemes with inherrited
attributes, I think, because you can take the inherrited attributes
into account when computing 'begin' and 'end'.
          Starting with this approach, it seems like other optimizations
are begged. For example, how about: when deciding which symbols to
reparse, just consider certain major symbols that are strategically
fit to such a purpose, rather than every symbol in the tree. For
example, in a Pascal-like language, maybe you could use simple
statements as the designated 'delta' symbol - rather than worry about
weather to reparse each subpart of a statement, just reparse the
whole statement.
          Anyway, this is my $.02, and it is not long considered and
obviously lacks detail -- a lot of the implementation depends on your
parsing technique (top-down, bottom-up, and other characteristics).
Well, I hope this helped but maybe I'm just pointing out the obvious,
in which case you can SUE ME :).


______________________________________________________________________________
                                              |
Byron C. Darrah | bus. mail: attn: Byron C. Darrah, Mail Station: B223
PHONE: (714) 732-9381 | Hughes Aircraft Company, GSD.
FAX: (714) 732-1953 | 1901 W. Malvern Ave.
bdarr@atr-2s.hac.com | Fullerton, California, USA
                                              | 92634
--

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