Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь
FAQ
Написать работу

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву

Мы поможем в написании ваших работ!

ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ Написать работу

Алгоритм 6.3. Функционирование распознавателя цепочек

↑

⇐ ПредыдущаяСтр 5 из 8Следующая ⇒

для LL (1)-грамматик

Шаг 1. Помещаем в стек начальный символ грамматики S, а во входной буфер исходную цепочку символов.

Шаг 2.До тех пор пока в стеке и во входном буфере останется только пустая строка e либо будет обнаружена ошибка в алгоритме разбора, выполняем одно из следующих действий:

- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® х при условии, что а Î FIRST (1, x), т.е. извлекаем из стека символ А и заносим в стек строку х, не меняя содержимого входного буфера;

- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® e при условии, что а Î FOLLOW (1, A), т.е. извлекаем из стека символ А и заносим в стек строку e, не меняя содержимого входного буфера;

- если на верхушке стека находится терминальный символ а, совпадающий с очередным символом входной строки, то выполняем операцию «выброс», т.е. удаляем из стека и входного буфера данный терминальный символ;

- если содержимое стека и входного буфера пусто, то исходная строка прочитана полностью, и разбор завершен удачно;

- если ни одно из данных условий не выполнено, то цепочка не принадлежит заданному языку, и алгоритм завершает свою работу с ошибкой.

Пример 6.1. Дана грамматика G ({ S, T, R }, {+, -, (,), a, b }, P, S), с правилами P: 1) S ® TR; 2) R ®e | + TR | - TR; 3) T ®(S) | a | b. Построить распознаватель для строки (a +(b - a)) языка грамматики G.

Этап 1. Преобразуем грамматику G в грамматику G ¢, не содержащую e -правил:

N ₀ = { R };

N ₁= { R }, т.к. N ₀ = N ₁, то во множество P¢ войдут правила:

1) S ® TR | T;2) R® +TR | +T | -TR | -T; 3) T ®(S) | a | b.

Этап 2. Построение множеств FIRST (1, A) для каждого нетерминала А представлено в таблице 6.1.

Таблица 6.1 – Построение множеств FIRST (1, A)

FIRST_i (1, A) FIRST (1, A)

S T T, (, a, b T, (, a, b (, a, b

R +, - +, - +, - +, -

T (, a, b (, a, b (, a, b (, a, b

Этап 3. Построение множеств FOLLOW (1, A) для каждого нетерминала А представлено в таблице 6.2.

Таблица 6.2 – Построение множеств FOLLOW (1, A)

Шаг Нетерминалы FOLLOW_i (1, A) FOLLOW_i^’ (1, A) FOLLOW_i^’’ (1, A)

S ) ), e ), e

R Æ Æ Æ

T R R, +, - R, +, -

S ), e ), e ), e

R ), e ), e ), e

T R, +, - R, +, - R, +, -,), e

S ), e ), e ), e

R ), e ), e ), e

T R, +, -,), e R, +, -,), e R, +, -,), e

FOLLOW (1, S) ), e

FOLLOW (1, R) ), e

FOLLOW (1, T) +, -,), e

Этап 4. Множества FIRST (1, A) и FOLLOW (1, A) для каждого нетерминала А сведены в таблицу 6.3.

Таблица 6.3 – Множества FIRST (1, A) и FOLLOW (1, A)

A FIRST (1, A) FOLLOW (1, A)

S (, a, b ), e

R +, - ), e

T (, a, b +, -,), e

Грамматика G является LL (1) - грамматикой, т.к. для каждого нетерминала А, имеющего альтернативные выводы, множества FIRST (1, A) попарно не пересекаются, а для нетерминала R они также не пересекаются со множеством FOLLOW (1, R).

Шаг 5. Разбор строки (a +(b - a)) для грамматики G показан в таблице 6.4.

Таблица 6.4 - Разбор строки (a +(b - a)) для грамматики G

Стек Входной буфер Действие

S (a +(b - a)) свертка S ® TR, т.к. (Î FIRST (1, TR)

TR (a +(b - a)) свертка T ®(S), т.к. (Î FIRST (1, (S))

(S) R (a +(b -a)) выброс

S) R a +(b - a)) свертка S ® TR, т.к. a Î FIRST (1, TR)

TR) R a +(b - a)) свертка T ® a, т.к. a Î FIRST (1, a)

aR) R a +(b - a)) выброс

R) R +(b - a)) свертка R ®+ TR, т.к. +Î FIRST (1, TR)

+ TR) R +(b - a)) выброс

TR) R (b - a)) свертка T ®(S), т.к. (Î FIRST (1, (S))

(S) R) R (b - a)) выброс

S) R) R b - a)) свертка S ® TR, т.к. b Î FIRST (1, TR)

TR) R) R b - a)) свертка T ® b, т.к. b Î FIRST (1, b)

bR) R) R b - a)) выброс

R) R) R - a)) свертка R ®- TR, т.к. -Î FIRST (1, - TR)

- TR) R) R - a)) выброс

TR) R) R a)) свертка T ® a, т.к. a Î FIRST (1, a)

aR) R) R a)) выброс

R) R) R )) свертка R ®e, т.к.) Î FOLLOW (1, R)

) R) R )) выброс

R) R ) свертка R ®e, т.к.) Î FOLLOW (1, R)

) R ) выброс

R e свертка R ®e, т.к. eÎ FOLLOW (1, R)

e e строка принята полностью

Шаг 6. Получили следующую цепочку вывода:

S Þ TR Þ(S) R Þ(TR) R Þ(aR) R Þ(a + TR) R Þ(a +(S) R) R Þ(a +(TR) R) R Þ

Þ(a +(bR) R) R Þ(a +(b - TR) R) R Þ(a +(b - aR) R) R Þ(a +(b - a) R) R Þ(a +(b - a)) R

Þ(a +(b - a)).

Нисходящее дерево разбора цепочки представлено на рисунке 6.1.

⇐ Предыдущая 1 2 3 456 7 8 Следующая ⇒

Познавательные статьи:

Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров

Последнее изменение этой страницы: 2019-04-30; просмотров: 322; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.198 (0.006 с.)