Алгоритм разбора сверху-вниз
Пусть дана КС-грамматика G = (N; T; P; S). Рассмотрим разбор сверху-вниз (предсказывающий разбор) для грамматики G.
Главная задача предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора с точки зрения построения дерева разбора проиллюстрирован на рис. 4.1
Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной цепочки предсказывающий анализатор должен определить правило S
X1X2 ... ; которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y
a ... : Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.
На рис. 4.2 условно показана структура предсказывающего анализатора, который определяет
Рис. 4.1. очередное правило с помощью таблицы. Такую таблицу можно построить и непосредственно по грамматике. Таблично-управляемый предсказывающий анализатор имеет входную ленту, управляющее устройство (программу), таблицу анализа, магазин (стек) и выходную ленту. Входная лента содержит анализируемую строку, заканчивающуюся символом $ - маркером конца строки. Выходная лента содержит последовательность примененных правил вывода.
Рис. 4.2. Таблица анализа - это двумерный массив M[A; a], где A - нетерминал, и a - терминал или символ $. Значением M[A; a] может быть некоторое правило грамматики или элемент "ошибка".
Магазин может содержать последовательность символов грамматики с $ на дне. В начальный момент магазин содержит только начальный символ грамматики на верхушке и $ на дне.
Анализатор работает следующим образом. Вначале анализатор находится в конфигурации, в которой магазин содержит S$, на входной ленте w$ (w - анализируемая цепочка), выходная лента пуста.
На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действия анализатора. Имеются следующие возможности.
- Если X=a=$, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.
- Если X= a $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.
- Если X - терминал, и X a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.
- Если X - нетерминал, анализатор заглядывает в таблицу M[X; a]. Возможны два случая:
- Значением M[X; a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.
- Значением M[X; a] является "ошибка". В этом случае анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку. Работа анализатора может быть задана следующей программой:
Поместить '$', затем S в магазин; do {X=верхний символ магазина; if (X - терминал) if (X==InSym) {удалить X из магазина; InSym=очередной символ; } else {error(); break;} else if (X - нетерминал) if (M[X,InSym]=="X->Y1Y2...Yk") {удалить X из магазина; поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку); вывести правило X->Y1Y2...Yk; } else {error(); break;} /*вход таблицы M пуст*/ } while (X!='$'); /*магазин пуст*/ if (InSym != '$') error(); /*Не вся строка прочитана*/
Пример 4.3. Рассмотрим грамматику арифметических выражений G=({E; E', T, T', F}, {id, +, *, (, )}, P, E) с правилами:
В таблица 4.3 приведена предсказывающего анализатора для этой грамматики. Пустые клетки таблицы соответствуют элементу "ошибка".
Таблица 4.3. Нетерминал | Входной символ |
id | + | * | ( | ) | $ |
E | ETE' | | | ETE' | | |
E' | | E'+TE' | | | E'e | E'e |
T | TFT' | | | TFT' | | |
T' | | T'e | T'*FT' | | T'e | T'e |
F | Fid | | | F(E) | | |
При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную в таблица 4.4.
Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рис. рис. 4.3.
Таблица 4.4. Магазин | Вход | Выход |
E$ | id + id * id$ | |
TE'$ | id + id * id$ | E TE' |
FT'E'$ | id + id * id$ | T FT' |
id T'E'$ | id + id * id$ | F id |
T'E'$ | +id * id$ | |
E'$ | +id * id$ | T' e |
+TE'$ | +id * id$ | E' +TE |
TE'$ | id * id$ | |
FT'E'$ | id * id$ | T FT' |
id T'E'$ | id * id$ | F id |
T'E'$ | *id$ | |
*F'T'E'$ | *id$ | T' *FT' |
FT'E'$ | id$ | |
id T'E'$ | id$ | F id |
T'E'$ | $ | |
E'$ | $ | T' e |
$ | $ | E' e |
Содержание раздела