Projects top banner

The computational power of parsing expression grammars

Journal of Computer and System Sciences

Article

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/(log⁡n)2) steps of computation per input symbol. © 2020

B Loff

N Moreira

Publication

Year of publication: 2020

Identifiers

ISSN: 0022-0000

Other: 2-s2.0-85079405991

Locators

Alternative Titles

Preprint

File