ВУЗ:
Составители:
36
6. Автоматные грамматики и конечные
автоматы
Алгоритм разбора цепочек
При рассмотрении под регулярной грамматикой будем понимать леволи-
нейную грамматику, а кроме того, будем считать, что анализируемая цепочка
заканчивается специальным символом ⊥ – признаком конца цепочки.
Для леволинейных грамматик существует следующий алгоритм определе-
ния того, принадлежит ли анализируемая цепочка языку, порождаемому этой
грамматикой (алгоритм разбора):
1. первый символ исходной цепочки a
1
a
2
...a
n
⊥ заменяем нетерминалом A, для
которого в грамматике есть правило вывода A → a
1
(другими словами,
производим «свертку» терминала a
1
к нетерминалу A);
2. затем многократно (до тех пор, пока не считаем признак конца цепочки)
выполняем следующие шаги: полученный на предыдущем шаге нетерми-
нал A и расположенный непосредственно справа от него очередной терми-
нал a
i
исходной цепочки заменяем нетерминалом B, для которого в
грамматике есть правило вывода B → Aa
i
(i = 2, 3,.., n);
Это эквивалентно построению дерева разбора методом «снизу-вверх»: на
каждом шаге алгоритма строим один из уровней в дереве разбора, поднимаясь
от листьев к корню.
При работе этого алгоритма возможны следующие ситуации:
1. прочитана вся цепочка; на каждом шаге находилась единственная нужная
«свертка»; на последнем шаге свертка произошла к символу S. Это означа-
ет, что исходная цепочка a
1
a
2
...a
n
⊥ ∈ L(G);
2. прочитана вся цепочка; на каждом шаге находилась единственная нужная
«свертка»; на последнем шаге свертка произошла к символу, отличному от
S. Это означает, что исходная цепочка a
1
a
2
...a
n
⊥ ∉ L(G);
3. на некотором шаге не нашлось нужной «свертки», т.е. для полученного на
предыдущем шаге нетерминала A и расположенного непосредственно
справа от него очередного терминала a
i
исходной цепочки не нашлось не-
терминала B, для которого в грамматике было бы правило вывода
B → Aa
i
. Это означает, что исходная цепочка a
1
a
2
...a
n
⊥ ∉ L(G);
4. на некотором шаге работы алгоритма оказалось, что есть более одной под-
ходящей «свертки», т.е. в грамматике разные нетерминалы имеют правила
вывода с одинаковыми правыми частями, и поэтому непонятно, к какому
из них производить свертку. Это говорит о недетерминированности раз-
бора. Анализ этой ситуации будет рассмотрен далее, а пока допустим, что
разбор на каждом шаге детерминированный.
Для того чтобы быстрее находить правило с подходящей правой частью,
зафиксируем все возможные свертки (это определяется только грамматикой и
не зависит от вида анализируемой цепочки).
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
