Удаление бесполезных символов из грамматики

Порождающие и непорождающие нетерминалы

Описание

Определение:

Нетерминал [math]A[/math] называется порождающим (англ. generating), если из него может быть выведена конечная терминальная цепочка. Иначе он называется непорождающим.

Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.

Лемма:

После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.

Доказательство:

[math]\triangleright[/math]

Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.

[math]\triangleleft[/math]

Алгоритм

Шаг 0. Множество порождающих нетерминалов пустое.
Шаг 1. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.
Шаг 2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части.
Шаг 3. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], где [math]\left| \Gamma \right|[/math] — размер грамматики. Однако используя очередь можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Модификация алгоритма с очередью

Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:

• [math]\mathrm{isGenerating[nonterm_i]}[/math] — является ли нетерминал [math]\mathrm{nonterm_i}[/math] порождающим или нет,
• [math]\mathrm{counter[rule_i]}[/math] — счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
• [math]\mathrm{concernedRules[nonterm_i]}[/math] — для каждого нетерминала [math]\mathrm{nonterm_i}[/math] список номеров правил, в правой части которых он встречается,
• [math]\mathrm{Q}[/math] — очередь нетерминалов, помеченных порождающими, но ещё не обработанных.

Вначале для всех нетерминалов в [math]\mathrm{isGenerating}[/math] поставим [math]false[/math]. В [math]\mathrm{counter}[/math] поставим количество нетерминалов в правой части. Нетерминалы, у которых счётчик [math]\mathrm{counter}[/math] нулевой, добавим в очередь и отметим их порождающими.
Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем [math]\mathrm{counter}[/math] для всех правил из [math]\mathrm{concernedRules}[/math] для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.
Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим следующую грамматику:

[math] S\rightarrow Ac\\ A\rightarrow SD\\ D\rightarrow aD\\ A\rightarrow a [/math]

Применяя описанный алгоритм:

1. Изначально множество порождающих нетерминалов состоит из одного элемента [math]A[/math].
2. Добавим в множество нетерминал [math]S[/math], так как существует правило [math]S\rightarrow Ac[/math], в правой части которого стоят нетерминал [math]A[/math], который есть в множестве, и терминал [math]c[/math].
3. После следующего обхода правил из грамматики множество не изменится.
4. Теперь удалим правила [math]A\rightarrow SD[/math] и [math]D\rightarrow aD[/math], так как они содержат нетерминалы, которых нет в полученном множестве.

Достижимые и недостижимые нетерминалы

Описание

Определение:

Нетерминал [math]A[/math] называется достижимым (англ. reachable) в КС-грамматике [math]\Gamma[/math], если существует порождение [math]S \Rightarrow^* \alpha A \beta[/math]. Иначе он называется недостижимым (англ. unreachable).

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.

Лемма:

После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.

Доказательство:

[math]\triangleright[/math]

Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.

[math]\triangleleft[/math]

Алгоритм

Шаг 0. Множество достижимых нетерминалов состоит из единственного элемента: [math]\lbrace S \rbrace[/math].
Шаг 1. Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.
Шаг 2. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], однако используя обход в глубину можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим следующую грамматику:

[math] S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c [/math]

Применяя описанный алгоритм:

1. Возьмём множество, состоящее из единственного элемента: [math]\lbrace S \rbrace[/math].
2. Из [math]S[/math] достижимы нетерминалы [math]A[/math], [math]B[/math], [math]C[/math] и [math]D[/math]. Добавим их в множество и получим [math]\lbrace S, A, B, C, D \rbrace[/math].
3. Множество изменилось. Переберём заново правила из грамматики. Из [math]A[/math] можно вывести [math]E[/math] и [math]F[/math], добавим их в множество.
4. Снова переберём правила. Из [math]C[/math] можно вывести только терминал, а [math]G[/math] нет в множестве.
5. После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: [math]\lbrace S, A, B, C, D, E, F \rbrace[/math].
6. Теперь удалим правило [math]G\rightarrow AD[/math], так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

Полезные и бесполезные нетерминалы

Описание

Определение:

Нетерминал [math]A[/math] называется полезным (англ. useful) в КС-грамматике [math]\Gamma[/math], если он может участвовать в выводе, то есть существует порождение вида [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w[/math]. Иначе он называется бесполезным (англ. useless).

Теорема:

Грамматика [math]\Gamma[/math] не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика [math]\Gamma[/math] не содержит ни недостижимых нетерминалов, ни непорождающих.

Доказательство:

[math]\triangleright[/math]

[math]\Leftarrow[/math] Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными. [math]\Rightarrow[/math] Рассмотрим любой нетерминал [math]A[/math]. Так как он достижим, существуют [math]\alpha[/math] и [math]\beta[/math] такие, что [math]S \Rightarrow ^* \alpha A \beta[/math]. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует [math]\omega \in \Sigma ^ *[/math]: [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega[/math], и [math]A[/math] — не бесполезный.

[math]\triangleleft[/math]

Алгоритм

Алгоритм состоит из двух этапов:

1. Удалить из грамматики правила, содержащие непорождающие нетерминалы.
2. Удалить из грамматики правила, содержащие недостижимые нетерминалы.

Корректность алгоритма

Достаточность данных действий следует из доказанной выше теоремы.

Теорема:

После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.

Доказательство:

[math]\triangleright[/math]

Допустим, что в грамматике появился непорождающий нетерминал [math]A[/math]. Так как до удаления недостижимых нетерминалов существовал вывод из [math]A[/math] некоторой конечной цепочки терминалов [math]\omega[/math], то было удалено хотя бы какое-то одно правило из этого вывода. Пусть [math]B\rightarrow\alpha[/math] — правило, первым из удалённых применяемое в выводе [math]A \Rightarrow ^* \omega[/math]. Оно могло быть удалено только в том случае, если в [math]\alpha[/math] присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то [math]B[/math] — достижим, следовательно достижимы и все нетерминалы из [math]\alpha[/math]. Значит, это правило не могло быть удалено.

[math]\triangleleft[/math]

Пример

1. Пусть нам дана грамматика:

[math] S\rightarrow AS|BS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f [/math]

2. Удалим правила, содержащие непорождающие нетерминалы:

[math] S\rightarrow AS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f [/math]

3. Теперь удалим недостижимые нетерминалы:

[math] S\rightarrow AS|s \\ A\rightarrow a [/math]

Замечание

Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:

[math] S\rightarrow AB|a \\ A\rightarrow b [/math]

Все нетерминалы в этой грамматике достижимы. Однако, если удалить [math]B[/math] как непорождающий, то нетерминал [math]A[/math] станет недостижимым.

См. также

• Контекстно-свободные грамматики
• Нормальная форма Хомского

Источники информации

• Wikipedia — Formal grammar
• Wikipedia — Chomsky normal form
• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)