Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм синтаксического анализа простого предшествования




 

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

Возможны следующие варианты.

1) Ни одно из отношений не определено. Тогда входная цепочка отвергается.

2) Для пары символов определено отношение <• или , тогда выполняется перенос.

При переносе анализатор записывает символ <• в стек, если соответствующее отношение выполняется для данной пары, после чего переносит в стек левый символ входной цепочки. Во входной цепочке осуществляется сдвиг (переход) к следующему символу.

3) Для пары определено отношение >, тогда выполняется свертка.

При выполнении свертки, анализатор работает следующим образом.

3.1 Просматривает символы в стеке, пока не обнаружит символ <•. Выделяет подцепочку, состоящую из просмотренных символов (без знака <•). Снимает со стека найденные символы.

3.2 Ищет правило вывода грамматики, правая часть которого совпадает с подцепочкой, выделенной на предыдущем шаге. Если такое правило найдено, переход к следующему шагу, иначе – к последнему шагу 4.

3.3 Исключает из стека найденные на первом шаге подцепочку и символ <•. В итоге образуется пара, состоящая из символа на верхушке стека и нетерминального символа из левой части продукции, найденной на шаге 3.2.

3.4 Ищет отношение предшествования, выполняющееся для пары, образованной на предыдущем шаге (это только <• или ).

Если ни одно отношение предшествования не выполнено, входная цепочка отвергается.

В противном случае в стек записывается символ <•, если для пары выполнено данное отношение, и символ из левой части продукции. На этом свертка заканчивается.

4) Анализируются цепочки, записанные в стеке и на входной ленте. Если в стеке находится цепочка $ <• S, где S – стартовый символ грамматики, а на входной ленте только маркер конца строки $, то входная цепочка принимается (допускается). В противном случае – цепочка отвергается.

 




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 901; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




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