Алгоритм разбора сверху-вниз

Пусть дана КС-грамматика G = (N, T, P, S). Рассмотрим предсказывающий разбор (или разбор сверху-вниз) для грамматики G.

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

Рис. 4.1:

Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной цепочки предсказывающий анализатор должен определить правило S X₁X₂... , которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X₁, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

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

Рис. 4.2:

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

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

Таблица анализа - это двумерный массив M[A, a], где A - нетерминал, и a - терминал или символ $. Значением M[A, a] может быть некоторое правило грамматики или элемент «ошибка».

Магазин может содержать последовательность символов грамматики с $ на дне. В начальный момент магазин содержит только начальный символ грамматики на верхушке и $ на дне.

Анализатор работает следующим образом. Вначале анализатор находится в конфигурации, в которой магазин содержит S$, на входной ленте w$ (w - анализируемая цепочка), выходная лента пуста. На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действия анализатора. Имеются следующие возможности.

1. Если X = a = $, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.

2. Если X = a $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X - терминал, и X a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

4. Если X - нетерминал, анализатор заглядывает в таблицу M[X, a]. Возможны два случая:

• Значением M[X, a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.
• Значением M[X, a] является «ошибка». В этом случае анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

Работа анализатора может быть задана следующей программой:

do {X=верхний символ магазина; if (X - терминал || X=="$") if (X==InSym) {удалить X из магазина; InSym=очередной символ; } else error(); else /*X - нетерминал*/ if (M[X,InSym]=="X->Y1Y2...Yk") {удалить X из магазина; поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку); вывести правило X->Y1Y2...Yk; } else error(); /*вход таблицы M пуст*/ } while (X!=$) /*магазин пуст*/

Пример 4.3. Рассмотрим грамматику арифметических выражений G = ({E, E', T, T', F}, {id, +, *, (, )}, P, E) с правилами:

	E TE'		T' *FT'
	E' +TE'		T' e
	E' e		F (E)
	T FT'		F id

Таблица предсказывающего анализатора для этой грамматики приведена на рис. 4.3. Пустые клетки таблицы соответствуют элементу «ошибка».

Рис. 4.3:

При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную на рис. 4.4. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рис. 4.5.

Рис. 4.4:

Рис. 4.5:

Функции FIRST и FOLLOW

При построении таблицы предсказывающего анализатора нам потребуются две функции - FIRST и FOLLOW.

Пусть G = (N, T, P, S) - КС-грамматика. Для - произвольной цепочки, состоящей из символов грамматики, определим FIRST( ) как множество терминалов, с которых начинаются строки, выводимые из . Если ^*e, то e также принадлежит FIRST( ).

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, т.е. множество терминалов a таких, что существует вывод вида S ^* Aa для некоторых , (N T)^*. Заметим, что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ также принадлежит FOLLOW(A).

Рассмотрим алгоритмы вычисления функции FIRST.

Алгоритм 4.3. Вычисление FIRST для символов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X) для каждого символа X (N T).

Метод. Выполнить шаги 1-3:

• Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) = .
• Если в P имеется правило X e, то добавить e к FIRST(X).
• Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:

если X - нетерминал и имеется правило вывода X Y ₁Y ₂...Y _k, то включить a в FIRST(X), если a FIRST(Y _i) для некоторого i, 1 i k, и e принадлежит всем FIRST(Y ₁), ..., FIRST(Y _i-1), то есть Y ₁...Y _i-1 ^*e. Если e принадлежит FIRST(Y _j) для всех j = 1, 2, ..., k, то добавить e к FIRST(X).

Алгоритм 4.4. Вычисление FIRST для цепочки.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X₁X₂...X_n), X_i (N T).

Метод. Выполнить шаги 1-3:

• При помощи предыдущего алгоритма вычислить FIRST(X) для каждого X (N T).
• Положить FIRST(X₁X₂...X_n) = .
• Добавить к FIRST(X₁X₂...X_n) все не e-элементы из FIRST(X₁). Добавить к нему также все не e-элементы из FIRST(X₂), если e FIRST(X₁), не e-элементы из FIRST(X₃), если e принадлежит как FIRST(X₁), так и FIRST(X₂), и т.д. Наконец, добавить цепочку e к FIRST(X₁X₂...X_n), если e FIRST(X_i) для всех i.

Рассмотрим алгоритм вычисления функции FOLLOW.

Алгоритм 4.5. Вычисление FOLLOW для нетерминалов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FOLLOW(X) для каждого символа X N.

Метод. Выполнить шаги 1-4:

• Положить FOLLOW(X) = для каждого символа X N.
• Добавить $ к FOLLOW(S).
• Если в P eсть правило вывода A B , где , (N T)^* то все элементы из FIRST( ), за исключением e, добавить к FOLLOW(B).
• Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять:

если в P есть правило A B или A B , , (N T)^*, где FIRST( ) содержит e (т.е. ^*e), то все элементы из FOLLOW(A) добавить к FOLLOW(B).

Пример 4.4. Рассмотрим грамматику из примера 4.3. Для нее

	FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
	FIRST(E') = {+, e}
	FIRST(T') = {*, e}
	FOLLOW(E) = FOLLOW(E') = { ), $}
	FOLLOW(T) = FOLLOW(T') = {+, ), $}
	FOLLOW(F) = {+, *, ), $}

Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i = 1, поскольку FIRST(id) = {id} и FIRST(”(”) = {”(”} в соответствии с шагом 1. На шаге 3 при i = 1, в соответствии с правилом вывода T FT' к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.

При вычислении множеств FOLLOW на шаге 2 в FOLLOW(E) включается $. На шаге 3, на основании правила F (E), к FOLLOW(E) добавляется также правая скобка. На шаге 4, примененном к правилу E TE', в FOLLOW(E') включаются $ и правая скобка. Поскольку E' ^*e, они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.