Back to Search
Start Over
The computational power of parsing expression grammars.
- Source :
-
Journal of Computer & System Sciences . Aug2020, Vol. 111, p1-21. 21p. - Publication Year :
- 2020
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PARSING (Grammar)
*TURING machines
*PALINDROMES
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 111
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 142393724
- Full Text :
- https://doi.org/10.1016/j.jcss.2020.01.001