Контекстно-свободные языки и грамматики

Задача разбора

Вывод цепочек

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматике. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.

ОпределениеЦепочка b Î (V_TÈV_N)^* непосредственно выводима из цепочки в грамматике (обозначается:aÞb), если и , где , и правило вывода содержится во множестве Р.

Определение Цепочка b Î (V_TÈV_N)^* выводима из цепочки в грамматике (обозначается aÞ*b), если существует последовательность цепочек (n³0) такая, что .

Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода.

Вывод называется правосторонним (левосторонним), если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему правому (левому) нетерминальному символу в цепочке.

Вывод можно рассматривать также как процесс получения одной строки из другой. С понятием вывода тесно связано понятие разбора строки языка. С одной стороны, разбор— это задача выяснения принадлежности заданной строки языку, порождае­мому заданной грамматикой. С другой стороны, разбор — это последовательность правил грамматики, определенным образом соответствующая выводу.

ПримерГрамматика G₁=({0, 1}, {A, S}, P₁, S), где множество Р состоит из правил вида: 1) S® 0A1;2)0A® 00A1;3) A®e.

В грамматике G₁ SÞ*000111, т.к. существует вывод .

Дерево разбора

Графическим способом отображения процесса разбора цепочек является дерево разбора (или дерево вывода).

Определение дерево разбора грамматики называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

- каждая вершина дерева обозначается символом грамматики ;

- корнем дерева является вершина, обозначенная начальным символом грамматики S;

- листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой строки e;

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

Дерево разбора можно построить двумя способами: сверху вниз и снизу вверх.