Регулярная древовидная грамматика

В теоретической информатике и теории формального языка регулярная древовидная грамматика — это формальная грамматика , описывающая набор направленных деревьев или терминов . Грамматику регулярных слов можно рассматривать как особый вид грамматики регулярного дерева, описывающий набор однопутных деревьев .

Определение

Регулярная древовидная грамматика G определяется набором

г знак равно ( N , Σ, Z , п ),

где

• N — конечное множество нетерминалов,
• Σ — ранговый алфавит (т. е. алфавит, символы которого имеют соответствующую арность ), не пересекающийся с N ,
• Z — начальный нетерминал, при этом Z ∈ N и
• P — конечное множество продукций формы A → t , где A ∈ N и t ∈ T _Σ ( N ) , где T _Σ ( N ) — ассоциированная алгебра терминов , т.е. набор всех деревьев, составленных из символов в Σ ∪ N в соответствии с их арностью, где нетерминалы считаются нулевыми.

Происхождение деревьев

Грамматика G неявно определяет набор деревьев: любое дерево, которое может быть получено из с использованием набора правил P называется описываемым G. , Z набор деревьев известен язык G. Этот как Более формально отношение ⇒ _G на множестве T _Σ ( N ) определяется следующим образом:

Дерево t ₁ ∈ T _Σ ( N ) можно за один шаг превратить в дерево t ₂ ∈ T _Σ ( N ) (короче: t ₁ ⇒ _G t ₂ ), если существует контекст S и продукция ( A → t ) ∈ P такие, что:

• t ₁ = S [ A ], и
• т ₂ знак равно S [ т ].

Здесь контекст означает дерево, в котором ровно одно отверстие; если S контекстом, S [ t ] обозначает результат заполнения дерева t в дырку S. является таким

Древовидным языком, порожденным G , является язык L ( G ) знак равно { t ∈ T _Σ | Z ⇒ _{Г *} т } .

Здесь T _Σ обозначает множество всех деревьев, составленных из символов Σ, а ⇒ _{G *} обозначает последовательные применения ⇒ _G .

Язык, порожденный некоторой регулярной древовидной грамматикой, называется регулярным древовидным языком .

Примеры

Пример дерева вывода из G ₁ в линейной (левая верхняя таблица) и графической (основной рисунок) обозначениях

Пусть G ₁ = ( N ₁ , Σ ₁ , Z ₁ , P ₁ ), где

• N ₁ = { Bool , BList } — наш набор нетерминалов,
• Σ ₁ = { true , false , nil , cons (.,.) } — наш ранжированный алфавит, арность обозначена фиктивными аргументами (т. е. символ cons имеет арность 2),
• Z ₁ = BList — наш стартовый нетерминал, а
• набор П ₁ состоит из следующих продукций:
  • Логическое значение → ложь
  • Бул → правда
  • BList → ноль
  • BList → минусы ( Bool , BList )

Пример вывода из грамматики G ₁ :

BList ⇒ минусы ( Bool , BList ) ⇒ минусы ( ложь , минусы ( Bool , BList )) ⇒ минусы ( ложь , минусы ( истина , ноль )).

На изображении показано соответствующее дерево вывода ; это дерево деревьев (основное изображение), тогда как дерево вывода в грамматиках слов представляет собой дерево строк (верхняя левая таблица).

Язык дерева, порожденный G _{1 ,} представляет собой набор всех конечных списков логических значений, то есть L ( G ₁ ) оказывается равным T _Σ1 . Грамматика G ₁ соответствует объявлениям алгебраических типов данных (на языке программирования Standard ML ):

  datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList

Каждый член L ( G ₁ ) соответствует значению Standard-ML типа BList.

В качестве другого примера, пусть G ₂ = ( N ₁ , Σ ₁ , BList ₁ , P ₁ ∪ P ₂ ) , используя нетерминальный набор и алфавит сверху, но расширяя производственный набор с помощью P ₂ , состоящий из следующих продукций:

• BList ₁ → минусы ( истина , BList )
• BList ₁ → минусы ( ложь , BList ₁ )

