AN EFFICIENT RECOGNITION AND SYNTAX-ANALYSIS ALGORITHM FOR CONTEXT-FREE LANGUAGES,
ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
An efficient algorithm of recognition and syntax-analysis for the full class of context-free languages without the difficulty of exponential growth of computing time with the length n of input sequence is presented. 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 cubed - recognizable in the sense of Hartmanis and Stearns by a double-tape or double-head single-tape Turing machine and it is n to the 4th power - recognizable by a single-head single-tape Turing machine. The size of memory required for recognition is proportional to n squared. If we use a random-access memory whose size is proportional to n squared, the computing time required for syntax-analysis is upper-bounded by C sub 1 n cubed C sub 2 n squared N, where N denotes the number of non-equivalent valid derivation sequences for a given input sequence and C sub is are constants independent of input sequences. If we use two tapes of length C sub 3 n squared and two tapes of length C sub 4 n as working memories, the computing time for syntax-analysis is upper-bounded by n cubed C sub 5 C sub 6 N.
- Humanities and History
- Computer Programming and Software
- Computer Hardware