Optimal incremental parsing

Reviewer: Frank Lawrence Friedman

The author describes how an incremental parser driven by LALR(1) tables can achieve optimal reuse of internal representations of parsed strings with the same time complexity as an exhaustive parser. Two definitions of optimality are used: maximum node reuse, and minimal subtree substitution in response to substring text substitution. It is shown how an incremental LALR(1) parser can either map a substring to a minimal subtree substitution or maximize node reuse while reparsing after such a substitution. The discussions of the minimal subtree substitution and maximal node reuse mechanisms are based on manipulations of threaded trees, as described in earlier works on incremental parsing. The trees, augmented with attribute values, are viewed as a typical form of parser output usable by other modules of a complete compiling system. The optimality and correctness proof outlines given in the paper are based entirely on the properties of the threaded tree data structure. These trees provide the ability to better see relations between derivations (as relations between threaded trees), which is necessary to describe incremental changes in a natural way. Optimality in the substring-to-subtree mapping assumes the existence of well-formed sentences in all cases, and the proof is based on finding the optimal grafting point using a lazy nearest common ancestor computation. Maximal node reuse is shown to be achievable using the same basic concepts and “essentially the same procedures” as those used for minimal subtree substitution. Algorithm costs are shown to be proportional to the length of the program being analyzed. The author appears to have a good command of the full scope of the literature on the subjects discussed, and goes to reasonable lengths to position the contribution of this paper in light of previous results. Aside from works by the author, there are no citations of papers published between 1991 and 1995.