Какова связь между деривацией и деривационными деревьями?

Это было написано в книге Уллмана, но я плохо понимал, как это работает. Кто-нибудь может объяснить даже в простом контексте? Я был бы очень рад.

Источник

1 ответ

Решение

Деривация - это некоторая последовательность, которая начинается с начального символа S, заканчивается строкой на языке, а промежуточные шаги могут содержать терминалы и нетерминалы. Каждый шаг в последовательности расширяет один нетерминал, используя производственное правило.

Дерево разбора основано на начальном символе, имеет конечные символы в виде листьев, а дочерние элементы узла соответствуют производственному правилу.

Например, с грамматикой S -> a | 1 | S + S, вывод для a + a + 1 возможно

S -> S + S -> a + S -> a + S + S -> a + S + 1 -> a + a + 1

и соответствующее дерево разбора может быть

   S
 / | \
S  +  S
|    /|\
a   S + S
    |   |
    a   1

Некоторые вопросы, которые следует задать на этом этапе: Для заданного языка или грамматики у конкретной строки есть только одно дерево разбора? Только один вывод? Для конкретного деривации существует ли уникальное дерево разбора или наоборот?

Источник
Другие вопросы по тегам