Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Алгоритм LR-анализа




 

Схематически LR-анализатор представлен на рис. 36. Он состоит из входного потока, выхода, стека, управляющей программы и таблицы синтаксического анализа, состоящей из двух частей (действие (action) и переход (goto)). Управляющая программа для всех LR-анализаторов одна и та же; изменяются только таблицы синтаксического анализа. Программа синтаксического анализа считывает символы из входного буфера по одному и использует стек для хранения строк вида s0X1s1X2s2 …Xmsm (sm находится на вершине стека). Каждый символ X, является символом грамматики, а каждый si — символом состоянием. Каждый символ состояния обобщает информацию, содержащуюся в стеке ниже его. Комбинация символа состояния на вершине стека и текущего входного символа используется в качестве индекса таблицы синтаксического анализа и определяет дальнейшее действие — перенос или свертку. При реализации грамматические символы нe обязаны появляться в стеке, однако для облегчения понимания принципов работы LR-анализатора их лучше рассматривать.

Таблица синтаксического анализа состоит из двух частей — функции действий синтаксического анализа a ction и функции переходов goto. Управляющая программа LR-анализатора функционирует следующим образом. Она определяет sm, текущее состояние на вершине стека, и ai текущий входной символ. Затем программа обращается к асtion[sm, аi], ячейке таблицы действий синтаксического анализа, определяемой состоянием sm и символом аi, которая может иметь одно из четырех значений:

1) перенос s, где s — состояние;

2) свертка в соответствии с продукцией А →β;

3) допуск;

4) ошибка.

Рис. 36. Модель LR-анализатора

Функция goto получает в качестве аргументов состояние и символ грамматики и воз­вращает новое состояние. Функция goto таблицы синтаксического ана­лиза, построенная на основе грамматики Gс использованием LR- метода, представляет собой функцию переходов детерминированного конеч­ного автомата. Начальным состоянием этого ДКА является состояние, изначально размещаемое на вершине стека LR-анализатора.

Конфигурация LR-анализатора представляет собой пару, первый компонент кото­рой — содержимое стека, а второй — непросмотренная часть входного потока: (s0Xls)X2s2 …Xmsm,aiai+1an $). Эта конфигурация представляет правосентенциальную форму Х1Х2 …Xm aiai+1…an, по сути, тем же способом, что и ПС-анализатор; новым яв­ляется только наличие в стеке состояний.

Следующий шаг синтаксического анализатора определяется текущим входным символом а, и состоянием на вершине стека sm в соответствии со значением ячейки таблицы action[sm, аi]. Конфигурации, получаемые после каждого из четырех типов действий, следующие.

1. Если action[sm, аi] = "перенос s", синтаксический анализатор выполняет перенос, пе­реходя в конфигурацию (s0Xls1X2s2 …Xmsmais,aiai+1an $). Синтаксический анализа­тор переносит в стек текущий входной символ аi, и очередное состояние s, опреде­ляемое значением action[sm, аi]; текущим входным символом становится ai+1.

2. Если action[sm, аi] = "свертка А → β”, то синтаксический анализатор выполняет свертку, переходя в конфигурацию (s0Xls1X2s2 …Xm-rsm-rAs,aiai+1an $), где s = goto[sm-r,A], а r — длина β, правой части продукции. Здесь синтаксический ана­лизатор вначале снимает со стека 2r - символов (r символов состояний и r символов грамматики), выводя на вершину стека состояние sm-r. Затем он вносит в стек А (левую часть продукции) и s, запись из ячейки

goto[sm-r, А]. Текущий входной символ при этом не изменяется. Последовательность снимаемых со стека символов грамматики X m-r+1 … Хт всегда соответствует правой части продукции свертки.

3. Если action[sm, ai] = "допуск", синтаксический анализ завершает свою работу.

4. Если action[sm, ai] = "ошибка", синтаксический анализатор обнаружил ошибку и вызывает подпрограмму восстановления после нее.

Все LR-анализаторы ведут себя одинаково; единственная разница между ними заключается в таблицах action и goto.




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


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


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



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




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