- •Лабораторные работы по курсу «Системное программное обеспечение»
- •9. Для ll(1) анализатора построить управляющую таблицу m
- •10. Аналитически написать правила вывода для цепочки ll(1) анализатора.
- •11. Реализовать управляющую таблицу m для lr(k) анализатора.
- •12. Построить множество lr(0)-таблиц не содержащих ε-правила.
- •14. Определить функции перехода g(X)
- •15. Определить функцию переноса-свертки f(u)
- •16. Для функции перехода g(X) и функции переноса-свертки f(u) спроектировать управляющую таблицу.
14. Определить функции перехода g(X)
Используя отношение OBLOW, построим таблицу переходов конечного (недетерминированного) автомата.
|
S |
F |
L |
i |
* |
: |
( |
) |
ɛ |
S0 |
|
|
|
|
|
|
|
|
|
(1 |
|
F1,F4 |
L2 |
i3 |
|
|
|
|
|
F1 |
|
|
|
|
|
:1 |
|
|
|
:1 |
|
F4 |
L1, L2 |
i3 |
|
|
|
|
|
L1 |
|
|
|
|
|
|
|
)1 |
|
)1 |
|
|
|
|
|
|
|
|
|
L2 |
|
|
|
|
*2 |
|
|
|
|
*2 |
|
|
|
|
|
|
|
|
|
i3 |
|
|
|
|
|
|
|
|
|
F4 |
|
|
|
|
|
|
|
|
|
┴ |
S0 |
|
|
|
|
|
(1 |
|
|
Преобразуем недетерминированный автомат в эквивалентный ему детерминированный автомат, таблица переходов которого будет иметь вид:
|
S |
F |
L |
i |
: |
( |
)
|
* |
{┴} |
{S0} |
|
|
|
|
{ (1 } |
|
|
{S0} |
|
|
|
|
|
|
|
|
{F1,F4} |
|
|
|
|
:1 |
|
|
|
{L2} |
|
|
|
|
|
|
*2 |
|
{F4} |
|
|
|
|
|
|
|
|
{L1, L2} |
|
|
|
|
|
|
{)1} |
{*3} |
{i3} |
|
|
|
|
|
|
|
|
{:1} |
|
{F4} |
{L1,L2} |
{i3} |
|
|
|
|
{*2} |
|
|
|
|
|
|
|
|
{)1} |
|
|
|
|
|
|
|
|
{(1} |
|
{F1,F4} |
{L2} |
{i3} |
|
|
|
|
Определим множество магазинных символов:
|
{S0} |
{F1,F4} |
{L2} |
{F4} |
{L1,L2} |
{i3} |
{:1} |
{*2} |
{)1} |
{(1} |
{┴} |
Vp |
S0 |
Fx |
L2 |
F4 |
Lx |
i3 |
:1 |
*2 |
)1 |
(1 |
┴ |
Тогда функция переходов g(X) LR(0)- анализатора для грамматики G имеют вид:
|
S |
F |
L |
i |
: |
( |
)
|
* |
┴ |
S0 |
|
|
|
|
(1 |
|
|
S0 |
|
|
|
|
|
|
|
|
Fx |
|
|
|
|
:1 |
|
|
|
L2 |
|
|
|
|
|
|
*2 |
|
F4 |
|
|
|
|
|
|
|
|
Lx |
|
|
|
|
|
|
)1 |
*3 |
i3 |
|
|
|
|
|
|
|
|
:1 |
|
F4 |
Lx |
i3 |
|
|
|
|
*2 |
|
|
|
|
|
|
|
|
)1 |
|
|
|
|
|
|
|
|
(1 |
|
Fx |
L2 |
i3 |
|
|
|
|