Задачи по программированию по курсу ЯПиМТ. Родионова Т.Е. - 28 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

28
abE
S aAS b Ошибка
A abSAОшибка
a Выброс Ошибка Ошибка
b Ошибка Выброс Ошибка
$ Ошибка Ошибка Допуск
С помощью этой таблицы проанализируем входную цепочку abbab. В стеке находит-
ся маркер конца стека и начальный символ S.
Таблица разбора цепочки имеет вид:
Входная цепочка Содержимое стека Применяемое правило
Действие
abbab S$ --
abbab aAS
$
1 Выброс
bbab AS$ 1A→ bSA
bbab dSAS$ 1,4 Выброс
bab SAS$ 1,4 S→ b
bab bAS$ 1,4,2 Выброс
ab AS$ 1,4,2 A→ a
ab aS$ 1,4,2,3 Выброс
bS$ 1,4,2,3 S→ b
bb$ 1,4,2,3,2 Выброс
e
$
1,4,2,3,2 Допуск
Получаем, что цепочка допущена.
Алгоритм анализа входной цепочки следующий: на каждом шаге определяется
аванцепочка ( это цепочка из k символов впереди) и верхний символ стека. По этим дан-
ным определяется элемент управляющей матрицы. Возможны следующие варианты дей-
ствий:
- верхний символ магазина заменяется цепочкой (применение правой части правила)
и к списку применяемых правил добавляется новый номер правила;
- верхний символ стека совпадает с текущим входным символом, следовательно, он
выбрасывается из магазина;
- входная цепочка пуста и стек пуст, то работа прекращается, и цепочка считается
допущенной;
- при возникновении ошибки разбор прекращается, и выдается сообщение об ошиб-
ки.
Ко второму классу относятся распознаватели, которые, читая входную цепочку строят ее дерево вы-
вода начиная с вершин, соответствующих наиболее мелким конструкциям, икончаякорнем. Вэтомслучае
детерминированный разбор реализуется в терминах “сдвиг” и “свертка”. Сдвиг – это перенос символа из

Страницы