<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>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Derivatives of Parsing Expression Grammars

Name: Derivatives of Parsing Expression Grammars
Creator: Aaron Moss
Keywords: FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Electronic computers. Computer science, QA1-939, 0202 electrical engineering, electronic engineering, information engineering, Computer Science - Formal Languages and Automata Theory, QA75.5-76.95, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 21 Aug 2017Embargo end date: 01 Jan 2014Publisher:Open Publishing AssociationJournal:Electronic Proceedings in Theoretical Computer Science, volume 252, pages 180-194 (eissn: 2075-2180,

Authors: Aaron Moss;

doi: 10.4204/eptcs.252.18 , 10.48550/arxiv.1405.4841

arXiv: http://arxiv.org/abs/1405.4841

Derivatives of Parsing Expression Grammars

- Summary
- Subjects
- Related research
  (1)
- Metrics

Abstract

This paper introduces a new derivative parsing algorithm for recognition of parsing expression grammars. Derivative parsing is shown to have a polynomial worst-case time bound, an improvement on the exponential bound of the recursive descent algorithm. This work also introduces asymptotic analysis based on inputs with a constant bound on both grammar nesting depth and number of backtracking choices; derivative and recursive descent parsing are shown to run in linear time and constant space on this useful class of inputs, with both the theoretical bounds and the reasonability of the input class validated empirically. This common-case constant memory usage of derivative parsing is an improvement on the linear space required by the packrat algorithm.

In Proceedings AFL 2017, arXiv:1708.06226

Related Organizations

University of Waterloo
Canada

Keywords

FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Electronic computers. Computer science, QA1-939, Computer Science - Formal Languages and Automata Theory, QA75.5-76.95, Mathematics

1 Research products, page 1 of 1

egg software on GitHub
IsRelatedTo

Impact byBIP!

	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).	4
	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