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

Эта статья находится в разработке!

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

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

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

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

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

Символ [math]A[/math] называется недостижимым в КС-грамматике [math]\Gamma[/math], если [math]A[/math] не появляется ни в одной выводимой цепочке.

Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:

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

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

Символ [math]A[/math] называется бесполезным в КС-грамматике [math]\Gamma[/math], если он является недостижимым или непроизводящим.

Теорема:

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

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

[math]\triangleright[/math]

Любой терминальный символ является генерирующим. Пусть [math]A \rightarrow \alpha[/math] и известно, что [math]\alpha[/math] состоит только из генерирующих символов, тогда [math]A[/math] - генерирующий символ. Если [math]\alpha = \epsilon[/math], тогда [math]A[/math] также генерирующий символ.

[math]\triangleleft[/math]