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

Цели преобразований грамматик

Читайте также:
  1. LR(k)-грамматики
  2. Алгоритм 5. Преобразование грамматики к БНФ (Хомского).
  3. Грамматика
  4. Грамматика
  5. ГРАММАТИКА
  6. Грамматики предшествования
  7. Композиции преобразований

В общем случае для КС-грамматик невозможно проверить их однозначность и эквивалентность. Но для конкретных случаев бывает можно и нужно привести заданную грамматику к некоторому определённому виду таким образом, чтобы получить грамматику, эквивалентную исходной. Заранее определённый вид зачастую позволяет упростить работу с языком и построение распознавателей для него. Итак, преобразования грамматик могут преследовать две цели:

1) упрощение правил грамматики;

2) облегчение создания распознавателя языка.

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

Все преобразования грамматик условно разбиваются на две группы:

1. исключение из грамматики тех правил и символов, без которых она может существовать (позволяет упростить правила);

2. изменение вида и состава правил грамматики. При этом могут появиться новые правила и нетерминальные символы (упрощений правил нет).

4.2.2.2. Приведённые грамматики

Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (e-правил).

Рассмотрим некоторую грамматику G(VT,VN,P,S) и дадим необходимые определения.

Нетерминальный символ AÎVN называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е. {a½AÞ*a, aÎVT*}=Æ.

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

Символ x Î(VTÈVN) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G. Это значит, что он не может появиться ни в одной цепочке вывода. Для исключения всех недостижимых символов не обязательно рассматривать все сентенциальные формы грамматики, достаточно воспользоваться специальным алгоритмом удаления недостижимых символов. После удаления таких символов правила также упрощаются.

e -правилами, или правилами с пустой цепочкой, называются все правила грамматики вида A®e, AÎVN. Грамматика G называется грамматикой без e -правил, если в ней нет правил вида (A®e), AÎVN, A¹S, и существует только одно правило (S®e)ÎP, если eÎL(G) и при этом S не встречается в правой части ни одного правила грамматики G. Для упрощения процесса построения распознавателя цепочек языка L(G) любую грамматику целесообразно привести к виду без e-правил.

Циклом в грамматике G называется вывод вида AÞ*A, AÎVN. Очевидно, что такой вывод бесполезен, поэтому в распознавателях КС-языков рекомендуется избегать возможности появления циклов.

Циклы возможны в случае существования в грамматике цепных правил вида A®B, A,BÎVN. Достаточно устранить цепные правила из набора правил грамматики, чтобы исключить возможность появления циклов.

Для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):

§ удалить все бесплодные символы;

§ удалить все недостижимые символы;

§ удалить e-правила;

§ удалить цепные правила.

Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.


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


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

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