Сборник по задачам и примерам Assembler


Синтаксический анализ - часть 2


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

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

Если судить по рисунку, то программа синтаксически правильная. Но каким бразом выясняет этот факт транслятор? Как отмечено выше, существует несколько методов выполнения синтаксического анализа. Все они делятся на два класса в зависимости от того, как они движутся по дереву трансляции во время разбора — сверху вниз или снизу вверх. Алгоритмы «сверху вниз» стремятся построить дерево трансляции начиная вывод от начального символа языка к анализируемой цепочке. И наоборот, алгоритмы «снизу вверх» строят дерево трансляции от анализируемой цепочки терминалов к начальному символу языка. Важно подчеркнуть, что на самом деле никакого дерева в памяти нет и не строится. Как показано выше, его структура заложена в правилах грамматики. Используя алгоритм конкретного метода синтаксического разбора и представленные определенным образом в памяти правила грамматики, мы и производим движение по воображаемому дереву трансляции.

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

Метод рекурсивного спуска

Главное свойство нисходящих методов — их целенаправленность. Метод рекурсивного спуска — наиболее яркий и простой представитель этих методов. Основ ной его недостаток — сильная зависимость от конкретного языка. Программа распознавателя рекурсивного спуска представляет собой, по сути, набор рекурсивных процедур — по одной для каждого из нетерминалов грамматики. Первой получает управление процедура, соответствующая нетерминалу — начальному символу языка. Эта процедура уже знает, что она должна делать. Если первый символ в этом правиле — терминал, то процедура знает об этом и ждет его. Это ожидание заключается в том, что процедура сравнивает код терминала, который должен быть первым, согласно правилу, с кодом первой лексемы из лексической свертки входной строки. Если они совпадают, то процесс разбора идет дальше. Если они не совпадают, то фиксируется ошибка. Если очередным символом правила должен быть нетерминал, то в этом месте вызывается соответствующая ему процедура. Эта процедура тоже построена исходя из правила грамматики для этого нетерминала, поэтому ее действия также уже предопределены. И так будет продолжаться до тех пор, пока разбор не вернется к первому правилу, то есть управление вернется процедуре, соответствующей правилу грамматики для начального символа языка. В нашем случае последним должен быть проанализирован факт того, что последний символ во входной строке — терминал кон_прог.




Начало  Назад  Вперед



Книжный магазин