The computational power of parsing expression grammars

• Type: Article in International Scientific Journal
• Date: 2020

Authors

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

Journal

Title: Journal of Computer and System Sciences

Vol. 111

Pages: 1-21

ISSN: 0022-0000

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 7 Citations

Scopus - 7 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 21