Построение КА по регулярной грамматике

Вход: Регулярная грамматика .

Выход: КА .

Шаг 1. Пополнить грамматику правилом , где и - новый нетерминал, для каждого правила вида , если в грамматике нет соответствующего ему правила , где .

Шаг 2. Начальный символ грамматики принять за начальное состояние КА . Из нетерминалов образовать множество состояний автомата , а из терминалов – множество символов входного алфавита .

Шаг 3. Каждое правило преобразовать в функцию переходов , где .

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

Шаг 5. Если в грамматике имеется правило , где - начальный символ грамматики, то поместить во множество заключительных состояний.

Шаг 6. Если получен НКА, то преобразовать его в ДКА.

Пример Дана регулярная грамматика с правилами . Построить по регулярной грамматике конечный автомат.

Решение задачи состоит из следующей последовательности действий.

1 Построим по регулярной грамматике КА.

1.1 Пополним грамматику правилами и , где - новый нетерминал.

1.2 Начальное состояние конечного автомата . Множество состояний автомата , множество символов входного алфавита .

1.3 Значения сформированной функции переходов даны в таблице 2.7.

Таблица 2.7 – Функция переходов автомата

	S	A	B	N
a	A, B	A	N
b		N	B

1.4 Множество заключительных состояний .

1.5 Для начального символа грамматики e-правила отсутствуют.

Конечный автомат М - недетерминированный, граф НКА представлен на рисунке 2.5.

Рисунок 2.5 - Граф НКА

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

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

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

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

Определение Цепочка 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;

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

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

Нисходящее дерево разбора

При построении дерева вывода сверху вниз построение начинается с целевого символа грамматики, который помещается в корень дерева. Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня. На втором шаге среди всех концевых вершин дерева выбирается крайняя (крайняя левая — для левостороннего вывода, крайняя правая — для правостороннего) вершина, обозначенная нетерминальным символом, для этой вершины выбирается нужное правило грамматики, и она раскрывается на несколько вершин следующего уровня. Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами, в противном случае надо вернуться ко второму шагу и продолжить построение.

Восходящее дерево разбора

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

Поскольку все известные языки программирования имеют нотацию записи «слева — направо», компилятор также всегда читает входную программу слева направо (и сверху вниз, если программа разбита на несколько строк). Поэтому для построения дерева вывода методом «сверху вниз», как правило, используется левосторонний вывод, а для построения «снизу вверх» — правосторонний вывод. На эту особенность компиляторов стоит обратить внимание. Нотация чтения программ «слева направо» влияет не только на порядок разбора программы компилятором (для пользователя это, как правило, не имеет значения), но и ни порядок выполнения операций — при отсутствии скобок большинство равноправных операций выполняются в порядке слева направо, а это уже имеет существенное значение.

Однозначность грамматик

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

3.2 Преобразование КС-грамматик

Определение КС-грамматика называется приведенной, если она не имеет циклов, e-правил и бесполезных символов.

Рассмотрим основные алгоритмы приведения КС-грамматик.

Перед всеми другими исследованиями и преобразованиями КС-грамматик выполняется проверка существования языка грамматики.

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