Non-canonical parsing

1 October 1973

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02724847,p. 122-129
https://doi.org/10.1109/swat.1973.16

Abstract

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.

Keywords

This publication has 4 references indexed in Scilit:

Bounded context parsable grammars
Information and Control, 1975
LR-regular grammars An extension of LR(k) grammars
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1971
Total Precedence Relations
Journal of the ACM, 1970
On the translation of languages from left to right
Information and Control, 1965