Noncanonical LALR(1) parsing

This paper addresses the longstanding problem of the recognition lim-itations of classical LALR(1) parser generators by proposing the usage of noncanonical parsers. To this end, we present a definition of noncanon-ical LALR(1) parsers, NLALR(1). The class of grammars accepted by NLALR(1) parsers is a proper superclass of the NSLR(1) and LALR(1) grammar classes. Among the recognized languages are some nondeter-ministic languages. The proposed parsers retain many of the qualities of canonical LALR(1) parsers: they are deterministic, easy to construct, and run in linear time. We argue that they could provide the basis for a range of powerful noncanonical parsers