Язык анализа сверху вниз (TDPL) и его обобщение (GTDPL)
Top-down parsing language
TDPL: формальная грамматика для анализа синтаксиса, разработанная А. Бирманом. Изучение нисходящего разбора с поддержкой ограниченного возврата. GTDPL – расширение TDPL.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Язык анализа сверху вниз (TDPL) — это тип аналитической формальной грамматики, разработанный Александром Бирманом в начале 1970-х годов для формального изучения поведения общего класса практических парсеров, работающих сверху вниз и поддерживающих ограниченную форму возврата (backtracking). Изначально Бирман назвал свой формализм схемой TMG (TS), по имени TMG — раннего генератора парсеров, но позднее Ахо и Уллман дали ему название TDPL в своей классической антологии «Теория разбора, трансляции и компиляции».
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 it was later given the name TDPL by Aho and Ullman in their classic anthology The Theory of Parsing, Translation and Compiling.
Общая TDPL
Небольшое изменение TDPL, известное как обобщенный TDPL или GTDPL, значительно повышает кажущуюся выразительность TDPL, сохраняя при этом тот же минималистский подход (хотя они на самом деле эквивалентны). В GTDPL вместо рекурсивного правила TDPL в форме A → BC/D используется форма правила A → B[C,D]. Это правило интерпретируется следующим образом: когда нетерминал A вызывается для некоторой входной строки, он сначала рекурсивно вызывает B. Если B успешно выполняется, то A затем вызывает C для оставшейся части входной строки, не обработанной B, и возвращает результат C исходному вызывающему. Если же B не выполняется, то A вызывает D для исходной входной строки и передает результат обратно вызывающему. Важное отличие этой формы правила от формы A → BC/D, используемой в TDPL, заключается в том, что C и D никогда не вызываются в одном и том же вызове A: то есть, правило GTDPL действует скорее как "чистая" конструкция "если/то/иначе", используя B в качестве условия. В GTDPL легко выразить интересные языки, не являющиеся контекстно-свободными, такие как классический пример {anbncn}. Грамматика GTDPL может быть сведена к эквивалентной грамматике TDPL, распознающей тот же язык, хотя этот процесс нетривиален и может значительно увеличить количество необходимых правил. Кроме того, как TDPL, так и GTDPL можно рассматривать как сильно ограниченные формы грамматик выражений для разбора, все из которых представляют один и тот же класс грамматик.
A slight variation of TDPL, known as Generalized TDPL or GTDPL, greatly increases the apparent expressiveness of TDPL while retaining the same minimalist approach (though they are actually equivalent). In GTDPL, instead of TDPL's recursive rule form A → BC/D, the rule form A → B[C,D] is used. This rule is interpreted as follows: When nonterminal A is invoked on some input string, it first recursively invokes B. If B succeeds, then A subsequently invokes C on the remainder of the input left unconsumed by B, and returns the result of C to the original caller. If B fails, on the other hand, then A invokes D on the original input string, and passes the result back to the caller. The important difference between this rule form and the A → BC/D rule form used in TDPL is that C and D are never both invoked in the same call to A: that is, the GTDPL rule acts more like a "pure" if/then/else construct using B as the condition. In GTDPL it is straightforward to express interesting non context free languages such as the classic example {anbncn}. A GTDPL grammar can be reduced to an equivalent TDPL grammar that recognizes the same language, although the process is not straightforward and may greatly increase the number of rules required. Also, both TDPL and GTDPL can be viewed as very restricted forms of parsing expression grammars, all of which represent the same class of grammars.