Regular look-ahead and look-back for lr parsers
Manuel E. Bermudez · 1984
A problem that arises when building bottom-up parsers with LR(k) techniques is that the LR(k) characteristic automaton is frequently nondeterministic. A common approach to the problem of eliminating this nondeterminism is to use a look-ahead scheme. In this dissertation we develop a general model for look-ahead LR techniques, which also incorporates parse-time look-back on the state stack of the LR(0) parser. The method consists of constructing finite-state machines to recognize regular supersets of the context-free look-ahead and look-back languages. We describe several different ways to accomplish this. These choices are incorporated as parameters to the model, along with other parameters that define whether finite or arbitrary look-ahead and/or look-back will take place at parse-time. Manipulating these parameters yields a total of forty-two look-ahead LR grammar classes. We prove here that among these are all the significant well-known techniques such as LALR(k) (DeR{69}), SLR(k) (DeR{71}), NQLALR(1) (D&P{82}) and LRR(C&C{73}). The relationships among these forty-two grammar classes are exhaustively examined.