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

   2)  Можно попытаться упорядочить свертки так, чтобы наиболее вероятные из них делались первыми.

   3)  Можно добавить информацию, позволяющую определять, приведут ли некоторые свертки к успеху. Например, если первая свертка использует правило А → а₁... а_k, где а₁ — первый входной символ, и мы знаем, что нет такой цепочки yΣ*, что S=>*Ay, то эту свертку можно сразу исключить. Вообще мы хотим быть уверены в том, что если $а—содержимое магазина L1, то α—префикс правовыводимой цепочки. Хотя проверить это, вообще говоря, сложно, некоторые понятия (такие, как предшествование), помогают исключить многие цепочки α, которые могли бы появиться в L1.

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

6. Детерминированный восходящий синтаксический анализ

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

Разбор  с помощью детерминированного алгоритма типа «перенос — свертка»

     Ранее в этой работе было показано, что восходящий разбор можно провести, чередуя свертки и переносы, с помощью двух магазинов. Разбор типа „перенос—свертка" состоит в переносе входных символов в магазин, пока в.его верхней части не окажется основа. В этот момент делается свертка основы. Если не попадается ошибок, то процесс повторяется до тех пор, пока вся входная цепочка не будет прочитана, а в магазине останется один начальный символ грамматики. Ранее был изложен работающий именно таким образом алгоритм с возвратами, который мог вначале неправильно выбирать свертки для некоторых основ, но в конце концов делал правильные выборы. В этой части будет рассмотрен класс грамматик, для которых всегда возможен детерминированный безвозвратный анализ такого типа. Это LR(k)-грамматики, образующие наиболее широкий класс грамматик, анализируемых естественным образом снизу вверх с помощью детерминированного преобразователя с магазинной памятью. Буква L в названии LR(k)-грамматик указывает на то, что входная цепочка читается слева (left) направо, R — на то, что выдается правый (right) разбор, a k — число входных символов, на которые алгоритм „заглядывает вперед”.

     Пусть αх— правовыводимая цепочка какой-то грамматики, причем α — либо пустая цепочка, либо оканчивается нетерминальным символом. Тогда α называется открытой частью цепочки αх, а х—замкнутой частью. Границу между α и x называется рубеж.

     Алгоритм разбора типа „перенос—свертка” можно рассматривать как программу расширенного детерминированного МП-преобразователя, который проводит разбор снизу вверх. Для данной входной цепочки ω МП-преобразователь моделирует в обратном порядке ее правый вывод. Допустим, что S = α_{0 r}α₁ =>_r ... =>_r α_m = ω — правый вывод цепочки ω. Каждая правовыводимая цепочка α_i распределяется в памяти ДМП-преобразователя так, что ее открытая часть хранится в магазине, а замкнутая — на входной ленте справа от головки. Например, если α_i = αAx, то αА будет в магазине (причем А— верхний символ), а х—это еще не прочитанная часть первоначальной входной цепочки.

     Допустим, что α_i-l = γBz и на шаге α_i-l =>_r α_i применено правило B → βy, причем уβ — αA и yz=x. Имея в магазине цепочку αА, МП-преобразователь перенесет несколько (возможно, ни одного) символов с левого конца цепочки х в магазин, пока не обнаружит правый конец основы цепочки α_i. К этому моменту в магазин будет перенесена цепочка у.

     Затем МП-преобразователь должен локализовать левый конец основы. Как только он это сделает, он заменит основу (здесь ею будет цепочка βу), занимающую верхнюю часть магазина, подходящим нетерминалом (здесь нетерминалом В) и выдаст номер правила B → βy. Теперь в магазине окажется γB, a z образует непрочитанную часть входа. Эти цепочки являются соответственно открытой и замкнутой частями правовыводимой цепочки а_i-1.

     Заметим, что основа цепочки αАх никогда не может лежать целиком внутри α, хотя она может быть полностью внутри х, т. е. а_i-1 может иметь вид αAx₁Bx₂ и к ней можно применить правило вида B → y, где х₁ух₂=х, чтобы получить а_i. Так как цепочка х₁ может быть очень длинной, то может потребоваться много операций переноса, прежде чем α_i будет сведена к α_i-l.

     Итак, в ходе разбора алгоритм типа „перенос—свертка" должен принимать решения трех типов. Во-первых, перед каждым шагом надо определить, перенести ли в магазин входной символ или делать свертку. Это решение фактически состоит в выяснении того, где в правовыводимой цепочке находится правый конец основы. Второе и третье решения надо принять после того, как локализован правый конец основы. Как только становится известным, что в верхней части магазина образовалась основа, нужно локализовать в магазине ее левый конец. Затем, когда основа уже выделена, надо найти подходящий нетерминал, которым следует ее заменить.

     Грамматика, в которой никакие два различные правила не имеют одинаковых правых частей, называется детерминироеанно (или однозначно) обратимой или просто обратимой. Можно показать, что каждый контекстно-свободный язык порождается по крайней мере одной обратимой КС-грамматикой.

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

     В качестве примера рассмотрим грамматику G с правилами  1) S→SaSb

     2) S→e

и правый вывод   S => SaSb => SaSaSbb => SaSabb => Saabb => aabb

     Разберем  цепочку aabb, используя магазин и  применяя операции переноса и cвертки. Символ $ будет служить концевым маркером входной цепочки и дна магазина.

     Работу  алгоритма разбора типа „перенос—свертка" опишем в терминах конфигураций, представляющих собой тройки вида (αХ, х, π), где

     1) αХ — содержимое магазина, причем Х — верхний символ;

     2) x —непрочитанная часть входной цепочки;

     3) π —выход к данному моменту.

     Эти конфигурации имеют тот же вид, что  и конфигурации расширенного МП-преобразователя, только в них опущено состояние и магазин предшествует входу. Вначале алгоритм находится в конфигурации ($, aabb$, e). Ему надо догадаться, что основой правовыводимой цепочки aabb является входящая в нее на левом конце пустая цепочка е

