Удаление бесполезных символов из грамматики — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 3 промежуточные версии 3 участников) | |||
Строка 47: | Строка 47: | ||
# Добавим в множество нетерминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>. | # Добавим в множество нетерминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>. | ||
# После следующего обхода правил из грамматики множество не изменится. | # После следующего обхода правил из грамматики множество не изменится. | ||
− | # Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они | + | # Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержат нетерминалы, которых нет в полученном множестве. |
== Достижимые и недостижимые нетерминалы == | == Достижимые и недостижимые нетерминалы == | ||
Строка 84: | Строка 84: | ||
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>. | # Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>. | ||
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество. | # Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество. | ||
− | # Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> | + | # Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нет в множестве. |
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>. | # После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>. | ||
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве. | # Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве. |
Текущая версия на 19:21, 4 сентября 2022
Содержание
Порождающие и непорождающие нетерминалы
Описание
Определение: |
Нетерминал называется порождающим (англ. 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 (рус.)