Вывод в КС-грамматиках и правила построения дерева вывода
- Формальные грамматики позволяют задавать языки, представляющие множества цепочек, построенных по определенным правилам. Используемый способ задания позволяет построить любую цепочку, принадлежащую языку. Чтобы сделать процесс построения, называемый выводом, наглядным, его изображают в виде графа, точнее, в виде дерева, которое называют синтаксическим деревом или деревом вывода. Учитывая, что вывод любой цепочки языка, принадлежащей языку, порождаемому заданной грамматикой, должен начинаться с начального символа, правила построения дерева можно сформулировать так:
1) В качестве начальной вершины или корня дерева возьмем вершину, которую обозначим начальным символом грамматики <I>; эта вершина образует нулевой ярус дерева,
2) Если при выводе цепочки на очередном шаге используется правило грамматики <A> ® a
и вершина, помеченная нетерминалом <A>, расположена на ярусе с номером k-1, то к построенному дереву нужно добавить столько вершин, сколько содержится символов в цепочке a, расположить эти вершины на ярусе k , обозначить их символами цепочки a
и соединить эти вершины дугами с вершиной <A>.
Результатом вывода является множество конечных узлов - листьев, которые выписываются при обходе дерева слева - вниз - направо - вверх . Рассмотрим, например, грамматикy Г1. 8:
- Г1. 8:
- Vт = {a, b}, Va = {<I>},
- R = {<I> ® a<I>b,
<I> ® ab },
которая порождает язык L(Г8) = {aa...abb...b}, где а и b
повторяются по n раз,
n=1,2,...
- Вывод цепочки с помощью правил этой грамматики имеет вид:
Пред.Страница След.Страница Раздел Содержание