Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе
Материал из Вики ИТ мехмата ЮФУ
Версия от 10:43, 29 февраля 2012; Admin (обсуждение | вклад) (→Таблица соответствия регулярных выражений и автоматных грамматик)
Содержание
- 1 Тема 2. Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе
- 1.1 Эквивалентность регулярных выражений и автоматных грамматик
- 1.2 Основные обозначения в регулярных выражениях
- 1.3 Альтернативные обозначения в регулярных выражениях
- 1.4 Таблица соответствия регулярных выражений и автоматных грамматик
- 1.5 Задания к теме 2 «Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе»
Тема 2. Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе
Эквивалентность регулярных выражений и автоматных грамматик
- Автоматная грамматика порождает автоматный язык
- Регулярное выражение порождает регулярное множество
- Автоматный язык является регулярным множеством и наоборот. Поэтому для любо автоматной грамматики можно записать эквивалентное регулярное выражение (языки, ими порождаемые, будут совпадать). Наоборот, для любого регулярного выражения можно построить эквивалентную автоматную грамматику.
- Автоматная грамматика легко переводится на язык синтаксических диаграмм.
Основные обозначения в регулярных выражениях
Регулярное выражение над алфавитом Σ - это
- 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 | ε)
В этом случае * и + не используются
Таблица соответствия регулярных выражений и автоматных грамматик
Фрагмент выражения | Участок синтаксической диаграммы | Фрагмент кода |
R | ||
ε | ||
RQ | ||
R ! Q | ||
R* | ||
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 «Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе»
- Реализовать программу 2
- Реализовать в программе 2 семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа)
- Составить синтаксическую диаграмму идентификатора. Реализовать по ней распознаватель.
- Составить синтаксическую диаграмму для целого со знаком, начинающегося не с цифры 0. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для чередующихся букв и цифр. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для списка букв, разделенных символом , или ;. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для списка цифр, разделенных одним или несколькими пробелами. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для выражения вида 1+2-3-4+5. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для вещественного с десятичной точкой 123.45678. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для выражения вида 1234*567, где вместо знака * может стоять знак операции +, -, /, div или mod. Реализовать распознаватель. Оттестировать.
- Составить синтаксическую диаграмму для выражения вида Id1.Id2.Id3 (количество точек между идентификаторами может быть произвольным). Реализовать распознаватель. Оттестировать.