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

         

На каждом такте анализатор рассматривает


На каждом такте анализатор рассматривает 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) с правилами:



В таблица 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.

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




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий