Top-down parsing language

Top-Down Parsing Language (TDPL) is a type of analytic formal grammar developed by Alexander Birman in the early 1970s in order to study formally the behavior of a common class of practical top-down parsers that support a limited form of backtracking. Birman originally named his formalism the TMG Schema (TS), after TMG, an early parser generator, but the formalism was later given the name TDPL by Aho and Ullman in their classic anthology The Theory of Parsing, Translation and Compiling.

Formally, a TDPL grammar G is a tuple consisting of the following components:

A TDPL grammar can be viewed as an extremely minimalistic formal representation of a recursive descent parser, in which each of the nonterminals schematically represents a parsing function. Each of these nonterminal-functions takes as its input argument a string to be recognized, and yields one of two possible outcomes:

Note that a nonterminal-function may succeed without actually consuming any input, and this is considered an outcome distinct from failure.

A nonterminal A defined by a rule of the form A ← ε always succeeds without consuming any input, regardless of the input string proved. Conversely, a rule of the form A ← f always fails regardless of input. A rule of the form A ← a succeeds if the next character in the input string is the terminal a, in which case the nonterminal succeeds and consumes that one terminal; if the next input character does not match (or there is no next character), then the nonterminal fails.

A nonterminal A defined by a rule of the form A ← BC/D first recursively invokes nonterminal B, and if B succeeds, invokes C on the remainder of the input string left unconsumed by B. If both B and C succeed, then A in turn succeeds and consumes the same total number of input characters that B and C together did. If either B or C fails, however, then A backtracks to the original point in the input string where it was first invoked, and then invokes D on that original input string, returning whatever result D produces.

...
Wikipedia