ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

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

Напомним, что синтаксический анализатор для автоматного языка можно тривиально построить, основываясь на автоматной грамматике или конечном автомате, описывающем этот язык. Теория и практика построения такого анализатора были детально рассмотрены в учебном пособии “Теория формальных языков. Грамматики и автоматы” [16]. Но, как известно, класс автоматных грамматик очень узок. Любой язык, допускающий вложенность конструкций не является автоматным языком, и даже язык арифметических выражений с вложенными скобками нельзя описать с помощью А-грамматики. Эти грамматики и анализаторы автоматных языков используются только на первой фазе трансляции - лексическом анализе.

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

Итак, основная задача синтаксического анализатора сводится к тому, чтобы по заданной КС-грамматике и произвольной цепочке, он мог бы ответить на вопрос о принадлежности цепочки языку. Рассмотрим, например КС-грамматику G₁ со следующими перенумерованными продукциями:

(1) S ® aBcD

(2) B ® BaD

(3) B ® d

(4) D ® Dd

(5) D ® d

На рисунке 4.1 показано дерево вывода цепочки adadcdd по заданной грамматике. Ее левый вывод имеет вид: S Þ aBcD Þ aBaDcD Þ adaDcD Þ adadcD Þ adadcDd Þ adadacdd, а левый разбор[16] (последовательность правил, применяемых при левом выводе) - 123545. Правый вывод данной цепочки: S Þ aBcD Þ aBcDd Þ aBcdd Þ aBaDcdd Þ aBadcdd Þ adadacdd и обращенный правый разбор - 352541.

Очевидно, что цепочка adadacdd принадлежит языку L(G₁), в чем убеждает дерево ее вывода. Таким образом, для того, чтобы ответить на вопрос принадлежит ли цепочка заданному языку, необходимо построить вывод данной цепочки, а еще лучше дерево вывода.

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

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

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

N ® DôND

D ® 0ô1ô2ô3ô4ô5ô6ô7ô8ô9

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

Алгоритмы восходящего анализа часто называют алгоритмами отсечения основ или алгоритмами типа “перенос-свертка” и здесь при анализе и построении дерева разбора применяют процесс обратный порождению - свертку или редукцию. Заданная цепочка принадлежит языку, если ее удается свернуть к начальному символу грамматики. На рис. 4.3 показаны этапы этого алгоритма на примере той же цепочки 35 и заданной грамматики целых чисел.

На рис. 4.2 и 4.3 выводы различны, но деревья вывода совпадают. Заметим, что в последнем построении на каждом шаге редуцируется основа (самая левая простая фраза) текущей сентенциальной формы и поэтому правее от основы сентенциальная форма всегда содержит только терминальные символы.

В рассмотренных примерах мы не коснулись главных проблем синтаксического анализа. При нисходящем анализе на каждом шаге мы заменяли самый левый нетерминал V на правую часть соответствующего правила. Пусть для нетерминала V существует n правил: V® x₁ôx₂ô¼ôx _n. Как узнать, какой цепочкой x _i надо заменить V? При восходящем анализе на каждом шаге редуцируется основа. Как найти основу и тот нетерминал, к которому она должна приводится?

Одно из решений - выбор некоторого варианта наугад, в предположении, что он верен. Если в дальнейшем обнаружится ошибка, то возврат назад и попытка применить другой вариант. Такой подход - не что иное, как попытка моделирования недетерминированного МП-преобразователя, который в общих чертах мы уже обсуждали в первой части пособия [10]. Такие алгоритмы носят название недетерминированных или алгоритмов синтаксического анализа с возвратами. Попытаемся формализовать эти алгоритмы.

Поиск по сайту: