4.2. Восходящий разбор с возвратами

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

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

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

Рассмотрим грамматику с правилами 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, , P, S) без циклов и аннулирующих правил (все правила занумерованы от 1 до p) и входная цепочка  = a₁, a₂, , a_n (n  1).

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

Метод.

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

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

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

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

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

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

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

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

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

(q, i, , ) (q, i, A, j ), при условии, что A правило из P с номером j в линейном упорядочивании, определенном в (1). Номер этого правила ( j ) записывается в L2. Если шаг 1 применим, то повторить его еще раз. В противном случае перейти у шагу 2.

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

(q, i, , ) (q, i+1, a _i , m ), при условии, что i  n+1. Затем перейти к шагу 1. Если i = n+1 перейти к шагу 3.

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

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

(q, n+1, $S, ) (t, n+1, $S, ) .

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

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

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

(q, n+1, , ) (b, n+1, , ), при условии, что   $S. Перейти к шагу 5.

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

(а) (b, i, A, j ) (q, i, B, k ), если A правило из P с номером j, и следующим правилом в упорядочении (1), правая часть которого является суффиксом цепочки , является правило A  с номером k. (Заметим что  =). Перейти к циклу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы).

(б) (b, n+1, A, j ) (b, n+1, , ), если A правило из P с номером j и для цепочки  не остается никакой другой свертки. Перейти к шагу 5. (Если других сверток не существует, надо “взять назад” данную свертку и продолжать возврат, оставляя входной указатель на n+1).

(в) (b, i, A, j ) (q, i+1, a, m ), если i n+1, A правило из P с номером j и для  не осталось никакой другой свертки. Здесь символ а = а _i переносится в магазин L1, а m поступает в L2. Перейти к 1. (Мы вернулись к предыдущей свертке, и так как других сверток нет, попробуем сделать перенос).

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

Пример 4.2.

Рассмотрим работу алгоритма на примере все той же грамматики G для упрошенных арифметических выражений с правилами:

(1)	Е  ET
(2)	Е  Т
(3)	T  TF
(4)	T  F
(5)	F  a

Если наверху магазина появятся E+T, то сначала попытаемся сделать свертку, используя E E+T, а потом E T. Если же появятся TF, то сначала попробуем T TF, а потом T F. Для входа аа восходящий алгоритм пройдет следующие конфигурации:

(q, 1, $, ) ² (q, 2, $a, m) ¹ (q, 2, $F, 5m) ¹ (q, 2, $T, 45m)

¹ (q, 2, $E, 245m) ² (q, 3, $E, m245m) ² (q, 4, $Ea, mm245m)

¹ (q, 4, $EF, 5mm245m) ¹ (q, 4, $ET, 45mm245m)

¹ (q, 4, $EE, 245mm245m) ⁴ (b, 4, $EE, 245mm245m)

^5б (b, 4, $ET, 45mm245m) ^5б (b, 4, $EF, 5mm245m)

^5б (b, 4, $Ea, mm245m) ^5г (b, 3, $E, m245m) ^5г (b, 2, $E, 245m)

² (q, 3, $T, m45m) ² (q, 4, $Ta, mm45m) ¹ (q, 4, $TF, 5mm45m)

¹ (q, 4, $T, 35mm45m) ¹ (q, 4, $E, 235mm45m) ³ (t, 4, $E, 235mm45m)

Таким образом, получается обращенный правый разбор h(235mm45m)=23545. 

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

Пусть для каждого символа из магазинных цепочек, участвующих в конфигурациях рассмотренных алгоритмов разбора с возвратами требуется только одна ячейка памяти и пусть число элементарных операций, необходимых для вычисления одного шага алгоритма ограничено. Тогда для входной цепочки длины n алгоритмам требуется емкость памяти С₁n и время C₂ⁿ , где C₁ и C₂ - некоторые константы. То есть магазинные списки линейно зависят от длины входной цепочки, а число шагов экспоненциально.

Известно несколько способов модернизации алгоритмов с возвратами, ускоряющих их работу.

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

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

(3) Можно ограничить количество допустимых возвратов. В частности, в алгоритме нисходящего анализа можно упорядочить альтернативы так, чтобы первыми испытывались наиболее длинные из них. Как только альтернатива, из которой выводится префикс необходимой части входной цепочки, обнаружена, другие альтернативы исключаются из рассмотрения. Конечно, полученный таким образом префикс может оказаться “ошибочным” и тогда попытка разбора окончится неудачей. Но в практических ситуациях это редко создает серьезные проблемы.

(4) Можно заглядывать вперед на k входных символов, чтобы определить надо ли использовать данную альтернативу или свертку. Далее мы увидим, что с помощью подглядывания вперед можно полностью устранить необходимость возвратов.

Но все эти пути конечно полумеры, и на практике лучше использовать алгоритмы без возвратов (детерминированные).

Другая проблема, связанная с возвратным анализом - слабые возможности в смысле локализации, а тем более нейтрализации ошибок. Если входная цепочка не верна, то компилятор должен объявить, какие входные символы причастны к ошибке. Кроме того, когда ошибка найдена, компилятор должен исправить ее так, чтобы анализ мог продолжаться и обнаружить другие ошибки, если они попадутся. Если входные цепочки построены неправильно, то алгоритм с возвратами просто объявит об ошибке, оставив входной указатель на первом входном символе. Это, конечно же, можно обойти, усложнив алгоритм или добавляя в грамматику альтернативные правила, порождающие наиболее распространенные синтаксические ошибки. Благодаря ним синтаксически неправильные цепочки станут правильными с точки зрения новой грамматики. Появление в выходе номера такого “ошибочного” правила служит сигналом, локализующим ошибку во входной цепочке. Но сколько потребуется ошибочных правил? Методы, изложенные ниже, обладают большими способностями к обнаружению ошибок.

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