ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.04.2021
Просмотров: 508
Скачиваний: 2
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
6
Лабораторная
работа
№
1
Создание
простейшего
распознавателя
Цель
работы
Активировать
имеющиеся
навыки
программирования
,
приобрести
навыки
автоматного
программирования
,
получить
практический
опыт
построения
простейших
распознавателей
(
лексических
анализаторов
).
Содержание
работы
Построение
распознавателя
комментариев
языков
C
и
C++
с
использованием
автоматной
модели
.
Задание
1.
Построить
детерминированный
конечный
автомат
распознавателя
многострочных
комментариев
языка
C
и
выполнить
его
программную
реализацию
.
2.
Усовершенствовать
распознаватель
для
корректного
удаления
комментариев
языков
C
(
многострочных
)
и
C++ (
однострочных
).
Методические
рекомендации
к
заданию
В
соответствии
с
п
.1
Задания
,
распознаватель
должен
,
проведя
лексический
анализ
входного
файла
,
содержащего
текст
программы
на
языке
C,
сформировать
выходной
(
новый
)
файл
,
содержащий
тот
же
текст
,
но
с
удаленными
из
него
комментариями
вида
/*...*/
.
Рассматриваются
только
комментарии
языка
C
и
не
производится
анализ
каких
-
либо
иных
лексем
.
Следует
учесть
,
что
такие
комментарии
не
могут
быть
вложенными
.
Конечный
автомат
распознавателя
проще
всего
представить
в
виде
традиционного
графа
(
диаграммы
)
состояний
,
в
котором
состояния
представлены
узлами
,
а
переходы
–
дугами
.
Условием
перехода
из
одного
состояния
в
другое
(
событием
,
входным
сигналом
)
является
значение
одного
очередного
символа
,
считанного
из
входного
потока
.
При
любом
переходе
из
одного
состояния
в
другое
может
производиться
запись
в
выходной
поток
как
последнего
считанного
символа
,
так
и
произвольного
символа
или
любой
цепочки
символов
.
Таким
образом
,
каждая
дуга
в
графе
должна
быть
маркирована
и
входным
символом
a
,
и
выходной
цепочкой
символов
γ
,
т
.
е
.
записью
вида
«
a
/
γ
».
При
этом
для
компактной
и
наглядной
записи
выражений
допускается
:
–
указывать
допустимые
символы
входной
цепочки
в
виде
множества
,
например
,
запись
«{
a
,
b
,
c
,
0..9
} / …»
будет
означать
принадлежность
считанного
символа
указанному
множеству
,
т
.
е
.
его
равенство
одному
из
элементов
этого
множества
;
–
использовать
некоторое
обозначение
или
метасимвол
для
входного
символа
в
записи
условия
,
например
,
запись
«
c
∉
{
0..9
} / …»
будет
означать
,
что
считанный
символ
не
является
десятичной
цифрой
(
является
любым
другим
возможным
символом
);
–
использовать
некоторое
обозначение
для
особых
(
типичных
)
ситуаций
,
например
«
else
», «
default
»
и
т
.
п
.
для
обозначения
всех
остальных
случаев
,
т
.
е
.
образованных
исключением
из
алфавита
языка
(
полного
множества
возможных
входных
символов
)
всех
тех
символов
,
которые
указаны
в
условиях
перехода
всех
остальных
дуг
,
исходящих
из
этого
же
состояния
;
–
использовать
квантор
∀
,
если
переход
осуществляется
при
чтении
любого
возможного
символа
(
немаркированная
дуга
означает
безусловный
переход
из
одного
состояния
в
другое
,
при
котором
чтение
очередного
символа
не
производится
);
–
использовать
некоторое
обозначение
или
метасимвол
для
обозначения
конца
входной
цепочки
(
при
реализации
программы
–
конца
файла
),
например
«
EOF
», «
⊥
»
и
т
.
п
.;
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
7
–
использовать
некоторое
обозначение
или
метасимвол
для
обозначения
множества
пустых
символов
–
символов
-
разделителей
, –
таких
как
пробел
,
перевод
строки
,
возврат
каретки
,
табуляция
и
т
.
п
.,
например
«
B
», «
blank
», « »
и
т
.
п
.;
–
не
указывать
выходную
цепочку
вместе
с
символом
«/»
или
указывать
«… /
λ
»,
если
при
данном
переходе
ничего
не
выводится
в
выходной
поток
;
–
использовать
некоторое
обозначение
для
входного
символа
при
его
выводе
в
выходной
поток
,
например
: «
c
∈
{
0..9
} /
c
» –
символы
входного
потока
,
являющиеся
цифрами
,
дублируются
в
выходной
поток
; «
∀
c
/
c
» –
дублирование
любого
считанного
символа
в
выходной
поток
.
Для
построения
распознавателя
необходим
детерминированный
и
полностью
определенный
конечный
автомат
.
Это
означает
,
что
в
каждом
состоянии
для
каждого
возможного
входного
символа
должен
быть
определен
ровно
один
переход
.
Конечный
автомат
распознавателя
будет
являться
недетерминированным
,
если
хотя
бы
в
одном
состоянии
некоторый
считанный
символ
приводит
к
одновременному
выбору
двух
или
более
направлений
перехода
,
что
невозможно
реализовать
без
использования
параллельных
процессов
,
рекурсии
и
/
или
последующего
обратного
движения
по
входной
цепочке
(
возврата
).
Конечный
автомат
распознавателя
будет
являться
определенным
не
полностью
или
недоопределенным
,
если
хотя
бы
в
одном
состоянии
существует
хотя
бы
один
входной
символ
из
множества
возможных
,
для
которого
не
задан
переход
,
что
приведет
к
неразрешимой
ситуации
при
реализации
распознавателя
.
По
этой
причине
необходимо
ввести
конец
файла
как
входной
символ
.
После
реализации
простейшего
лексического
анализатора
в
соответствии
с
п
.1
Задания
необходимо
оценить
его
адекватность
.
При
выполнении
п
.2
Задания
в
первую
очередь
следует
уточнить
диаграмму
состояний
распознавателя
для
многострочных
и
однострочных
комментариев
.
При
этом
необходимо
учесть
все
особенности
комментариев
и
некоторых
других
лексем
языка
C++,
в
частности
:
–
многострочные
комментарии
не
могут
быть
вложенными
;
–
многострочный
комментарий
может
использоваться
вместо
символа
-
разделителя
и
его
удаление
не
должно
приводить
к
«
склеиванию
»
лексем
и
их
неправильной
интерпретации
транслятором
;
–
окончанию
«
*/
»
многострочного
комментария
может
предшествовать
символ
«
*
»
в
любом
количестве
;
–
комментарии
не
могут
являться
частью
строковой
или
символьной
константы
(
начинаться
или
заканчиваться
внутри
нее
–
комментарии
не
должны
распознаваться
внутри
строковых
и
символьных
констант
,
а
строковые
и
символьные
константы
не
должны
распознаваться
внутри
комментариев
);
–
строковые
и
символьные
константы
могут
включать
в
себя
как
символы
одинарную
и
двойную
кавычки
в
виде
последовательностей
«
\'
»
и
«
\"
»,
которые
не
являются
завершением
записи
константы
,
а
также
любые
управляющие
последовательности
,
запись
которых
начинается
с
символа
«
\
»);
–
строковая
константа
может
занимать
несколько
строк
в
исходном
тексте
программы
;
–
любой
из
символов
перевода
строки
или
возврата
каретки
(«\r»
или
«\n»)
завершают
однострочный
комментарий
,
при
этом
они
являются
равнозначными
и
сохраняются
в
выходной
поток
.
Общий
вид
автомата
,
соответствующего
этим
требованиям
,
будет
следующим
(
конечное
состояние
,
соответствующее
концу
входного
потока
,
и
ведущие
в
него
дуги
не
изображены
):
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
8
На
данной
диаграмме
видно
,
что
переход
между
состояниями
,
которые
находятся
в
частях
автомата
,
соответствующих
распознаванию
комментариев
,
строковых
и
символьных
констант
,
невозможен
,
т
.
е
.
эти
конструкции
не
могут
перекрываться
или
быть
вложенными
друг
в
друга
.
При
реализации
необходимо
обеспечить
корректное
завершение
программы
(
запись
символов
,
закрытие
файлов
и
т
.
п
.)
при
обнаружении
конца
входного
файла
в
любом
состоянии
автомата
.
Фрагмент
возможной
реализации
(
упрощенный
)
лексического
анализатора
на
языке
С
с
использованием
стандартных
библиотек
показан
ниже
.
typedef enum States { Normal, Slash, Comment, ... } States;
/*
перечисление
всех
состояний
автомата
*/
int main(int argc, char ** argv)
{
FILE * fi, * fo; /*
входной
и
выходной
файл
*/
States State = Normal; /*
текущее
состояние
*/
int c; /*
считанный
символ
(
только
один
текущий
!) */
fi = fopen(argv[1], "rb");
if (!fi)
{
fprintf(stderr, "Input file \"%s\" open error.\n", argv[1]);
return 1;
}
fo = fopen(argv[2], "wb");
if (!fo)
{
fclose(fi);
fprintf(stderr, "Output file \"%s\" open error.\n", argv[2]);
return 2;
}
while ((c=fgetc(fi)) != EOF) /*
считываем
символ
и
проверяем
, */
{ /*
не
конец
ли
файла
*/
switch (State) /*
обрабатываем
считанный
символ
в
*/
{ /*
зависимости
от
текущего
состояния
*/
case Normal:
if (c == '/') /*
если
встретили
слэш
, */
State = Slash; /*
то
перешли
в
соответствующее
состояние
*/
else if (
с
== ...) /*
если
еще
что
-
то
,
то
аналогично
*/
State = ...; /*
и
т
.
д
. */
...
else
fputc(c, fo); /*
дублируем
считанный
символ
*/
break; /*
в
выходной
поток
*/
Распознавание
комментариев
Распознавание
строковых
литералов
Распознавание
символьных
констант
N
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
9
case Slash: /*
если
предыдущим
был
слэш
,
то
... */
if (c == '*')
State = Comment;
else
State = Normal;
break;
... /*
и
т
.
д
.
обрабатываем
все
состояния
автомата
*/
}
}
fclose(fi); /*
не
забывайте
закрывать
файлы
! */
fclose(fo); /*
особенно
выходной
,
т
.
к
.
он
был
открыт
для
записи
*/
return 0;
}
В
отчете
по
лабораторной
работе
должны
быть
полностью
отражены
оба
варианта
распознавателя
(
по
каждому
пункту
задания
).
Основная
часть
должна
содержать
графы
состояний
разработанных
конечных
автоматов
и
протоколы
работы
лексических
анализаторов
.
В
выводах
по
работе
необходимо
привести
оценку
адекватности
разработанных
лексических
анализаторов
.
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
10
Лабораторная
работа
№
2
Распознаватель
числовых
констант
Цель
работы
Получить
практический
опыт
использования
нормальной
формы
Бэкуса
-
Наура
для
формального
описания
регулярных
языков
и
построения
лексических
анализаторов
на
основе
порождающих
грамматик
,
закрепить
навыки
автоматного
программирования
.
Содержание
работы
Построение
распознавателя
числовых
констант
языков
C
и
C++
с
использованием
нормальной
формы
Бэкуса
–
Наура
и
детерминированных
конечных
автоматов
,
используя
в
качестве
основы
распознаватель
комментариев
,
созданный
в
лабораторной
работе
№
1.
Задание
1.
Определить
грамматику
,
порождающую
цепочки
,
соответствующие
записи
числовых
констант
языков
C/C++,
используя
нормальную
форму
Бэкуса
–
Наура
.
2.
Построить
конечный
автомат
лексического
анализатора
этих
цепочек
.
3.
Реализовать
синтаксический
анализатор
на
основе
разработанного
конечного
автомата
.
Методические
рекомендации
В
первую
очередь
необходимо
формализовать
предметную
область
с
использованием
естественного
языка
,
т
.
е
.
определить
множество
типов
данных
в
соответствии
с
вариантом
индивидуального
задания
и
возможные
способы
записи
констант
этих
типов
.
При
этом
можно
также
использовать
метасимволы
,
регулярные
выражения
,
синтаксические
диаграммы
Вирта
и
другие
нотации
для
наглядного
представления
синтаксиса
.
Необходимо
учесть
,
что
могут
существовать
различные
способы
записи
констант
для
одних
и
тех
же
значений
,
и
возможное
наличие
символов
-
модификаторов
,
уточняющих
тип
константы
.
Особое
внимание
следует
обратить
на
необязательные
части
в
записи
константы
(
например
,
знак
числа
,
дробная
часть
,
символ
-
модификатор
и
др
.).
В
соответствии
с
формализованным
описанием
необходимо
построить
грамматику
,
порождающую
заданные
константы
,
в
нормальной
форме
Бэкуса
–
Наура
.
Учитывая
,
что
язык
заданных
лексем
является
регулярным
,
желательно
также
использовать
регулярную
(
лево
-
или
праволинейную
)
грамматику
,
или
даже
привести
ее
к
виду
автоматной
грамматики
,
что
упростит
в
дальнейшем
построение
конечного
автомата
и
реализацию
лексического
анализатора
.
В
записи
правил
грамматики
можно
использовать
метасимвол
«|»
для
компактной
записи
правых
частей
правил
,
но
не
допускается
использование
других
метасимволов
расширений
нотации
Бэкуса
–
Наура
и
регулярных
выражений
.
Построенная
грамматика
(
с
целью
упрощения
)
не
должна
порождать
комментарии
,
символьные
константы
и
строковые
литералы
,
а
также
числовые
константы
,
не
принадлежащие
группе
типов
данных
,
заданной
вариантом
индивидуального
задания
.
В
соответствии
с
построенной
грамматикой
необходимо
определить
конечный
автомат
,
который
должен
идентифицировать
успешное
распознавание
цепочки
,
ошибки
распознавания
и
пропуск
непринятых
цепочек
.
Автомат
не
должен
принимать
числовые
константы
тех
типов
,
которые
не
соответствуют
варианту
индивидуального
задания
–
в
этих
случаях
должна
идентифицироваться
ошибка
распознавания
или
осуществляться
пропуск
цепочек
(
их
игнорирование
без
попытки
начать
распознавание
).
Например
,
считав
из
входного
потока
цепочку
«123.»,
распознаватель
вещественных
констант
продолжит
чтение
и
анализ
символов
,
а
распознаватель
целочисленных
–
выдаст
ошибку