Younger, D. H.

Recognition and parsing of context-free languages in time n3


A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language. A special merit of this algorithm is that it is completed in a number of steps proportional to the "cube" of the number of symbols in the tested string. As a byproduct of the grammatical analysis, required by the recognition algorithm, one can obtain, by some additional processing not exceeding the "cube" factor of computational complexity, a parsing matrix--a complete summary of the grammatical structure of the sentence. It is shown that this simulation likewise requires a number of steps proportional to only the "cube" of the test string length.