Accession Number:

AD0631692

Title:

AN EFFICIENT RECOGNITION AND SYNTAX-ANALYSIS ALGORITHM FOR CONTEXT-FREE LANGUAGES,

Descriptive Note:

Corporate Author:

ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1966-03-01

Pagination or Media Count:

52.0

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 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.

Subject Categories:

  • Humanities and History
  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE