Incremental parsing of expressions

In syntax-directed editors, the user edits some object on the screen according to the structure of that object. The appearance of the object is derived from some internal representation maintained by the editor. If the object is an expression, the editor maintains a tree-representation internally. During editing of an expression, a minor change in the appearance of an expression (e.g., ab × c is to be changed into a + b ×c) may necessitate a significant restructuring of this tree-representation. This article describes an algorithm that incrementally adjusts the tree-representation of an expression, while the user edits the expression in terms of its appearance rather than in terms of tree-transformations.