Efficient incremental parsing for context-free languages

Abstract

An incremental parsing algorithm based on dynamic programming techniques is described. The analyzer takes the automaton generated from a general class of context-free grammars as driver, 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 has 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. In an empirical comparison, ICE appears to be superior to the other context-free analyzers and comparable to standard deterministic parsers, when the input string is not ambiguous.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>