Efficient LR(1) processor construction

Strings from LR(k) grammars can be recognized and parsed in linear time by a processor that is directed by a pre-computed parsing table. This paper deals with two questions of practical importance: the effort required to generate an LR(k)parsing table for a grammar and the size of the table generated. Knuth has described an algorithm for checking an arbitrary context-free grammar for the LR(k) condition and producing a parsing table, if possible. The time-complexity of this algorithm and the size of the table it produces are each exponential functions of the grammar size. Thus, for very large grammars — such as those defining the syntax of a programming language — it is not feasible to use this algorithm directly.

This paper presents a practical method of checking large cfgs for the LR(1) condition and generating the corresponding parsing table. It significantly decreases both the computation required to produce the parsing table and the size of the resulting table. It operates as follows. The given grammar G is partitioned into a number of parts. Each part is checked for LR(1)-ness and individual parsing tables are generated, using the Knuth algorithm. Certain conditional modifications to these tables are then made; if the conditions are satisfied, the grammar G is LR(1) and the modified tables can be combined into a single parsing table for G. Because of the exponential nature of the Knuth algorithm, this process of partitioning, computing and combining can greatly improve the efficiency of the table generation procedure.

Using this method LR(1) parsers for a number of programming languages, including ALGOL, have been constructed. The empirical evidence obtained has verified the efficacy of this method: in one programming language example, table construction time was reduced by a factor of nine and the table size was reduced by a factor of three.