Ищете поиск грамматики атрибутов для красно-черного дерева

Question

У меня есть рекурсивная грамматика обходного порядка. T--> L | TNT
Для красно-черного дерева, которое является TBinary tree и L является Leaf и N является Node.

Поскольку я ищу, каждый узел определяется как пара (цвет, значение). Я пытаюсь найти 2 вещи.

1. Я хочу расширить грамматику, чтобы стать грамматикой атрибута, которая проверяет, удовлетворены ли условия красно-черного дерева или нет. Проблема в том, что я не знаю, как добавить условия красно-черной к грамматике?
2. Поиск синтезированных и унаследованных атрибутов грамматики.

Answer 1

Производство

T → T N T 

является (экспоненциально) неоднозначно, так как нет никаких признаков ли влево или вправо T должен быть расширен в первую очередь.

С N включает в себя цвет, мы могли бы просто распространять цвет с помощью синтаксического анализа, если он предоставляет дополнительную информацию. (Это эквивалентно синтезирование атрибута цвета для каждого T путем копирования атрибута цвета в N или черном для листьев). Это приводит к:

RN → "red" value 
BN → "black" value 
RT → BT RN BT 
BT → L | T BN T 
T → BT | RT 

, которая на самом деле не поможет, так как четвёртое производство все еще неразрешимо двусмысленными.

Фактически, нет никакого способа устранить неоднозначность. Даже если каждый N помечен своей черной глубиной, все же невозможно однозначно построить дерево из последовательности в порядке.

Рассмотрим следующие два дерева:

 B        B 
    /\       /\ 
    / \      / \ 
    R B      R B 
    /\       /\ 
/ \      / \ 
    B B      B B 
    \        /
    \       /
     R        R 

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

B R R B B B 

Таким образом, мы должны заключить, что нет достаточной информации в в порядке очереди, чтобы восстановить оригинальное красно-черное дерево.

Альтернативной проблемой было бы построение действительное красно-черное дерево из последовательности в обратном порядке двоичного дерева поиска. Существует алгоритм снизу вверх, который будет делать это, что не требует, чтобы узлы были аннотированы с их цветом. Кроме того, алгоритм имеет сложность O (1) для каждого добавленного узла.

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

Я уверен, что однажды решил эту проблему, но у меня нет подходящего решения, и меня не удивляет, что найти ее в Интернете нелегко. Если это то, что вы ищете, я 'd предлагаю начать с Ralph Hinze's 1999 paper на красно-черном дереве.