Язык синтаксического анализа сверху вниз
Язык нисходящего синтаксического анализа (TDPL) — это тип аналитической формальной грамматики, разработанный Александром Бирманом в начале 1970-х годов. [1] [2] [3] для того, чтобы формально изучить поведение общего класса практических нисходящих парсеров , поддерживающих ограниченную форму обратного отслеживания . Бирман первоначально назвал свой формализм TMG Schema (TS) в честь TMG , раннего генератора синтаксического анализатора дали ему название TDPL , но позже Ахо и Ульман в их классической антологии The Theory of Parsing, Translation and Compiling . [4]
Определение грамматики TDPL
[ редактировать ]Формально грамматика TDPL G представляет собой четверку, состоящую из следующих компонентов:
- Конечное множество N символов нетерминальных .
- Конечное множество Σ терминальных символов , не пересекающееся с N .
- Конечное множество P правил производства , где правило имеет одну из следующих форм:
- A → ε, где A — нетерминал, а ε — пустая строка.
- A → f , где f — отличительный символ, обозначающий безусловный отказ .
- A → a , где a — любой терминальный символ.
- A → BC/D , где B , C и D — нетерминалы.
Интерпретация грамматики
[ редактировать ]Грамматику TDPL можно рассматривать как чрезвычайно минималистичное формальное представление синтаксического анализатора рекурсивного спуска , в котором каждый из нетерминалов схематически представляет функцию синтаксического анализа . Каждая из этих нетерминальных функций принимает в качестве входного аргумента распознаваемую строку и дает один из двух возможных результатов:
- Success , и в этом случае функция может опционально двигаться вперед или использовать один или несколько символов входной строки, переданной ей, или
- сбой , и в этом случае входные данные не потребляются.
Обратите внимание, что нетерминальная функция может выполниться успешно, фактически не потребляя никаких входных данных, и это считается результатом, отличным от неудачи.
Нетерминал A , определенный правилом вида A → ε, всегда завершается успешно, не потребляя никаких входных данных, независимо от предоставленной входной строки. И наоборот, правило вида A → f всегда терпит неудачу независимо от входных данных. Правило формы A → a завершается успешно, если следующим символом во входной строке является терминал a , и в этом случае нетерминал завершается успешно и потребляет этот терминал; если следующий входной символ не соответствует (или следующего символа нет), то нетерминал завершается неудачей.
Нетерминал A, определенный правилом формы A → BC/D , сначала рекурсивно вызывает нетерминал B , и если B завершается успешно, вызывает C оставшейся неиспользованной B. для оставшейся части входной строки , Если и B, и C преуспевают, то A , в свою очередь, добивается успеха и потребляет то же общее количество входных символов, что и B и C вместе. Однако если B или C терпят неудачу, то A возвращается к исходной точке входной строки, где он был впервые вызван, а затем вызывает D для этой исходной входной строки, возвращая любой результат, который D. дает
Примеры
[ редактировать ]Следующая грамматика TDPL описывает обычный язык, состоящий из последовательности букв a и b произвольной длины:
- С → АС/Т
- Т → БС/Э
- А → а
- Б → б
- Э → е
Следующая грамматика описывает контекстно-свободный язык Дика , состоящий из строк произвольной длины совпадающих фигурных скобок, таких как '{}', '{{}{{}}}' и т. д.:
- С → ОТ/Э
- Т → ВС/Пт
- У → CS/F
- О → {
- С → }
- Э → е
- ж → ж
Приведенные выше примеры могут быть представлены эквивалентно, но гораздо более кратко при грамматики выражений как синтаксическом анализе обозначений S ← (a/b)* и S ← ({S})*, соответственно.
Обобщенный 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 для исходной входной строки и передает результат обратно вызывающей стороне.
Важное различие между этой формой правила и формой правила A → BC/D , используемой в TDPL, заключается в том, что C и D никогда не вызываются одновременно в одном и том же вызове A : то есть правило GTDPL действует больше как «чистый» if/ then/else с использованием B в качестве условия.
В GTDPL легко выражать интересные неконтекстно -свободные языки, такие как классический пример {a н б н с н }.
Грамматику GTDPL можно свести к эквивалентной грамматике TDPL, которая распознает тот же язык, хотя этот процесс не является простым и может значительно увеличить количество необходимых правил. [5] Кроме того, и TDPL, и GTDPL можно рассматривать как очень ограниченные формы синтаксического анализа грамматик выражений , которые представляют один и тот же класс грамматик. [5]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Бирман, Александр (1970). Схема признания TMG . Цифровая библиотека ACM (доктор философии). Принстонский университет.
- ^ Бирман, Александр; Уллман, Джеффри Д. (октябрь 1970 г.). «Алгоритмы анализа с возвратом». SWAT '70: Труды 11-го ежегодного симпозиума по теории коммутации и автоматов : 153–174. дои : 10.1109/SWAT.1970.18 .
- ^ Бирман, Александр; Уллман, Джеффри Д. (1973). «Алгоритмы синтаксического анализа с обратным поиском» (PDF) . Информация и контроль . 23 (1): 1–34. дои : 10.1016/S0019-9958(73)90851-6 .
- ^ Ахо, Альфред В.; Уллман, Джеффри Д. (1972). Теория синтаксического анализа, трансляции и компиляции: Том 1: Синтаксический анализ . Река Аппер-Сэддл, Нью-Джерси: Прентис-Холл. стр. 456–485. ISBN 978-0-13-914556-8 .
- ^ Jump up to: Перейти обратно: а б Форд, Брайан. Анализ грамматик выражений: синтаксическая основа, основанная на распознавании