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

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

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

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

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

Знак = означает что обе лексемы имеют одинаковый уровень предшествования и должна рассматривается грамматическим процессором в качестве одной конструкции языка. Если для пар отношение предшествования не существует это означает что они не могут находиться рядом ни в каком грамматически правильном предложении. Если подобные комбинации лексем встречаются в процессе грамматического разбора то она должна рассматриваться как синтаксическая ошибка. Существуют алгоритмы автономного построения матриц предшествования на основе формального описания грамматики. Для применимости метода операторного предшествования необходимо чтобы отношения предшествования были заданы однозначно.

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

Другой метод грамматического разбора:

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

Существует алгоритм который по любой допустимой КС грамматике и данной цепочке символов выясняет принадлежит ли цепочка языку порождаемому этой грамматикой. Но время работы такого алгоритма экспоненциально зависит от длины цепочки что с практической точки зрения совершенно неприемлемо. Алгоритмы анализа расходующего на обработку входной цепочки линейное время приемлемы только некоторым подклассам КС грамматик.