The computational power of parsing expression grammars

• Tipo: Artigo em Revista Científica Internacional
• Data: 2020

Autores

Loff, B (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: Journal of Computer and System Sciences

Vol. 111

Páginas: 1-21

ISSN: 0022-0000

Editora: Elsevier

Indexação

ISI Web of Knowledge - 7 Citações

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-00R-P8H

DOI: 10.1016/j.jcss.2020.01.001

Abstract (EN): We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally "universal", in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(logn)(2)) steps of computation per input symbol. (C) 2020 Published by Elsevier Inc.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 21