Удаление бесполезных символов из грамматики
Порождающие и непорождающие нетерминалы
Описание
Определение: |
Нетерминал называется порождающим (англ. generating), если из него может быть выведена конечная терминальная цепочка. Иначе он называется непорождающим. |
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.
Лемма: |
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится. |
Доказательство: |
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова. |
Алгоритм
Шаг 0. Множество порождающих нетерминалов пустое.
Шаг 1. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.
Шаг 2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части.
Шаг 3. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
Время работы алгоритма
Данный алгоритм работает за очередь можно ускорить его до .
, где — размер грамматики. Однако используяМодификация алгоритма с очередью
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
- — является ли нетерминал порождающим или нет,
- — счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
- — для каждого нетерминала список номеров правил, в правой части которых он встречается,
- — очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
Вначале для всех нетерминалов в
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем для всех правил из для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем .
Пример
Рассмотрим следующую грамматику:
Применяя описанный алгоритм:
- Изначально множество порождающих нетерминалов состоит из одного элемента .
- Добавим в множество нетерминал , так как существует правило , в правой части которого стоят нетерминал , который есть в множестве, и терминал .
- После следующего обхода правил из грамматики множество не изменится.
- Теперь удалим правила и , так как они содержит нетерминалы, которых нет в полученном множестве.
Достижимые и недостижимые нетерминалы
Описание
Определение: |
Нетерминал КС-грамматике , если существует порождение . Иначе он называется недостижимым (англ. unreachable). | называется достижимым (англ. reachable) в
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.
Лемма: |
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится. |
Доказательство: |
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова. |
Алгоритм
Шаг 0. Множество достижимых нетерминалов состоит из единственного элемента:
Шаг 1. Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.
Шаг 2. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
Время работы алгоритма
Данный алгоритм работает за обход в глубину можно ускорить его до .
, однако используяПример
Рассмотрим следующую грамматику:
- Возьмём множество, состоящее из единственного элемента: .
- Из достижимы нетерминалы , , и . Добавим их в множество и получим .
- Множество изменилось. Переберём заново правила из грамматики. Из можно вывести и , добавим их в множество.
- Снова переберём правила. Из можно вывести только терминал, а нету в множестве.
- После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: .
- Теперь удалим правило , так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
Полезные и бесполезные нетерминалы
Определение: |
Нетерминал | называется полезным (англ. useful) в КС-грамматике , если он может участвовать в выводе, то есть существует порождение вида . Иначе он называется бесполезным (англ. useless).
Теорема: |
Грамматика не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика не содержит ни недостижимых нетерминалов, ни непорождающих. |
Доказательство: |
Необходимость. Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными. Достаточность. Рассмотрим любой нетерминал . Так как он достижим, существуют и такие, что . Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует : , и — не бесполезный. |
Алгоритм удаления бесполезных нетерминалов
- Удалить из грамматики правила, содержащие непорождающие нетерминалы.
- Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Корректность алгоритма
Достаточность данных действий следует из доказанной выше теоремы.
Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.
Допустим, что в грамматике появился непорождающий нетерминал
. Так как до удаления недостижимых нетерминалов существовал вывод из некоторой конечной цепочки терминалов , то было удалено хотя бы какое-то одно правило из этого вывода.Пусть
— правило, первым из удалённых применяемое в выводе . Оно могло быть удалено только в том случае, если в присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то — достижим, следовательно достижимы и все нетерминалы из . Значит, это правило не могло быть удалено.Пример
1. Пусть нам дана грамматика:
2. Удалим правила, содержащие непорождающие нетерминалы:
3. Теперь удалим недостижимые нетерминалы:
Замечание
Шаги алгоритма нельзя менять местами.
Рассмотрим следующую грамматику:
Все нетерминалы в этой грамматике достижимы. Однако, если удалить
как непорождающий, то нетерминал станет недостижимым.См. также
Источники информации
- Wikipedia — Formal grammar
- Wikipedia — Chomsky normal form
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)