4. Синтаксический анализ

4.1. Дерево порождения для кс-грамматики

В соответствии с классификацией по Хомскому грамматика является контекстно-свободной, если все порождающие правила имеют вид:

A → γ,

где A – нетерминальный символ, γ – цепочка из терминальных и нетерминальных символов.

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

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

4.2. Автомат с магазинной памятью

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

Автомат с магазинной памятью задается семеркой множеств:

{Σ, Q, q₀, F, Γ, Z₀, δ},

где Σ – множество (алфавит) входных символов; Q – множество состояний МПА; q₀ – начальное состояние, ;  F – множество заключительных состояний, ; Γ – множество (алфавит) магазинных символов; Z₀ – начальный магазинный символ, ; δ – множество правил перехода.

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

(a, B, q_i) → (λ, γB, q_j),

где , а символ B и символы из цепочки γ все принадлежат алфавиту Γ, означает, что в магазин, содержащий верхний символ B, записывается цепочка символов γ, текущее состояние становится q_j , после чего делается переход к чтению следующего входного символа. Правило:

(a, B, q_i) → (a, λ, q_j),

означает, что из магазина удаляется верхний символ B, текущее состояние становится q_j , переход к чтению следующего входного символа не производится.

До начала функционирования МПА в магазине имеется начальный магазинный символ, МПА находится в начальном состоянии. На каждом шаге работы читается очередной символ входной цепочки, начиная с первого, читается верхний символ магазина, и выполняются действия по такому правилу перехода, которое соответствует этим символам и текущему состоянию. Работа МПА заканчивается, когда не будет ни одного подходящего правила, чтобы можно было продолжать работу. Если при этом выполнены три условия: цепочка прочитана вся, магазин пуст, МПА находится в заключительном состоянии, то цепочка считается распознанной. Если же хотя бы одно из этих условий нарушено, цепочка считается нераспознанной. Цепочка считается нераспознанной и в том случае, если МПА никак не может остановиться, т.е. когда он зациклил, и нет продвижения по входной цепочке.

МПА будет детерминированным (ДМПА), если на каждом шаге возможно применение не более одного правила перехода. Если же на каком-либо шаге можно выполнить действия по двум или более правилам перехода, то МПА будет недетерминированным (НМПА), тогда он должен выполнять действия в соответствии со всеми этими правилами параллельно. Гипотетически такое одновременное выполнение нескольких переходов можно представить так: Создаются копии МПА в количестве, соответствующем количеству одновременно выполняемых правил, после чего каждая копия независимо от других выполняет действия по своему правилу. Некоторые из копий могут попадать в тупики, их работа заканчивается, но это не влияет на работу других копий. Если, в конце концов, хотя бы одна из копий распознает входную цепочку, то считается, что входная цепочка распознана недетерминированным МПА. Входная цепочка считается нераспознанной, если ни одна из копий МПА не распознала цепочку. Таким образом, НМПА проверяет все возможные варианты действий на каждом шаге работы. Следует заметить, что количество всех работающих копий может оказаться таким большим, что превысит любое наперед заданное число, поэтому функционирование НМПА можно представить чисто гипотетически.

При грамматическом разборе дерево порождения может строиться двумя основными способами: сверху вниз и снизу вверх. В обоих случаях входная цепочка символов читается слева направо. При разборе сверху вниз вначале строится корень дерева – начальный нетерминал. Затем, в соответствии с левым каноническим порождением, подбираются такие порождающие правила, чтобы, в конце концов, висячие вершины дерева совпали с символами входной цепочки. Такой вариант разбора называют LL-разбором (от англ. left – левый), так как цепочка символов читается слева направо, а дерево строится, как при левом каноническом порождении.

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

4.3. LL-разбор КС-грамматики автоматом с магазинной памятью

Пусть задана КС-грамматика. Построим по ней МПА, выполняющий грамматический LL-разбор. Множество входных символов Σ в МПА будет совпадать с множеством терминальных символов грамматики. Множество состояний Q будет состоять из единственного состояния q₀, оно же будет начальным и заключительным. Множество магазинных символов Γ будет содержать все терминальные и нетерминальные символы грамматики: Γ = Σ U N. Начальный магазинный символ Z₀ будет совпадать с начальным символом грамматики S. Правила перехода δ для МПА будем строить следующим образом. Для каждого порождающего правила вида A → γ будет правило перехода:

(λ, A, q₀) → (λ, γ^–1, q₀), (*)

где γ^–1 – правая часть правила γ в обратном порядке, а для каждого терминального символа a правило перехода:

(a, a, q₀) → (λ, λ, q₀). (**)

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

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

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

Пример 5. Пусть задана грамматика простых арифметических выражений (S – начальный нетерминал):

S → S + T | T

T → T * F | F

F → (S) | a

Пусть цепочка на входе: a + a. В табл. 6 представлен тот вариант шагов LL-разбора, который приводит к успешному распознаванию.

Табл. 6

№ шага	Входные символы	Содержимое магазина	Порождающее правило
1	a + a	S	S → S + T
2	a + a	S + T	S → T
3	a + a	T + T	T → F
4	a + a	F + T	F → a
5	a + a	a + T
6	+ a	+ T
7	a	T	T → F
8	a	F	F → a
9	a	a
10	λ	λ

В табл. 6 не приведены другие варианты шагов разбора, которые приводят в тупик или зацикливают. Для этого примера неудачных вариантов оказывается бесконечно много. Так, при применении переходов с многократным повторением одного и того же порождающего правила S → S + T содержимое магазина будет неограниченно увеличиваться: S, S + T, S + T + T, S + T + T + T, … Применение переходов с порождающими правилами S → T, T → F, F → a приведет к тому, что содержимое магазина будет изменяться так: S, T, F, a, λ. После этого во входной цепочке останутся непросмотренными символы: + a, т.е. возникнет тупик.

Конец примера.