Noncanonical Extensions of LR Parsing Methods

Bottom up LR-parsing is the most powerful, practical method of linear time parsing known. Various attempts have been made to enhance the power and flexibility of the LR method, without losing the property of linear time parsing, or introducing inordinately large constant factors which prohibit practicality. In this paper, we survey the particular line of this work which adds power through allowing noncanonical operation of the LR parser --- reducing non-leftmost phrases. We show that for some natural extensions, the use of noncanonical parsing is beneficial in enlarging the class of accepted grammars or languages, while for others, the class of resulting grammars constitute a non-recursive set. The original goal of this work was to investigate the particular class of grammars parsable by noncanonical LR parsers using LALR lookahead. Unfortunately, this particular class of grammars is not believed to be recursively enumerable in its full generality. However, by weakening the noncanonica..