Upper bounds on the size of LR(k) parsers (Q1062769)

The size of an LR(k) parser essentially depends on the number of different LR(k) tables or states of the parser which is always bounded by y \(2^{| G|^{k+1}}\). However, it appears to be rather difficult to prove that this or any other double exponential upper bound is strict. In this paper, the author shows that such a bound is too conservative for many important subclasses of context-free grammars. In particular, it is shown that for non-right recursive grammars the number of LR(k) states is at most \(| G|^{k| G|}\). \(2^{| G|}\). Some other classes such as the left linear and the right linear grammars are also analyzed. Examples of grammars with large LR(k) parsers are given.