Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Non-Canonical Extensions of Bottom-Up Parsing Techniques

Non-Canonical Extensions of Bottom-Up Parsing Techniques

File(s)
75-226.pdf (1.69 MB)
75-226.ps (792 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6913
Collections
Computer Science Technical Reports
Author
Szymanski, Thomas G.
Williams, John H.
Abstract

A bottom-up parsing technique which can make non-leftmost possible reductions in sentential forms is said to be non-canonical. Nearly every existing parsing technique can be extended to a non-canonical method which operates on larger classes of grammars and languages than the original technique. Moreover, 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.

Date Issued
1975-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-226
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance