Simplified Parsing Expression Derivatives

This paper presents a new derivative parsing algorithm for parsing expression grammars; this new algorithm is both simpler and faster than the existing parsing expression derivative algorithm presented by Moss [12]. This new algorithm improves on the worst-case space and runtime bounds of the previo...

Descripción completa

Detalles Bibliográficos
Autor principal: Moss, Aaron
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206630/
http://dx.doi.org/10.1007/978-3-030-40608-0_30
_version_ 1783530446915633152
author Moss, Aaron
author_facet Moss, Aaron
author_sort Moss, Aaron
collection PubMed
description This paper presents a new derivative parsing algorithm for parsing expression grammars; this new algorithm is both simpler and faster than the existing parsing expression derivative algorithm presented by Moss [12]. This new algorithm improves on the worst-case space and runtime bounds of the previous algorithm by a linear factor, as well as decreasing runtime by about half in practice.
format Online
Article
Text
id pubmed-7206630
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066302020-05-08 Simplified Parsing Expression Derivatives Moss, Aaron Language and Automata Theory and Applications Article This paper presents a new derivative parsing algorithm for parsing expression grammars; this new algorithm is both simpler and faster than the existing parsing expression derivative algorithm presented by Moss [12]. This new algorithm improves on the worst-case space and runtime bounds of the previous algorithm by a linear factor, as well as decreasing runtime by about half in practice. 2020-01-07 /pmc/articles/PMC7206630/ http://dx.doi.org/10.1007/978-3-030-40608-0_30 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Moss, Aaron
Simplified Parsing Expression Derivatives
title Simplified Parsing Expression Derivatives
title_full Simplified Parsing Expression Derivatives
title_fullStr Simplified Parsing Expression Derivatives
title_full_unstemmed Simplified Parsing Expression Derivatives
title_short Simplified Parsing Expression Derivatives
title_sort simplified parsing expression derivatives
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206630/
http://dx.doi.org/10.1007/978-3-030-40608-0_30
work_keys_str_mv AT mossaaron simplifiedparsingexpressionderivatives

Ejemplares similares