ВОСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ

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

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

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

Рассмотрим грамматику с правилами S ® AB, A ® ab и B® aba. Пусть ababa - входная цепочка. Сначала перенесем в магазин a. Так как свертка пока невозможна, перенесем b. Затем цепочку ab, расположенную наверху магазина, заменим нетерминалом А. Получим частичное дерево, показанное на рис. 4.4 а.

Так как А не допускает другой свертки, переносим в магазин а, а потом b. Затем можно опять свернуть ab к A (см. рис. 4.4 б).

Перенеся в магазин а, мы обнаруживаем, что свертка невозможна. Возвращаемся к последней позиции, в которой была сделана свертка, а именно, когда в магазине была цепочка Aab, то есть дерево было таким, как на рисунке 4.4 а. Так как другая свертка здесь невозможна, то делаем перенос вместо свертки. В магазине окажется Aaba. Тогда aba можно свернуть к B. Получим дерево с рис. 4.4 в. Далее заменим AB на S и получим завершенное дерево с рис. 4.4 г.

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

Одна из ловушек имеет место для грамматик с циклами, т.е. грамматик порождающих выводы A Þ⁺A для некоторого нетерминала A. Число частичных деревьев при этом может быть бесконечным, и мы исключим такие грамматики из рассмотрения. Трудности создаются и аннулирующими правилами, так как они приводят к произвольному числу “сверток” пустой цепочки к нетерминал.

Алгоритм 4.2. Алгоритм восходящего разбора с возвратами.

Вход. КС-грамматика G = (N, S, P, S) без циклов и аннулирующих правил (все правила занумерованы от 1 до p) и входная цепочка w = a₁, a₂, ¼, a_n (n ³ 1).

Выход. Один обращенный правый разбор цепочки w, если он существует, или слово “ошибка” в противном случае.

Метод.

(1) Произвольным образом упорядочить правила грамматики.

(2) Анализатор будет изложен в терминах 4-х компонентных конфигураций, подобных конфигурациям из алгоритма 4.1. В конфигурации (q, i, a, b):

(а) q - состояние алгоритма (их всего три: q - нормальной работы, b - возврата, t - завершения).

(б) i - текущая позиция входного указателя (предполагается, что (n+1) -м символом служит правый концевой маркер $).

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

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

(3) Начальная конфигурация алгоритма - (q, 1, $, e).

(4) Сам алгоритм начинает работу с попытки применить шаг 1.

Шаг 1. Попытки свертки

(q, i, ab, g)÷¾ (q, i, aA, j g), при условии, что A®b правило из P с номером j в линейном упорядочивании, определенном в (1). Номер этого правила (j) записывается в L2. Если шаг 1 применим, то повторить его еще раз. В противном случае перейти у шагу 2.

Шаг 2. Перенос

(q, i, a, g)÷¾ (q, i+1, aa _i , m g), при условии, что i ¹ n+1. Затем перейти к шагу 1. Если i = n+1 перейти к шагу 3.

При выполнении шага 2, i-ый входной символ переносится в верхнюю часть магазина L1, позиция указателя увеличивается на единицу и в магазин L2 записывается символ m, чтобы указать, что сделан перенос.

Шаг 3. Допускание

(q, n+1, $S, g)÷¾ (t, n+1, $S, g).

Выдать обращенный разбор цепочки w - h(g), где h - гомоморфизм, определенный равенствами h(m)= e и h(j)= j для всех номеров правил. После этого остановиться.

Если шаг 3 неприменим, то перейти к шагу 4.

Шаг 4. Переход в состояние возврата

(q, n+1, a, g)÷¾ (b, n+1, a, g), при условии, что a ¹ $S. Перейти к шагу 5.

Шаг 5. Возврат

(а) (b, i, aA, j g)÷¾ (q, i, a¢B, k g), если A®b правило из P с номером j, и следующим правилом в упорядочении (1), правая часть которого является суффиксом цепочки ab, является правило A ®b¢ с номером k. (Заметим что ab = a¢b¢). Перейти к циклу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы).

(б) (b, n+1, aA, j g)÷¾ (b, n+1, ab, g), если A®b правило из P с номером j и для цепочки ab не остается никакой другой свертки. Перейти к шагу 5. (Если других сверток не существует, надо “взять назад” данную свертку и продолжать возврат, оставляя входной указатель на n+1).

(в) (b, i, aA, j g)÷¾ (q, i+1, aba, m g), если i ¹n+1, A®b правило из P с номером j и для ab не осталось никакой другой свертки. Здесь символ а = а _i переносится в магазин L1, а m поступает в L2. Перейти к 1. (Мы вернулись к предыдущей свертке, и так как других сверток нет, попробуем сделать перенос).

(г) (b, i, aa, m g)÷¾ (q, i -1, a, g), если вверху магазина L2 находится символ переноса m. (Здесь в позиции i исчерпаны все альтернативы и надо “взять назад” операцию переноса. Вход указателя сдвигается влево, терминал устраняется из L1, а символ переноса удаляется из L2). Если этот шаг невозможен, объявить об ошибке.

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