48
правок
Изменения
Нет описания правки
=== Пример ===
Рассмотрим грамматику, причем сразу пронумеруем правила::#<tex>S\rightarrow ABC|</tex>#<tex>S\rightarrow DS</tex>:#<tex>A\rightarrow \varepsilon</tex>:#<tex>B\rightarrow AC</tex>:#<tex>C\rightarrow \varepsilon</tex>:#<tex>D\rightarrow d</tex>
''Поскольку правило 6 содержит справа терминалы, оно заведомо не будет влиять на ответ, поэтому мы не будем его учитывать.''
{| class="wikitable"
|Построим массив списков <tex>\mathtt{concerned\text{-}rules}</tex>.
{| class="wikitable"
| colspan=5 |<tex>\mathtt{concerned\text{-}rules}</tex>
|-
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
|-
|2
|1, 4
|1
|1, 4
|2
|}
|-
|Зададим начальные значения массивам <tex>\mathtt{counter}</tex> и <tex>\mathtt{is\text{-}epsilon}</tex>.
{| class="wikitable"
|colspan=5 | <tex>\mathtt{counter}</tex>
|-
!1
!2
!3
!4
!5
|-
|3
|2
|0
|2
|0
|}
{| class="wikitable"
|colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>
|-
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
|-
|0
|0
|0
|0
|0
|}
|-
|Заметим, что правила 3 и 5 являются <tex>\varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>\mathtt{Q}</tex> лежит <tex>A</tex> и <tex>C</tex>. <tex>\mathtt{counter}</tex> остался без изменений, а <tex>\mathtt{is\text{-}epsilon}</tex> выглядит следующим образом:
{| class="wikitable"
|colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>
|-
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
|-
|0
|1
|0
|1
|0
|}
|-
|Достанем из очереди <tex>A</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится, а <tex>\mathtt{counter}</tex> станет таким:
{| class="wikitable"
|colspan=5 | <tex>\mathtt{counter}</tex>
|-
!1
!2
!3
!4
!5
|-
|2
|2
|0
|1
|0
|}
|-
|Достанем из очереди <tex>C</tex>. После проведения действий из алгоритма в очередь добавится <tex>B</tex>.
{| class="wikitable"
|colspan=5 | <tex>\mathtt{counter}</tex>
|-
!1
!2
!3
!4
!5
|-
|1
|2
|0
|0
|0
|}
{| class="wikitable"
|colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>
|-
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
|-
|0
|1
|1
|1
|0
|}
|-
|Достанем из очереди <tex>B</tex>. После действий алгоритма в очередь добавится S.
{| class="wikitable"
|colspan=5 | <tex>\mathtt{counter}</tex>
|-
!1
!2
!3
!4
!5
|-
|0
|2
|0
|0
|0
|}
{| class="wikitable"
|colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>
|-
!<tex>S</tex>
!<tex>A</tex>
!<tex>B</tex>
!<tex>C</tex>
!<tex>D</tex>
|-
|1
|1
|1
|1
|0
|}
|-
|Достанем из очереди <tex>S</tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\varepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.
|}
Если применять алгоритм без модификации с очередью, то действия будут следующие:
# Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
