Context-free language processing in time n3
Daniel H. Younger · Annual Symposium on Switching & Automata Theory · 1966
Three problems in language processing are the recognition of strings that are sentences of a given language, the parsing of sentences according to a given grammar, and the syntax-directed translation of sentences in one language to those in another. Limiting our attention to context-free languages, we consider first the simplest of these problems--recognition. A procedure is given whereby for an arbitrary string of length n and a specification of a context-free grammar, the string is recognized as generated by that grammar or not; the time, i.e. number of steps, required by this algorithm is proportional to n3. For a linear or metalinear grammar, this procedure is simplified to yield recognition in time Kn2. The algorithm for recognition is then extended to procedures for parsing and syntax-directed translation.