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

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

Описание

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

Нетерминал [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]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]. Значит, это правило не могло быть удалено.

Пример

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 (рус.)