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

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика. Обозначим через М_r^G расширенный недетерминированный МП-преобразователь ({q}, Σ, N Σ {$}, {1, . . . , p}, δ, q, $, Ø), причем верх магазина расположен справа и δ определяется так:

1. δ(q, e, α) содержит (q, A, i), если А→α — правило из Р с номером I,

     2) δ(q, a, e) = {(q, а, е)} для всех а Σ,

     3)  δ(q, e, $S) = {(q, e, е)}

     Этот МП-преобразователь содержит элементы алгоритма разбора, называемого алгоритмом типа перенос—свертка. На такте, соответствующем правилу 2), М_r переносит входной символ в магазин. Всякий раз, когда наверху магазина появляется основа М_r может свернуть ее по правилу 1) и выдать номер правила, использованного при свертке. Затем М_r может продолжать переносить в магазин входные символы, пока в его верхней части не появится новая основа. Эта основа свертывается, а на выход выдается номер соответствующего правила. М_r действует так до тех пор, пока в магазине не останется только начальный символ с маркером дна магазина. По правилу 3) М_r может перейти тогда в конфигурацию с пустым магазином.

     Теорема. Пусть G = (N, Σ, Р, S) — КС-грамматика. Тогда τ_e (M_r) = {( ω, π^R)|S => _πω}.

     Приведем  пример:

     Правым анализатором для грамматики G₀ будет

     М_r^G0  = ({q}, Σ, N Σ, {1, 2, . . . , 6}, δ, q, $, Ø}, где

     δ (q, e, E+T) = {(q, E, 1)}

     δ (q, e, T) = {( q, E, 2)}

     δ (q, e, T*F) = {(q, T, 3)}

     δ (q, e, F) = {(q, T, 4)}

     δ (q, e, a) = {(q, F, 5)}

     δ (q, e, (E)) = {(q, F, 6)}

     δ (q, b, e) = {(q, b, e)} для всех b Σ

     δ (q, e, $E) = {(q, e, e)}

     Для входной цепочки а + а*а левый анализатор М_r^G0 может среди других сделать такую последовательность тактов:

     (q, a+a*a, $, e) |— (q, +a*a, $a, e)

                  |— (q, +a*a, $F, 6)

                  |— (q, +a*a, $T, 64)

                  |— (q, +a*a, $E, 642)

                  |— (q, a*a, $E+, 642)

                  |— (q, *a, $E+a, 642)

                  |— (q, *a, $E+F, 6426)

                |— (q, *a, $E +T, 64264)

       |— (q, a, $E +T*, 64264)

                  |— (q, e, $E +T*a, 64264)

                  |— (q, e, $E+T*F, 642646)

                  |— (q, e, $E+T, 6426463)

                  |— (q, e, $E, 64264631)

                  |— (q, e, e, 64264631)

     Таким образом, для входной цепочки  a+a*a анализатор М_r^G0 выдает правый разбор 64264631.

     4. Сравнение нисходящего  разбора с восходящим

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

     Определение. Назовем КС-грамматику G левоанализируемой, если существует такой ДМП-преобразователь Р, что τ (P) = {(x$, π)|(х, π) T_l^G} и правоанализируемой, если существует такой ДМП-преобразователь Р, что τ (P) = {(x$, π)|(х, π) T_r^G}

     В обоих случаях ДМП-преобразователю  разрешается использовать концевой маркер для указания правого конца  входной цепочки.

     Заметим, что все КС-грамматики лево- и правоанализируемы в неформальном смысле, но в данном формальном определении отражен именно детерминизм.

     Мы  обнаружим, что классы лево- и правоанализируемых грамматик несравнимы, т. е. ни один из них не является подмножеством другого. Это удивительно с той точки зрения что LL-грамматики, которые можно детерминированно левоанализировать естественным образом, образуют подмножество LR-грамматик, которые можно детерминированно правоанализировать естественным образом. Приведем примеры грамматик, лево- (право-) анализируемых, но не право- (лево-) анализируемых.

     Пусть грамматика G₁ определена правилами

     1) S→ВАb  2) S→CАc

     3) А→ВА  4)  А→а

     5) В→а   6)  С→а

     L(G₁) = aa⁺b+aa⁺c. Можно показать, что G₁ не является ни LL-, ни LR-грамматикой, потому что до тех пор, пока мы не увидим последний символ цепочки, неизвестно, каким нетерминалом В или С порождается первый символ а.

     Однако  можно “неестественно” получить левый разбор произвольной входной цепочки с помощью ДМП-преобразователя. Рассмотрим в качестве входной цепочки aⁿ⁺²b (n≥0). Тогда ДМП-преобразователь может сделать левый разбор 15(35)ⁿ4, помещая в магазин все символы а до тех пор, пока он не увидит b. При этом на выходе ничего не порождается. Когда b появится, ДМП-преобразователь может выдать 15(35)ⁿ4, подсчитав n с помощью занесенных в магазин символов а. Подобным же образом для входа aⁿ⁺²c можно получить 26(35)ⁿ4 на выходе. В любом случае вся хитрость в том, чтобы отложить порождение выхода до того, как появится b или с.

     Теперь  докажем, что не существует ДМП-преобразователя, способного порождать правильные правые разборы для всех входных цепочек. Допустим, что ДМП-преобразователь М порождает правые разборы 55ⁿ43ⁿ1 для цепочки aⁿ⁺²b и 65ⁿ43ⁿ2 для цепочки aⁿ⁺²c . Докажем неформально, что такой преобразователь невозможен. Это доказательство существенно опирается на результаты работы Гинзбурга и Грейбах [1966], где показано, что {aⁿbⁿ| n≥1} {aⁿb²ⁿ| n≥1} не является детерминированным КС-языком. Можно доказать следующие утверждения:

     1) Пусть aⁱ поступает на вход преобразователя М. Тогда либо его выход пуст, либо он выдает 5 или 6, и преобразователь М можно “обмануть”, подав на вход с или b соответственно и сделав тем самым его выход ошибочным.

     2) По мере того как символы а поступают на вход М, они должны так или иначе запасаться в магазине. Точнее, можно показать, что найдутся такие числа j и k, магазинные цепочки α и β и состояние q, что (q₀, а^k+jp, Z_o, e)|—* (q, e, β^pα, е) для всех р≥0, где q₀ и Z_o — начальные состояние и магазинный символ преобразователя М.

     3) Если после k+jр символов а на входе М появляется один символ b, то М не может выдать 4 до тех пор, пока не сотрет магазинную ленту вплоть до α. В противном случае мы могли бы “обмануть” М, предварительно поместив на вход дополнительные j символов а, в то время как М будет выдавать то же количество чисел 5, которое он выдавал раньше, так что оба выхода правильными быть не могут.

     4) После того как магазин сократится до цепочки α, преобразователь М уже не может “помнить”, сколько символов было на входе, потому что теперь конфигурации преобразователя М для разных значений р (где k+jp — число символов a) отличаются только их состояниями. Таким образом, М не знает, сколько теперь надо выдать чисел 3.

     Приведем  пример. Пусть G₂ определяется правилами

     1) S→Аb  2) S→Аc

     3) А→B  4)  А→а

     5) В→а  

     L(G₂) = a⁺b+a⁺c. Легко показать, что G₂— правоанализируемая грамматика. С помощью рассуждений, аналогичных проведенным в предыдущем упражнении, можно показать, что G₂ нелевоанализируема.

     Теорема. Классы лево- и правоанализируемых грамматик несравнимы.

     Доказательство. Два предыдущих примера.

     Несмотря  на эту теорему, восходящий синтаксический анализ, как правило, привлекательнее  нисходящего, так как для данного  языка программирования часто легче  написать правоанализируемую грамматику, чем левоанализируемую. К тому же, как отмечалось, LL-грамматики содержатся в классе LR-грамматик. Также естественное моделирование недетерминированного МП-преобразователя в случае, когда он является правым анализатором, работает для более общего класса грамматик, чем в случае левого анализатора.

     Однако с точки зрения процесса трансляции левый анализ предпочтительнее. Мы покажем, что каждый простой СУ-перевод можно выполнить с помощью

     1) МП-преобразователя, дающего левые разборы входных цепочек, за которым следует

     2) ДМП-преобразование, отображающее левые разборы в выходные цепочки данного СУ-перевода.

     Интересно, что существуют простые СУ-переводы, для которых в приведенном  выше утверждении нельзя заменить «левый разбор» на «правый разбор».

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

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика. Определим язык L_l^G левых и язык L_r^G правых разборов грамматики G:

     L_l^G = {π|S_π => ω для переходной ω L(G)}

     L_r^G = {π^R|S => _πω для переходной ω L(G)}

     Обозначения _π=> и =>_π можно распространить на СУ-схемы, договорившись, что (α, β) _π=>(γ, δ) тогда и только тогда, когда (α, β)=>*(γ, δ), причем на каждом шаге этого вывода заменяется самый левый нетерминал первой компоненты выводимой пары и примененные при этом правила, из которых удалены элементы перевода, образуют последовательность π. Аналогично для СУ-схемы определяется =>_π.

     Определение. СУ-схема называется семантически однозначной, если в ней нет двух различных правил вида А →α, β и А →α, γ.

     В семантически однозначной СУ-схеме для каждого правила входной грамматики есть точно один элемент перевода.

     Теорема. Пусть T = (N, Σ, Δ, R, S)—семантически однозначная простая СУ-схема. Тогда существует такой ДМП-преобразователь P, что τ_е(P) ={(π, у)|(S, S) _π=> (x,у) для некоторой цепочки хΣ^*}.

     Доказательство. Пусть P = ({q), {1, . . . , p}, NΔ, Δ, δ, q, S,Ø), где 1, . . . , p - номера правил входной грамматики, a δ определяется так:

     1) Пусть А→а — правило входной грамматики с номером i и А→α, β—единственное соответствующее правило схемы. Тогда δ (q, i, A) = (q, β, е).

     2) δ (q, e, b) = (q, e, b) для всех bΔ.

     МП-преобразователь  P детерминированный, потому что правило 1) применяется только тогда, когда наверху магазина находится нетерминал, а правило 2) применяется только тогда, когда наверху выходной символ. Корректность преобразователя Р следует из утверждения, которое легко доказывается с помощью метода индукции:

