Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 36 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

38
цепочки и переходим из текущего состояния в другое состояние по дуге,
помеченной этим символом. Состояние, в которое мы при этом попада-
ем, становится текущим.
При работе этого алгоритма возможны следующие ситуации (аналогичные
ситуациям, которые возникают при разборе непосредственно по регулярной
грамматике):
1. прочитана вся цепочка; на каждом шаге находилась единственная дуга,
помеченная очередным символом анализируемой цепочки; в результате
последнего перехода оказались в состоянии S. Это означает, что исходная
цепочка принадлежит языку L(G);
2. прочитана вся цепочка; на каждом шаге находилась единственная «нуж-
ная» дуга; в результате последнего шага оказались в состоянии, отличном
от S. Это означает, что исходная цепочка не принадлежит языку L(G);
3. на некотором шаге не нашлось дуги, выходящей из текущего состояния и
помеченной очередным анализируемым символом. Это означает, что ис-
ходная цепочка не принадлежит языку L(G);
4. на некотором шаге работы алгоритма оказалось, что есть несколько дуг,
выходящих из текущего состояния, помеченных очередным анализируе-
мым символом, но ведущих в разные состояния. Это говорит о
недетерминированности разбора.
Диаграмма состояний определяет конечный автомат, построенный по ре-
гулярной грамматике, который допускает множество цепочек, составляющих
язык, определяемый этой грамматикой. Состояния и дуги ДС – это графическое
изображение функции переходов конечного автомата из состояния в состояние
при условии, что очередной анализируемый символ совпадает с символом-
меткой дуги. Среди всех состояний выделяется начальное (считается, что в на-
чальный момент своей работы автомат находится в этом состоянии) и конечное
(если автомат завершает работу переходом в это состояние, то анализируемая
цепочка им допускается).
Конечный автомат (КА) – это пятерка (K, VT, δ, H, S), где
K – конечное множество состояний;
VT – конечное множество допустимых входных символов;
δ – отображение множества K × VT → K, определяющее поведение авто-
мата; отображение F часто называют функцией переходов;
H ∈ K – начальное состояние;
S ∈ K – заключительное состояние (либо конечное множество заключи-
тельных состояний).
δ(A, t)=B означает, что из состояния A по входному символу t происходит
переход в состояние B.
Конечный автомат допускает цепочку a
1
a
2
...a
n
, если δ(H,a
1
) = A
1
; δ(A
1
,a
2
)
= A
2
; … ; δ(A
n-2
,a
n-1
) = A
n-1
; δ(A
n-1
,a
n
) = S, где a
i
∈ VT, A
j
∈ K, j = 1, 2 , ... ,n-1;
i = 1, 2, ... ,n; H – начальное состояние, S – одно из заключительных состояний.

Страницы