Язык L ( G2 _хотя ) — это набор всех конечных списков логических значений, которые содержат true бы один раз . Набор L ( G ₂ ) не имеет аналога типа данных ни в стандартном ML, ни в каком-либо другом функциональном языке. Это собственное подмножество L ( G ₁ ). Термин, приведенный выше, также находится в L ( G ₂ ), как показывает следующий вывод:

Список ₁ ⇒ минусы ( ложь , BList ₁ ) ⇒ минусы ( ложь , минусы ( правда , BList )) ⇒ минусы ( ложь , минусы ( истина , ноль )).

Свойства языка

Если L ₁ , L ₂ оба являются регулярными древесными языками, то множества деревьев L ₁ ∩ L ₂ , L ₁ ∪ L ₂ и L ₁ \ L ₂ также являются регулярными древесными языками, и можно решить, является ли L ₁ ⊆ L ₂ , и является ли L ₁ = L ₂ .

Альтернативные характеристики и связь с другими формальными языками

• Регулярные древовидные грамматики являются обобщением грамматик обычных слов .
• Регулярные древовидные языки также являются языками, распознаваемыми древесными автоматами «снизу вверх» и недетерминированными древесными автоматами «сверху вниз».
• Раджив Алур и Партасарати Мадхусудан связали подкласс обычных языков двоичного дерева с вложенными словами и языками с видимым расположением вниз .

Приложения

Приложения регулярных древовидных грамматик включают:

• Выбор инструкций при генерации кода компилятора
• Процедура принятия решения для первого порядка логической теории формул над равенством (=) и набором членства (ε) в качестве единственных предикатов
• Решение ограничений на математические множества
• Набор всех истин, выразимых в логике первого порядка о конечной алгебре (которая всегда является регулярным древовидным языком)
• Граф-поиск

См. также

• Установить ограничение - обобщение регулярных древовидных грамматик.
• Грамматика, примыкающая к дереву

Дальнейшее чтение

• Регулярные древовидные грамматики были описаны еще в 1968 году:
  • Брейнерд, WS (1968). «Минимализация древовидных автоматов» . Информация и контроль . 13 (5): 484–491. дои : 10.1016/s0019-9958(68)90917-0 . hdl : 10945/40204 .
  • Тэтчер, Дж.В.; Райт, Дж. Б. (1968). «Обобщенная теория конечных автоматов с применением к задаче решения логики второго порядка». Теория математических систем . 2 (1): 57–81. дои : 10.1007/BF01691346 . S2CID   31513761 .
• Книга, посвященная древовидным грамматикам: Ниват, Морис; Подельски, Андреас (1992). Древовидные автоматы и языки . Исследования в области компьютерных наук и искусственного интеллекта. Том. 10. Северная Голландия.
• Алгоритмы на основе регулярных древовидных грамматик обсуждаются с точки зрения эффективности в: Эйкен, А.; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по функциональным языкам программирования и архитектуре компьютеров . стр. 427–447. CiteSeerX   10.1.1.39.3766 .
• Учитывая отображение деревьев в веса, Дональда Кнута обобщение алгоритма кратчайшего пути Дейкстры может быть применено к грамматике обычного дерева для вычисления для каждого нетерминала минимального веса выводимого дерева. Основываясь на этой информации, легко перечислить его язык в порядке возрастания веса. В частности, любой нетерминал с бесконечным минимальным весом порождает пустой язык. Видеть: Кнут, DE (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. дои : 10.1016/0020-0190(77)90002-3 .
• Обычные древесные автоматы были обобщены, чтобы допускать проверки равенства между одноуровневыми узлами в деревьях. Видеть: Богерт, Б.; Тайсон, Софи (1992). «Ограничения равенства и неравенства на прямых подчленах в древовидных автоматах». Учеб. 9-й СТАКС . ЛНКС. Том. 577. Спрингер. стр. 161–172.
• Разрешение проверок равенства между более глубокими узлами приводит к неразрешимости. Видеть: Томмаси, М. (1991). Древовидные автоматы с проверками связи между двоюродными братьями . ЛИВЛ-ИТ.