An efficient algorithm of recognition and syntax-analysis for the full class of context-free languages without the difficulty of exponen¬tial growth of computing time with the length a of input sequence is pre¬sented. This algorithm makes use of a fundamental algebraic property of a context-free language. It is shown in this paper that a context-free language is n-recognizable in the sense of Hartmanis and Stearns by a double-tape or double-head single-tape Turing machine and it is n4 recognizable by a single-head single-tape Turing machine. The size of memory required for recognition is proportional to n2. If we use a'random-access memory whose size is proportional to n2, the computing time required for syntax-analysis is upper-bounded by C1n3 + C2n2N, where N denotes the number of non-equivalent valid derivation sequences for a given input se¬quence and Cis are constants independent of input sequences. If we use two tapes of lengthC3n2 and two tapes of length C4n as working memories, the computing time for syntax-analysis is upper-bounded by n3 (C5 + C 6N)
展开▼