и что эту  основу надо свернуть к S. Алгоритм должен перейти в конфигурацию ($S, aabb$, 2). После этого он перенесет в магазин входной символ, перейдя в конфигурацию ($Sа, abb$, 2). Затем догадается, что наверху магазина находится основа е и сделает свертку, перейдя в конфигурацию ($SaS, abb$, 22). Продолжая в том же духе, алгоритм сделает такую последовательность тактов:

                      ($, aabb$, e) |— ($S, aabb$, 2)

                               |— ($Sa, abb$, 2)

                               |— ($SaS, abb$, 22)

                               |— ($SaSa, bb$, 22)

                           |— ($SaSaS, bb$, 222)

                               |— ($SaSaSb, b$, 222)

                               |— ($SaS, *$. 2221)

                   |— ($SaSb, $, 2221)

       |— ($S, $, 22211)

                               |— допуск

LR(k)-грамматики

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

     Грамматика будет LR(k)-грамматикой, если для произвольного правого вывода

S = α₀ => _rα₁ => _rα₁ => _r ... =>_r α_m = z в каждой правовыводимой цепочке α_i читая ее слева

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

     Допустим, что a_i-1 = αAω и α_i = αβω, где β—основа цепочки α. Допустим далее, что αβ = Х₁ Х₂. . .Х_r. Если КС-грамматика является LR(k)-грамматикой, можно быть уверенным в следующем:

     1) Зная Х₁ Х₂. . .Х_j и первые k символов цепочки X_j+1…X_rω, можно не сомневаться, что правый конец основы не будет достигнут до тех пор, пока не станет j = r¹).

     2) Зная αβ и не более k символов цепочки ω, всегда можно определить, что β — основа и ее надо свернуть к А.

     3) Если a_i-1 = S, то можно уверенно сигнализировать о том что входную цепочку следует допустить.

     Заметим, что, проходя по последовательности α_m, α_m-1,. . . , α₀, мы вначале видим только цепочку FIRST_k (α_m) = FIRST_k (z). На каждом шаге цепочка символов, на которые мы, “заглядываем вперед" (аванцепочка), состоит из k или менее терминальных символов.

     Теперь перейдем к определению LR (k)-грамматики, но прежде введем простое понятие пополненной грамматики.

     Определение. Пусть G = (N, Σ, P, S) — КС-грамматика. Пополненной грамматикой, полученной из G, называется грамматика G' = (N{S'}, Σ, P {S'→S}, S'). Другими словами, это просто G с новым начальным правилом S' → S, где S' — новый

начальный символ, не принадлежащий N. Будем считать, что S' → S — нулевое правило грамматики G', а остальные правила занумерованы числами 1,2, ..., р. Это начальное правило добавляется для того, чтобы свертку, в которой используется нулевое правило, можно было интерпретировать как сигнал о том, что цепочка допускается.

     Дадим точное определение LR (k)-грамматики.

     Определение. Пусть G = (N,Σ, Р, S) — КС-грамматика и G' = (N', Σ, Р', S') — полученная из нее пополненная грамматика. Будем называть G LR (k)-грамматикой для k≥0, если из условий  1) S' => *_G^’rαAω => _G^’rαβω,

     2) S' => *_G^’rγBx => _G^’rαβy,

     3) FIRST_k(ω) = FIRST_k(y)

следует, что  αAy = γВх (т. е. α = γ, А = В и х = у).

     Грамматика G называется LR-грамматикой, если она LR(k)- грамматика для некоторого k≥0.

     Это определение говорит о том, что если αβω и αβy—правовыводимые цепочки пополненной грамматики, у которых FIRST_k(ω) = FIRST_k(y), и А→B — последнее правило, использованное в правом выводе цепочки αβω, то правило А→B должно использоваться также в правом разборе при свертке αβy к αАy. Так как А дает β независимо от ω, то LR (k)-условие говорит о том, что в FIRST_k(ω) содержится информация, достаточная для определения того, что αβ за один шаг выводится из αA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, работая с LR (k)- грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор. Если начальный символ S не встречается в правых частях правил, то в определении LR (k)- грамматики вместо S' можно взять S, а именно G = (N,Σ, P, S)

     будет LR (k)-грамматикой, если из трех условий  1) S => *_rαAω => _rαβω,

     2) S => *_rγBx => _rαβy,

     3) FIRST_k(ω) = FIRST_k(y)

следует, что  αАy = γBx.

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

     В качестве примера рассмотрим грамматику G с правилами   S → Sa | а

     Если  игнорировать ограничение, касающееся появления начального символа в правых частях правил, и пользоваться вторым определением, то G придется считать LR (0)-грамматикой.

     Однако, согласно правильному определению, G не LR (0)- грамматика, так как из трех условий   1)  S' => ⁰_G^’r S' => _G^’rS,

     2) S' => *_G^’rS => _G^’rSa,

    3) FIRST₀(e) = FIRST₀(a)=e

не следует, что S'а=S. Применяя определение к этой ситуации, имеем а=е, β=S, ω = e, γ=e, A=S', B = S, х = е и y=0. Проблема здесь заключается в том, что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видя символа, стоящего после S (т. е. наблюдая “нулевое” количество символов). В соответствии с логикой G не должна быть LR (k)-грамматикой и она не будет ею, если пользоваться первым определением.