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