Теория и реализация языков программирования




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


На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действия анализатора. Имеются следующие возможности.

  1. Если X=a=$, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.
  2. Если X= a
    $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.
  3. Если X - терминал, и X
    a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.
  4. Если X - нетерминал, анализатор заглядывает в таблицу M[X; a]. Возможны два случая:
    1. Значением M[X; a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.
    2. Значением 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) с правилами:

\begin{align*} &E\rightarrow TE' &T&' \rightarrow *FT' \\ &E'\rightarrow +TE' &T&' \rightarrow e \\ &E'\rightarrow e &F& \rightarrow (E) \\ &T\rightarrow FT' &F& \rightarrow id. \\ \end{align*}

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

Таблица 4.3.

НетерминалВходной символ
id+*()$
EE
TE'
E
TE'
E'E'
+TE'
E'
e
E'
e
TT
FT'
T
FT'
T'T'
e
T'
*FT'
T'
e
T'
e
FF
id
F
(E)

При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную в таблица 4.4.


Содержание  Назад  Вперед