Extended LALR(1) Parsing

Abstract

We identify a class of context-free grammars, called the extended LALR(1) (ELALR(1)), which is a superclass of LALR(1) and a subclass of LR(1). Our algorithm is essentially a smarter method for merging similar states in the LR(1) state machines. LALR(1) would merge every pair of similar states. In contrast, our algorithm merges a pair of similar states only if no (reduce-reduce) conflicts will be created. Thus, when no conflicts occur, our algorithm produces exactly the same state machines as the LALR(1) algorithm. However, when the LALR(1) algorithm reports conflicts, our algorithm may still produce a (larger) conflict-free state machine. In the extreme case when no states can be merged, our algorithm simply returns the original LR(1) machines. An important characteristic of the ELALR(1) algorithm is that there is no backtracking. On the other hand, the ELALR(1) algorithm does not guarantee the minimum state machines.