Efficient LR(1) processor construction
A. J. Korenjak · 1969
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.