Noncanonical Extensions of Bottom-Up Parsing Techniques
Thomas G. Szymanski, John H. P. Williams · SIAM Journal on Computing · 1976
A bottom-up parsing technique which can make nonleftmost possible reductions in sentential forms is said to be noncanonical Nearly every existing parsing technique can be extended to a noncanonical method which operates on larger classes of grammars and languages than the original technique. Moreover, most of the resulting parsers run in time linearly proportional to the length of their input strings. Several such extensions are defined and analyzed from the points of view of both power and decidability. The results are presented in terms of a general bottom-up parsing model which yields a common decision procedure for testing membership in many of the existing and extended classes.