Incremental LR Parsing

this paper we present an incremental LR parsing technique. The technique is applicable to all grammars in the LR, SLR, and LALR families. We present the technique in terms of the LR(1) grammars in this paper. The extension to other grammars should be obvious. An LR(1) parser maintains a stack of states, of which the top element is considered the current state of the parser. A state in the parse stack actually represents a subtree of the yet-to-be-built parse tree. Parsing operations are determined from the current state and the next look-ahead token. The parser performs two kinds of operations: shift and reduction. The shift operations correspond to state transitions on an LR(1) finite state machine [1]. As soon as the handl