Метод восходящего разбора

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

оператор, процедура. Последовательность понятий и их допустимое использование в правилах определяет синтаксически правильные структуры, образующие программы. Одной из наиболее простых и широко используемых форм записи грамматик является нормальная форма Бэкуса-Наура (БНФ). Метаязык,

предложенный Бэкусом и Науром, впервые использ-ся для описания синтаксиса реального языка программирования Алгол 60. Наряду с обозначениями метасимволов, в нем использовались содержательные

обозначения нетерминалов. Это сделало описание языка нагляднее и позволило в дальнейшем широко исп-ть данную нотацию для описания реальных языков программирования. Были использованы следующие обозначения:

- символ "::=" отделяет левую часть правила от правой (символ "::=" можно

читать как “является по определению”, иногда вместо "::=" используется символ

"®");

- нетерминалы обозначаются произвольной символьной строкой,

заключенной в угловые скобки "<" и ">" (нетерминалы являются именами

конструкций, определенными внутри грамматики);

- терминалы - это символы, используемые в описываемом языке;

- каждое правило определяет порождение нескольких альтернативных

цепочек, отделяемых друг от друга символом вертикальной черты "|".

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

При восходящем разборе построение дерева начинается с терминальных

листьев путем подстановки правил, применимых к входной цепочке в

произвольном порядке. На следующем шаге новые узлы полученных

поддеревьев используются как листья во вновь применяемых правилах.

Процесс построения дерева разбора завершается, когда все символы входной

цепочки будут являться листьями дерева, корнем которого окажется

начальный нетерминал. Если в результате полного перебора всех возможных

правил невозможно построить требуемое дерево разбора, то рассматриваемая

входная цепочка не принадлежит данному языку.

При использовании восходящего метода на множестве терминальных и

нетерминальных символов необходимо ввести три отношения, называемые

«отношения предшествования» и обозначаемые как

Отношения не похожи на обычные арифметические отношения

<, >, =. Отношение не является отношением эквивалентности, а отношения

и не обязательно транзитивны, т. е. для отношения предшествования не

выполняются некоторые правила, привычные для отношения арифметического

порядка. Например,

Отношения предшествования удобно занести в матрицу, в которой

строки и столбцы помечены терминалами грамматики.

Отношение означает, что обе лексемы имеют одинаковый уровень

предшествования и должны рассматриваться грамматическим процессором в

качестве одной конструкции языка. Если для пар отношения предшествования

не существует, это означает, что они не могут находиться рядом ни в одном

грамматически правильном предложении. Если подобная комбинация лексем

встретится в процессе грамматического разбора, то она должна

рассматриваться как синтаксическая ошибка.

Существуют алгоритмы автоматического построения матриц

предшествования на основе формального описания грамматики (рис 2.6).

Применение метода операторного предшествования возможно в случае,

когда отношения предшествования заданы однозначно.

Например, не должно быть одновременно отношений

 и Это требование выполняется для используемой грамматики,

однако некоторые из отношений грамматики Паскаля не являются

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

На рис. 2.7 изображен пошаговый процесс грамматического разбора

предложения присваивания в строке 14

Процесс сканирования слева направо продолжается на каждом шаге

грамматического разбора лишь до тех пор, пока не определится очередной

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

фрагмент, ограниченный отношениями  . Как только подобный

фрагмент выделен, он интерпретируется как некоторый очередной

нетерминальный символ в соответствии с каким-либо правилом грамматики.

Этот процесс продолжается до тех пор, пока предложение не будет

распознано целиком. Следует обратить внимание на то, что каждый фрагмент

дерева грамматического разбора строится, начиная с оконечных узлов

вверх, в сторону корня дерева. Отсюда и возник термин «восходящий разбор».

Для метода операторного предшествования имена нетерминальных

символов несущественны. Таким  образом, вся информация о грамматике и

синтаксических правилах языка содержится в матрице операторного

предшествования

 

Нисходящий метод

Другой метод грамматического разбора – нисходящий метод,

называемый рекурсивным спуском. Это один из  методов грамматического

анализа, где правила формальной грамматики раскрываются, начиная со

стартового символа, до получения требуемой последовательности токенов.

Процессор грамматического разбора, основанный на этом методе, состоит

из отдельных процедур для каждого нетерминального символа, определенного

в грамматике. Каждая такая процедура носит имя нетерминала и ищет во

входном потоке подстроку, начинающуюся с текущей лексемы, которая

может быть интерпретирована как нетерминальный символ, связанный с

данной процедурой. В процессе своей работы она может вызывать другие

подобные процедуры или даже рекурсивно саму себя для поиска других

нетерминальных символов. Если эта процедура находит соответствующий

нетерминальный символ, то она заканчивает свою работу, передает в

вызвавшую ее программу признак успешного завершения и устанавливает

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

Если же процедура не может найти подстроку, которая могла бы быть

интерпретирована как требуемый нетерминальный символ, она заканчивается

с признаком ошибки или вызывает процедуру выдачи диагностического

сообщения и процедуру восстановления. Тело каждой такой процедуры

пишется непосредственно по правилам вывода соответствующего

нетерминала:  для правой части каждого правила осуществляется поиск

подцепочки, выводимой их этой правой части. При этом терминалы

распознаются самой процедурой, а нетерминалы соответствуют вызовам

процедур, носящих их имена.

На рис. 2.8 представлен разбор методом рекурсивного спуска оператора

присваивания в строке 14

 

 

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: