Дерево вывода предложения (сентенции) грамматики. Синтаксическое дерево⁠⁠

Предыдущая статья: Хомски и его иерархия грамматик.

Посмотрите на следующую грамматику:

G = ({a, b}, {S, A, B}, {S → AB, A → aA | a, B → bB | b}, S)

| - означает ИЛИ, к пример A можно заменить на aA или просто a.

Кстати как вы думаете, какой язык описывает эта грамматика? Ответ будет в следующей статье, пока поразмышляйте над этим, а теперь к делу.

Давайте выведем какое-нибудь предложение данной грамматики:

S => AB => aAB => aAbB => aaAbB => aaabB => aaabb

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

Что же, можно сказать, всякий вывод предложения грамматики, порождает дерево, по крайней мере в неявном виде. Как вы думаете как называется обратная задача? Когда дано некое предложение грамматики например тоже самое aaabb и требуется восстановить дерево вывода.

Об этом в следующей статье…