Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Управляющая программа анализатора

 

Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида s0X1s1X2…Xmsm, где sm – вершина магазина. Каждый Xi – символ грамматики, а si – символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. Комбинация символа состояния на вершине магазина и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в магазине; однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

 

Программа, управляющая LR-анализатором, ведет себя следующим образом. Рассматривается пара: sm – текущее состояние на вершине магазина, ai – текущий входной символ; после этого вычисляется action [ sm, ai ], которое может иметь одно из четырех значений:

  1. shift s, где s – состояние,
  2. свертка по правилу A→β,
  3. допуск (accept)
  4. ошибка.

 

Функция goto получает состояние и символ грамматики и выдает состояние. Функция goto, строящаяся по грамматике G, есть функция переходов детерминированного магазинного автомата, который распознает язык, порождаемый грамматикой G.

Управляющая программа выглядит следующим образом:

Установить ip на первый символ входной цепочки w$;

while (цепочка не закончилась)

{

Пусть s – состояние на вершине магазина,

a – символ входной цепочки, на который указывает ip.

if (action [s, a] == shift s’)

{

push (a);

push (s’);

ip++;

}

else if (action [s, a] == reduce A→β)

{

for (i=1; i<=|β|; i++)

{

pop ();

pop ();

}

Пусть s’ – состояние на вершине магазина;

push (A);

push (goto [s’, A ]);

Вывод правила (A→β);

}

else if (action [s, a] == accept)

{

return success;

}

Else

{

error ();

}

}

 

Управляющая таблица LR(0)-анализатора

 

Обсудим подробно алгоритм построения управляющей таблицы на примере LR(0)-анализаторов.

 

Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику G0:

 

(1) S (L)
(2) S x
(3) L S
(4) L L, S

Определение. Пусть G = (VT, VN, P, S) – КС-грамматика. Пополненной грамматикой (augmented grammar) будем называть грамматику G' = (VT, VN+{S'}, P+{ S'→S }, S'), где
S' – нетерминал, непринадлежащий множеству N.

Определение. Пусть G = (VT, VN, P, S) – КС-грамматика. Будем называть [A→w1.w2,, u] LR(k)-ситуацией (LR(k)-item), если A→w1w2 является правилом из P и u – цепочка терминалов, длина которой не превосходит k.

 

Понятно, что LR(0)-ситуации не должны содержать терминальной цепочки, то есть мы можем записывать их следующим образом: [A→w1.w2].

 


<== предыдущая | следующая ==>
Восходящие анализаторы | Далее мы рассмотрим поведение анализатора грамматики при разборе входной цепочки

Date: 2016-05-25; view: 260; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию