Thumbnail
Access Restriction
Subscribed

Author Korenjak, A. J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Syntax-directed compiler ♦ Lr(k) grammar ♦ Context-free language ♦ Syntactic analysis ♦ Algol ♦ Deterministic language ♦ Language processor ♦ Parser
Abstract A practical method for constructing LR(k) processors is developed. These processors are capable of recognizing and parsing an input during a single no-backup scan in a number of steps equal to the length of the input plus the number of steps in its derivation.The technique presented here is based on the original method described by Knuth, but decreases both the effort required to construct the processor and the size of the processor produced. This procedure involves partitioning the given grammar into a number of smaller parts. If an LR(k) processor can be constructed for each part (using Knuth's algorithm) and if certain conditions relating these individual processors are satisfied, then an LR(k) processor for the entire grammar can be constructed for them. Using this procedure, an LR(1) parser for ALGOL has been obtained.
Description Affiliation: RCA Labs., Princeton, NJ (Korenjak, A. J.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 12
Issue Number 11
Page Count 11
Starting Page 613
Ending Page 623


Open content in new tab

   Open content in new tab
Source: ACM Digital Library