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

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

Возможны следующие варианты.

1. Ни одно из отношений не определено. Тогда входная цепочка отвергается.

2) Для пары символов определено отношение <• или , тогда выполняется перенос.

При переносе анализатор записывает символ <• в стек, если соответствующее отношение выполняется для данной пары, после чего переносит в стек левый символ входной цепочки. Во входной цепочке осуществляется сдвиг (переход) к следующему символу.

3) Для пары определено отношение •>, тогда выполняется свертка.

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

3.1 Просматривает символы в стеке, пока не обнаружит символ <•. Выделяет подцепочку, состоящую из просмотренных символов ( без знака <•). Снимает со стека найденные символы.

3.2 Ищет правило вывода грамматики, правая часть которого совпадает с подцепочкой, выделенной на предыдущем шаге. Если такое правило найдено, переход к следующему шагу, иначе – к последнему шагу 4.

3.3 Исключает из стека найденные на первом шаге подцепочку и символ <• . В итоге образуется пара, состоящая из символа на верхушке стека и нетерминального символа из левой части продукции, найденной на шаге 3.2.

3.4 Ищет отношение предшествования, выполняющееся для пары, образованной на предыдущем шаге ( это только <• или ) .

Если ни одно отношение предшествования не выполнено, входная цепочка отвергается.

В противном случае в стек записывается символ <• , если для пары выполнено данное отношение, и символ из левой части продукции. На этом свертка заканчивается.

4) Анализируются цепочки, записанные в стеке и на входной ленте. Если в стеке находится цепочка $ <• S, где S – стартовый символ грамматики, а на входной ленте только маркер конца строки $, то входная цепочка принимается ( допускается). В противном случае – цепочка отвергается.

Алгоритм синтаксического анализа приоритета операторов

Алгоритм аналогичен алгоритму синт.анализа простого предшествования.

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

При выполнении свертки с вершины стека выбираются все терминальные символы, связанные отношением , совместно с окружающими их нетерминалами.

Так как нетерминальные символы не играют роли в определении отношений между терминалами, можно заменить все нетерминалы одним символом.

69. Общие алгоритмы синтаксического анализа: нисходящие методы синтаксического анализа, метод рекурсивного спуска, предиктивный синтаксический анализатор, определение LL(k)-грамматики, алгоритм раз­бора для LL(1)-грамматик, алгоритм построения управляющей таблицы для LL(1)-грамматики, сравнительный анализ нисходящих методов синтаксического анализа.

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

Метод, лежащий в основе нисходящего синт.анализа, это метод подбора альтернатив.

Анализ методом рекурсивного спуска

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

Рассмотрим пример, в котором откат необходим.

Пример 15

Рассмотрим грамматику

S → cAd

A → ab|a

и входную строку w = cad.

При нисходящем построении дерева разбора для этой строки вначале создаем дерево, состоящее из одного узла, помеченного как S. Указатель входа указывает на с, первый символ строки w. Теперь воспользуемся первой продукцией для S, чтобы получить дерево, показанное на рис. 27а.

Рис. 27. Шаги нисходящего разбора

Крайний слева лист, с, соответствует первому символу строки w, так что переместим указатель входа к а, второму символу строки w, и рассмотрим следующий лист дерева, помеченный А. Теперь можно воспользоваться для А первой альтернативой и получить дерево, изображенное на рис. 27б. Здесь обнаружено соответствие считанного символа листу дерева, и осуществляется переход к следующему символу — d. Однако d не соответствуют листу дерева b, значит, надо вернуться к А с тем, чтобы выбрать новую альтернативу для работы.

Возвращаясь к А, необходимо вернуть указатель входа в позицию 2, в которой он был когда впервые выбирали продукцию для разложения А. Это означает, что процедура для А должна хранить указатель входа в локальной переменной. При рассмотрении второй альтернативы для А получаем дерево, показанное на рис. 21в. Лист а соответствует второму символу w, а лист d - третьему. Поскольку в этот момент построено дерево разбора для w, прекращаем работу и сообщаем об успешном завершении разбора.

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

При разборе методом рекурсивного спуска:

1. Для каждого нетерминального символа грамматики стоится процедура разбора, которая имеет на входе цепочку символов w.

2. Если в грамматике определено более 1-го правила для нетерминала А, то проц-ра разбора ищет правило, кот. начинается с нужного терминала а в правой части.

3. Если такого правила нет, цепочка не принимается.

4. Если такое правило найдено, то запоминается номер правила и для каждого нетерминала в цепочке за терминалом а рекурсивно вызывается проц-ра разбора этого символа.

Предиктивные анализаторы

Во многих случаях аккуратная разработка грамматики, устранение из нее левой рекурсии и ее левая факторизация позволяют получить грамматику, которая может быть проанализирована синтаксич анализатором, работающим методом рекурсивного спуска и не требующим отката. Для построения предиктивного синтаксич анализатора необходимо знать, какая из альтернатив A → α₁|α₂|…|α_n данного анализируемого нетерми­нала A, порождает строку, начинающуюся с полученного входного символа а. То есть правильная альтернатива должна точно определяться по первому, порождаемому ею символу. Обычно в языках программирования управляющие конструкции отвечают этому правилу. Например, если есть продукции

stmt → if expr then stmt else stmt |while expr do stmt | begin stmt_list end

то ключевые слова if, while и begin однозначно определяют возможную альтернативу для рассматриваемой инструкции stmt.

LL(k)-грамматикой наз-ся грамматика, у которой для любой ее сентенциальной формы, полученной в рез-те некоторого левостороннего вывода для однозначного выбора продукции, имеющей в левой части символ А, достаточно знать k-очередных символов входной строки.