MODELING DETERMINISTIC SYNTAX ANALYZERS BY REDUCTION PROCEDURES,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1968
- Accession Number
- AD0681131
Entities
People
- Allen J. Korenjak
- Daniel A. Walters
Organizations
- RCA Corporation