<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>
handle: 11311/815321
For the deterministic context-free languages, we compare the space and time complexity of their LR (1) parsers, constructed in two different ways: the classic method by Knuth [7] for BNF grammars, and the recent one by the authors [2], which directly builds the parser from EBNF grammars represented as transition networks. For the EBNF grammars, the classic Knuth’s method is indirect as it needs to convert them to BNF. We describe two parametric families of formal languages indexed by the number of stars, which exhibit a linear growth of the parser size (number of states) in passing from the classic to our novel direct methods. Experimental measurements of the number of parser states and of the parsing speed for two real languages (Java and JSON) confirm the advantage of the new direct parser model for EBNF grammars.
extended BNF grammar; EBNF; LR(1); ELR(1); transition network; TN; shift-reduce; bottom-up parser; parsing performance
extended BNF grammar; EBNF; LR(1); ELR(1); transition network; TN; shift-reduce; bottom-up parser; parsing performance
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). | 1 | |
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 |