- •Построение матрицы операторного предшествования
- •Автомат с магазинной памятью (сокращенно мп-автомат)
- •Преобразователь с магазинной памятью (сокращенно мп - преобразователь)
- •Опишем lr(k)-алгоритм разбора.
- •Алгоритм построения управляющей таблицы для lr(0)-грамматики без -правил
- •Алгоритм построения управляющей таблицы для slr(1)-грамматики без -правил
- •Включение -правил в lr(0)- и slr (1)-грамматики
- •Алгоритм построения анализатора типа “перенос –свертка” для грамматик простого предшествования
- •Описание алгоритма
Алгоритм построения управляющей таблицы для slr(1)-грамматики без -правил
4) Для магазинного символа Т, представляющего множество грамматических вхождений Q, и входного символа a значение f(a) определяется следующим образом.
а) Если начальное вхождение S0 Q и a = , то f() = ДОПУСК.
б) Если a и g(a) ошибка, то f(a) = перенос. в) Если Xj Q – самое правое грамматическое вхождение i-го правила AXj и a СЛЕД(А), то f(a) = (СВЕРТКА, i). Значение остальных элементов таблицы для f(a) – ОШИБКА.
в) Если Xj Q – самое правое грамматическое вхождение i-го правила AXj и a СЛЕД(А), то f(a) = (СВЕРТКА, i). Значение остальных элементов таблицы для f(a) – ОШИБКА.
Если имеется множество грамматических вхождений, не удовлетворяющих условиям а, б и в, то грамматика не принадлежит классу SLR(1).
E E + T
E T
T TP
T P
P (E)
P i
{Eo,E1} |
{E1,E5} |
{T2,T3} |
{T1,T3} |
{P3} |
{P4} |
{+1} |
{3} |
{(5} |
{)5} |
{i6} |
{} |
Ex |
Ey |
Tx |
Ty |
P3 |
P4 |
+1 |
3 |
(5 |
)5 |
i6 |
|
g() |
+ |
|
( |
) |
i |
E |
T |
P |
|
|
|
(5 |
|
i6 |
Ex |
Tx |
P4 |
(5 |
|
|
(5 |
|
i6 |
Ey |
Tx |
P4 |
i6 |
|
|
|
|
|
|
|
|
Ex |
+1 |
|
|
|
|
|
|
|
Tx |
|
3 |
|
|
|
|
|
|
P4 |
|
|
|
|
|
|
|
|
Ey |
+1 |
|
|
)5 |
|
|
|
|
+1 |
|
|
(5 |
|
i6 |
|
Ty |
P4 |
3 |
|
|
(5 |
|
i6 |
|
|
P3 |
)5 |
|
|
|
|
|
|
|
|
Ty |
|
3 |
|
|
|
|
|
|
P3 |
|
|
|
|
|
|
|
|
Функции действия f(a) для рассматриваемого примера изображены на
f(a) |
+ |
|
( |
) |
i |
|
|
|
|
П |
|
П |
|
(5 |
|
|
П |
|
П |
|
i6 |
С, 6 |
С, 6 |
|
С, 6 |
|
С, 6 |
Ex |
П |
|
|
|
|
Д |
Tx |
С, 2 |
П |
|
С, 2 |
|
С, 2 |
P4 |
С, 4 |
С, 4 |
|
С, 4 |
|
С, 4 |
Ey |
П |
|
|
П |
|
|
+1 |
|
|
П |
|
П |
|
3 |
|
|
П |
|
П |
|
)5 |
С, 5 |
С, 5 |
|
С, 5 |
|
С, 5 |
Ty |
С, 1 |
П |
|
С, 1 |
|
С, 1 |
P3 |
С, 3 |
С, 3 |
|
С, 3 |
|
С, 3 |