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

[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]]

===Основные определения===
*[http://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE Иерархия грамматик Хомского]
*[http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8 Автоматная (регулярная) грамматика]
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 Конечный автомат]

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

=====Правая автоматная грамматика для целого со знаком=====
 Beg -> +A | -A | цB
 A -> цB
 B -> цB | ε

=====Граф автоматной грамматики для целого со знаком=====
[[Изображение:IntSigned.png|Граф автоматной грамматики целого со знаком]]

=====Регулярное выражение для целого со знаком=====
 '''(+|-|)ц+'''

=====Программа 1 с таблицей переходов=====
<source lang="Delphi">
// Реализация конечного автомата таблицей

// Состояния:
// 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.</source>

====Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»====
=====Общее=====
# Реализовать программу 1. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком. 
# Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов"
# В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом
# Выдавать место ошибки в виде 
 +123+
     ^
 Знак + не может содержаться внутри целого

=====Индивидуальные задания=====
# Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
# Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
# Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
# Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
# Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
# Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
# Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.

Для задания 7
=====Граф автоматной грамматики идентификаторов=====
[[Изображение:Id.png|Граф автоматной грамматики идентификаторов]]