Accession Number:

AD0681131

Title:

MODELING DETERMINISTIC SYNTAX ANALYZERS BY REDUCTION PROCEDURES,

Descriptive Note:

Corporate Author:

RCA LABS PRINCETON N J

Personal Author(s):

Report Date:

1968-09-01

Pagination or Media Count:

67.0

Abstract:

Bottom-to-top parsers for arbitrary context-free grammars process input strings in exponential time, while parsers for the LRk grammars require only linear time. The broad objective of the present investigation is to determine the linearizing features of LRk 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 LRk 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 LRk grammars and their processors that allow the reduction in parsing time from exponential to linear are exhibited. Author

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE