  We present a computational model for Parsing Expression Grammars (PEGs). The
predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A.
Birman and J. Ullman in the 1960-s, B. Ford showed in 2004 that both formalisms
recognize the same class named Parsing Expression Languages (PELs). A. Birman
and J. Ullman established such important properties like TDPLs generate any
DCFL and some non-context-free languages like $a^nb^nc^n$, a linear-time
parsing algorithm was constructed as well. But since this parsing algorithm was
impractical in the 60-s TDPLs were abandoned and then upgraded by B. Ford to
PEGs, so the parsing algorithm was improved (from the practical point of view)
as well. Now PEGs are actively used in compilers (eg., Python replaced
LL(1)-parser with a PEG one) so as for text processing as well. In this paper,
we present a computational model for PEG, obtain structural properties of PELs,
namely proof that PELs are closed over left concatenation with Boolean closure
of regular closure of DCFLs, and present an extension of the PELs class based
on the extension of our computational model. Our model is an upgrade of
deterministic pushdown automata (DPDA) such that during the pop of a symbol it
is allowed to return the head to the position of the push of the symbol. We
provide a linear-time simulation algorithm for the 2-way version of this model,
which is similar to the S. Cook famous linear-time simulation algorithm of
2-way DPDA.
