  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).
  Using this characterisation we show that:
  (*) PEGs have unexpected power and semantics. We present several PEGs with
surprising behaviour, and languages which, unexpectedly, have PEGs, including a
PEG for the language of palindromes whose length is a power of two.
  (*) PEGs are computationally `universal', in the following sense: take any
computable function $f:\{0,1\}^\ast\to \{0,1\}^\ast$; then there exists a
computable function $g: \{0,1\}^\ast \to \mathbb{N}$ such that $\{ f(x)
\#^{g(x)} x \mid x \in \{0,1\}^\ast \}$ has a PEG.
  (*) There can be no pumping lemma for PEGs. There is no total computable
function $A$ with the following property: for every well-formed PEG $G$, there
exists $n_0$ such that for every string $x \in \mathcal{L}(G)$ of size $|x| \ge
n_0$, the output $y = A(G, x)$ is in $\mathcal{L}(G)$ and has $|y| > |x|$.
  (*) PEGs are strongly non real-time for Turing machines. There exists a
language with a PEG, such that neither it nor its reverse can be recognised by
any multi-tape online Turing machine which is allowed to do only $o(n/\log n)$
steps after reading each input symbol.
