Non-canonical parsing

Although the field of "canonical parsing" (i.e. parsing in which we always reduce the leftmost phrase of a sentential form) has been extensively studied, the field of non-canonical parsing has been relatively untouched, In this paper, we first motivate the whole study by presenting a language which is intrinsically non-canonical and then we develop a general model of bottom-up parsing which incorporates the capability of making non-canonical reductions. These parsers have the important properties of operating in linear time and of being implementable on "traditional" automata. Finally, in section 3 we extend several existing parsing methods to utilize our ideas and examine the relationships between the various classes so produced.