Разработка компиляторов
Управляющая таблица 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] .
Далее мы рассмотрим поведение анализатора грамматики при разборе входной цепочки.
