Конечные автоматы и реализация распознавателей на их основе — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Программа 1 с таблицей переходов) |
Admin (обсуждение | вклад) (→Программа 1 с таблицей переходов) |
||
(не показано 12 промежуточных версий этого же участника) | |||
Строка 24: | Строка 24: | ||
// Состояния: | // Состояния: | ||
− | // | + | // S - начальное состояние |
// A - после знака | // A - после знака | ||
// B - после цифры | // B - после цифры | ||
− | // | + | // Fin - конечное состояние |
// Err - состояние ошибки | // Err - состояние ошибки | ||
Строка 37: | Строка 37: | ||
type | type | ||
− | States = ( | + | States = (S,A,B,Fin,Err); |
KindCh = (Digit, Sign, Eot, Unknown); | KindCh = (Digit, Sign, Eot, Unknown); | ||
Строка 50: | Строка 50: | ||
end; | end; | ||
− | var P: array [ | + | var P: array [S..B,Digit..Unknown] of States := |
((B, A, Err, Err), | ((B, A, Err, Err), | ||
(B, Err, Err, Err), | (B, Err, Err, Err), | ||
− | (B, Err, | + | (B, Err, Fin, Err)); |
procedure error(); | procedure error(); | ||
Строка 68: | Строка 68: | ||
read(ch); | read(ch); | ||
writeln('Состояния:'); | writeln('Состояния:'); | ||
− | while (State<> | + | while (State<>Fin) and (State<>Err) do |
begin | begin | ||
writeln(State); | writeln(State); | ||
Строка 76: | Строка 76: | ||
writeln(State); | writeln(State); | ||
end.</source> | end.</source> | ||
− | |||
− | |||
− | |||
====Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»==== | ====Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»==== | ||
+ | =====Общее===== | ||
+ | # Реализовать программу 1. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком. | ||
+ | # Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов" | ||
+ | # В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом | ||
+ | # Выдавать место ошибки в виде | ||
+ | +123+ | ||
+ | ^ | ||
+ | Знак + не может содержаться внутри целого | ||
− | + | =====Индивидуальные задания===== | |
− | |||
− | |||
# Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать. | # Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать. | ||
# Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать. | # Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать. | ||
Строка 91: | Строка 94: | ||
# Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать. | # Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать. | ||
# Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать. | # Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать. | ||
− | # | + | # Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки. |
+ | |||
+ | Для задания 7 | ||
+ | =====Граф автоматной грамматики идентификаторов===== | ||
+ | [[Изображение:Id.png|Граф автоматной грамматики идентификаторов]] |
Текущая версия на 10:19, 14 февраля 2013
Содержание
- 1 Основные определения
- 2 Тема 1. Конечные автоматы и реализация распознавателей на их основе
Основные определения
Тема 1. Конечные автоматы и реализация распознавателей на их основе
Правая автоматная грамматика для целого со знаком
Beg -> +A | -A | цB A -> цB B -> цB | ε
Граф автоматной грамматики для целого со знаком
Регулярное выражение для целого со знаком
(+|-|)ц+
Программа 1 с таблицей переходов
// Реализация конечного автомата таблицей
// Состояния:
// S - начальное состояние
// A - после знака
// B - после цифры
// Fin - конечное состояние
// Err - состояние ошибки
// Символы:
// Digit - встречена цифра
// Sign - встречен знак
// Eot - встречен конец текста
// Unknown - встречен неизвестный символ
type
States = (S,A,B,Fin,Err);
KindCh = (Digit, Sign, Eot, Unknown);
function Kind(ch: char): KindCh;
begin
case ch of
'0'..'9': Result := Digit;
'+','-': Result := Sign;
#13,#10: Result := Eot;
else Result := Unknown;
end;
end;
var P: array [S..B,Digit..Unknown] of States :=
((B, A, Err, Err),
(B, Err, Err, Err),
(B, Err, Fin, Err));
procedure error();
begin
writeln('error');
halt;
end;
var
ch: Char;
State: States := Beg;
begin
write('Введите целое со знаком: ');
read(ch);
writeln('Состояния:');
while (State<>Fin) and (State<>Err) do
begin
writeln(State);
State := P[State,Kind(ch)];
read(ch);
end;
writeln(State);
end.
Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»
Общее
- Реализовать программу 1. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком.
- Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов"
- В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом
- Выдавать место ошибки в виде
+123+ ^ Знак + не может содержаться внутри целого
Индивидуальные задания
- Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
- Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.
Для задания 7