Стр. 51 - Информационные структуры и их преобразование
Упрощенная HTML-версия
49
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Автомат не сработал. Надо было не заменять в точке, а продолжать
грузить дальше
.
Рассмотрим цепочку i+i*i
(
)
(
)
(
)
(
)
(
)
(
)
(
)
,$q E,$e,q T E,$e,q
F*T E,$e,q i*T E,$e,q *T E,$i,q T E,$i,*q
1
0
0
0
0
0
0
+
+
+
+
+
Детерминированный МП-автомат
Среди рассмотренных ранее автоматов большинство было
недетерминированных, т.е. в текущей конфигурации при следующем такте
нужно было выбрать вариант конфигурации.
МП-автомат
называется
недетерминированным,
если
для
(
)
αω δ ∈∀ ∈∀
,a,q F, q' и Q q
0
содержит не более одного состояния, и
(
)
(
)
,0 ,a,q енно
соответств
и 0 ,e,q
0
0
=αω δ
=α
δ
(
)
α
δ
,e,q
0
- содержит не более
одного состояния (обозначается:
(
)
1 ,a,q
0
≤αω δ
).
−
−
−
=
состояное
ьное
заключител
q
сравнение
q
состояние
начальное
q
Q
2
1
0
(
)
(
)
(
)
(
)
(
)
(
)
{ }
b,a x
e,q z,e,q
z,q z,c,q
xz,q z,x,q
2
1
1
0
0
0
=
=
δ
α = α
δ
=
δ
Проблема зацикливания
Конфигурация
автомата
(
)
i
i
,,q
βω
для
1 i
≥
называется
зацикливающийся, если существует такое состояние
(
)
(
)
(
)
1i
ki
ki
ki
1i
1i
i
i
иначе , ,, q
,, q
,,q
+
+
+
+
+
+
β≥ β
βω
βω
βω
.
Автомат ничего не считывает, а конфигурация магазина или растет,
или не уменьшается.
4.1. Общие методы синтаксического анализа.
Для КС – грамматики входная цепочка разобрана (проанализирована),
если известно дерево вывода. Но большинство компиляторов производит
разбор моделированием МП – автомата, анализирующего цепочки либо
сверху вниз, либо снизу вверх.
Способность МП – автомата проводить нисходящий разбор связана со
способностью МП – распознавания отображать входные цепочки в
последовательность левых выводов.
Восходящий разбор связан с отображением входной цепочки в
последовательность обращенных правых выводов.
