AN INCREMENTAL LL(1) PARSING ALGORITHM

Abstract

Given a parse tree for a sentence xzy and a string zBAR, an incremental parser builds the parse tree for the sentence xzyBAR by reusing as much of the parse tree for xzy as possible. The incremental LL(1) parsing algorithm in this paper makes use of a break-point table to identify reusable subtrees of the original parse tree in building the new parse tree. The break-point table may be computed from the grammar.