Студопедия

КАТЕГОРИИ:


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

Компиляторы. Синтаксический анализ. Метод нисходящего разбора

 

Синтаксический анализ – Во время синтаксического анализа предложения исходной программы распознаются как языковые конструкции описываемые используемые грамматикой. Можно рассматривать этот процесс как построение дерева грамматического разбора для транслируемых предложений.

Методы грамматического разбора можно разбить на 2 больших класса: восходящие и нисходящие в соответствии с порядком построения дерева грамматического разбора. Нисходящие методы начинают с правила грамматики, определяющие конечную цель анализа с корня дерева грамматического разбора и пытаются так его наращивать чтобы последующие узлы дерева соответствовали синтаксису анализируемого предложения.

Нисходящий метод(метод рекурсивного спуска)

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

Рассмотрим в качестве примера правило <read>::= READ (<id-list>), записанное в форме Бекуса-Наура (БНФ). Грамматика БНФ состоит из подмножества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка программирования. Это определение синтаксиса предложения READ языка Паскаль, обозначенное в грамматике как <read>. Символ “::=” можно читать как “является по определению”. Строки символов, заключенные в угловые скобки “<” и ”>”, называются нетерминальными символами, т.е. являются именами конструкций, определенными внутри грамматики. То, что не заключено в угловые скобки, называется терминальными символами грамматики - лексемами. Таким образом, это правило определяет, что конструкция <read> состоит из лексемы READ, за которой следует лексема “(“, за ней следует конструкция языка, называемая <id-list>, за которой следует лексема “)”. Для распознавания нетерминального символа <read> необходимо, чтобы было определение для нетерминального символа <id-list>.

<id-list>::= id | <id-list>,id

Это правило является рекурсивным, т.е. конструкция <id-list> определяется фактически в терминах себя самой.

Процедура метода рекурсивного спуска, соответствующая нетерминальному символу <read>, прежде всего исследует две последовательные лексемы, сравнивая их с READ и “(“. В случае совпадения эта процедура вызывает другую процедуру, соответствующую нетерминальному символу <id-list>. Если процедура <id-list > завершится успешно, то процедура <read> сравнивает следующую лексему с “)”. Если все эти проверки окажутся успешными, то процедура <read> завершается с признаком успеха и устанавливает указатель текущей лексемы на лексему, следующую за “)”. В противном случае процедура <read> завершится с признаком неудачи. Поэтапный процесс разбора представлен на рисунке 2.

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

<id-list>::= id {, id },

которое определяет нетерминальный символ <id-list> как состоящий из единственной лексемы id или же из произвольного числа следующих друг за другом лексем id, разделенных запятыми.

Выводы

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


<== предыдущая лекция | следующая лекция ==>
Компиляторы. Синтаксический анализ. Метод восходящего разбора | Компиляторы. Семантический анализ
Поделиться с друзьями:


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


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



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




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