Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм 5. Преобразование грамматики к БНФ (Хомского).

Читайте также:
  1. H. ПРЕОБРАЗОВАНИЕ ФУРЬЕ
  2. II. Алгоритмы манипуляций и инфекционная безопасность
  3. LR(k)-грамматики
  4. А) Преобразование анестетика из жидкой фазы в паровую и дозировние паров анестетика.
  5. Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния
  6. Алгоритм
  7. Алгоритм

Сначала множество нетерминальных символов новой грамматики строится на основе множества нетерминальных символов исходной грамматики: VN¢=VN.

Затем алгоритм работает с правилами P исходной грамматики и в зависимости от их вида строит множество правил P¢ и пополняет множество нетерминальных символов VN¢.

1. Правила вида A®a, A®BC, S®e, где A, B, CÎVN, aÎVT, переносятся во множество P¢ без изменений.

2. Если встречается правило вида (A®aB)ÎP, где A, BÎVN, aÎVT, то во множество правил P¢ добавляются правила A®<AaB>B и <AaB>®a, а новый символ <AaB> добавляется во множество нетерминальных символов VN¢.

3. Если встречается правило вида (A®Ba)ÎP, выполняется аналогичное действие: во множество правил P¢ добавляются правила A®B<ABa> и <ABa>®a, а новый символ <ABa> добавляется во множество нетерминальных символов VN¢.

4. Если встречается правило вида (A®ab)ÎP, где AÎVN, a, bÎVT, то во множество правил P¢ добавляются правила A®<Aa><Ab> и <Aa>®a, <Ab>®b, а новые символы <Aa>, <Ab> добавляются во множество нетерминальных символов VN¢.

5. Если встречается правило вида (A®X1X2…Xk)ÎP, где k>2, AÎVN, "i XiÎVTÈVN, то во множество правил P¢ добавляются правила A®X1¢<X2¢…Xk¢>,
<X2¢…Xk¢>®X2¢<X3¢…Xk¢>,

<Xk–1¢Xk¢>®Xk–1¢Xk¢,
где все новые нетерминальные символы <…> добавляются во множество нетерминальных символов VN¢. Что касается символов Xi¢, то их вид зависит от того, чем являлся исходный символ Xi. Если для некоторого i XiÎVN, то Xi¢ºXiÎVN¢; если XiÎVT, то Xi¢ – новый нетерминальный символ, т.е. Xi¢ÎVN¢ и в P¢ нужно добавить правило Xi¢®Xi.

Проиллюстрируем данный алгоритм на примере.

Пример 6. Преобразование КС-грамматики к БНФ.

Дана грамматика G({a,b,c},{A,B,C,S},P,S) в каноническом виде, где P:

S®AaB½Aa½bc

A®AB½a½aC

B®Ba½b

C®AB½c

Первоначально множество нетерминальных символов VN¢={A,B,C,S}, затем оно может пополняться. Последовательно рассматриваем правила P и анализируем каждое из них.

1) S®AaB – относится к пункту 5 алгоритма. Следовательно, в P¢ включаем S®A<aB>, <aB>®<a>B, <a>®a, а в множество VN¢ добавляем <aB>,<a>.

2) S®Aa – относится к 3 пункту алгоритма. Следовательно, в P¢ нужно включить S®A<a¢>, <a¢>®a, а в множество VN¢ добавить <a¢>. Но ранее уже появился нетерминал <a>, из которого выводился символ a, поэтому можно использовать его, тогда можно ограничиться правилом S®A<a>.

3) S®bc – относится к 4 пункту. Следовательно, в P¢ нужно включить S®<b><c>, <b>®b, <c>®c, а в множество VN¢ добавить <b>, <c>.

4) A®AB и A®a – в соответствии с первым пунктом алгоритма включается в P¢ без изменений.

5) A®aC – относится ко 2 пункту. Следовательно, в P¢ нужно включить A®<a>C, причем замечание из (2) справедливо и в данном случае.

6) B®Ba – аналогично (2), добавляется правило B®B<a>.

7) B®b, а также C®AB, C®c соответствуют требуемому виду правил и переносятся в грамматику без изменений.

Таким образом, получаем грамматику G¢({a,b,c},{A,B,C,<aB>,<a>, <b>,<c>,S},P¢,S) в нормальной форме Хомского, где P¢:

S®A<aB>½A<a>½<b><c>

A®AB½a½<a>C

B®B<a>½b

C®AB½c

<aB>®<a>B

<a>®a

<b>®b

<c>®c

Хотя эта грамматика содержит большее количество правил, чем исходная, но построение распознавателя для неё значительно упрощается.


Дата добавления: 2015-07-12; просмотров: 277 | Нарушение авторских прав


Читайте в этой же книге: Назначение синтаксического анализатора | Обработка синтаксических ошибок | Свойства и распознаватели КС-языков | Цели преобразований грамматик | Распознаватели КС-языков с возвратом | Нисходящий распознаватель с возвратом (с подбором альтернатив) | Табличные распознаватели КС-языков | Метод рекурсивного спуска | Разбор для LL(k)-грамматик | LR(k)-грамматики |
<== предыдущая страница | следующая страница ==>
Алгоритм 4. Устранение цепных правил| Пример 7.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)