AN EFFICIENT CONTEXT-FREE PARSING ALGORITHM,
Abstract
This paper describes a parsing algorithm for context-free grammars, which is of interest because of its efficiency. The algorithm runs in time proportional to n cubed (where n is the length of the input string) on all context-free grammars. It runs in time proportional to n squared on unambiguous grammars, and we actually show that it is n squared on a considerably larger class of grammars than this, but not on all grammars. These two results are not new, but they have been attained previously by two different algorithms, both of which require the grammar to be put into a special form before they are applicable. The algorithm runs in linear time on a class of grammars which includes LR(K) grammars and finite unions of them (and the LR(K) grammars include those of essentially all published algorithms which run in time n), and a large number of other grammars. These time n grammars in a practical sense include almost all unambiguous grammars, many ambiguous ones, and probably all programming language grammars. We present a method for compiling a recognizer from a time n grammar which runs much faster than our original algorithm would have, working directly with the grammar as it is recognized. We show some undecidability results about the class of grammars that are compilable by this method. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1968
- Accession Number
- AD0677685
Entities
People
- Jay Earley
Organizations
- Carnegie Mellon University