ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.04.2021
Просмотров: 507
Скачиваний: 2
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
16
Таблица
3.1
Соответствие
вариантов
разделов
грамматики
варианту
индивидуального
задания
Варианты
разделов
грамматики
Варианты
разделов
грамматики
Вариант
задания
I
II
III
IV
V
VI
Вариант
задания
I
II
III
IV
V
VI
1
а
б
г
а
б
б
11
б
а
а
а
б
г
2
б
б
г
а
а
б
12
в
г
г
в
б
б
3
а
б
в
г
б
б
13
а
а
в
а
б
г
4
б
б
в
г
а
б
14
б
а
в
а
б
а
5
в
б
б
г
а
в
15
г
а
в
а
б
а
6
б
д
а
а
а
б
16
а
в
б
б
б
а
7
г
г
б
в
б
а
17
г
в
б
б
а
а
8
г
а
а
а
а
г
18
а
д
б
б
б
а
9
г
г
г
в
б
б
19
б
в
б
б
б
а
10
в
г
б
в
б
а
20
в
в
б
б
а
а
Таблица
3.2
Содержание
разделов
грамматики
по
вариантам
Р
а
зд
ел
г
р
а
м
м
а
т
и
к
и
В
а
р
и
а
н
т
р
а
зд
ел
а
Правила
грамматики
Примечания
а
S
→
I=E;
б
S
→
I:=E;
в
S
→
(I,E)
I
г
S
→
I(E)
Операторы
присваивания
переменной
с
именем
I
значения
выражения
E
.
Переменная
с
именем
I
определяется
,
если
она
не
была
определена
ранее
а
E
→
E+T|E-T|T
T
→
T*M|T/M|M
M
→
(E)|I|C
Выражения
с
традиционными
арифме
-
тическими
операциями
+, –, *, /
и
круглыми
скобками
б
E
→
E"|"T|T
T
→
T&M|M
M
→
~M|(E)|I|C
Выражения
с
поразрядными
логическими
операциями
| (
или
), & (
и
), ~ (
инверсия
)
и
круглыми
скобками
в
E
→
E+T|E-T|T
T
→
M|F(E)
M
→
I|C
F
→
sin|cos|sqr|sqrt
Выражения
с
операциями
суммирования
,
вычитания
и
вызова
функции
(
синус
,
косинус
,
квадрат
числа
,
квадратный
корень
)
г
E
→
-E|+(T)|*(T)|S|M
T
→
E,T|E
M
→
I|C
Выражения
с
унарным
минусом
и
n-
местными
операциями
суммирования
и
умножения
в
префиксной
форме
II
д
E
→
T>T|T<T|T==T|T
T
→
T+M|T-M|M
M
→
!M|(E)|I|C
Выражения
с
логическими
и
арифме
-
тическими
операциями
,
семантика
которых
соответствует
языку
C
а
I
→
A|AA|AD|AAD
б
I
→
AI|A
в
I
→
AK|A
K
→
AK|DK|A|D
III
г
I
→
AK|A
K
→
DK|D
Идентификаторы
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
17
а
C
→
DC|D
б
C
→
DC|D|.R
R
→
DR|D
в
C
→
#R
R
→
DR|D
IV
г
C
→
D
Константы
а
A
→
а
|b|c|d|e|f|g|h|i|j|k|l|m|
n|o|p|q|r|s|t|u|v|w|x|y|z
V
б
A
→
а
|b|c|d|e|f|g|h|i|j|k|l|m|
n|o|p|q|r|s|t|u|v|w|x|y|z|_
Буквы
а
D
→
0|1|2|3|4|5|6|7|8|9
Десятичные
цифры
б
D
→
0|1
Двоичные
цифры
в
D
→
true|false
Логические
значения
VI
г
D
→
0|1|2|3|4|5|6|7
Восьмеричные
цифры
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
18
Лабораторная
работа
№
4
Генерация
промежуточного
кода
Цель
работы
Практическое
освоение
методов
построения
трансляторов
на
примере
метода
трансляции
в
промежуточный
код
.
Содержание
работы
Построение
транслятора
программ
в
промежуточный
код
.
Задание
На
основе
интерпретатора
языка
,
построенного
в
лабораторной
работе
№
3,
создать
транслятор
программы
в
промежуточный
код
,
представляющий
собой
список
триад
.
Методические
рекомендации
В
компиляторах
языков
программирования
для
оптимизации
программы
и
генерации
машинного
кода
используется
некоторый
промежуточный
код
,
который
может
быть
записан
в
форме
польской
инверсной
записи
,
тетрад
,
триад
и
др
.
Триада
(
тройка
) –
это
совокупность
операции
и
двух
ее
операндов
,
представляющая
собой
некоторую
элементарную
связку
.
Триады
могут
эффективно
использоваться
как
для
записи
порядка
вычисления
операций
в
выражении
(
в
том
числе
и
операторов
присваивания
),
так
и
для
представления
управляющих
конструкций
(
условные
и
безусловные
переходы
,
с
использованием
которых
также
строятся
циклы
),
и
являются
разумным
компромиссом
между
компактностью
структуры
данных
и
удобством
анализа
.
Список
триад
имеет
регулярную
структуру
,
за
счет
чего
к
нему
легко
применяются
различные
формальные
методы
анализа
и
алгоритмы
преобразований
(
в
т
.
ч
.
оптимизации
кода
).
Каждая
триада
имеет
вид
@(op1, op2)
или
просто
@ op1 op2
,
где
@
–
обозначение
операции
,
op1
и
op2
–
первый
(
левый
)
и
второй
(
правый
)
операнды
.
Например
,
выражение
a + 5
будет
представлено
триадой
+(a, 5)
или
+ a 5
.
В
качестве
обозначения
операций
могут
выступать
как
символы
,
используемые
для
их
записи
,
так
и
некоторые
целочисленные
значения
или
значения
перечисления
,
поставленные
в
соответствие
операциям
.
При
этом
следует
учесть
,
что
собственно
присваивание
тоже
рассматривается
как
операция
.
Кроме
того
,
с
точки
зрения
реализации
распознавателя
и
дальнейшей
оптимизации
промежуточного
кода
,
имеет
смысл
рассматривать
получение
значения
константы
и
обращение
к
переменной
как
элементарные
операции
,
а
также
предусмотреть
ситуации
,
когда
триада
не
соответствует
никакой
операции
(
фиктивная
триада
).
Операндами
триады
могут
быть
:
константное
значение
,
переменная
,
результат
вычисления
другой
триады
,
адрес
перехода
в
командах
передачи
управления
(
в
данной
работе
отсутствует
).
В
случае
унарных
операций
первый
операнд
является
единственным
,
а
второй
–
фиктивным
.
Операции
с
большей
арностью
(
например
,
выражение
(+ 1 2 3 4 5)
языка
LISP)
сводятся
к
последовательности
бинарных
операций
.
В
некоторых
случаях
это
требует
соблюдения
дополнительных
соглашений
(
например
,
вызовы
процедур
и
функций
с
различным
числом
параметров
),
использования
управляющих
конструкций
(
например
,
тернарная
операция
?:
языка
C)
или
применения
других
методов
,
поэтому
подобные
случаи
в
данной
работе
не
рассматриваются
.
В
записи
триад
числовые
константы
записываются
в
общепринятой
форме
,
операнды
-
переменные
обозначаются
их
именами
,
а
результат
другой
триады
–
ссылкой
на
нее
(
например
,
ее
номером
с
предшествующим
символом
«
^
»).
Допустим
,
дана
следующая
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
19
программа
,
состоящая
из
двух
операторов
присваивания
(
нумерация
операторов
приведена
условно
):
1)
a = 1;
2)
b = 2 * (a + 5);
Запись
этой
программы
в
виде
списка
триад
будет
следующей
:
1)
1:
=(a, 1)
// a = 1;
2)
2:
+(a, 5)
// a + 5
3:
×
(2, ^2)
// 2 * (a + 5)
4:
=(b, ^3)
// b = 2 * (a + 5);
Однако
,
с
учетом
приведенных
выше
замечаний
об
элементарных
операциях
,
представляемых
отдельными
триадами
,
эта
запись
должна
иметь
такой
вид
:
1)
1:
V(a,
∅
)
// a
2:
C(1,
∅
)
// 1
3:
=(^1, ^2)
// a = 1;
2)
4:
V(b,
∅
)
// b
5:
C(2,
∅
)
// 2
6:
V(a,
∅
)
// a
7:
C(5,
∅
)
// 5
8:
+(^6, ^7)
// a + 5
9:
×
(^5, ^8)
// 2 * (a + 5)
10:
=(^4, ^9)
// b = 2 * (a + 5);
Здесь
как
V
и
C
обозначены
операции
обращения
к
переменной
и
загрузки
константы
соответственно
,
а
∅
–
фиктивный
операнд
.
Необходимость
подобной
«
детальной
»
записи
вызвана
тем
,
что
разным
компьютерам
свойственны
различные
сочетания
инструкций
и
режимов
адресации
их
операндов
.
Эти
свойства
компьютеров
учитываются
на
этапах
оптимизации
и
генерации
машинного
кода
.
При
построении
транслятора
программ
в
промежуточный
код
в
качестве
основы
можно
использовать
интерпретатор
,
разработанный
в
лабораторной
работе
№
3.
В
этом
случае
необходимо
модифицировать
процедуры
разбора
для
нетерминальных
символов
разделов
I–IV
заданной
грамматики
(
в
соответствии
с
тем
же
вариантом
индивидуального
задания
).
Основу
грамматики
составляют
разделы
I
и
II,
правила
которых
определяют
множество
операций
,
их
приоритеты
и
синтаксис
их
использования
.
Соответствующие
процедуры
должны
вместо
выполнения
операции
добавлять
в
список
соответствующую
триаду
,
а
возвращаемым
значением
(
результатом
работы
)
процедуры
будет
являться
номер
этой
триады
,
который
будет
использоваться
в
вышестоящей
процедуре
в
качестве
операнда
в
записи
очередной
триады
и
т
.
д
.
Следует
отметить
,
что
если
возможны
правила
вида
A
→
B,
то
фактически
никакая
операция
не
выполняется
,
следовательно
,
новая
триада
в
список
не
добавляется
и
процедура
разбора
для
символа
A
просто
возвращает
то
же
значение
,
которое
возвратила
вызванная
ею
процедура
для
символа
B.
Аналогично
,
если
в
записи
выражений
для
задания
приоритетов
операций
используются
скобки
,
то
они
влияют
на
порядок
разбора
,
но
операцией
не
являются
.
Процедуры
разделов
III
и
IV
осуществляют
разбор
лексем
(
имен
переменных
и
записи
констант
)
и
реализуются
,
как
правило
,
при
помощи
автоматной
модели
с
использованием
правил
разделов
V
и
VI.
Эти
процедуры
образуют
лексический
анализатор
(
нижний
уровень
разбора
)
и
не
вызывают
других
процедур
,
поэтому
они
должны
просто
формировать
и
добавлять
в
список
триады
обращения
к
переменным
и
получения
констант
соответственно
.
Следует
также
обратить
внимание
на
то
,
что
в
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
20
выражении
в
правой
части
оператора
присваивания
могут
присутствовать
только
те
переменные
,
которые
уже
определены
ранее
,
тогда
как
новый
идентификатор
в
левой
части
приводит
к
определению
переменной
.
Следовательно
,
процедуры
для
распознавания
идентификаторов
в
левой
и
в
правой
частях
оператора
присваивания
будут
отличаться
друг
от
друга
по
реализации
,
но
,
при
этом
,
будут
формировать
одинаковые
триады
и
возвращать
одинаковые
значения
.
Транслятор
должен
формировать
список
триад
(
аналогично
примерам
выше
,
с
нумерацией
триад
,
но
,
конечно
,
без
комментариев
)
по
мере
разбора
входной
программы
и
по
окончании
работы
создавать
файл
протокола
,
содержащий
этот
список
в
виде
текста
.
В
случае
ошибки
в
протоколе
должно
фиксироваться
развернутое
сообщение
о
ее
причинах
(
аналогично
предыдущей
работе
).
Основная
часть
отчета
по
лабораторной
работе
должна
содержать
:
–
запись
грамматики
в
нотации
Бэкуса
–
Наура
(
получена
в
предыдущей
работе
);
–
описание
реализованного
способа
формирования
и
представления
триад
;
–
протоколы
работы
лексического
анализатора
.