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

ВОСХОДЯЩИЙ  СИНТАКСИЧЕСКИЙ АНАЛИЗ

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

1. Определение разбора

     Считается, что для некоторой КС-грамматики G цепочка ωL(G) разобрана или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно “физически” построить в памяти машины, но вероятнее, что будет использован какой-нибудь более оптимальный способ представления. Прослеживая шаг за шагом работу синтаксического анализатора, можно получить дерево разбора, хотя связь между этими процессами становится очевидной далеко не сразу.

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

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика, правила которой занумерованы 1, 2, ..., р. Пусть α (N Σ)*. Тогда:

a) левым разбором цепочки α называется последовательность правил, примененных при левом выводе цепочки α из S,

b) правым разбором цепочки α называется обращение последовательности правил, примененных при правом выводе цепочки α из S.

     Эти разборы можно представить в  виде последовательности номеров из множества {1, 2, . . . , p}.

В качестве примера  рассмотрим грамматику G₀ с такой нумерацией правил:  1)   E→E+T

            2)   E→T

            3)   T→ T*F

            4)   T→ F

            5)   F→ E

            6)   F→ a

    Левый разбор цепочки а*(а + а) — это последовательность 23465124646, а правый разбор —64642641532.

     Для описания левых и правых разборов введем дополнительные обозначения.

     Пусть G = (N, Σ, Р, S) — КС-грамматика, правила которой занумерованы числами от 1 до р. Будем считать, что α _i=>β, если α =>_iβ и применено i-e правило. Аналогично будем считать, что α =>_iβ, если α =>_rβ и применено i-e правило. Расширим эти обозначения, положив   (1)   α_π1 => γ,  если  α_π1 => β и β _π2 => γ,

     (2)   α => _{π1 π2}γ,  если  α => _π1β  и  β => _π2γ.

   2. Нисходящий разбор

     В этой части работы исследуется проблема левого анализа для КС-грамматик. Пусть π = i₁…i_n — левый разбор цепочки ωL(G), где G — КС-грамматика. Зная π, можно построить дерево разбора цепочки ω следующим “нисходящим” образом. Начнем с корня, помеченного S. Тогда i₁ дает правило, которое надо применить к S. Допустим, что i₁ — номер правила S→X₁. . .X_k. Присоединим k потомков к вершине, помеченной S, и пометим их Х₁, Х₂, . . ., X_k. Если X_i— первый слева нетерминал в цепочке X₁...X_k, то первыми i—1 символами цепочки ω должны быть X₁. . . X_i-1. Правило с номером i₂ должно тогда иметь вид X_i→Y_l. . .Y_i, и можно продолжить построение дерева разбора цепочки ω, применяя ту же процедуру к вершине, помеченной X_i. Продолжая в том же духе, можно построить все дерево разбора цепочки ω, соответствующее левому разбору π.

     Допустим  теперь, что даны КС-грамматика G = (N, Σ, Р, S), в которой правила занумерованы от 1 до р, и цепочка ω Σ *, для которой мы хотим построить левый разбор. Можно считать, что известны корень и крона дерева разбора и нам остается восполнить промежуточные вершины. Стратегия левого нисходящего разбора предлагает пытаться заполнять дерево разбора, начиная с корня, и двигаться слева направо, направляясь к кроне.

     Можно показать, что существует простая СУ-схема, отображающая цепочки языка L(G) в их левые (или правые) разборы. Мы определим здесь такую СУ-схему, хотя предпочитаем исследовать МП-преобразователь, реализующий соответствующий перевод, потому что от него легко перейти к реальному выполнению этого перевода.

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика, где правила занумерованы от 1 до р. Определим СУ-схему Т_l^G (или Т_l, если G подразумевается) как пятерку (N, Σ, {1, . . ., р}, R, S), где R состоит из таких правил А→ α, β, что А→ α —правило из Р с номером i, а β = i α ', где α ' — цепочка α, из которой устранены все терминалы.

     В качестве примера возьмем Go — с правилами, занумерованными, как в предыдущих примерах. Тогда Т_i = ({E, T, F}, { + , *, (, ), а}, {1, . . . , 6}, R, Е), где R состоит из правил:  1)   E→E+T, 1ET

                        2)   E→T, 2T

                        3)   T→ T*F, 3TF

                        4)   T→ F, 4F

                        5)   F→ E, 5E

                        6)   F→ a, 6

      Пара деревьев, изображенная на рис. 1, задает перевод цепочки а*(а+а).  
 

                             а       б 
 
 
 

     Рис. 1. Перевод схемой Т_i : а—вход; б—выход.

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

     Доказательство. С помощью индукции можно доказать, что (A, A) => *τ_i (ω, π) тогда и только тогда, когда A_π => _G ω.

     Для любой грамматики G можно построить недетерминированный МП-преобразователь, работающий как левый анализатор для G.

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

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

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

     Назовем М_l^G левым анализатором для G.

     Для входа ω анализатор M_l моделирует левый вывод в грамматике G цепочки ω из S. По правилам (1) M_l каждый раз “развертывает” нетерминал, расположенный наверху магазина, в соответствии с некоторым правилом из Р и одновременно выдает номер этого правила. Если наверху магазина находится терминальный символ, то M_l по правилу (2) проверяет, совпадает ли он с текущим входным символом. Таким образом, M_l может производить только левый вывод цепочки ω.

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

     Доказательство. Доказательство производится с помощью метода индукции. Предположение индукции состоит в том, что (q, ω, А, е) |— *(q, е, е, π) тогда и только тогда, когда А_π => ω.

     Заметим, что М_l^G — это почти, но не совсем МП-преобразователь, который получается из СУ-схемы T_l^G.

     В качестве примера построим левый анализатор для грамматики G₀.

     Здесь  М_l = ({q}, Σ, N Σ, {1, 2, . . . , 6}, δ, q, E, Ø}, где

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

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

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

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

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

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

                  |— (q, a+a*a, T+T, 12)

                  |— (q, a+a*a, E+T, 124)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 12463)

                  |— (q, a+a*a, E+T, 124634)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 12463466)

                  |— (q, a+a*a, E+T, 12463466)

     Левый анализатор представляет собой, вообще говоря, недетерминированное устройство. Чтобы пользоваться им на практике нужно уметь моделировать его  детерминированно. Для некоторых грамматик (например, для тех, что содержат циклы) полное моделирование невозможно (в данном случае потому, что некоторые цепочки имеют бесконечно много левых разборов). Кроме того, естественное моделирование непригодно для более широкого класса грамматик, а именно для леворекурсивных грамматик. Нисходящий анализ налагает существенное ограничение: должна быть устранена левая рекурсия.

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

     Можно рассмотреть более широкий класс  грамматик, для каждой из которых  возможен ДМП-преобразователь, реализующий  СУ-схему T_l. Он содержит все LL-грамматики и некоторые другие, которые можно анализировать только “неестественным” способом, т. е. таким, когда содержимое магазина не отражает в отличие от анализатора M_l последовательности шагов левого вывода. С точки зрения нисходящего анализа такие грамматики представляют только теоретический интерес.

     3. Восходящий разбор

     В этой части реферата будет рассмотрен правый разбор. Возьмем правый вывод в грамматике G₀ цепочки а+а*а из Е:

                        E => E + T

     => E + T*F

     => E + T*a

     => E + F*a

     => E + a*a

     => T + a*a

     => F + a*a

     => a + a*a

     Записывая в обратном порядке последовательность правил, участвующих в этом выводе, получаем правый разбор 64264631 цепочки а+а*а.

     Вообще  правый разбор цепочки ω в грамматике G = (N, Σ, Р, S) — это последовательность правил, с помощью которых можно свернуть цепочку ω к начальному символу S. В терминах деревьев выводов правый анализ цепочки ω представляет собой последовательность отсечений основ, сводящую дерево вывода с кроной ω к одной вершине, помеченной S. В сущности это равносильно процессу “заполнения” дерева вывода, начинающемуся с одной только кроны и идущему от листьев к корню. Поэтому с процессом порождения правого разбора часто ассоциируется термин “восходящий” анализ.

     По  аналогии с СУ-схемой T_l отображающей цепочки из L(G) в их левые разборы, можно определить СУ-схему Т_r, отображающую цепочки в правые разборы. В ней из элементов перевода устранены терминалы, а номера правил выводов пишутся справа.

     Далее рассмотрим МП-преобразователь, реализующий схему Т_r. По аналогии с расширенным МП-автоматом определим расширенный МП-преобразователь.

     Определение. Расширенным МП-преобразователем называется восьмерка P = (Q, Σ, Г, Δ, δ, q₀, Z₀, F), где все символы понимаются так же, как прежде, но только δ теперь обозначает отображение конечного подмножества множества Q (Σ {е})Г* в множество конечных подмножеств множества Q Г* *. Конфигурации определяются так же, как прежде, но обычно подразумевается, что верх магазина расположен справа, и запись (q, aω, βα, х) |— (р, ω, βγ , ху) означает, что δ(q, а, α) содержит (p, γ, y).

     Расширенный МП-преобразователь Р называется детерминированным, если

     1)  #δ(q, a, α)≤1 для всех qQ, aΣ {e} и αГ*,

     2)  цепочки α и β не являются суффиксами одна другой, если δ(q, a, α) Ø и δ(q, b, β) Ø для b=а или b=е.