Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!

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

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




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

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

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

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

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

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

ПримерДана грамматика G({a, (, )}, {S, R}, P, S), с правилами P:

1) S®(R | a; 2) R®Sa). Построить распознаватель для строки (((aa)a)a)^к.

Этап 1. Построим множества крайних левых и крайних правых символов L(A) и R(A) относительно всех нетерминальных символов грамматики (таблица 3.7).

Таблица 3.7 – Построение множеств L(A) и R(A) для грамматики G

Шаг Li(A) Ri(A)
L0(S)={(, a} L0(R)={S} R0(S)={R, a} R0(R)={)}
L1(S)={(, a} L1(R)={S, (, a} R1(S)={R, a, )} R1(R)={)}
L2(S)={(, a} L2(R)={S, (, a} R2(S)={R, a, )} R2(R)={)}
Результат L(S)={(, a} L(R)={S, (, a} R(S)={R, a, )} R(R)={)}

Этап 2. На основе построенных множеств и правил вывода грамматики составим матрицу предшествования символов (таблица 3.8).

Поясним заполнение матрицы предшествования. В правиле грамматики S®(R символ (стоит слева от нетерминального символа R. Во множестве L(R) входят символы S, (, a. Ставим знак в клетках матрицы, соответствующих этим символам, в строке для символа (.

В правиле грамматики R®Sa) символ a стоит справа от нетерминального символа S. Во множество R(S) входят символы R, a, ). Ставим знак ×> в клетках матрицы, соответствующих этим символам, в столбце для символа a.




В строке символа ^н ставим знак в клетках символов, входящих во множество L(S), т.е. символов (, a. В столбце символа ^к ставим знак ×> в клетках, входящих во множество R(S), т.е. символов R, a,).

В клетках, соответствующих строке символа S и столбцу символа a, ставим знак , т.к. существует правило R®Sa), в котором эти символы стоят рядом. По тем же соображениям ставим знак в клетках строки а и столбца ), а также строки ( и столбца R.

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

Символы S R a ( ) ^к
S          
R     ×>     ×>
a     ×>   ×>
(    
)     ×>     ×>
^н        




Дата добавления: 2015-02-18; просмотров: 749; Опубликованный материал нарушает авторские права? | Защита персональных данных


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

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете??? 8829 - | 7639 - или читать все...

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

 

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


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