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.

Cascades of two-input, one-output general function cells have been studied previously with the restriction that no external variable may drive more than one cell. Upon relaxing this restriction, it is shown that a variable that drives more than one cell in a cascade need never drive more than one cell that is not an EXCLUSIVE-OR cell, and that cell must be the first cell driven by the variable in the cascade. From this it follows that there exists a canonical form for cellular cascades with repeated inputs. Furthermore, the length of a cascade required to produce an n-variable function is bounded by (n2+n-4)/2, and there are functions that meet this bound for all n. Derived from knowledge of the canonical form, a realizability and synthesis algorithm is described that is an extension of previously described algorithms. The algorithm has been used to test the 402 Harvard functions, and a table of minimal-length cascades of realizable functions is included in the paper. Although the number of realizable functions is greatly increased when the input restriction is relaxed, it is shown that the fraction of n-variable functions that are realizable becomes vanishingly small as n grows large. In particular, for example, of the 2n+1symmetric functions of n-variables, precisely 12 are realizable for all n≥3.