Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования




Этот алгоритм в целом похож на алгоритм для грамматик простого предшество­вания, рассмотренный выше. Он также выполняется расширенным МП-автома­том и имеет те же условия завершения и обнаружения ошибок. Основное отличие состоит в том, что при определении отношения предшествования этот алгоритм не принимает во внимание находящиеся в стеке нетерминальные символы и при сравнении ищет ближайший к верхушке стека терминальный символ. Однако после выполнения сравнения и определения границ основы при поиске правила в грамматике нетерминальные символы следует, безусловно, принимать во вни­мание.

Алгоритм состоит из следующих шагов.

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

Шаг 2. Сравнить с помощью отношения предшествования терминальный сим­вол, ближайший к вершине стека (левый символ отношения), с текущим симво­лом входной цепочки, обозреваемым считывающей головкой (правый символ отношения). При этом из стека надо выбрать самый верхний терминальный сим­вол, игнорируя все возможные нетерминальные символы.

Шаг 3. Если имеет место отношение или =×, то произвести сдвиг (перенос то­щего символа из входной цепочки в стек и сдвиг считывающей головки на один шаг вправо) и вернуться к шагу 2. Иначе перейти к шагу 4.

Шаг 4. Если имеет место отношение ·>, то произвести свертку. Для этого надо найти на вершине стека все терминальные символы, связанные отношение («основу»), а также все соседствующие с ними нетерминальные символы (при определении отношения нетерминальные символы игнорируются). Если терминальных символов, связанных отношением =×, на верхушке стека нет, то в качестве основы используется один, самый верхний в стеке терминальный символ сте­ка. Все (и терминальные, и нетерминальные) символы, составляющие основу надо удалить из стека, а затем выбрать из грамматики правило, имеющее правую часть, совпадающую с основой, и поместить в стек левую часть выбранного правила. Если правило, совпадающее с основой, найти не удалось, то необходимо прервать выполнение алгоритма и сообщить об ошибке, иначе, если разбор не за­кончен, то вернуться к шагу 2.

Шаг 5. Если не установлено ни одно отношение предшествования между текущим символом входной цепочки и самым верхним терминальным символом в стеке, то надо прервать выполнение алгоритма и сообщить об ошибке.

Конечная конфигурация данного МП-автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования.

Пример

Дано: G({(, ), ^, &, ~, a}, {S, T, E, F}, P, S), где

P: SS^T | T

TT&E | E




E→~E | F

F→ (E) | a

Построить: распознаватель для G.

Таблица 3.10 - Построение множеств L(A) и R(A)

i Li(A) Ri(A)
L0(S)={S, T} L0(T)={T, E} L0(E)={~, F} L0(F)={(, a} R0(S)={T} R0(T)={E} R0(E)={E, F} R0(F)={), a}
L1(S)={S, T, E} L1(T)={T, E, ~, F} L1(E)={~, F, (, a} L1(F)={(, a} R1(S)={T, E} R1(T)={E, F} R1(E)={E, F, ), a} R1(F)={), a}
L2(S)={S, T, E, ~, F, (, a} L2(T)={T, E, ~, F, (, a} L2(E)={~, F, (, a} L2(F)={(, a} R2(S)={T, E, F, ), a} R2(T)={E, F, ) a} R2(E)={E, F, ), a} R2(F)={), a}
L3(S)={S, T, E, ~, F, (, a} L3(T)={T, E, ~, F, (, a} L3(E)={~, F, (, a} L3(F)={(, a} R3(S)={T, E, F, ), a} R3(T)={E, F, ) a} R3(E)={E, F, ), a} R3(F)={), a}

Таблица 3.11 - Построение множеств Lt(A) и Rt(A)

i Lt(A) Rt(A)
Lt0(S)={^} Lt0(T)={&} Lt0(E)={~} Lt0(F)={(, a} Rt0(S)={^} Rt0(T)={&} Rt0(E)={~} Rt0(F)={), a}
Lt1(S)={^, &, ~, (, a } Lt1(T)={&, ~, (, a} Lt1(E)={~, (, a} Lt1(F)={(, a} Rt1(S)={^, &, ~, ), a} Rt1(T)={&, ~, ), a} Rt1(E)={~, ), a} Rt1(F)={), a}
Lt2(S)={^, &, ~, (, a } Lt2(T)={&, ~, (, a} Lt2(E)={~, (, a} Lt2(F)={(, a} Rt2(S)={^, &, ~, ), a} Rt2(T)={&, ~, ), a} Rt2(E)={~, ), a} Rt2(F)={), a}

Таблица 3.12 - Матрица операторного предшествования символов грамматики

Символы ^ & ~ ( ) а
^ ·> ·> ·>
& ·> ·> ·> ·>
~ ·> ·> ·> ·>
(
) ·> ·> ·> ·>
а ·> ·> ·> ·>

Для ^ находящейся в правиле вывода слева от нетерминала Т, во множество Lt(Т) входят символы &, ~, (, a , значит в строке матрицы для ^ ставим знак меньшего предшествования в позициях этих символов. С другой стороны этот символ ^ находится справа от S. Во множество Rt(S) входят символы ^, &, ~, ), a, значит знак большего предшествования ставится в столбце для ^ в позициях этих символов. Символы ( и ) в правиле вывода находятся радом, поэтому в позиции этих символов ставится знак равного предшествования (игнорируя нетерминал Е).







Дата добавления: 2015-02-18; просмотров: 825; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 8865 - | 6713 - или читать все...

Читайте также:

 

3.84.243.246 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.