  CPEG is an extended parsing expression grammar with regex-like capture
annotation. Two annotations (capture and left-folding) allow a flexible
construction of syntax trees from arbitrary parsing patterns. More importantly,
CPEG is designed to guarantee structural constraints of syntax trees for any
input strings. This reduces the amount of user code needed to check whether the
intended elements exist.
  To represent the structural constraints, we focus on regular expression
types, a variant formalism of tree automata, which have been intensively
studied in the context of XML schemas. Regular expression type is inferred from
a given CPEG by the type inference that is formally developed in this paper. We
prove the soundness and the uniqueness of the type inference. The type
inference enables a CPEG to serve both as a syntactic specification of the
input and a schematic specification of the output.