(q, π, А, е) |— * (q, е, е, у) тогда и только тогда, когда существует такая цепочка xΣ*, что (A, A)_π=> (x, у).

     Чтобы описать СУ-перевод, не выполнимый никаким ДМП-преобразователем, отображающим L_r^G, где G—входная грамматика, в соответствующие выходы этого перевода, нам понадобится следующая лемма.

     Лемма.  Не существует такого ДМП-преобразователя Р, что τ(R) = {(ωс, ω^Rcω) | ω {а, b}*}.

     Доказательство. Здесь символ с играет роль правого концевого маркера. Допустим, что Р для входа ω выдает некоторую непустую цепочку, скажем dx, где d {а, b}. Пусть означает символ, противоположный d. Посмотрим, как работает Р с цепочкой ωc в качестве входа. Он должен выдать некоторую цепочку, но эта цепочка должна начинаться символом d. Следовательно, Р не отображает ωc в ω^Rcω, как требуется. Таким образом, Р не может ничего выдать на выходе, пока не будет достигнут правый концевой маркер с. В этот момент Р будет находиться в состоянии q_ω и хранить в магазине цепочку α_ω.

     Неформально α_ω должна быть по существу цепочкой ω, и тогда, стирая α_ω, P может выдать ω^R. Но стоит ему стереть α_ω, как он уже не может “вспомнить” всю цепочку ω, чтобы напечатать ее на выходе.

     Рассмотрим  входные цепочки вида ω — aⁱ. Существуют такие числа j и k, состояние q и цепочки α и β, что, прочитав на входе a^j+nkc, P помещает в магазин αβⁿ и переходит в состояние q. Тогда Р должен стереть содержимое магазина вплоть до α к тому моменту, когда он выдает ω^Rc. Но так как α от ω не зависит, то выдать ω уже невозможно. 

     Теорема. Существует простая СУ-схема T = (N, Σ, Δ, R, S), для которой нет такого ДМП-преобразователя P, что τ(P) ={(π^R, x)|(S, S)=>_π(ω, x) для некоторой цепочки ω}.

     Доказательство. Пусть Т определяется правилами

     1) S→Sa, aSa

     2) S→Sb, bSb