spoPresentation2
.pdf
Построение эквивалентных состояний КА
Дано: КА M(Q,V,G,q0,F), задающий язык L (М)
Получить: эквивалентный ему КА M’(Q’,V’,G’,q0’,F’), задающий тот же язык
L(M) = L(M’), не содержащий эквивалентных состояний
Дополнительные условия: нет
171
Построение эквивалентных состояний КА
1. n=0, строится R(0)
2. n++. Строится R(n):
R(n) = {r (n) | {q | G (q,a) ri (n-1), q Q, a V } }
Т.е. в новые классы входят те состояния, которые для одних и тех же входных символов переходят в одно и то же множество n-1 эквивалентных состояний (класс эквивалентности)
3. Если R(n) z R(n-1), то повторить шаг 2
172
Построение эквивалентных состояний КА
4. Q = R(n)
Каждый класс эквивалентности становится состоянием минимизированного КА, функции переходов в котором строятся очевидным образом
|
Пример |
|
|
|
|
|
B |
1 |
D |
|||
|
М ( {A,B,C,D,E}, {0,1}, G, A ,{D, |
|
||||||||||
0 |
0 |
|||||||||||
|
G |
A |
B |
C D |
E |
|
|
1 |
||||
|
A |
|
|
|||||||||
|
|
|
|
|||||||||
|
0 |
B |
|
|
C |
B |
|
|
|
|||
|
|
|
|
1 |
|
0 |
1 |
|||||
|
1 |
C |
D |
E |
E |
D |
|
C |
||||
|
|
|
1 |
E |
||||||||
|
|
|
|
|
|
|
|
|
|
173 |
||
|
|
|
|
|
|
|
|
|
|
|
||
Построение эквивалентных состояний КА
1. n=0; R(0) = { {A, B, C}, {D, E} }
2.1. n=1;
R(n) = {r (n) | {q | G (q,a) ri (n-1), q Q, a V } }
R(0) |
A B C |
D E |
0
A 
B C D E
174
Построение эквивалентных состояний КА
1. n=0; R(0) = { {A, B, C}, {D, E} }
2.1. n=1;
R(n) = {r (n) | {q | G (q,a) ri (n-1), q Q, a V } }
R(0) |
A B C |
D E |
1
A 
B C D E
175
Построение эквивалентных состояний КА
R(1) = { {A}, {B,C}, {D,E} }
2.2 n=2;
R(n) = {r (n) | {q | G (q,a) ri (n-1), q Q, a V } }
R(1) |
A B C |
D E |
0
A B C D E
176
Построение эквивалентных состояний КА
R(1) = { {A}, {B,C}, {D,E} }
2.2 n=2;
R(n) = {r (n) | {q | G (q,a) ri (n-1), q Q, a V } }
R(1) |
A B C |
D E |
1
A B C D E
177
Построение эквивалентных состояний КА
R(2) = { {A}, {B,C}, {D,E} }3. R(2)=R(1)
R(2) |
A |
|
B |
C |
D E |
|
|
4. Q = R(2) = { A, BC, DE } = { A, B, D } |
|||||||
G |
A |
B |
D |
|
B |
1 |
D |
0 |
B |
|
B |
|
|
||
|
|
0, 1 |
0 |
|
|||
1 |
B |
D |
D |
|
A |
1 |
|
|
|
||||||
178
КС - грамматики
Синтаксический анализатор – это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входного языка
СА – основная часть компилятора на этапе анализа
На вход СА поступает таблица лексем, сформированная ЛА
СА разбирает ее в соответствии с грамматикой входного языка
179
КС - грамматики
СА выполняет:
Поиск и выделение синтаксических конструкций в тексте исходной программы
Установку типа и проверку правильности синтаксической конструкции
Представление синтаксических конструкций в виде, удобном для генерации результирующего кода
180