ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.04.2021
Просмотров: 504
Скачиваний: 2
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
11
(
символ
«
точка
»
не
может
присутствовать
в
записи
этих
констант
)
и
перейдет
в
некоторое
исходное
состояние
,
ожидая
начала
следующей
подходящей
цепочки
во
входном
потоке
.
Цепочка
«123»,
если
за
ней
следует
не
алфавитно
-
цифровой
символ
(
например
,
пробел
),
будет
принята
как
константа
типа
int
и
не
будет
принята
распознавателем
вещественных
констант
,
так
как
лексема
закончилась
,
но
она
не
содержит
признаков
константы
вещественного
типа
(
десятичной
точки
или
символа
«e»).
Цепочка
«a123»
будет
просто
проигнорирована
обоими
автоматами
,
т
.
к
.
никакая
числовая
константа
не
может
начинаться
с
буквы
(
эта
лексема
–
идентификатор
)
Для
корректного
распознавания
числовых
констант
необходимо
также
распознавать
комментарии
,
символьные
константы
и
строковые
литералы
,
т
.
к
.
числовые
константы
как
лексемы
не
могут
находиться
внутри
них
.
Допустим
,
автомат
в
лабораторной
работе
№
1
распознавал
цепочки
некоторого
языка
L' –
комбинация
цепочек
(
любых
допустимых
и
в
любом
порядке
)
языков
комментариев
L
R
,
символьных
констант
L
C
и
строковых
литералов
L
S
.
Иными
словами
, L' = L
R
∪
L
C
∪
L
S
.
Грамматика
,
построенная
в
данной
работе
,
задает
язык
числовых
констант
L
N
и
,
следовательно
,
автомат
будет
являться
лексическим
анализатором
для
некоторого
языка
L = L
N
∪
L' = L
N
∪
L
R
∪
L
C
∪
L
S
.
Таким
образом
,
в
качестве
основы
следует
взять
конечный
автомат
из
лабораторной
работы
№
1
и
дополнить
его
новыми
состояниями
(
и
соответствующими
переходами
):
Здесь
множество
A
содержит
символы
,
которые
могут
являться
первыми
в
записи
распознаваемых
констант
.
Начиная
с
этого
символа
и
далее
,
в
области
«
Распознавание
числовых
констант
»,
входная
цепочка
должна
дублироваться
в
выходной
поток
и
завершаться
либо
типом
данных
константы
(
цепочка
принята
),
либо
сообщением
об
ошибке
(
цепочка
не
принята
).
Множество
B
–
символы
,
с
которых
могут
начинаться
лексемы
,
внутри
которых
распознавание
констант
невозможно
(
например
,
идентификаторы
и
ключевые
слова
).
Таким
образом
,
состояние
Z
играет
роль
состояния
,
блокирующего
распознавание
констант
.
Автомат
находится
в
таком
состоянии
,
пока
поступают
«
запрещающие
»
символы
множества
C
(
например
,
буквы
,
цифры
и
др
.).
Следует
отметить
,
что
множества
C
и
B
могут
отличаться
.
Вновь
распознавание
константы
может
начаться
только
после
«
разрешающего
»
символа
из
множества
D
(
например
,
символ
операции
,
скобка
и
т
.
п
.)
или
разделителя
(
например
,
пробел
и
т
.
п
.).
Распознаватель
,
реализованный
в
соответствии
с
построенным
автоматом
,
должен
в
результате
лексического
анализа
входного
файла
(
текст
программы
на
языках
C/C++)
сформировать
файл
отчета
,
содержащий
все
числовые
константы
из
входного
файла
в
том
порядке
,
в
каком
они
были
найдены
,
с
указанием
типа
этих
констант
.
При
отсутствии
в
записи
константы
модификаторов
(
суффиксов
,
уточняющих
тип
),
полагать
,
что
константа
имеет
базовый
тип
вне
зависимости
от
ее
значения
.
Если
цепочка
не
была
принята
,
то
необходимо
вывести
соответствующий
результат
и
показать
символ
,
приведший
к
ошибке
Лабораторная
работа
№
1
Z
Распознавание
комментариев
Распознавание
строковых
литералов
Распознавание
символьных
констант
N
Распознавание
числовых
констант
B
D
A
C
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
12
распознавания
.
Например
,
отчет
распознавателя
целочисленных
констант
может
иметь
следующий
вид
:
123
int
123ul
unsigned long
123.
ERROR
1e
ERROR
0x123L
long
...
Основная
часть
отчета
по
лабораторной
работе
должна
содержать
:
–
формализованное
описание
правил
записи
лексем
на
естественном
языке
;
–
запись
грамматики
в
нотации
Бэкуса
–
Наура
;
–
граф
состояний
конечного
автомата
для
представленной
грамматики
,
включающий
распознавание
комментариев
,
символьных
констант
и
строковых
литералов
;
–
протоколы
работы
лексического
анализатора
,
включая
специально
внесенные
ошибки
и
случаи
,
не
подлежащие
распознаванию
(
запись
чисел
внутри
строк
и
комментариев
,
цифры
в
идентификаторах
и
т
.
п
.).
В
выводах
по
работе
необходимо
привести
оценку
адекватности
разработанного
лексического
анализатора
,
в
т
.
ч
.
в
тех
случаях
,
когда
невозможно
однозначно
определить
границы
лексем
при
помощи
регулярной
грамматики
(
т
.
е
.
задача
должна
решаться
при
помощи
контекстно
-
свободных
грамматик
).
Варианты
индивидуальных
заданий
Вариант
индивидуального
задания
выбирается
по
общим
правилам
:
1.
Целочисленные
константы
: 8-
я
, 10-
я
и
16-
я
системы
счисления
;
все
возможные
целочисленные
типы
(
кроме
char
)
с
учетом
модификаторов
(
суффиксов
)
в
записи
константы
,
тип
по
умолчанию
–
int
.
2.
Вещественные
константы
(
с
плавающей
точкой
):
запись
в
виде
десятичной
дроби
,
показательной
формы
и
их
сочетания
;
все
возможные
типы
с
учетом
модификаторов
(
суффиксов
)
в
записи
константы
,
тип
по
умолчанию
–
double
.
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
13
Лабораторная
работа
№
3
Алгоритм
рекурсивного
спуска
Цель
работы
Изучение
LL-
методов
грамматического
разбора
для
контекстно
-
свободных
грамматик
и
их
практическое
освоение
на
примере
метода
рекурсивного
спуска
.
Содержание
работы
Построение
транслятора
для
языка
,
заданного
контекстно
-
свободной
грамматикой
,
с
использованием
метода
рекурсивного
спуска
.
Задание
1.
Записать
грамматику
,
заданную
вариантом
индивидуального
задания
,
включая
полные
множества
правил
,
терминальных
и
нетерминальных
символов
.
2.
Выполнить
преобразование
записанной
грамматики
к
виду
грамматики
рекурсивного
спуска
(
при
необходимости
).
3.
Построить
транслятор
(
интерпретатор
)
программ
заданного
языка
,
реализующий
алгоритм
рекурсивного
спуска
.
Методические
рекомендации
Заданная
грамматика
G
порождает
язык
L(G),
каждая
возможная
цепочка
которого
представляет
собой
один
оператор
присваивания
переменной
(
левый
операнд
)
значения
некоторого
выражения
(
правый
операнд
),
причем
,
при
первом
использовании
в
качестве
левого
операнда
,
переменная
определяется
,
а
при
использовании
ее
в
выражении
правого
операнда
–
должна
быть
определена
ранее
.
Последовательность
таких
операторов
,
которые
могут
быть
отделены
друг
от
друга
пустыми
символами
(
в
любом
количестве
,
в
т
.
ч
. 0),
представляет
собой
программу
на
языке
L'.
Таким
образом
, L' = ( L(G)
∪
∆
)*,
где
∆
–
множество
пустых
(
непечатаемых
)
символов
,
выполняющих
роль
разделителей
(
в
данном
случае
–
между
операторами
).
Тип
данных
,
значениями
которого
оперирует
программа
на
языке
,
порождаемом
заданной
грамматикой
,
определяется
записью
констант
этого
языка
(
разделы
IV
и
VI
грамматики
).
Следует
отметить
,
что
правила
грамматики
,
записанные
в
табл
. 3.2,
не
предполагают
наличия
разделителей
(
пустых
символов
)
между
лексемами
в
одном
операторе
,
в
то
время
,
как
для
большинства
языков
программирования
это
является
нормой
.
Это
сделано
для
упрощения
записи
правил
грамматики
.
Например
,
запись
правила
S
→
I=E;
из
раздела
I,
а
табл
. 3.2
с
учетом
наличия
пустых
символов
будет
иметь
вид
S
→δ
1
I
δ
2
=
δ
3
E
δ
4
;
,
где
δ
i
∈
∆
*
и
это
так
же
,
с
формальной
точки
зрения
,
должно
быть
раскрыто
при
помощи
правил
грамматики
.
Очевидно
,
что
ввод
разделителей
в
явном
виде
излишне
усложняет
запись
грамматики
,
поэтому
их
наличие
должно
быть
учтено
во
время
реализации
интерпретатора
.
При
выполнении
лабораторной
работы
необходимо
самостоятельно
определить
либо
возможность
,
либо
обязательное
отсутствие
таких
символов
,
как
пробел
,
табуляция
и
т
.
п
.,
между
терминальными
и
нетерминальными
символами
в
правых
частях
правил
разделов
I
и
II
грамматики
,
т
.
е
.
между
отдельными
лексемами
внутри
операторов
.
Прежде
,
чем
приступать
к
построению
транслятора
,
необходимо
убедиться
,
что
грамматика
,
заданная
в
соответствии
с
вариантом
индивидуального
задания
,
является
грамматикой
рекурсивного
спуска
или
привести
ее
к
такому
виду
.
Грамматикой
рекурсивного
спуска
называется
такая
грамматика
,
в
которой
для
любого
нетерминального
символа
A
∈
V
N
существует
либо
единственное
правило
A
→
α
,
где
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
14
α
∈
V
*
,
либо
только
правила
вида
A
→
a
1
β
1
|
a
2
β
2
| … |
a
n
β
n
,
где
a
1
,
a
2
,…,
a
n
∈
V
T
,
β
1
,
β
2
,…,
β
n
∈
V
*
причем
a
i
≠
a
j
,
при
i
≠
j
,
т
.
е
.
правые
части
этих
правил
начинаются
с
различных
терминальных
символов
.
Следовательно
,
по
первому
символу
каждой
цепочки
,
выводимой
из
некоторого
нетерминального
символа
A,
можно
однозначно
установить
соответствующее
правило
,
сравнивая
этот
символ
с
первыми
символами
правых
частей
правил
,
левые
части
которых
представлены
символом
А
.
Построение
распознавателя
для
языков
,
заданных
грамматикой
рекурсивного
спуска
,
выполняется
по
следующим
правилам
:
1.
Для
каждого
нетерминального
символа
A
∈
V
N
строится
своя
процедура
разбора
,
например
ProcA,
выполняющая
распознавание
всех
цепочек
,
выводимых
из
символа
A.
2.
Первый
символ
входного
потока
,
анализируемый
каждой
процедурой
разбора
(
т
.
е
.
первый
символ
строки
,
выводимой
из
соответствующего
нетерминального
символа
),
считывается
до
ее
вызова
.
3.
При
завершении
процедуры
разбора
,
ею
должен
быть
считан
один
символ
входного
потока
,
следующий
за
распознанной
цепочкой
(
т
.
е
.
выводимой
из
соответствующего
нетерминального
символа
).
4.
Алгоритм
каждой
процедуры
разбора
строится
в
соответствии
с
правой
частью
выбранного
правила
для
соответствующего
нетерминального
символа
:
–
если
очередной
символ
правой
части
правила
является
терминальным
,
то
он
должен
быть
равен
текущему
считанному
символу
входного
потока
(
на
первом
шаге
–
производится
выбор
правила
),
иначе
цепочка
не
принимается
(
выводится
сообщение
об
ошибке
);
при
успешном
сравнении
считывается
следующий
символ
входного
потока
и
происходит
переход
к
анализу
следующего
символа
правой
части
выбранного
правила
;
–
если
очередной
символ
правой
части
правила
является
нетерминальным
,
то
вызывается
соответствующая
ему
процедура
разбора
(
текущий
считанный
символ
будет
первым
анализируемым
символом
в
этой
процедуре
–
правило
2,
а
после
завершения
вызванной
процедуры
текущий
символ
уже
будет
считан
из
входного
потока
–
правило
3).
Каждая
процедура
,
как
правило
,
выполняет
некоторые
действия
в
соответствии
с
распознанной
цепочкой
и
возвращает
некоторое
значение
.
Например
,
в
случае
интерпретации
выражений
,
процедура
распознавания
константы
«
собирает
»
символы
константы
,
вычисляет
и
возвращает
ее
значение
,
а
процедура
распознавания
выражения
с
операцией
«+»
вызывает
процедуры
для
операндов
,
суммирует
возвращенные
ими
значения
и
возвращает
полученный
результат
.
Очевидно
,
что
операндом
может
являться
как
константа
,
так
и
другое
выражение
,
в
т
.
ч
.
содержащее
ту
же
операцию
.
Таким
образом
,
возможна
рекурсия
(
отсюда
и
название
метода
),
но
единственное
ограничение
–
рекурсия
не
должна
быть
левой
(
как
прямой
,
так
и
непрямой
).
Расширить
применение
метода
рекурсивного
спуска
можно
за
счет
:
–
приведения
исходной
грамматики
к
требуемому
виду
посредством
выполнения
левой
факторизации
,
устранения
левой
рекурсии
,
преобразования
к
нормальной
форме
Грейбах
и
т
.
п
.;
–
построения
конечных
автоматов
для
распознавания
лексем
,
записи
правил
в
регулярных
выражениях
,
привлечения
эвристического
анализа
,
модификации
базового
алгоритма
процедуры
разбора
и
др
.
Контекстные
зависимости
,
присущие
заданному
описанным
образом
языку
(
например
,
идентификаторы
,
которые
определенные
в
предшествующих
операторах
,
зарезервированные
слова
и
т
.
п
.)
реализуются
посредством
семантического
анализатора
.
Семантический
анализатор
представляет
собой
некоторую
структуру
данных
(
таблицу
идентификаторов
),
хранящую
информацию
о
текущем
контексте
,
и
обслуживающих
ее
алгоритмов
(
поиск
,
извлечение
,
добавление
и
т
.
п
.).
Выбранный
способ
программной
реализации
таблицы
идентификаторов
не
должен
вносить
существенных
ограничений
на
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
15
количество
идентификаторов
,
используемых
в
программе
,
и
их
длину
,
если
это
не
обусловлено
исходной
грамматикой
.
Транслятор
должен
после
интерпретации
каждого
оператора
программы
выводить
его
порядковый
номер
,
имя
переменной
и
значение
,
присвоенное
ей
в
этом
операторе
,
а
после
интерпретации
всей
программы
–
список
всех
переменных
и
их
значений
.
В
случае
ошибки
необходимо
выводить
развернутое
сообщение
о
ее
причинах
.
Ниже
приведены
примеры
протоколов
в
трех
случаях
:
успешная
интерпретация
,
ошибка
в
написании
идентификатора
(
имени
переменной
),
обработка
пустого
файла
:
Begin parsing.
Operator 1: a = 12
Operator 2: k34 = 0
Operator 3: c = 1
Operator 4: c = 18
Operator 5: x0 = 502
Operator 6: a = -3
Operator 7: sum = 517
End parsing.
5 variables defined:
a = -3
k34 = 0
c = 18
x0 = 502
sum = 517
Begin parsing.
Operator 1: a = 12
Operator 2:
Error 107: Identifier missing.
Abort parsing.
Begin parsing.
End parsing.
No variables defined.
Основная
часть
отчета
по
лабораторной
работе
должна
содержать
:
–
запись
исходной
грамматики
(
по
табл
. 3.1
и
3.2)
в
нотации
Бэкуса
–
Наура
;
–
описание
языка
,
порождаемого
заданной
грамматикой
(
на
естественном
языке
с
примерами
порождаемых
конструкций
);
–
вывод
о
том
,
принадлежит
или
нет
заданная
грамматика
классу
грамматик
рекурсивного
спуска
;
–
описание
преобразований
грамматики
(
в
случае
необходимости
)
и
полученную
в
результате
грамматику
рекурсивного
спуска
;
–
описание
алгоритмов
процедур
разбора
(
по
одной
для
каждого
раздела
грамматики
);
–
протоколы
работы
лексического
анализатора
,
включая
как
интерпретацию
правильных
программ
языка
,
так
и
случаи
идентификации
специально
внесенных
ошибок
.
Варианты
индивидуальных
заданий
В
соответствии
с
номером
варианта
индивидуального
задания
(
от
1
до
20)
из
табл
. 3.1
выбираются
варианты
6-
ти
разделов
грамматики
G(V
T
, V
N
, P, S).
Затем
,
в
соответствии
с
вариантами
разделов
,
из
табл
. 3.2
выписываются
правила
,
образующие
полное
множество
правил
P
грамматики
.
На
основе
полученного
множества
правил
P
строится
алфавит
грамматики
V = V
N
∪
V
T
.
Нетерминальный
символ
S
является
целевым
(
начальным
)
во
всех
полученных
грамматиках
.