Восходящий синтаксический анализ

     3) S→c, с

     Тогда L_r^G = 3(l+2)*, где G — входная грамматика. Если положить h(1) = a и h(2) = b, то требуемым переводом τ(p) будет {(3α, h(α)^Rch(α)) | α {1, 2}*}. Если бы ДМП-преобразователь Р, о котором говорится в теореме, существовал (с правым концевым маркером или без него), то можно было бы построить ДМП-преобразователь, определяющий перевод {(ωс, ω^Rcω) | ω {а, b}*}, а это противоречит предыдущей лемме.

     Итак, мы заключаем, что интересны как  левый, так и правый анализ.

5. Восходящий разбор в синтаксическом анализе с возвратами

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

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

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

     Рассмотрим  грамматику с правилами S→АВ, А→аb и В→aba. Пусть аbаbа—входная цепочка. Сначала перенесем в магазин первый символ а. Так как свертка пока невозможна, перенесем в магазин символ b. Затем цепочку ab, расположенную наверху магазина, заменим на А. Получили частичное дерево, показанное па рис. 2, a.

                 

Рис. 2. Частичные  деревья восходящего разбора.

     Так как А нельзя больше свернуть, перенесем в магазин а. Свертка опять невозможна, поэтому перенесем b. Тогда можно свернуть ab к А. Теперь получаем частичное дерево на рис. 2, б. Переносим в магазин символ а и обнаруживаем, что свертка невозможна. Возвращаемся к последней позиции, в которой была сделана свертка, а именно когда в магазине была цепочка Ааb (здесь b—верхний символ) и мы заменили аb на A, т. е. частичное дерево было таким, как на рис. 2, а. Так как другая свертка здесь невозможна, сделаем перенос вместо свертки. В магазине окажется Aaba. Тогда можно свернуть aba к В, получив при этом рис. 2, в. Далее заменим АВ на S и получим завершенное дерево, показанное на рис. 2, г.

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

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

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

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

     Вход. КС-грамматика G = (N, Σ, P, S) без циклов и е-правил (все ее правила занумерованы от 1 до р) и входная цепочка ω = a₁a₂…а_n (n≥1).

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

     Метод.

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

2) Алгоритм будет изложен в терминах 4-компонентных конфигураций. В конфигурации (s, i, α, β)

(а) s представляет  состояние алгоритма, 

(б) i представляет текущую позицию входного указателя

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

(в) α — содержимое магазина L1 (верх которого расположен справа)

(г) β — содержимое магазина L2 (верх которого расположен слева).

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

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

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

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

(q, i, αβ, γ) |— (q, i, αA, jγ)

при условии, что  А→β — правило из Р с номером j и β — первая правая часть в линейном упорядочении, определенном в 1), которая является суффиксом цепочки αβ. Номер этого правила записывается в L2. Если шаг 1 применим, повторить его. В противном случае перейти к шагу 2.

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

(q, i, α, γ) |— (q, i+1, αa_i, sγ)

при условии, что  i n+1. Перейти к шагу 1.

     Если i = n+1, перейти к шагу 3.

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

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

(q, n+1, $S, γ) |— (t, n+1, $S, γ)

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

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

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

(q, n+1, α, γ) |— (b, n+1, α, γ)

     при условии, что α$S. Перейти к шагу 5.

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

     (а)     (b, i, αА, jγ) |— (q, i, α'B, kγ)

     если  А→β — правило из Р с номером j, а следующим правилом в упорядочении 1), правая часть которого является суффиксом цепочки αβ, является правило B→β’ с номером k. (Заметим, что αβ = α’β’) Перейти к шагу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы.)

     (б)      (b, n+1, αA, jγ) |— (b, n+1, αβ, γ)

     если  А→β — правило из Р с номером j и для цепочки αβ не остается никакой другой свертки. Перейти к шагу 5. (Если других сверток не существует, надо “взять назад” данную свертку и продолжать возврат, оставляя входной указатель на позиции n+1.)

     (в)     (b, i, αA, jγ) |— (q, i + l, αβα, sγ)

     если  in+1, А→β — правило из Р с номером j и для αβ не остается никакой другой свертки. Здесь символ а = а_i переносится в магазин L1, а символ s поступает в L2. Перейти к шагу 1.

     (Мы  вернулись к предыдущей свертке  и, так как других сверток нет, попробуем сделать перенос.)

     (г)    (b, i, αa, sγ) |— (b, i - l, α, γ)

     если  наверху магазина L2 находится символ переноса s. (Здесь в позиции i исчерпаны все альтернативы и надо “взять назад” операцию переноса. Входной указатель сдвигается влево, терминальный символ устраняется из L1, а символ переноса s — из L2). Если этот шаг невыполним, объявить об ошибке.

     В качестве примера применим описанный алгоритм восходящего разбора к грамматике G с правилами   1)   E→E+T

                              2)   E→T

                              3)   T→ T*F

                              4)   T→ F

                              5)   F→ a

     Если  наверху магазина L1 появится Е+Т, то сначала попытаемся сделать свертку, используя E→E+T, а потом — используя E→T. Если же появится Т*F, то сначала попробуем T→T*F, а потом T→F. Для входа а * а восходящий алгоритм пройдет через конфигурации         (q, 1, $, e) |— (q, 2, $a,       s)

                              |— (q, 2, $F,       5s)

                              |— (q, 2, $T,       45s)

                              |— (q, 2, $E,      245s)

                              |— (q, 3, $E*,     s245s)

                              |— (q, 4, $E*a,   ss245s)

                              |— (q, 4, $E*F,   5ss245s)

                  |— (q, 4, $E*T,   45ss245s)

       |— (q, 4, $E*E,   245ss245s)

                              |— (q, 4, $E*E,   245ss245s)

                              |— (q, 4, $E*T,   45ss245s)

                              |— (q, 4, $E*F,   5ss245s)

                              |— (q, 4, $E*a,  ss245s)

                              |— (q, 3, $E*,     s245s)

       |— (q, 2, $E,       s245s)

                              |— (q, 3, $T*,     s45s)

                              |— (q, 4, $T*a,   ss45s)

       |— (q, 4, $T*F, 5ss45s)

       |— (q, 4, $T,      35ss45s)

       |— (q, 4, $E,       235ss45s)

       |— (q, 4, $E,       235ss45s)

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика. Будем называть π частичным правым разбором, совместимым с ω, если существуют такие α (N Σ)* и префикс х цепочки ω, что α => _πRx.

     Лемма. Пусть G — КС-грамматика без циклов и без е-правил. Тогда найдется такая константа с, что число частичных правых разборов, совместимых с входной цепочкой длины n, не превосходит сⁿ.

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

     Доказательство. В соответствии с предыдущей леммой число частичных правых разборов, совместимых с входной цепочкой, конечно. Пока алгоритм не найдет разбор входной цепочки, он перебирает в естественном порядке все частичные правые разборы. А именно, каждый частичный правый разбор кодируется последовательностью индексов правил и символов переноса (s), и алгоритм рассматривает все такие кодирующие последовательности в лексикографическом порядке. Этот лексикографический порядок определяется порядком символов, в котором s находится на последнем месте, а упорядочение индексов правил задается шагом 1 алгоритма. Заметим, что не каждая последовательность таких символов будет кодом совместимого частичного правого разбора.

     Длины магазинных списков в конфигурациях алгоритма линейно зависят от длины входной цепочки.

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

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

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