Жоғарыдан Төмен Құрастыру Тілі (ЖТҚТ) және оның нұсқалары
Top-down parsing language
Топ-даун синтаксистік талдау тілі (TDPL) – А.Бирман жасаған формалды грамматика. Парсерлерді зерттеуге арналған, кері іздеуді қолдайды. GTDPL нұсқасы да бар.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Жоғарыдан Төменге Қарай Синтаксистік Тіл (ЖТҚТ) – 1970 жылдардың басында Александр Бирман жасаған аналитикалық формальды грамматиканың бір түрі. Бұл тіл, шектеулі кері іздеуді қолдайтын, кең таралған жоғарыдан төменге қарай талдайтын құралдардың қалай жұмыс істейтінін формальды түрде зерттеу мақсатымен әзірленген. Бирман бастапқыда өзінің формализмін TMG Schema (TS) деп атады, бұл атау TMG, алғашқы талдау генераторының атынан алынған, бірақ кейіннен Ахо мен Ульманның «Синтаксистік талдау, аударма және компиляция теориясы» атты классикалық антологиясында ЖТҚТ деп атау берді.
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-дің Generalized TDPL немесе GTDPL деп аталатын шағын өзгеруі TDPL-дің айқын экспрессивтілігін күрт арттырады, бірақ сонымен бірге сол минималистік көзқарасты сақтайды (бірақ олар іс жүзінде эквивалентті). GTDPL-де TDPL-дің рекурсивті ереже түрі A → BC/D орнына A → B[C,D] түрі қолданылады. Бұл ереже былай түсіндіріледі: Егер терминалды емес A белгілі бір кіріс жолы бойынша шақырылса, ол бірінші кезекте B-ні рекурсивті түрде шақырады. Егер B сәтті орындалса, A кейін C-ні B-нің пайдаланбаған кіріс бөлігіне шақырады және C-нің нәтижесін бастапқы шақырушыға қайтарады. Ал егер B орындалмаса, A бастапқы кіріс жолы бойынша D-ні шақырады және нәтижені шақырушыға жібереді. Бұл ереже түрі мен TDPL-де қолданылатын A → BC/D ереже түрінің маңызды айырмашылығы – 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.