Удаление eps-правил из грамматики — различия между версиями
(→Пример) |
(→Пример) |
||
Строка 58: | Строка 58: | ||
C\rightarrow c|\varepsilon | C\rightarrow c|\varepsilon | ||
\end{array} | \end{array} | ||
− | </tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются | + | </tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами. |
# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила: | # Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила: | ||
#* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex> | #* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex> | ||
Строка 64: | Строка 64: | ||
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex> | # Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex> | ||
− | В результате мы получим новую грамматику без | + | В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил: |
<tex>\begin{array}{l l} | <tex>\begin{array}{l l} | ||
S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\ | S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\ |
Версия 19:58, 5 ноября 2013
Содержание
Используемые определения
Определение: |
Правила вида | называются -правилами.
Определение: |
Нетерминал | называется -порождающим, если .
Алгоритм удаления ε-правил из грамматики
Вход: КС грамматика
Выход: КС грамматика без -правил (может присутствовать правило , но в этом случае не встречается в правых частях правил); .
- Добавить все правила из в .
- Найти все . -порождаюшие нетерминалы
- Для каждого правила вида (где — последовательности из терминалов и нетерминалов, — -порождающие нетерминалы) добавить в все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов .
- Удалить все -правила из .
- Если в исходной грамматике выводилось , то необходимо добавить новый нетерминал , сделать его стартовым, добавить правило .
Доказательство корректности
Теорема: |
Если грамматика была построена с помощью описанного выше алгоритма по грамматике , то . |
Доказательство: |
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика
|
Пример
Рассмотрим грамматику:
, в которой , и являются -порождающими нетерминалами.- Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
- для
- для
- Удалим праила и
В результате мы получим новую грамматику без
-правил:Алгоритм поиска ε-порождающих нетерминалов
Вход: КС грамматика
Выход: множество -порождающих нетерминалов.
- Найти все -правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
- Перебираем правила грамматики . Если найдено правило , для которого верно, что каждый принадлежит множеству, то добавить в множество.
- Если на шаге 2 множество изменилось, то повторить шаг 2.
Доказательство корректности
Теорема: |
Описанный выше алгоритм находит все -порождающие нетерминалы грамматики . |
Доказательство: |
Для доказательства корректности алгоритма достаточно показать, что, если множество Пусть после завершения алгоритма существуют нетерминалы такие, что они являются -порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все -порождающие нетерминалы. -порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал , из которого выводится за наименьшее число шагов. Тогда в грамматике есть правило , где каждый нетерминал — -порождающий. Каждый входит в множество -порождающих нетерминалов, так как иначе вместо необходимо было взять . Следовательно, на одной из итераций алгоритма уже добавился в множество -порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все -порождающие нетерминалы. |
Пример
Рассмотрим грамматику:
- Возьмём множество состоящее из -порождающих нетерминалов .
- Добавим в множество, так как правая часть правила состоит только из нетерминалов из множества.
- Повторим второй пункт для правила и получим множество .
- Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.
Таким образом
-порождающими нетерминалами являются , , и .Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)