Efficient Incremental Parsing for Context-Free Languages
Manuel Vilares Ferro
Ph.D. dissertation at University of Nice-Sophia Antipolis
Abstract
An incremental parsing algorithm based on dynamic programming
techniques is described. The analyzer takes a general class of
context-free grammar as drivers, and any finite string as input. Given
an input string that has been modified, the algorithm cuts out the
parts of the old analysis that had been generated by the parts of the
input that changed. What remains are the parts of the analysis that
were generated by the stable part of the input. The new system has
been baptized ICE, after Incremental Context-Free
Environment.
Summing it up, the ICE system described in this thesis is a
generator of parsers for context-free languages, including the
possibility of incremental facilities. The final result, is the
attainment of a tool that in an empirical comparison appears to be
superior to the others context-free analyseurs and comparable to the
standard generators of deterministics parsers, when the input string
is not ambiguous.
Keywords: Context-Free Parsing, Dynamic
Programming, Earley Parsing, Incremental Parsing, Parse Forest,
Push-Down Automata.
This work was managed by B.Lang,
leader of the ChLoE project at INRIA. It was
partially supported by the Eureka
Software Factory project, and integrally developed at
the INRIA site of Rocquencourt, France.
Manuel Vilares Ferro /
vilares@dc.fi.udc.es