Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе
Содержание
Введение
Для описания лексем используются регулярные выражения.
Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в том смысле что языки, ими порождаемые, будут совпадать.
Автоматная грамматика легко переводится на язык синтаксических диаграмм.
Основные обозначения в регулярных выражениях
Регулярное выражение над алфавитом Σ - это
- a - отдельный символ из алфавита Σ
- ε - пустая цепочка
- Если R и Q - регулярные выражения, то RQ - регулярное выражение, являющееся конкатенацией цепочек, порождаемых R и Q
- Если R и Q - регулярные выражения, то R | Q - регулярное выражение, являющееся цепочкой, порождаемой либо R, либо Q
- Если R - регулярное выражение, то R* - повторение R ноль и более раз
- Если R - регулярное выражение, то R+ - повторение R один и более раз. Очевидно, что R+ = RR*
- Если R - регулярное выражение, то (R) - такое же регулярное выражение
Примеры регулярных выражений
Целое со знаком:
(+|-|)ц+
Идентификатор:
б(б|ц)*
Альтернативные обозначения в регулярных выражениях
- {R} = R*
- [R] = (R | ε)
В этом случае * и + не используются
Таблица соответствия регулярных выражений и автоматных грамматик
Во всех фрагментах кода предполагается, что в начале первый символ уже считан в переменную ch. Предполагается также, что после работы участка алгоритма в переменную ch будет считан следующий символ для разбора следующей конструкции.
Синтаксическая диаграмма для целого со знаком
Программа распознавания целого со знаком по синтаксической диаграмме
Правило. При разборе очередной конструкции первый символ уже должен быть считан с помощью 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#.
Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем
- Реализовать в программе семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа). Семантические действия следует добавлять перед каждым вызовом NextCh кроме первого. (1 балл)
- Идентификатор. (1 балл)
- Целое со знаком, начинающееся не с цифры 0.(1 балл)
- Чередующиеся буквы и цифры, начинающиеся с буквы.(1 балл)
- Список букв, разделенных символом , или ; В качестве семантического действия должно быть накопление списка букв в списке и вывод этого списка в конце программы.(1 балл)
Дополнительные задания (5 баллов)
Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем
- Список цифр, разделенных одним или несколькими пробелами. В качестве семантического действия должно быть накопление списка цифр в списке и вывод этого списка в конце программы (1 балл).
- Лексема вида aa12c23dd1, в которой чередуются группы букв и цифр, в каждой группе не более 2 элементов. В качестве семантического действия необходимо накопить данную лексему в виде строки (1 балл).
- Вещественное с десятичной точкой 123.45678 (1 балл).
- Лексема вида 'строка', внутри апострофов отсутствует символ ' (1 балл).
- Лексема вида /*комментарий*/, внутри комментария не может встретиться последовательность символов */ (1 балл).
Дополнительные сложные задания
- Лексема вида Id1.Id2.Id3 (количество идентификаторов может быть произвольным).