Accession Number : AD0681131

Title :   MODELING DETERMINISTIC SYNTAX ANALYZERS BY REDUCTION PROCEDURES,

Corporate Author : RCA LABS PRINCETON N J

Personal Author(s) : Korenjak,Allen J. ; Walters,Daniel A.

Report Date : SEP 1968

Pagination or Media Count : 67

Abstract : Bottom-to-top parsers for arbitrary context-free grammars process input strings in exponential time, while parsers for the LR(k) grammars require only linear time. The broad objective of the present investigation is to determine the 'linearizing' features of LR(k) processors so that they can be used in a wider class of parsers. This report describes the results of the first part of this investigation. A model of the LR(k) parsing algorithm is developed in a reduction system which has been previously used to model parsing procedures. By comparing this model to one previously obtained for bottom-to-top parsers, the features of LR(k) grammars and their processors that allow the reduction in parsing time from exponential to linear are exhibited. (Author)

Descriptors :   (*CONTEXT FREE GRAMMARS, MATHEMATICAL MODELS), PROGRAMMING LANGUAGES, COMPILERS, SET THEORY, SYNTAX, ALGORITHMS

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE