Accession Number:

AD0677685

Title:

AN EFFICIENT CONTEXT-FREE PARSING ALGORITHM,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1968-08-01

Pagination or Media Count:

148.0

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 LRK grammars and finite unions of them and the LRK 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

Subject Categories:

  • Linguistics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE