Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе
Содержание
- 1 Введение
- 2 Основные обозначения в регулярных выражениях
- 3 Альтернативные обозначения в регулярных выражениях
- 4 Таблица соответствия регулярных выражений и автоматных грамматик
- 5 Задания к теме 2 «Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе»
- 6 Дополнительные задания
- 7 Дополнительные сложные задания
Введение
Для описания лексем используются регулярные выражения.
Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в том смысле что языки, ими порождаемые, будут совпадать.
Автоматная грамматика легко переводится на язык синтаксических диаграмм.
Основные обозначения в регулярных выражениях
Регулярное выражение над алфавитом Σ - это
- 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 будет считан следующий символ для разбора следующей конструкции.
Синтаксическая диаграмма для целого со знаком
Программа 2 распознавания целого со знаком по синтаксической диаграмме
Правило. При разборе очередной конструкции первый символ уже должен быть считан с помощью 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.
Задания к теме 2 «Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе»
- Реализовать программу 2 на PascalABC.NET или C#.
- Реализовать в программе 2 семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа). Семантические действия следует добавлять перед каждым вызовом NextCh кроме первого.
Дополнительные задания
Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем
- Идентификатор.
- Целое со знаком, начинающееся не с цифры 0.
- Чередующиеся буквы и цифры, начинающиеся с буквы.
- Список букв, разделенных символом , или ; В качестве семантического действия должно быть накопление списка букв в списке и вывод этого списка в конце программы.
- Список цифр, разделенных одним или несколькими пробелами. В качестве семантического действия должно быть накопление списка цифр в списке и вывод этого списка в конце программы.
- Лексема вида aa12c23dd1, в которой чередуются группы букв и цифр, в каждой группе не более 2 элементов. В качестве семантического действия необходимо накопить данную лексему в виде строки.
- Вещественное с десятичной точкой 123.45678.
- Лексема вида 'строка', внутри апострофов отсутствует символ '
- Лексема вида /*комментарий*/, внутри комментария не может встретиться последовательность символов */
Дополнительные сложные задания
- Лексема вида Id1.Id2.Id3 (количество идентификаторов может быть произвольным).