Синтаксические диаграммы автоматных языков и реализация распознавателей на их основе — различия между версиями
Admin (обсуждение | вклад) (→Таблица соответствия регулярных выражений и автоматных грамматик) |
Admin (обсуждение | вклад) (→Дополнительные задания (5 баллов)) |
||
(не показаны 34 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]] | [[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]] | ||
− | === | + | ====Введение==== |
− | = | + | Для описания лексем используются регулярные выражения. |
− | + | ||
− | + | Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в | |
− | + | том смысле что языки, ими порождаемые, будут совпадать. | |
− | + | ||
+ | Автоматная грамматика легко переводится на язык синтаксических диаграмм. | ||
====Основные обозначения в регулярных выражениях==== | ====Основные обозначения в регулярных выражениях==== | ||
Регулярное выражение над алфавитом Σ - это | Регулярное выражение над алфавитом Σ - это | ||
− | # a - отдельный символ | + | # a - отдельный символ из алфавита Σ |
# ε - пустая цепочка | # ε - пустая цепочка | ||
# Если R и Q - регулярные выражения, то RQ - регулярное выражение, являющееся конкатенацией цепочек, порождаемых R и Q | # Если R и Q - регулярные выражения, то RQ - регулярное выражение, являющееся конкатенацией цепочек, порождаемых R и Q | ||
Строка 18: | Строка 19: | ||
# Если R - регулярное выражение, то (R) - такое же регулярное выражение | # Если R - регулярное выражение, то (R) - такое же регулярное выражение | ||
− | =====Примеры===== | + | =====Примеры регулярных выражений===== |
Целое со знаком: | Целое со знаком: | ||
(+|-|)ц+ | (+|-|)ц+ | ||
Строка 32: | Строка 33: | ||
====Таблица соответствия регулярных выражений и автоматных грамматик==== | ====Таблица соответствия регулярных выражений и автоматных грамматик==== | ||
+ | Во всех фрагментах кода предполагается, что в начале первый символ уже считан в переменную ch. Предполагается также, что после работы участка алгоритма в переменную ch будет считан следующий символ для разбора следующей конструкции. | ||
{| border="1" cellpadding = "10" | {| border="1" cellpadding = "10" | ||
| '''Фрагмент выражения''' || '''Участок синтаксической диаграммы'''|| '''Фрагмент кода''' | | '''Фрагмент выражения''' || '''Участок синтаксической диаграммы'''|| '''Фрагмент кода''' | ||
|- | |- | ||
− | | R || [[Изображение:R.png]] || <source lang="Pascal">if ch = R then NextCh | + | | R || [[Изображение:R.png]] || <source lang="Pascal">if ch = R then |
− | + | NextCh | |
+ | else error;</source> | ||
|- | |- | ||
| ε || [[Изображение:eps.png]] || | | ε || [[Изображение:eps.png]] || | ||
|- | |- | ||
− | | RQ || [[Изображение:RandQ.png]] || <source lang="Pascal">if ch = R then NextCh | + | | R ! ε || [[Изображение:Roreps.png]] || <source lang="Pascal">if ch = R then |
− | + | NextCh;</source> | |
− | if ch = Q then NextCh | + | |- |
− | + | | RQ || [[Изображение:RandQ.png]] || <source lang="Pascal">if ch = R then | |
+ | NextCh | ||
+ | else error; | ||
+ | if ch = Q then | ||
+ | NextCh | ||
+ | else error;</source> | ||
|- | |- | ||
| R ! Q || [[Изображение:RorQ.png]] || <source lang="Pascal">if ch in [R,Q] then NextCh | | R ! Q || [[Изображение:RorQ.png]] || <source lang="Pascal">if ch in [R,Q] then NextCh | ||
else error;</source> | else error;</source> | ||
|- | |- | ||
− | | R | + | | R+ || [[Изображение:Rstar.png]] || <source lang="Pascal">if ch = R then |
− | + | NextCh | |
+ | else error; | ||
while ch = R do | while ch = R do | ||
NextCh;</source> | NextCh;</source> | ||
|- | |- | ||
− | | R | + | | R* || [[Изображение:Rplus.png]] || <source lang="Pascal">while ch = R do |
+ | NextCh;</source> | ||
|- | |- | ||
| (R) || || | | (R) || || | ||
Строка 62: | Строка 72: | ||
[[Изображение:SyntNum.png|300px|Синтаксическая диаграмма целого со знаком]] | [[Изображение:SyntNum.png|300px|Синтаксическая диаграмма целого со знаком]] | ||
− | =====Программа | + | =====Программа распознавания целого со знаком по синтаксической диаграмме===== |
+ | |||
+ | '''Правило.''' При разборе очередной конструкции первый символ уже должен быть считан с помощью NextCh. | ||
+ | |||
<source lang="Delphi">// Разбор целого со знаком с помощью синтаксических диаграмм | <source lang="Delphi">// Разбор целого со знаком с помощью синтаксических диаграмм | ||
var | var | ||
Строка 86: | Строка 99: | ||
NextCh; | NextCh; | ||
− | if ch | + | if char.IsDigit(ch) then |
NextCh | NextCh | ||
else error; | else error; | ||
− | while ch | + | while char.IsDigit(ch) do |
NextCh; | NextCh; | ||
Строка 99: | Строка 112: | ||
end.</source> | end.</source> | ||
− | ==== | + | ====Основные задания (5 баллов)==== |
− | + | Реализовать программу на PascalABC.NET или C#. | |
− | # Реализовать в программе | + | |
− | # | + | Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем |
− | # | + | |
− | # | + | # Реализовать в программе семантические действия по накоплению в строке распознанного целого числа и преобразованию его в целое в конце разбора (при встрече завершающего символа). Семантические действия следует добавлять перед каждым вызовом NextCh кроме первого. (1 балл) |
− | # | + | # Идентификатор. (1 балл) |
− | + | # Целое со знаком, начинающееся не с цифры 0.(1 балл) | |
− | # | + | # Чередующиеся буквы и цифры, начинающиеся с буквы.(1 балл) |
− | # | + | # Список букв, разделенных символом , или ; В качестве семантического действия должно быть накопление списка букв в списке и вывод этого списка в конце программы.(1 балл) |
− | # | + | |
− | # | + | ====Дополнительные задания (5 баллов) ==== |
+ | Составить синтаксическую диаграмму, реализовать по ней распознаватель и выполнить указанные семантические действия для следующих лексем | ||
+ | |||
+ | # Список цифр, разделенных одним или несколькими пробелами. В качестве семантического действия должно быть накопление списка цифр в списке и вывод этого списка в конце программы (1 балл). | ||
+ | # Лексема вида aa12c23dd1, в которой чередуются группы букв и цифр, в каждой группе не более 2 элементов. В качестве семантического действия необходимо накопить данную лексему в виде строки (1 балл). | ||
+ | # Вещественное с десятичной точкой 123.45678 (1 балл). | ||
+ | # Лексема вида 'строка', внутри апострофов отсутствует символ ' (1 балл). | ||
+ | # Лексема вида /*комментарий*/, внутри комментария не может встретиться последовательность символов */ (1 балл). | ||
+ | |||
+ | ==== Дополнительные сложные задания ==== | ||
+ | # Лексема вида Id1.Id2.Id3 (количество идентификаторов может быть произвольным). |
Текущая версия на 11:27, 4 декабря 2015
Содержание
Введение
Для описания лексем используются регулярные выражения.
Регулярные выражения тесно связаны с автоматными грамматиками: по любой автоматной грамматике можно записать эквивалентное ей регулярное выражение и наоборот. Эквивалентность понимается в том смысле что языки, ими порождаемые, будут совпадать.
Автоматная грамматика легко переводится на язык синтаксических диаграмм.
Основные обозначения в регулярных выражениях
Регулярное выражение над алфавитом Σ - это
- 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 (количество идентификаторов может быть произвольным).