Программа реализации конечного автомата, распознающего целое число

К основной странице курса

Основные определения

• Иерархия грамматик Хомского
• Автоматная грамматика
• Конечный автомат
• Синтаксическая диаграмма
• Регулярные выражения

Тема 1. Конечные автоматы и реализация распознавателей на их основе

Автоматная грамматика для целого со знаком

Beg -> +A | -A | цB
A -> цB
B -> цB | ε

Граф автоматной грамматики для целого со знаком

Регулярное выражение для целого со знаком

(+|-|)ц+

Программа 1 с таблицей переходов

// Реализация конечного автомата таблицей
// Beg     - начальное состояние
// A       - после знака
// B       - после цифры
// En      - конечное состояние
// Err     - состояние ошибки
// Digit   - встречена цифра
// Sign    - встречен знак
// Eot     - встречен конец текста
// Unknown - встречен неизвестный символ

type
  States = (Beg,A,B,En,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 [Beg..B,Digit..Unknown] of States :=
  ((B, A, Err, Err),
   (B, Err, Err, Err),
   (B, Err, En, Err));

procedure error();
begin
  writeln('error');
  halt;
end;

var 
  ch: Char;
  State: States := Beg;
begin
  read(ch);
  while (State<>En) and (State<>Err) do
  begin
    writeln(State);
    State := P[State,Kind(ch)];
    read(ch);
  end;
  writeln(State);
end.

Граф автоматной грамматики идентификаторов

Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе».

1. Реализовать программу 1. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком.Сделать все варианты ошибок.
2. Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов"
3. Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.
4. Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
5. Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
6. Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
7. Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
8. Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
9. Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
10. В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом

Тема 2. Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе

Синтаксическая диаграмма для целого со знаком

Программа 2 распознавания целого со знаком по синтаксической диаграмме

// Вместо таблицы - условные операторы
procedure error();
begin
  writeln('error');
  halt;
end;

var ch: Char;

begin
  var s: string := '';

  read(ch);
  if ch in ['+','-'] then
    read(ch);
    
  if ch in ['0'..'9'] then
    read(ch)
  else error;
  
  while ch in ['0'..'9'] do
    read(ch);
  
  if ch<>#13 then
    error;
    
  writeln('Распознано целое число');
end.

Задания к теме 2 «Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе»

1. Реализовать программу 2
2. Реализовать в программе 2 семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа)
3. Построить автоматную грамматику для идентификаторов.
4. По данной грамматике построить граф грамматики, представляющий ДКА, и реализовать анализатор с помощью таблицы
5. Преобразовать граф грамматики в синтаксическую диаграмму и построить программу разбора без использования таблицы
6. Построить автоматную грамматику для распознавания вещесивенных и синтаксическую диаграмму для нее