AN EFFICIENT RECOGNITION AND SYNTAX-ANALYSIS ALGORITHM FOR CONTEXT-FREE LANGUAGES,
Abstract
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 i's 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).
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1966
- Accession Number
- AD0631692
Entities
People
- T. Kasami
Organizations
- University of Illinois Urbana–Champaign