Язык синтаксического анализа сверху вниз (TDPL) - это тип аналитической формальной грамматики, разработанный Александром Бирманом в начале 1970-х годов для формального изучения поведения общего класса практических синтаксических анализаторов сверху вниз, которые поддерживают ограниченную форму поиска с возвратом . Бирман первоначально назвал свой формализм TMG Schema (TS) в честь TMG , раннего генератора синтаксического анализатора , но позже Ахо и Ульман дали ему имя TDPL в их классической антологии The Theory of Parsing, Translation and Compiling .
Определение грамматики TDPL [ править ]
Формально грамматика TDPL G представляет собой кортеж, состоящий из следующих компонентов:
- Конечное множество N из нетерминальных символов .
- Конечное множество Σ из терминальных символов , которые не пересекаются с N .
- Конечное множество Р из продукционных правил , где правило , имеет одну из следующих форм:
- A ← ε, где A - нетерминал, а ε - пустая строка.
- A ← f , где f - выделенный символ, обозначающий безусловный отказ .
- A ← a , где a - любой терминальный символ.
- A ← BC / D , где B , C и D нетерминалы.
Интерпретация грамматики [ править ]
Грамматику TDPL можно рассматривать как чрезвычайно минималистичное формальное представление метод рекурсивных спуска , в котором каждый из нетерминалов схематически представляет собой синтаксический анализ функцию . Каждая из этих нетерминальных функций принимает в качестве входного аргумента строку, которую нужно распознать, и дает один из двух возможных результатов:
- успех , и в этом случае функция может опционально двигаться вперед или использовать один или несколько символов входной строки, предоставленной ей, или
- сбой , и в этом случае ввод не потребляется.
Обратите внимание, что нетерминальная функция может завершиться успешно, фактически не потребляя никаких входных данных, и это считается результатом, отличным от неудачи.
Нетерминал A, определенный правилом формы A ← ε, всегда преуспевает, не потребляя никаких входных данных, независимо от предоставленной входной строки. И наоборот, правило формы A ← f всегда терпит неудачу независимо от ввода. Правило формы A ← a считается успешным, если следующий символ во входной строке - это терминал a , и в этом случае нетерминал преуспевает и потребляет этот один терминал; если следующий входной символ не совпадает (или следующего символа нет), то нетерминал терпит неудачу.
Нетерминальный определяется правилом вида ← BC / D первого рекурсивно вызывает нетерминальное B , и если Б успешно, вызывает C на оставшуюся часть входной строки влево неизрасходованный с помощью B . Если оба B и C успешны, то A, в свою очередь, преуспевает и потребляет то же общее количество входных символов, что и B и C вместе. Однако, если либо B, либо C терпят неудачу, то A возвращается. к исходной точке во входной строке , где он был первым вызывается, а затем вызывает D на этой исходной входной строке, возвращая то , что результат D производит.
Примеры [ править ]
Следующая грамматика TDPL описывает регулярный язык, состоящий из последовательности произвольной длины букв a и b:
S ← AS / T
T ← BS / E
A ← a
B ← b
E ← ε
Следующая грамматика описывает язык контекстно-свободных скобок, состоящий из строк произвольной длины и совпадающих фигурных скобок, таких как '{}', '{{} {{}}}' и т. Д .:
S ← OT / E
T ← SU / F
U ← CS / F
O ← {
C ←}
E ← ε
F ← f
Приведенные выше примеры могут быть представлены эквивалентно, но гораздо более сжато при синтаксическом анализе грамматической записи выражений как S ← (a / b) * и S ← ({S}) * соответственно.
Обобщенный TDPL [ править ]
Небольшая вариация TDPL, известная как Generalized TDPL или GTDPL, значительно увеличивает кажущуюся выразительность TDPL, сохраняя при этом тот же минималистский подход (хотя на самом деле они эквивалентны). В GTDPL вместо рекурсивной формы правил TDPL A ← BC / D мы используем альтернативную форму правил A ← B [C, D] , которая интерпретируется следующим образом. Когда нетерминальный вызывается на некоторой входной строке, то сначала рекурсивно вызывает B . Если B успешно, то A впоследствии вызывает C для оставшейся части ввода, оставшейся неиспользованной B , и возвращает результатC исходному абоненту. С другой стороны, если B терпит неудачу, то A вызывает D в исходной входной строке и передает результат обратно вызывающей стороне.
Важное различие между этой формой правила и формой правила A ← BC / D, используемой в TDPL, заключается в том, что C и D никогда не вызываются одновременно в одном и том же вызове A : то есть правило GTDPL действует скорее как «чистое» if / then / else построить с использованием B в качестве условия.
В GTDPL просто выражать интересные неконтекстно -свободные языки, такие как классический пример {a n b n c n }.
Грамматика GTDPL может быть сокращена до эквивалентной грамматики TDPL, которая распознает тот же язык, хотя этот процесс непростой и может значительно увеличить количество требуемых правил. [1] Кроме того, и TDPL, и GTDPL можно рассматривать как очень ограниченные формы грамматик синтаксического анализа , которые представляют один и тот же класс грамматик. [1]
См. Также [ править ]
Ссылки [ править ]
Внешние ссылки [ править ]
