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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 25: Строка 25:
 
===Модификация алгоритма с очередью===
 
===Модификация алгоритма с очередью===
 
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
 
Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:
*<tex>\mathrm{isGenerating[nonterm_i]}</tex> {{---}} является ли нетерминал <tex>\mathrm{nonterm_i}</tex> порождающим или нет,
+
*<tex>\mathrm{isGenerating[nonterm_i]}</tex> {{---}} является ли нетерминал <tex>nonterm_i</tex> порождающим или нет,
 
*<tex>\mathrm{counter[rule_i]}</tex> {{---}} счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
 
*<tex>\mathrm{counter[rule_i]}</tex> {{---}} счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,
*<tex>\mathrm{concernedRules[nonterm_i]}</tex> {{---}} для каждого нетерминала <tex>\mathrm{nonterm_i}</tex> список номеров правил, в правой части которых он встречается,
+
*<tex>\mathrm{concernedRules[nonterm_i]}</tex> {{---}} для каждого нетерминала <tex>nonterm_i</tex> список номеров правил, в правой части которых он встречается,
 
*<tex>\mathrm{Q}</tex> {{---}} очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
 
*<tex>\mathrm{Q}</tex> {{---}} очередь нетерминалов, помеченных порождающими, но ещё не обработанных.
  
Строка 43: Строка 43:
 
  A\rightarrow a     
 
  A\rightarrow a     
 
</tex>
 
</tex>
Применяя описанный алгоритм:
 
 
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
 
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
 
# Добавим в множество нетерминал <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>, так как они содержит нетерминалы, которых нет в полученном множестве.
  
 
== Достижимые и недостижимые нетерминалы ==
 
== Достижимые и недостижимые нетерминалы ==
===Описание===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (англ. ''unreachable'').
 
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (англ. ''unreachable'').
 
}}
 
}}
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми.  
+
 
 +
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
 +
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
 +
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
 +
# Если на шаге 2 множество изменилось, повторить шаг 2.
 +
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
 +
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 62: Строка 66:
 
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
 
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
 
}}
 
}}
===Алгоритм===
 
'''Шаг 0.''' Множество достижимых нетерминалов состоит из единственного элемента: <tex>\lbrace S \rbrace</tex>.<br>
 
'''Шаг 1.''' Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.<br>
 
'''Шаг 2.''' Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
 
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
 
  
 
=== Время работы алгоритма ===
 
=== Время работы алгоритма ===
Строка 80: Строка 79:
 
     C\rightarrow c
 
     C\rightarrow c
 
</tex>
 
</tex>
Применяя описанный алгоритм:
 
 
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
 
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \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>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>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
  
 
== Полезные и бесполезные нетерминалы ==
 
== Полезные и бесполезные нетерминалы ==
===Описание===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 100: Строка 97:
 
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
 
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
 
|proof=
 
|proof=
<tex>\Leftarrow</tex>
+
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.
<br/>
 
:Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.
 
  
<tex>\Rightarrow</tex>
+
''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
<br/>
 
:Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
 
 
}}
 
}}
  
===Алгоритм===
+
== Алгоритм удаления бесполезных нетерминалов ==
Алгоритм состоит из двух этапов:
 
 
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
 
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
 
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
 
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.
Строка 117: Строка 109:
 
Достаточность данных действий следует из доказанной выше теоремы.
 
Достаточность данных действий следует из доказанной выше теоремы.
  
{{Теорема
+
Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.
|id=th1
+
 
|statement=
 
После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.
 
|proof=
 
 
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
 
Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.
  
 
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
 
Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.
}}
 
  
 
=== Пример ===
 
=== Пример ===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)