Разработка компиляторов



         

Управляющая таблица 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] .

Далее мы рассмотрим поведение анализатора грамматики при разборе входной цепочки.




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