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

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

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

Эквивалентность регулярных выражений и автоматных грамматик

• Автоматная грамматика порождает автоматный язык
• Регулярное выражение порождает регулярное множество
• Автоматный язык является регулярным множеством и наоборот. Поэтому для любо автоматной грамматики можно записать эквивалентное регулярное выражение (языки, ими порождаемые, будут совпадать). Наоборот, для любого регулярного выражения можно построить эквивалентную автоматную грамматику.
• Автоматная грамматика легко переводится на язык синтаксических диаграмм.

Основные обозначения в регулярных выражениях

Регулярное выражение над алфавитом Σ - это

1. a - отдельный символ
2. ε - пустая цепочка
3. Если R и Q - регулярные выражения, то RQ - регулярное выражение, являющееся конкатенацией цепочек, порождаемых R и Q
4. Если R и Q - регулярные выражения, то R | Q - регулярное выражение, являющееся цепочкой, порождаемой либо R, либо Q
5. Если R - регулярное выражение, то R* - повторение R ноль и более раз
6. Если R - регулярное выражение, то R+ - повторение R один и более раз. Очевидно, что R+ = RR*
7. Если R - регулярное выражение, то (R) - такое же регулярное выражение

Примеры

Целое со знаком:

(+|-|)ц+

Идентификатор:

б(б|ц)*

Альтернативные обозначения в регулярных выражениях

• {R} = R*
• [R] = (R | ε)

В этом случае * и + не используются

Таблица соответствия регулярных выражений и автоматных грамматик

Фрагмент выражения	Участок синтаксической диаграммы	Фрагмент кода
R		if ch = R then NextCh else error;
ε
RQ		if ch = R then NextCh else error; if ch = Q then NextCh else error;
R ! Q		if ch in [R,Q] then NextCh else error;
R*		if ch = R then NextCh else error; while ch = R do NextCh;
R+
(R)

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

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

// Разбор целого со знаком с помощью синтаксических диаграмм
var 
  ch: Char;
  pos: integer;

procedure error();
begin
  writeln('^':pos);
  writeln('Ошибка в символе ',ch);
  halt;
end;
 
procedure NextCh;
begin
  read(ch);
  pos += 1;  
end; 
 
begin
  NextCh;
  if ch in ['+','-'] then
    NextCh;
 
  if ch in ['0'..'9'] then
    NextCh
  else error;
 
  while ch in ['0'..'9'] do
    NextCh;
 
  if ch<>#13 then
    error;
 
  writeln('Распознано целое число');
end.

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

1. Реализовать программу 2
2. Реализовать в программе 2 семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа)
3. Составить синтаксическую диаграмму идентификатора. Реализовать по ней распознаватель.
4. Составить синтаксическую диаграмму для целого со знаком, начинающегося не с цифры 0. Реализовать распознаватель. Оттестировать.
5. Составить синтаксическую диаграмму для чередующихся букв и цифр. Реализовать распознаватель. Оттестировать.
6. Составить синтаксическую диаграмму для списка букв, разделенных символом , или ;. Реализовать распознаватель. Оттестировать.
7. Составить синтаксическую диаграмму для списка цифр, разделенных одним или несколькими пробелами. Реализовать распознаватель. Оттестировать.
8. Составить синтаксическую диаграмму для выражения вида 1+2-3-4+5. Реализовать распознаватель. Оттестировать.
9. Составить синтаксическую диаграмму для вещественного с десятичной точкой 123.45678. Реализовать распознаватель. Оттестировать.
10. Составить синтаксическую диаграмму для выражения вида 1234*567, где вместо знака * может стоять знак операции +, -, /, div или mod. Реализовать распознаватель. Оттестировать.
11. Составить синтаксическую диаграмму для выражения вида Id1.Id2.Id3 (количество точек между идентификаторами может быть произвольным). Реализовать распознаватель. Оттестировать.