A Practical Method for Constructing LR(k) Processors

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.

CACM November, 1969

Korenjak, A. J.

LR(k) grammar, syntactic analysis, parser, deterministic
language, syntax-directed compiler, language
processor, context-free language ALGOL

4.12 5.2 5.23

CA691105 JB February 15, 1978  12:52 PM

1086	4	1825
1132	4	1825
1234	4	1825
1263	4	1825
1265	4	1825
1270	4	1825
1323	4	1825
1358	4	1825
1379	4	1825
1380	4	1825
1453	4	1825
1464	4	1825
1484	4	1825
1491	4	1825
1498	4	1825
1613	4	1825
1614	4	1825
1665	4	1825
1768	4	1825
1781	4	1825
1787	4	1825
1824	4	1825
1825	4	1825
1825	4	1825
1836	4	1825
1860	4	1825
1861	4	1825
2015	4	1825
2083	4	1825
2110	4	1825
2127	4	1825
2178	4	1825
2179	4	1825
2187	4	1825
2252	4	1825
2317	4	1825
2325	4	1825
2341	4	1825
2545	4	1825
2546	4	1825
2645	4	1825
2652	4	1825
2684	4	1825
2698	4	1825
2733	4	1825
2842	4	1825
2929	4	1825
2934	4	1825
3069	4	1825
669	4	1825
679	4	1825
691	4	1825
761	4	1825
949	4	1825
989	4	1825
1781	5	1825
1825	5	1825
1825	5	1825
1825	5	1825
2061	5	1825
2179	5	1825
3184	5	1825
1140	6	1825
1141	6	1825
1477	6	1825
1477	6	1825
1491	6	1825
1491	6	1825
1825	6	1825
1825	6	1825
2015	6	1825
2110	6	1825
3184	6	1825
773	6	1825