Изменения

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

Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ

10 248 байт убрано, 20:48, 5 ноября 2014
→‎Пример работы
<tex>\begin{array}{l l}
A \rightarrow \varepsilon|BB|CD\\ B \rightarrow BB|CD\\
C \rightarrow (\\
D \rightarrow BE|)\\
E \rightarrow )\\
\end{array}</tex>
Инициализация массива <tex>d</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
Заполнение массива <tex>d</tex>.
 
{| clear="both" |}
Итерация <tex>m = 1</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
Итерация <tex>m = 2</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
Итерация <tex>m = 3</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
Итерация <tex>m = 4</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
Итерация <tex>m = 5</tex>.
 {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
| align="center"| ●
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
| align="center"| ●
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| clear<div style="clear:both;" |}></div>
== См. также ==
Kabanov
418
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/40683»

Навигация