63
правки
Изменения
Новая страница: «{{Определение |definition= '''Контекстно-свободной грамматикой''' называется грамматика, у которо…»
{{Определение
|definition=
'''Контекстно-свободной грамматикой''' называется грамматика, у которой в левых частях все правил стоят только одиночные нетерминалы.
}}
Язык, задаваемый контекстно-свободной грамматикой называется ''контекстно-свободным языком''.
{{Определение
|definition=
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
{{Определение
|definition=
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется его вывод такой, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
}}
Аналогичным образом определяется ''правосторонний вывод''.
{{Определение
|definition=
'''Деревом разбора''' называется дерево, на вершинах которого записаны терминалы или нетерминалы, а дети вершины, на которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами имеют детей.
}}
{{Определение
|definition=
'''Кроной''' дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева из корня в глубину.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
|definition=
'''Контекстно-свободной грамматикой''' называется грамматика, у которой в левых частях все правил стоят только одиночные нетерминалы.
}}
Язык, задаваемый контекстно-свободной грамматикой называется ''контекстно-свободным языком''.
{{Определение
|definition=
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
{{Определение
|definition=
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется его вывод такой, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
}}
Аналогичным образом определяется ''правосторонний вывод''.
{{Определение
|definition=
'''Деревом разбора''' называется дерево, на вершинах которого записаны терминалы или нетерминалы, а дети вершины, на которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами имеют детей.
}}
{{Определение
|definition=
'''Кроной''' дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева из корня в глубину.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
