Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

Определение:

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

Язык, задаваемый контекстно-свободной грамматикой называется контекстно-свободным языком.

Определение:

Выводом слова [math]\alpha[/math] называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово [math]\alpha[/math].

Определение:

Левосторонним выводом слова [math]\alpha[/math] называется его вывод такой, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.

Аналогичным образом определяется правосторонний вывод.

Определение:

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

Определение:

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

Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.