Слайд 2
Основные определения
ДМПА:
P = (Q, Σ, Γ, δ, q0,
Z0, F),
где
Q – конечное множество состояний;
Σ – конечный входной алфавит;
Γ – конечный алфавит магазинных символов;
δ – функция,
переходов, отображение множества Q×(Σ∪{e}∪{⊥})×Γ во множество Q×Γ*;
q0∈Q – начальное состояние;
Z0∈Γ – начальный символ;
F⊆Q – множество заключительных состояний.
Слайд 3
Основные определения
Конфигурация ДМПА P
(q, w, α)∈Q×Σ*×Γ*,
где:
q – текущее состояние устройства;
w – неиспользованная
часть входной цепочки;
α – содержимое магазина;
«⊥» – маркер конца входной цепочки.
Начальная конфигурация – (q0, w, Z0), где w∈Σ*, заключительная конфигурация – (q, ⊥, α), где q∈F и α∈Γ*.
Слайд 4
Основные определения
Такт работы ДМПА P при δ(q, a,
Z) = (q', γ), где q, q'∈Q, a∈Σ∪{e}∪{⊥}, w∈Σ*,
Z∈Γ, α, γ∈Γ*:
(q, aw, Zα) (q', w, γα),
Если δ(q, a, Z) = (q', γ), то ДМПА P может:
перейти в состояние q';
сдвинуть головку на одну ячейку вправо;
заменить верхний символ магазина цепочкой γ магазинных символов.
Частные случаи: Z = e, γ = e, a = e, a = ⊥.
Слайд 5
Основные определения
ДКА:
M = (Q, Σ, δ, q0, F),
где
Q – конечное
множество состояний;
Σ – конечное множество входных символов;
δ – функция переходов, отображение множества Q×(Σ∪{⊥})
во множество Q;
q0∈Q – начальное состояние;
F⊆Q – множество заключительных состояний.
Слайд 6
Основные определения
Конфигурация ДКА M
(q, w)∈Q×Σ*,
Начальная конфигурация – (q0,
w), где w∈Σ*, заключительная конфигурация – (q, ⊥), где
q∈F.
Такт работы ДКА M при δ(q, a) = q', где q, q'∈Q, a∈Σ∪{⊥}:
(q, aw) (q', w)
Слайд 7
Способы задания функции переходов
Граф переходов
Переход ДМПА δ(q, a,
Z) = (q', γ):
Переход ДКА δ(q, a) = q':
Слайд 8
Способы задания функции переходов
Переход в конечное состояние
Переход ДКА
δ(q, a) = q', где q'∈F:
Переход ДМПА δ(q, a,
Z) = (q', γ), где q'∈F:
Слайд 9
Способы задания функции переходов
Таблица переходов
Таблица переходов ДМПА:
δ(q, a,
Z) :
(q', γ);
HALT (a = ⊥, q∈F);
ERROR.
Слайд 10
Способы задания функции переходов
Таблица переходов
Таблица переходов ДКА:
δ(q, a)
:
q';
HALT (a = ⊥, q∈F);
ERROR.
Слайд 11
Способы задания функции переходов
Переход в конечное состояние
Слайд 12
Определение функции переходов
1. Построить граф переходов, а потом
преобразовать его в таблицу переходов.
2. Построение графа начинается с
начального состояния q0. Если начальное состояние может являться также и конечным, помечаем это двойной границей окружности.
3. Для каждого состояния графа qi определяем, есть ли из данного состояния такие переходы (a, Z, γ), которые соответствуют допустимому символу a из входной цепочки и допустимому символу Z на вершине стека (если автомат с магазинной памятью), которые пока еще отсутствуют в графе. Если есть, то проверяем, ведет ли данный переход в уже имеющееся состояние. Если да, то добавляем в граф только новый переход (a, Z, γ). Если нет, то добавляем в граф новое состояние и переход (a, Z, γ) в него. Если новое состояние может являться конечным, помечаем это двойной границей окружности.
4. Если в процессе выполнения шага 3 в графе появились новые состояния или переходы, возвращаемся на шаг 3, иначе граф переходов построен.
Слайд 13
Включение действий в синтаксис
Действия:
〈A1〉, 〈A2〉, …
Функция переходов ДМПА:
δ(q,
a, Z) = (q', γ, 〈A〉).
Функция переходов ДКА:
δ(q, a)
= (q', 〈A〉).
Отсутствие действия:
〈A〉 = e или 〈A〉 = ∅.
Слайд 14
Алгоритм работы ДМПА
Пусть M – магазин (стек), α = a1a2…an⊥
– входная цепочка. Тогда:
1. q := q0, M :=
Z0, k := 1.
2. Ищем δ(q, a, Z), где: a = ak, M = Zβ или a = ak, Z = e или a = e, M = Zβ.
3. Если δ(q, a, Z) не определена, то ошибка в позиции k. Если значений δ(q, a, Z) несколько – таблица переходов построена неверно. Если δ(q, a, Z) = (q', γ, 〈A〉), то:
3.1. Если 〈A〉 ≠ e и 〈A〉 ≠ ∅, то выполнить действие 〈A〉.
3.2. q := q'.
3.3. M := γβ.
3.4. Если a ≠ e, то k := k + 1.
4. Если δ(q, a, Z) = HALT, то разбор успешно завершен.
5. Если δ(q, a, Z) = ERROR, то имеем во входной цепочке синтаксическую ошибку в позиции k.
Слайд 15
Алгоритм работы ДКА
Пусть α = a1a2…an⊥ – входная цепочка. Тогда:
1.
q := q0, k := 1.
2. Ищем δ(q, a),
где a = ak.
3. Если δ(q, a) не определена, то ошибка в позиции k. Если значений δ(q, a) несколько – таблица переходов построена неверно. Если δ(q, a) = (q', 〈A〉), то:
3.1. Если 〈A〉 ≠ e и 〈A〉 ≠ ∅, то выполнить действие 〈A〉.
3.2. q := q'.
3.3. k := k + 1.
4. Если δ(q, a) = HALT, то разбор успешно завершен.
5. Если δ(q, a) = ERROR, то имеем во входной цепочке синтаксическую ошибку в позиции k.
Слайд 16
Посимвольный разбор
Число с фиксированной точкой
Примеры:
«N.M», «N.», «.M», «N»,
где
N – целая, а M – дробная часть числа.
Слайд 17
Посимвольный разбор
Число с фиксированной точкой
Граф переходов после минимизации:
Слайд 18
Посимвольный разбор
Число с фиксированной точкой
Таблица переходов ДКА:
Примечание: объединение
символов алфавита.
Слайд 19
Посимвольный разбор
Число с фиксированной точкой
Получили ДКА M =
(Q, Σ, δ, q0, F), где:
Q = {q0, q1,
q2, q3, q4};
Σ = {+, –, ., 0-9};
δ(Q×Σ) = {{q1, q2, q3, ERROR}, {ERROR, q2, q3, ERROR}, {ERROR, ERROR, q5, ERROR}, {ERROR, q4, q3, HALT}, {ERROR, ERROR, q4, HALT}};
F = {q3, q4}.
Слайд 20
Посимвольный разбор
Число с фиксированной точкой
Пример разбора цепочки «–15.2»:
(q0,
«–15.2⊥») 1 (q1, «15.2⊥»)
2 (q3, «5.2⊥»)
3 (q3, «.2⊥»)
4 (q4, «2⊥»)
5 (q4, «⊥»)
6 HALT
Разбор завершен успешно. Другой пример:
(q0, «.2.⊥») 1 (q2, «2.⊥»)
2 (q4, «.⊥»)
3 ERROR
Имеем синтаксическую ошибку в позиции 3.
Слайд 21
Посимвольный разбор
Число с фиксированной точкой
Ограничение количества значащих цифр:
Действия:
〈A1〉
– count := 1;
〈A2〉 – count := count +
1; если count > N, δ(q, a) = ERROR.
Слайд 22
Посимвольный разбор
Идентификатор в скобках
Примеры:
xyz, (((abc))), …
Слайд 23
Посимвольный разбор
Идентификатор в скобках
Таблица переходов ДМПА:
Убираем лишнее состояние:
Слайд 24
Посимвольный разбор
Идентификатор в скобках
Получили ДМПА P = (Q,
Σ, Γ, δ, q0, Z0, F), где:
Q = {q0,
q1, q2};
Σ = {(, ), _, a-z, A-Z, 0-9};
Γ = {(} ;
δ(Q×(Σ∪{e}∪{⊥})×Γ) = {{(q0, «(»), (q1, e), ERROR, ERROR, ERROR}, {ERROR, (q1, e), (q1, e), (q2, e), HALT}, {ERROR, ERROR, ERROR, (q2, e), HALT}};
Z0 = e;
F = {q1, q2}.
Слайд 25
Посимвольный разбор
Идентификатор в скобках
Пример разбора цепочки «((a123))»:
(q0, «((a123))⊥»,
e) 1 (q0, «(a123))⊥», «(»)
2 (q0, «a123))⊥», «((»)
3 (q1, «123))⊥», «((»)
4 (q1, «23))⊥», «((»)
5 (q1, «3))⊥», «((»)
6 (q1, «))⊥», «((»)
7 (q2, «)⊥», «(»)
8 (q2, «⊥», e)
9 HALT
Разбор завершен успешно.
Слайд 26
Посимвольный разбор
Идентификатор в скобках
Пример разбора цепочки «(x))»:
(q0, «(x))⊥»,
e) 1 (q0, «x))⊥»,
«(»)
2 (q1, «))⊥», «(»)
3 (q1, «)⊥», e)
4 ERROR
Имеем ошибку в позиции 4. Пример разбора цепочки «()»:
(q0, «()⊥», e) 1 (q0, «)⊥», «(»)
2 ERROR
Ошибка в позиции 2.
Слайд 27
Разбор по лексемам
Вложенные операторы
Язык L описывает вложенные операторы
языка Pascal «begin end;». Таблица переходов ДМПА при посимвольном
разборе:
Слайд 28
Разбор по лексемам
Вложенные операторы
Таблица переходов ДМПА при разборе
по лексемам:
Σ = {b, e, g, i, n, d,
«;», _} → Σ' = {begin, end, «;»}
Слайд 29
Разбор по лексемам
Вложенные операторы
Алфавит языка Σ делится на
три подмножества:
1. Подмножество символов-разделителей ΣS⊂Σ;
2. Подмножество символов пунктуации ΣP⊂Σ;
3.
Подмножество лексемных символов ΣL⊂Σ:
ΣL = Σ – (ΣS∪ΣP).
Алфавит Σ':
Σ'⊆ΣP∪ΣL+.
Лексема x – либо x∈ΣP, либо x∈ΣL+, отделенная от других лексем символами алфавитов ΣS и ΣP.
Слайд 30
Разбор по лексемам
Вложенные операторы
Пример:
begin
begin end ;
end;
begin
end;
1. begin
(1:1);
2. begin (2:3);
3. end (2:9);
4. ; (2:13);
5. end (3:1);
6.
; (3:4);
7. begin (4:1);
8. end (5:1);
9. ; (5:4).
Слайд 31
Разбор по лексемам
Вложенные операторы
Пример разбора:
(q0, «bbe;e;be;⊥»,
e) 1 (q0, «be;e;be;⊥», b)
2 (q0, «e;e;be;⊥», bb)
3 (q1, «;e;be;⊥», b)
4 (q0, «e;be;⊥», b)
5 (q1, «;be;⊥», e)
6 (q0, «be;⊥», e)
7 (q0, «e;⊥», b)
8 (q1, «;⊥», e)
9 (q0, «⊥», e)
10 HALT
Слайд 32
Разбор по лексемам
Вложенные операторы
Пример:
begin end;
end;
1. begin (1:1);
2. end
(1:7);
3. ; (1:10);
4. end (2:1);
5. ; (2:4);
(q0,
«be;e;⊥», e) 1 (q0, «e;e;⊥», b)
2 (q1, «;e;⊥», e)
3 (q0, «e;⊥», e)
4 ERROR
