<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
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.
linear grammars, size bounds, LR parser, double exponential upper bound, context-free grammars, Theory of compilers and interpreters, recursive grammars
linear grammars, size bounds, LR parser, double exponential upper bound, context-free grammars, Theory of compilers and interpreters, recursive grammars
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |