Датчик дерева

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

Манипулирование древовидными структурами вместо слов позволяет TT моделировать синтаксически-ориентированные преобразования формальных или естественных языков. Однако TT не так хороши, как их словесные аналоги, с точки зрения алгоритмической сложности , свойств замыкания и т. д. В частности, большинство основных классов не закрыты по композиции .

Основными классами преобразователей деревьев являются:

Древовидные преобразователи сверху вниз (TOP)

TOP T — это кортеж ( Q , Σ, Γ, I , δ ) такой, что:

• Q — конечное множество , множество состояний ;
• Σ — алфавит конечного ранга , называемый входным алфавитом ;
• Γ — алфавит конечного ранга, называемый выходным алфавитом ;
• I — подмножество Q ; множество начальных состояний , и
• δ — набор правил вида $q(f(x_{1},\dots ,x_{n}))\to u$, где f — символ Σ, n — арность f , q — состояние, u — дерево на Γ и $Q\times 1..n$, такие пары являются нулевыми .

Примеры правил и интуиций по семантике

Например,

$q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))$

это правило – принято писать $q(x_{i})$ вместо пары $(q,x_{i})$ – и его интуитивная семантика заключается в том, что под действием q дерево с f в корне и тремя детьми преобразуется в

$g(a,q'(x_{1}),h(q''(x_{3})))$

где рекурсивно $q'(x_{1})$ и $q''(x_{3})$ заменяются соответственно применением $q'$ о первом ребенке и с применением $q''$ на третьем.

Семантика как переписывание терминов

Семантика бинарное каждого состояния преобразователя T и самого T представляет собой отношение между входными деревьями (на Σ) и выходными деревьями (на Γ).

Способ формального определения семантики состоит в том, чтобы увидеть $\delta$ как система переписывания терминов , при условии, что в правых частях вызовы записаны в виде $q(x_{i})$, где состояния q — унарные символы. Тогда семантика $[\![q]\!]$ состояния q определяется выражением

$[\![q]\!]=\{u\mapsto v\mid u{\text{ is a tree on }}\Sigma ,\ v{\text{ is a tree on }}\Gamma {\text{, and }}q(u)\to _{\delta }^{*}v\}.$

Семантика T тогда определяется как объединение семантики его начальных состояний:

$[\![T]\!]=\bigcup _{q\in I}[\![q]\!].$

Детерминизм и область

Как и в случае с древовидными автоматами, TOP называется детерминированным (сокращенно DTOP ), если никакие два правила δ не имеют одной и той же левой части и существует не более одного начального состояния. В этом случае семантика DTOP является частичной функцией от входных деревьев (на Σ) до выходных деревьев (на Γ), как и семантика каждого из состояний DTOP.

Область область преобразователя — это его семантики. Аналогично, образ преобразователя — это образ его семантики.

Свойства ДТОП

• DTOP не закрываются при объединении : это уже относится к детерминированным преобразователям слов.
• Областью применения DTOP является обычный древовидный язык . Кроме того, домен можно распознать по детерминированному нисходящему древовидному автомату (DTTA), размер которого не превышает экспоненциального размера исходного DTOP.

То, что домен распознается DTTA, неудивительно, учитывая, что левые части правил DTOP такие же, как и для DTTA. Что касается причины экспоненциального взрыва в худшем случае (которой не существует в словесном случае), рассмотрим правило $q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))$. Чтобы вычисление завершилось успешно, оно должно быть успешным для обоих дочерних элементов. Это означает, что правильный ребенок должен находиться в области $p_{3}$. Что касается левого дочернего элемента, он должен находиться в домене обоих $p_{1}$ и $p_{2}$. Как правило, поскольку поддеревья можно копировать, одно поддерево может оцениваться в нескольких состояниях во время выполнения, несмотря на детерминизм и в отличие от DTTA. Таким образом, конструкция DTTA, распознающая область DTOP, должна учитывать наборы состояний и вычислять пересечения их областей, следовательно, экспоненту. В частном случае линейного DTOP, то есть DTOP, где каждый $x_{i}$ появляется не более одного раза в правой части каждого правила, конструкция линейна во времени и пространстве.

• Образ DTOP не является обычным древовидным языком.

Рассмотрим преобразователь, кодирующий преобразование $f(x)\to g(x,x)$; то есть дублировать дочерний элемент ввода. Это легко сделать по правилу $q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))$, где p кодирует личность . Тогда, при отсутствии каких-либо ограничений на первый дочерний элемент входных данных, изображение представляет собой классический нерегулярный древовидный язык.

• Однако область применения DTOP не может быть ограничена обычным древовидным языком. То есть, имея DTOP T и язык L , вообще невозможно построить DTOP. $T'$ такая, что семантика $T'$ это T , ограниченный L ​ .

Это свойство связано с причиной, по которой детерминированные нисходящие древовидные автоматы менее выразительны, чем восходящие автоматы: как только вы идете по заданному пути, информация из других путей становится недоступной. Рассмотрим преобразователь, кодирующий преобразование $f(x,y)\to y$; то есть вывести правый дочерний элемент ввода. Это легко сделать по правилу $q(f(x_{1},x_{2}))\to p(x_{2})$, где p кодирует личность. Теперь предположим, что мы хотим ограничить этот преобразователь конечной (и, следовательно, в частности, регулярной) областью. $\{f(c,a),\ f(c,b)\}$. Мы должны использовать правила $q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b$. Но в первом правиле $x_{1}$ вообще не появляется, так как из левого дочернего элемента ничего не производится. Таким образом, невозможно проверить, что левый дочерний элемент — c . Напротив, поскольку мы производим результат от правильного дочернего элемента, мы можем проверить, является ли он a или b . В общем, критерием является то, что DTOP не может проверять свойства поддеревьев, из которых они не производят выходные данные.

• DTOP не закрыты по композиции . Однако эту проблему можно решить, добавив функцию просмотра вперед : древовидный автомат, связанный с преобразователем, который может выполнять тесты в области , на которые преобразователь не способен.

Это следует из пункта об ограничении домена: составление идентификатора кодировки DTOP на $\{f(c,a),\ f(c,b)\}$ с одной кодировкой $f(x,y)\to y$ должен дать преобразователь с семантикой $\{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}$, который, как мы знаем, не выражается с помощью DTOP.

• Проблема проверки типов — проверка того, включен ли образ регулярного древовидного языка в другой регулярный древовидный язык — разрешима.
• Проблема эквивалентности — проверка того, определяют ли два DTOP одни и те же функции — разрешима.

Преобразователи дерева снизу вверх (BOT)

Как и в более простом случае древесных автоматов, восходящие преобразователи дерева определяются аналогично их нисходящим аналогам, но действуют от листьев дерева к корню, а не от корня к листьям. Таким образом, основное различие заключается в форме правил, которые имеют вид $f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)$.

Ссылки

• Комон, Хьюберт; Доше, Макс; Жилерон, Реми; Жакмар, Флоран; Лужье, Денис; Лёдинг, Кристоф; Тисон, Софи; Томмаси, Марк (ноябрь 2008 г.). «Глава 6: Преобразователи деревьев» . Техники и приложения древовидных автоматов . Проверено 11 февраля 2014 г.
• Хосоя, Харуо (4 ноября 2010 г.). Основы обработки XML: подход «дерево-автомат» . Издательство Кембриджского университета. ISBN  978-1-139-49236-2 .