<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>
doi: 10.1007/bf00263764
In this paper we show how one can improve upon an algorithm by Aho and Ullman [3] for eliminating unit productions from an LR(k) parser so that the elimination concerned can be made in all cases, instead of only in the special case required by [3] where no two unit productions have the same left-hand side. In most practical grammars this special case does not in fact arise. Since the elimination of unit productions both reduces the size of the parser and increases its speed, it is of value to have a general method for achieving this objective. The algorithm provided eliminates from the parser all nonterminals that occur as left-hand sides of unit productions. This substantially contributes to the reduction in size obtained, and also provides a solution to an open problem by Aho and Ullman [3]. An application of the Algorithm to the parser construction method of Pager [19] is considered, and a method is provided for the use of default reductions and the elimination of final states in conjunction with the elimination of unit reductions. The sizes of the parsers obtained using the parser's algorithm are compared with those of Anderson, Eve, and Horning [4].
General topics in the theory of software, Formal languages and automata
General topics in the theory of software, Formal languages and automata
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). | 19 | |
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). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |