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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

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

Введение

Для описания лексем используются регулярные выражения.

Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в том смысле что языки, ими порождаемые, будут совпадать.

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

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

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

  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 | ε)

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

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

Во всех фрагментах кода предполагается, что в начале первый символ уже считан в переменную ch. Предполагается также, что после работы участка алгоритма в переменную ch будет считан следующий символ для разбора следующей конструкции.

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


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

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

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

Правило. При разборе очередной конструкции первый символ уже должен быть считан с помощью NextCh.

// Разбор целого со знаком с помощью синтаксических диаграмм
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 char.IsDigit(ch) then
    NextCh
  else error;
 
  while char.IsDigit(ch) do
    NextCh;
 
  if ch<>#13 then
    error;
 
  writeln('Распознано целое число');
end.

Основные задания (5 баллов)

Реализовать программу на PascalABC.NET или C#.

Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем

  1. Реализовать в программе семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа). Семантические действия следует добавлять перед каждым вызовом NextCh кроме первого. (1 балл)
  2. Идентификатор. (1 балл)
  3. Целое со знаком, начинающееся не с цифры 0.(1 балл)
  4. Чередующиеся буквы и цифры, начинающиеся с буквы.(1 балл)
  5. Список букв, разделенных символом , или ; В качестве семантического действия должно быть накопление списка букв в списке и вывод этого списка в конце программы.(1 балл)

Дополнительные задания (5 баллов)

Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем

  1. Список цифр, разделенных одним или несколькими пробелами. В качестве семантического действия должно быть накопление списка цифр в списке и вывод этого списка в конце программы (1 балл).
  2. Лексема вида aa12c23dd1, в которой чередуются группы букв и цифр, в каждой группе не более 2 элементов. В качестве семантического действия необходимо накопить данную лексему в виде строки (1 балл).
  3. Вещественное с десятичной точкой 123.45678 (1 балл).
  4. Лексема вида 'строка', внутри апострофов отсутствует символ ' (1 балл).
  5. Лексема вида /*комментарий*/, внутри комментария не может встретиться последовательность символов */ (1 балл).

Дополнительные сложные задания

  1. Лексема вида Id1.Id2.Id3 (количество идентификаторов может быть произвольным).