--PAGE_BREAK--Необходимо соблюдать следующие параметры монитора:
- частота кадров монитора не должна быть ниже 75 Гц;
- должна быть достаточная яркость и контрастность монитора, чтобы была возможность получения информации с монитора без напряжения для глаз;
С эргономичной точки зрения необходимо следующее:
- удобный доступ к дисководу, CD-ROM;
- удобство работы с методической литературой;
- удобное положение (по высоте) клавиатуры, либо стул, регулируемый по высоте.
Практические работы должны проводиться за компьютером на вычислительном центре, например аудитории 205. Общее освещение данной аудитории достаточно для проведения лекций, но не для работы за компьютером и чтением литературы. Поэтому требуется использование дополнительного местного освещения.
Для работы с литературой, например, методического пособия, требуется дополнительное пространство на рабочем столе. Его можно освободить, убрав со стола системный блок в стол и применив специальную конструкцию стола, показанную на рисунке 7. Стул должен быть вращающимся для удобства маневрирования, а также с регулировкой по высоте, чтобы обеспечить оптимальные условия при работе с клавиатурой и монитором.
Примерное рабочее место студента показано на рисунке 7.
Рисунок 7 – Рабочее место студента
1 – монитор, 2 – системный блок, 3 – клавиатура, 4 – стул, 5 – методический материал, 6 – стол.
Заключение
Результатом проделанной работы явилось создание учебного комплекса состоящего из двух программ LEXAN и SINAN, соответственно программа лексического и грамматического разбора. При этом была разработана общая схема компилятора с описанием структур и их взаимодействия.
При работе над проектом были созданы алгоритмы, позволяющие производить синтаксический разбор с помощью таблиц, что позволяет наглядно понять один из способов формирования деревьев грамматического разбора.
Разработка включает в себя первые два из четырех этапов учебного комплекса по созданию компилятора. Разработанная структура позволяет реализовать последующие этапы, т.к. определены последующие направления и описаны способы взаимодействия между этапами. На следующих этапах должны формироваться промежуточный и ассемблерный коды.
Данный проект позволит разобраться студентам с методами анализа программы и на практике проверить знания, полученные при изучении предмета «Системное программное обеспечение». Также является основой для дальнейшей разработки учебного комплекса.
Был выполнен экономический расчет, в результате которого были подсчитаны общие затраты на выполнение дипломного проекта, они составили 7000 рублей.
Список использованных источников
1. Бек Л. Введение в системное программирование.: Пер. с англ. – М.: Мир, 1998.
2. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир, 1975.
3. Карпов В.Э. Классическая теория компиляторов. – itlab.net.ru/ materials/compiler/compiler.html
4. Конспект лекций по теме «Трансляторы». – www.kulichki.net/ kit/library/transl.zip
5. Креншоу Д. Давайте создадим компилятор! – kit.kulichki.net/ crenshaw/crenshaw.html
6. Лабораторные работы по курсу Системное ПО. – www.fi.ru/~mill/ LabFl-97.htm
7. Основы компиляции. structur.h1.ru/compil.htm
8. Романов Е.Л. Основы построения трансляторов. – www.kulichki. net/kit/library/nstu_trans.zip.
9. Пратт Т. Языки программирования. Разработка и реализация.: Пер. с англ. – М.: Мир, 1979.
10. Типовые нормы времени на программирование задач для ЭВМ. – М.: Экономика, 1989.
11. Типовые нормы времени на разработку конструкторской документации. – М.: Экономика, 1991.
12. Фаронов В.В. Турбо Паскаль. Книга1. Основы Турбо Паскаля. – М.: Учебно-инженерный центр «МВТУ-ФЕСТО ДИДАКТИК», 1992.
13. Шаньгин В. Ф., Илюшечкин В. М., Тимофеев П. А. Программирование микропроцессорных систем. / Под ред. В. Ф. Шаньгина. – М.: Высш. шк., 1990.
Приложение А
Пример выполнения задания по работе со сканером LEXAN
Дана следующая грамматика языка:
1. ::= PROGRAM VAR BEGIN END.
2. ::= id
3. ::= | ;
4. ::= :
5. ::= INTEGER
6. ::= id | , id
7. ::= | ;
8. ::= |
9. ::= id :=
10. ::= | + | —
11. ::= id | int | ( )
12. ::= FOR DO
13. ::= id := TO
14. ::= | BEGIN END
Используя программу LEXAN произвести следующие действия:
1. Выбрать элементы из таблицы терминальных символов, при желании можно изменить названия ключевых слов (таблица 1);
2. Написать исходный текст на учебном языке с использованием заданной грамматики;
3. Заполнить таблицы: – символьных имен (таблица 2);
– литералов (таблица 3);
– лексического анализа (выходных символов);
4. Проверить правильность заполнения таблиц встроенным анализатором;
5. При наличии ошибок, исправить имеющиеся, и повторно обработать программой LEXAN;
6. Получить листинг полученных результатов.
7. Сохранить результат в файл.
Сначала производится анализ, какие терминальные символы входят в грамматику: ”PROGRAM”, ”VAR”, ”BEGIN”, ”END”, ”.”, ”INTEGER”, ”;”, ”:=”, ”+”, ”-”, ”FOR”, ”DO”, ”TO”.
Исходная программа, написанная с использованием терминов исходной грамматики:
program prog1;
var
i, x:integer;
begin
x:=0;
for i:=1 to 10 do
x:=x+i;
end.
Далее выбираются терминальные символы, использованные в программе, заполняется таблица выбранных терминальных символов. Примерное представление таблицы выбранных терминальных символов показано в таблице 19.
Таблица 19
№ стр.
Терминальный символ
Комментарий (обозначение)
Код
1
PROGRAM
1
2
;
27
3
VAR
2
4
,
29
Продолжение таблицы 19
№ стр.
Терминальный символ
Комментарий (обозначение)
Код
5
:
31
6
INTEGER
5
7
BEGIN
3
8
:=
28
9
FOR
8
10
TO
9
11
DO
10
12
+
32
13
END
4
14
.
30
Определяются символические имена, встречающиеся в программе, и заполняется таблица 20 в порядке их появления в тексте
Таблица 20
Специф
Идентификатор
Тип
Размер, занимаемый в памяти, байт
Относительный адрес в памяти
1
prog1
2
i
3
x
В тексте определяются литералы и заносятся в таблицу 21 в порядке их появления.
Таблица 21
Специф
Литерал
Тип
Размер, занимаемый в памяти, байт
1
0
Integer
2
2
1
Integer
2
3
10
Integer
2
Во время заполнения этих трех таблиц заполняется четвертая – таблица 22 (таблица выходных кодов лексем): в поле «Таблица» подставляются номера таблиц (таблица терминальных символов – №1, таблица символических имен – №2, таблица литералов – №3), в поле строка – код элемента (из таблицы 1), спецификаторы (из таблицы 2 и 3). Поле «№п.п.» заполняется автоматически.
Таблица 22
№ п.п.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Таблица
1
2
1
1
2
1
2
1
1
1
1
2
1
3
1
Строка
1
1
27
2
2
29
3
31
5
27
3
3
28
1
27
№ п.п.
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Таблица
1
продолжение
Удобная ссылка:
Скачать дипломную работу бесплатно
подобрать список литературы
Программно методический комплекс для обучения процессу создания компиляторов
--PAGE_BREAK--Далее мы рассмотрим некоторые из этих составных частей процесса компиляции.
1.3 Лексический анализ. Сканер
Лексический анализатор представляет собой модуль разбора текста программы. Разбор происходит в зависимости от имеющихся у него в памяти терминальных символов и правилами определения типов данных. Каждый язык имеет свои ограничения по типам данных, допущения и особенности создания (строения) конструкций, применению операторов и т.п. При работе сканера используются три таблицы: таблица терминальных символов, таблица символических имен и таблица литералов – это заполняемые таблицы. Таблица терминальных символов хранит все ключевые слова и специальные символы используемые в языке, а также коды, соответствующие каждому символу. Таблица символических имен заполняется в процессе разбора текста программы и хранит в себе имена идентификаторов (символических имен). Таблица литералов также заполняется в процессе разбора программы и хранит в себе литералы: численные и строковые значения, с указанием типов данных и относительных адресов.
Распределение по таблицам происходит следующим образом.
Сканер в процессе анализа текста программы выделяет один из элементов текста и сравнивает с каждым терминальным символом. Если такой символ найден, то в выходной код передаются код таблицы и спецификатор (номер строки в таблице). В случае если этот элемент не является терминальным символом проверяется, является ли он идентификатором (первый символ обычно буква, остальные могут быть либо буквой, либо цифрой), если такой определен, то данный элемент заносится в таблицу символических имен, а к выходному коду добавляется пара численных значений: номер таблицы и спецификатор найденного элемента. В случае если такой элемент в таблице уже имеется, то в выходной код заносится номер таблицы и его спецификатор. В таблицу литералов заносят численные, строковые и иные определенные языком значения. При этом распознается тип значения и тут же заполняется относительная таблица адресов.
Выходной код, сформированный сканером, передается на следующую стадию обработки – синтаксический анализ.
Таким образом, алгоритм работы простейшего сканера можно описать так:
· просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему;
· для выбранной части входного потока выполняется функция распознавания лексемы;
· при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;
· при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера — либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.
Таблица терминальных символов в простейшем случае может иметь следующий вид как показано в таблице 1.
Таблица 1 – Таблица терминальных символов
№ п.п.
Терминальный символ
Комментарий (обозначение)
1
PROGRAM
Заголовок программы
2
VAR
Описание переменных
3
BEGIN
Начало тела программы
4
END
Конец тела программы
5
INTEGER
Целый тип данных
6
FOR
Счетный оператор цикла (для)
7
TO
Ключевое слово счетного оператора цикла (до)
8
DO
Ключевое слово (выполнить)
Продолжение таблицы 1
№ п.п.
Терминальный символ
Комментарий (обозначение)
9
WHILE
Оператор цикла с предусловием (пока)
10
DIV
Деление целочисленное
11
MOD
Остаток от целочисленного деления
12
AND
Логическое И
13
OR
Логическое ИЛИ
14
:=
Присвоить значение
Сначала заполняется таблица лексем (терминальных символов), затем начинается считывание и обработка входного текста программы пользователя. При работе сканера происходит заполнение таблиц символических имен и литералов.
Данные таблицы могут выглядеть следующим образом:
Таблица 2 – Таблица символических имен
№ п.п.
Идентификатор
Тип
Размер, занимаемый в памяти, байт
Относительный адрес в памяти
1
I
INTEGER
2
Y
REAL
3
X1
REAL
…
Таблица 3 – Таблица литералов
№ п.п.
Литерал
Тип
Размер, занимаемый в памяти, байт
Относительный адрес в памяти
1
1
INTEGER
2
0
2
100
INTEGER
2
2
…
Результатом работы сканера является последовательность кодов лексем. Каждый код лексемы обычно представляется кодом таблицы и спецификатором (порядковый номер в таблице, куда занесена лексема). Это позволяет избежать дополнительного поиска по таблицам на следующих этапах трансляции. Например в результате обработки сканером следующего предложения языка Паскаль
FOR I:=1 TO 100 DO Y:=X1
будет получена строка:
,
где в угловых скобках пара чисел задает код таблицы и спецификатор. Можно оформить и в виде таблицы.
Таблица 4 – Таблица выходных символов
№ п.п.
1
2
3
4
5
6
7
8
9
10
Таблица
1
2
1
3
1
3
1
2
1
2
Строка
6
1
14
1
7
2
8
2
14
3
Функционально в сканере могут быть выделены следующие модули[4]:
1) выделение из входной строки очередного слова;
2) поиск в таблицах лексем и определение кода лексемы;
3) формирование и вывод выходной строки.
Для модуля выделения слова важна информация о том, какие символы могут быть признаками начала или конца слова. Например, в языке Паскаль ключевые слова отделяются от других элементов предложения пробелами. Сложнее обстоит дело с выделением идентификаторов и чисел, поскольку разделителем для них может служить любой другой символ, не входящий по определению в идентификатор или число.
При заполнении таблиц выполняется проверка на наличие в ней элемента, совпадающего с выделенным идентификатором или константой, и при совпадении занесение в таблицу не выполняется.
В задачи последнего модуля входит занесение в выходную строку кодов лексем.
В дополнение к своей основной функции, распознаванию лексем, сканер обычно также выполняет чтение строк исходной программы и, возможно, печать листинга исходной программы. Комментарии игнорируются сканером, за исключением того случая, когда они должны быть напечатаны и, таким образом, эффективно удаляются из исходной программы до начала процесса грамматического разбора.
Следующей стадией анализа является синтаксический разбор.
Лексический и синтаксический анализаторы взаимодействуют между собой. Существует два основных способа взаимодействия:
1) реализуется на основе прямого лексического анализа. От синтаксического анализатора поступает запрос «дать лексему» и указывается тип лексемы;
2) непрямой лексический анализ. Синтаксический анализатор выдает запрос «дать лексему», тип лексемы не указывается. Нет решающего блока, считаем, что работает группа параллельных автоматов.
1.4 Синтаксический и семантический анализ
Синтаксический анализ — это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Это – самая сложная часть компилятора.
Синтаксический анализатор расчленяет исходную программу на составные части, формирует ее внутреннее представление, заносит информацию в таблицу символов и другие таблицы. При этом производится полный синтаксический и, по возможности, семантический контроль программы. Фактически, это — синтаксически управляемая программа. При этом обычно стремятся отделить синтаксис от семантики насколько это возможно — когда синтаксический анализатор распознает конструкцию исходного языка, он вызывает семантическую процедуру, которая контролирует эту конструкцию, заносит информацию куда надо, проверяет на дублирование описания переменных, проверяет соответствие типов и т.п.
Процесс синтаксического анализа может рассматриваться как построение дерева грамматического разбора для транслируемых предложений. Грамматики могут использоваться как для порождения так и для распознавания предложений языка. Порождение начинается с начального понятия (или аксиомы грамматики). При распознавании с помощью грамматических правил порождается предложение, которое затем сравнивается с входной строкой. При этом применение правил подстановки для порождения очередного символа предложения зависит от результатов сравнения предыдущих символов с соответствующими символами входной строки. Результат анализа исходного предложения в терминах грамматических конструкций удобно представлять в виде дерева. Такие деревья обычно называются деревьями грамматического разбора или синтаксическими деревьями. На рисунке 3 изображено дерево грамматического разбора для предложения READ (VALUE).
Рисунок 3 – Дерево грамматического разбора
Методы грамматического разбора разбиваются на два больших класса восходящие и нисходящие – в соответствии с порядком построения дерева грамматического разбора. Нисходящие (методы сверху-вниз) начинаются с аксиомы грамматики, с корня дерева и пытаются так его наращивать, чтобы последующие узлы дерева соответствовали синтаксису анализируемого выражения. Восходящие (методы снизу-вверх) начинают с элементов предложения (с «листьев») и отыскивают в грамматике какому понятию они соответствуют, т.е. определяют родительскую вершину для этих элементов, и т.д. пока не приходят к корню дерева (аксиоме грамматики). В современных компиляторах применяются как нисходящие, так и восходящие методы.
Достоинством восходящего метода является его несомненная простота, а также высокая скорость выполнения (не тратится время на поиск правила редукции).
Однако все эти достоинства напрочь меркнут перед главным недостатком данного метода. Дело в том, что здесь практически отсутствует какая бы то ни была диагностика (и тем более — локализация) ошибок. Во вторых, некоторые ошибки в исходном выражении не диагностируются вовсе. Например, выражения, в которых встречаются идущие подряд скобки “(” и “)”.
Поэтому при дальнейшем рассмотрении будет рассматриваться нисходящий разбор, как наиболее пригодный метод при ручном написании компилятора [4].
Кроме этого, алгоритмы синтаксического (грамматического) разбора (контроля) делят на синтаксически-ориентированные и синтаксически-неориентированные. Синтаксически-ориентированные алгоритмы являются универсальными для некоторого семейства языков и переход к распознаванию предложений другого языка выполняется путем смены грамматики, т.е. грамматика выполняет роль некоей «программы» распознавания предложений языка. Главным достоинством этого класса алгоритмов является их универсальность, а недостатком — наличие избыточности вследствие ориентации на семейство языков.
Синтаксически-неоpиентиpованные алгоритмы отличаются тем, что порядок действий в них определяется правилами грамматики данного конкретного языка. Достоинством этого класса алгоритмов является отсутствие избыточности, а недостатком — невозможность перенастройки на распознавание предложений другого языка.
В дальнейшем мы будем работать с синтаксически-неориентированными алгоритмами, т.к. будем работать лишь с одним языком – учебный язык на основе языка Паскаль.
1.5 Грамматики
Грамматика языка программирования является формальным описанием его синтаксиса или формы, в которой записаны отдельные предложения программы или вся программа. Грамматика не описывает семантику или значения различных предложений. Информация о семантике содержится в программах генерации объектного кода. В качестве иллюстрации разницы между синтаксисом и семантикой рассмотрим два предложения:
I:=J+K
и
I:=X+Y
где Х и Y являются действительными переменными, a I, J, К — целыми переменными. Эти два предложения имеют одинаковый синтаксис. Оба являются операторами присваивания, в которых присваиваемое значение определяется выражением, состоящим из двух имен переменных, разделенных оператором сложения. Однако семантика этих двух предложений совершенно различна. Первое предложение говорит о том, что переменные в выражении должны быть сложены с использованием целых арифметических операций, а результат сложения должен быть присвоен переменной I. Второе предложение задает сложение с плавающей точкой, результат которого должен быть преобразован в целое число перед присваиванием. Очевидно, эти два предложения будут скомпилированы в различные последовательности машинных команд, хотя их грамматическое описание одинаково. Различия между ними проявятся на этапе генерации объектного кода.
На рисунке 4 показаны БНФ грамматики, используемые в дипломном проекте. Подчеркнутые волнистой линией элементы могут опускаться (не использоваться).
1. ::= PROGRAM VAR BEGIN END.
2. ::= id ;
3. ::= {; } ;
4. ::= :
5. ::= INTEGER | REAL | STRING
6. ::= id {, id }
7. ::= { ; } ;
8. ::= | | | | | |
9. ::= id :=
10. ::= – { + | – }
11. ::= { * | DIV | / }
12. ::= id | int | real | | ()
13. ::= READ ( )
14. ::= WRITE ( {, } )
15. ::= FOR DO
16. ::= id := TO|DOWNTO
17. ::= | BEGIN END
18. ::= |
19. ::= ′ ′
20. ::= string
21. ::= IF THEN ELSE
22. ::=
23. ::= > | = |
24. ::= WHILE DO
25. ::= REPEAT UNTIL
Рисунок 4 – Упрощенная грамматика языка Паскаль
продолжение
--PAGE_BREAK--Существует несколько различных форм записи грамматик, среди которых мы рассмотрим форму Бекуса—Наура (БНФ). БНФ не самое мощное из известных средств описания синтаксиса. Однако эта форма достаточно проста, широко используется и предоставляет достаточные для большинства приложений средства. На рис.4 изображена одна из возможных грамматик БНФ.
Грамматика БНФ состоит из множества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка программирования. Рассмотрим, например, правило 13 на рис. 4:
::= READ ( )
Это определение синтаксиса предложения READ языка Паскаль, обозначенное в грамматике как . Символ ::= можно читать как «является по определению». С левой стороны от этого символа находится определяемая конструкция языка (в нашем случае— ), а с правой—описание синтаксиса этой конструкции. Строки символов, заключенные в угловые скобки , называются нетерминальными символами (т. е. являются именами конструкций, определенными внутри грамматики). То, что не заключено в угловые скобки, называется терминальными символами грамматики (лексемами). В этом правиле вывода нетерминальными символами являются и . Терминальными символами являются лексемы READ, (, ). Таким образом, это правило определяет, что конструкция состоит из лексемы READ, за которой следует лексема (, за ней следует конструкция языка, называемая , за которой следует лексема ). Пробелы при описании грамматических правил не существенны и вставляются только для наглядности.
Для распознавания нетерминального символа необходимо чтобы было определение для нетерминального символа . Это определение дается правилом 6 на рис. 4:
::= id {, id }
Эта нотация, означает, что конструкция, заключенная в фигурные скобки, может быть либо опущена, либо повторяться один или более число раз. Таким образом, правило 6 определяет нетерминальный символ как состоящий из единственной лексемыid или же из произвольного числа следующих друг за другом лексемid, разделенных запятой. В соответствии с этим новым определением процедура, соответствующая нетерминальному символу , сначала ищет лексемуid, а затем продолжает сканировать входной текст до тех пор, пока следующая пара лексем не совпадет с запятой иid. Такая запись устраняет проблему левой рекурсии.
1.6 Формирование промежуточного кода
Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. Дерево грамматического разбора оказывается неудобным в работе при работе при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно генерацией объектного кода внутреннее представление программы преобразуется в одну из соответствующих форм записи.
Примерами таких форм записи являются:
- обратная польская запись операций;
- тетрады операций;
- триады операций;
- собственно команды ассемблера.
Обратная польская запись — это постфиксная запись операций. Преимуществом ее является то, что все операции записываются непосредственно в порядке их выполнения. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрады представляют собой запись операций в форме из четырех составляющих:
(,,).
Тетрады используются редко, так как требуют больше памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя операндами.
Триады представляют собой запись операций в форме из трех составляющих: (,), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение A := B*C + D — B*10, записанное в виде триад будет иметь вид:
1) * ( B, C )
2) + ( ^1, D )
3) * ( B, 10 )
4) — ( ^2, ^3 )
5) := ( A, ^4 )
Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой.
Команды ассемблера удобны тем, что при их использовании внутреннее представление программы полностью соответствует объектному коду и сложные преобразования не требуются. Однако использование команд ассемблера требует дополнительных структур для отображения их взаимосвязи. Кроме того, внутреннее представление программы получается зависимым от результирующего кода, а это значит, что при ориентации компилятора на другой результирующий код потребуется перестраивать как само внутреннее представление программы, так и методы его обработки в алгоритмах оптимизации (при использовании триад или тетрад этого не требуется).
Для построения внутреннего представления объектного кода (в дальнейшем — просто кода) по дереву вывода может использоваться простейшая рекурсивная процедура. Эта процедура прежде всего должна определить тип узла дерева — он соответствует типу операции, символ которой находится в листе дерева для текущего узла. Этот лист является средним листом узла дерева для бинарных операций и крайним левым листом — для унарных операций. После определения типа процедура строит код для узла дерева в соответствии с типом операции. Если все узлы следующего уровня для текущего узла есть листья дерева, то в код включаются операнды, соответствующие этим листьям, и получившийся код становится результатом выполнения процедуры. Иначе процедура должна рекурсивно вызвать сама себя для генерации кода нижележащих узлов дерева и результат выполнения включить в свой порожденный код.
Поэтому для построения внутреннего представления объектного кода по дереву вывода в первую очередь необходимо разработать формы представления объектного кода для четырех случаев, соответствующих видам текущего узла дерева вывода:
оба нижележащих узла дерева — листья (терминальные символы грамматики);
только левый нижележащий узел является листом дерева;
только правый нижележащий узел является листом дерева:
оба нижележащих узла не являются листьями дерева.
Метод четверок
Каждая четверка записывается в виде:
операция, op1, op2, результат,
где операция — это выполняемая объектным кодом функция
op1, op2 — операнды этой операции
Например,
(-a+b)*(c+d)
будет соответствовать такой последовательности четверок
— a, T1
+ T1, b T2
+ c, d T3
* T2, T3, T4
Из сформированных четверок нетрудно сгенерировать машинный код.
1.7 Обоснование создания учебного комплекса
Создание учебного комплекса обосновано сложностью предметной области создания компиляторов и отсутствием подобного наглядного материала, позволяющего поэтапно отследить процессы, происходящие в компиляторе (работа анализаторов, заполнение таблиц).
Из описанного выше материала видно, что компиляторы имеют очень много вариантов построения, это определяет дополнительную сложность при выборе оптимальной структуры компилятора. Процесс компиляции довольно сложен и труден для восприятия в целом. Он содержит в себе множество понятий, подходов обработки, методов разбора, таблиц, формальные грамматики. Поэтому целесообразно разбиение комплекса на ряд лабораторных работ, в которых будут описаны практические методики изучения различных этапов компиляции на основе специальных обучающих программ.
1.8 Обзор существующих разработок
На текущий момент существует множество разработок, связанных с созданием компиляторов. В основном это методические, учебные пособия по проектированию компиляторов, где рассматриваются основные принципы анализа текста программы и синтеза объектного кода. В основном в этих материалах приводятся примеры как написать оптимальную программу компиляции по скорости, используя стеки, таблицы предшествования и т.п. структуры, не позволяющие или затрудняющие передавать данные между этапами как требуется в учебном комплексе.
Работа с методическим (теоретическим) материалом подразумевает выполнение задания с дальнейшей проверкой преподавателем, что затрачивает его время и силы. Программная реализация дает возможность самому проконтролировать себя на правильность проведенного анализа или корректность синтезированного кода.
Руководство по написанию компиляторов Креншоу [5] позволяет создать свой компилятор, но его особенностью является прямой перевод считанного текста в выходной код, что не дает наглядности внутреннего представления компилятора. Этот компилятор является однопроходным, он не хранит и создает в памяти таблиц, вся обработка описывается в процедурах.
Существующие компиляторы не дают наглядное представление внутренних структур, а обычно имеют один исполняемый файл, реализующий перевод текста программы в объектный или исполняемый файл. Ставка обычно делается либо на скорость компиляции, либо на минимальный размер генерируемого файла.
Компиляторы компиляторов в основной своей массе создают лишь лексические анализаторы, оставляя дорабатывать синтаксическую часть самому программисту. При обзоре не было найдено российских разработок компиляторов компиляторов, что так же говорит о том, что при работе с существующими разработками добавится еще одна проблема – проблема языка.
1.9 Обоснование разработки
Разработка является учебным комплексом, включающим в себя лабораторные работы по изучению процесса компиляции. Это программа, позволяющая без руководителя выполнять и проверять выданные задания (проверять выполненные задания). Теоретический материал для проведения лабораторной работы сформирован в методической (описательной) части.
Особенность данной разработки в том, что спроектированный компилятор построен поэтапно (модульно). Результат работы каждого из этапов может быть зафиксирован (сохранен) в виде файла с определенной структурой. Это файл с промежуточным кодом, получаемый от сканера, файл с формируемой таблицей переходов (хранит структуру дерева), файл с промежуточным кодом (тетрады), ассемблерный код. На каждом из этапов имеется возможность генерации файла отчета со структурами, с описанием и указанием ошибок, а также дополнительной служебной информацией.
Данный комплекс служит для ознакомления с принципами компиляции, получения практических навыков лексического анализа и грамматического разбора (синтаксический анализ), формирования промежуточного кода. Комплекс построен таким образом, чтобы по возможности охватить все этапы компиляции, наглядно представляя формируемые таблицы.
При проектировании (разработке, планировании) комплекса ставка делалась на наглядность происходящих процессов и доступность для понимания правил формирования и заполнения множества таблиц. При работе с программным продуктом не показана работа со стеком, т.к. вся реализация, весь анализ происходит только с таблицами и только в таблицах, исключение составляет разве что входной текст программы и выходной код.
Учебное пособие состоит из:
- вводной части (теоретические сведения):
1) описание компиляторов, их суть, назначение;
2) лексический анализатор (сканер);
3) синтаксический анализатор, дерево грамматического разбора;
4) получение промежуточного кода;
- практической (работа с программами):
1) обзор компиляторов (Паскаль, C, Delphi);
2) работа с программой LexAn;
3) работа с программой SinAn;
4) работа с программой SinAn;
— проверка полученных знаний с помощью контрольных вопросов и заданий.
Учебный комплекс служит для облегчения работы преподавателя, возможности самостоятельно изучения материала, получения практических навыков по изучаемой дисциплине, возможности более наглядного представления информации и т.п.
Учебный комплекс включает в себя несколько взаимосвязанных лабораторных работ, охватывающих всю предметную область или основную ее часть, например обучение процессу компиляции. При этом при выполнении каждой лабораторной работы происходит поэтапное изучение предметной области.
Лабораторные работы обычно включает в себя:
- теоретические сведения;
- порядок выполнения работы;
- контрольные вопросы и задания.
Теоретические сведения дают представление об изучаемой области, ознакомление с ее основными принципами, структурами и характерными особенностями. При этом часто производится разбор какого-либо наглядного примера.
Для проведения лабораторных работ могут использоваться различные технические средства. Это могут быть различного рода стенды, имитирующие работу реальных устройств, сами устройства, выступающие в роли исследуемого объекта, компьютер, с набором необходимых для работы программ, а также другие устройства и оборудование, подходящие для этой цели.
Использование в лабораторных работах оборудования позволяет получать дополнительные практические навыки, когда студент может влиять на работу исследуемого объекта, изменяя различные входные и управляющие параметры. При этом учащийся лучше понимает всю картину происходящего, исследуемые процессы.
Во время выполнения лабораторных работ часто приходится снимать показания с приборов, получать различные данные от датчиков, программ и т.п., заносить их в таблицы и обрабатывать соответствующим образом. При этом производятся расчеты, связанные с работой, оформляется отчет, который и сдается преподавателю на проверку.
Контрольные вопросы формируют исходя из цели проведения лабораторной работы и того, что должен вынести обучающийся в результате ее выполнения: определения, термины, понятия, связанные с изучаемым объектом, принципы его работы, строение.
2 Создание учебной разработки
2.1 Краткое описание учебного компилятора
Учебный компилятор состоит из четырех отдельных модулей, это:
1) лексический анализатор (сканер) LEXAN;
2) синтаксический анализатор (парсер) SYNAN;
3) генератор промежуточного кода PROMKOD;
4) генератор ассемблерного кода ASMKOD.
На данном этапе реализованы первые два. Эти модули (этапы) взаимодействуют между собой с помощью промежуточных файлов.
Среда LEXAN генерирует файл с расширением LEX, в котором хранятся таблицы, полученные в результате разбора текста программы: таблица выбранных терминальных символов, таблица символических имен, таблица лексем и таблица выходных кодов лексем, которая и представляет собой программу в виде ссылок на три предыдущие таблицы. Данный файл является входным на этапе синтаксического анализа.
Среда SINAN генерирует файл с расширением SYN, хранящий в себе формируемую таблицу переходов, представляющую собой грамматическое дерево в табличном виде. В этом же файле хранятся таблицы выбранных терминальных символов, символических имен и лексем. Данный файл является входным на этапе генерации промежуточного кода.
Среда PROMKOD генерирует файл PRK, хранящий в себе упрощенное дерево грамматического разбора, представленное в виде таблицы триад.
Среда ASMKOD генерирует файл ASK, представляющий собой программу на ассемблере.
В результате проведенного анализа была выбрана многопроходная схема просмотра компилятора. На каждом этапе (лексический анализ, синтаксический анализ, формирование промежуточного кода, формирование ассемблерного кода) происходит новый просмотр (проход) по программе, представленной в различном виде. На первом этапе (сканер) – в виде текста программы, на втором (парсер) – в виде кодов лексем, на третьем – дерево грамматического разбора, на четвертом – таблица промежуточного кода. Это сделано для поэтапного обучения процессу компиляции и возможности работы с внутренним представлением программы.
Все данные, кроме входного текста программы помещаются в таблицы. Это сделано для того, чтобы не использовать стек и все данные представлять по возможности в одном месте.
продолжение
--PAGE_BREAK--
продолжение
--PAGE_BREAK--
продолжение
--PAGE_BREAK--
2.4.4 Формируемая таблица переходов. Правила заполнения
Таблица представляет собой набор ячеек. Столбцы и строки нумеруются. Столбцы определяют номер распознанной лексемы (элемента конструкции), строки определяют номер полученной конструкции.
В таблице могут существовать только два вида данных: указатели на таблицы и переходы.
Указатели на таблицы состоят из символа признака ссылки на таблицу «$», номера таблицы и, через запятую, кода (для терминального символа) или спецификатора. Номера таблиц: 1– таблица терминальных символов, 2 – таблица символических имен, 3 – таблица литералов.
Указатели на ячейки состоят из символа «@» и следующих за ним через запятую адресов столбца и строки, куда следует перейти, оказавшись в данной ячейке.
Все ячейки первого столбца зарезервированы для значений ссылок обратного перехода на ячейку, следующую за вызвавшей переход в данную строку и называются ячейками возврата.
Чтобы заполнить формируемую таблицу переходов необходимо знать следующие правила.
Таблица заполняется в точности по БНФ, показанной на рисунке 4, при этом строки таблицы являются элементами конструкций данной грамматики. Разбор делается по данным, полученным из таблиц терминальных символов, символических имен, литералов, выходных кодов лексем.
1) Заполнение таблицы начинается с левой верхней ячейки, каждый раз смещаясь на следующую, более правую.
2) При наличии вложенности конструкции (найден нетерминальный символ) создается (заполняется) новая строка, где в первой ячейке указывается адрес возврата: указатель перехода «@», номер строки, номер столбца, откуда осуществлен переход плюс один (т.е. переход на следующую ячейку за той, из которой был произведен вызов).
3) При наличии нескольких элементов, разделенных знаком «|», осуществляется перебор вариантов, которые подходят значениям, указанным в таблице выходных кодов.
4) При соответствии значения ячейки или одного из элементов ИЛИ терминальному символу указывается признак ссылки на таблицу «$», затем номер таблицы – 1 и код элемента в таблице терминальных символов (номер таблицы и код берется из таблицы кодов лексем).
5) При соответствии значения ячейки или одного из элементов ИЛИ идентификатору указывается признак ссылки на таблицу «$», затем номер таблицы – 2 и спецификатор (номер таблицы и спецификатор берется из таблицы кодов лексем).
6) При соответствии значения ячейки или одного из элементов ИЛИ литералу указывается признак ссылки на таблицу «$», затем номер таблицы – 3 и спецификатор (номер таблицы и спецификатор также берется из таблицы кодов лексем).
7) Подчеркнутые элементы в БНФ грамматике не обязательны (они могут отсутствовать).
2.4.5 Правила заполнения формируемой таблицы переходов
Разбор делается по данным, полученным от БНФ грамматик, из таблиц терминальных символов, выходных кодов лексем.
Заполнение формируемой таблицы переходов начинается со второй ячейки первой строки.
Для терминальных символов алгоритм может выглядеть таким образом.
Допустим, производится анализ первого элемента таблицы кодов лексем.
1) Номер позиции в таблице кодов лексем равен 1. Производится чтение данных из первого столбца таблицы кодов лексем. Полученное значение номера таблицы – 1 (таблица терминальных символов), код равен 1 (по таблице кодов – «объявление программы»).
2) Рассматривается первый элемент БНФ грамматики, им является ключевое слово PROGRAM, оно принадлежит таблице терминальных символов – 1, по таблице кодов определяется код, он равен 1.
3) Производится сравнение номеров таблиц, полученных на этапе 1 и этапе 2. Значения совпали.
4) Производится сравнение кодов таблиц. Значения совпали.
5) Во вторую ячейку первой строки формируемой таблицы переходов заносится указатель на таблицу 1, код 1 – «$1,1».
6) Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 2).
7) В грамматике БНФ начинает рассматриваться следующий элемент конструкции – нетерминальный символ .
8) Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1).
При несовпадении значений на этапах 3 и 4 происходит прекращение разбора, если только терминальный символ не является элементов массива ИЛИ – «|» (например ::= INTEGER | REAL | STRING) или не является необязательным элементом конструкции (например, PROGRAMprog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).
Для нетерминальных символов алгоритм примерно такой.
Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ является нетерминальным символом. В формируемой таблице переходов данные заносятся в третью ячейку первой строки.
1) Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы – 2 (таблица символических имен), спецификатор равен 1.
2) Конструкция, определяющая структуру нетерминального символа , в грамматике БНФ имеет номер 2.
3) В формируемой таблице переходов добавляется новая строка, где в первую ячейку заносится адрес возврата на ячейку, вызвавшую переход, смещенную на 1 вправо (в данном случае указывается переход на четвертую ячейку первой строки – «@1,4»).
4) Номер позиции в таблице кодов лексем не изменяется (остается равным 2).
5) В грамматике БНФ начинает рассматриваться следующий элемент конструкции – id (идентификатор).
6) Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (в данном примере строка 2, столбец 2).
Для идентификаторов алгоритм примерно такой.
Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции является первым ее элементом. В формируемой таблице переходов данные заносятся во вторую ячейку второй строки.
1) Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы – 2 (таблица символических имен), спецификатор равен 1.
2) Рассматривается первый элемент БНФ грамматики конструкции , этот элемент является идентификатором, следовательно является элементом таблицы символических имен – таблицы 2.
3) Производится сравнение номеров таблиц. Значения совпали.
4) Во вторую ячейку второй строки заносится указатель на таблицу 2, спецификатор 1 (его значение берется из таблицы кодов лексем) – «$2,1»
5) Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 3).
6) В грамматике БНФ начинает рассматриваться следующий элемент конструкции – терминальный символ «;».
7) Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1) – вторая строка, третья ячейка.
При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ – «|» (например ::= id | int | real | | () ) или не является необязательным элементом конструкции (например, PROGRAMprog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).
Если конструкция закончилась, то осуществляется переход на первую ячейку (ячейку возврата) текущей строки в формируемой таблице перехода. По значению адреса, содержащегося в ячейке возврата активной (готовой для внесения данных) стает ячейка с указанным номером строки и номером столбца. В грамматике БНФ осуществляется переход к элементу, следующему за элементом конструкции, который был определен в текущей конструкции. Например, после определения последнего элемента конструкции «;» осуществляется возврат к элементу, следующему за элементом, вызвавшим эту конструкцию. Возврат осуществлен на строку 1 грамматики БНФ, к элементу VAR, следующему за нетерминальным символом .
Для литералов алгоритм примерно такой.
Допустим, производится анализ шестнадцатого элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции является вторым элементом конструкции ИЛИ. В формируемой таблице переходов данные заносятся во вторую ячейку десятой строки.
1) Номер позиции в таблице кодов лексем равен 16. Производится чтение данных из шестнадцатого столбца таблицы кодов лексем. Полученное значение номера таблицы – 3 (таблица литералов), спецификатор равен 1.
2) Рассматривается второй элемент множества ИЛИ БНФ грамматики конструкции , этот элемент является литералом целого типа, следовательно является элементом таблицы литералов – таблицы 3.
3) Производится сравнение номеров таблиц. Значения совпали.
4) Во вторую ячейку десятой строки заносится указатель на таблицу 3, спецификатор 1 (его значение берется из таблицы кодов лексем) – «$3,1»
5) Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 17).
6) В грамматике БНФ начинает рассматриваться следующий элемент конструкции , т.к. он отсутствует это говорит о том, что конец конструкции.
7) Вызывается обработка конца конструкции.
При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ – «|» (например ::= id | int | real | | () ) или не является необязательным элементом конструкции (например, PROGRAMprog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).
Описание работы с элементами массива ИЛИ БНФ грамматики.
Если в БНФ грамматике встречается массив ИЛИ, перебор значений осуществляется с левого.
При возникновении ошибки при работе с одним из элементов массива ИЛИ осуществляется переход к следующему, находящемуся правее.
В случае, когда последний (крайний правый) элемент массива ИЛИ или значение в ячейке не удовлетворительно, происходит прекращение разбора программы.
В случае положительного результата (сравнение одного из элементов удачно или сравнение с конечным результатом переходов удачно) происходит переход на следующую лексему грамматики БНФ, на следующий элемент таблицы кодов лексем, на следующую ячейку (на 1 правее) формируемой таблицы переходов.
Ниже рассматривается пример программы.
Program prog1;
var a,b,c:integer;
begin
a:=1+b*(a–c);
end.
Полученная последовательность символов от программы LEXAN представлена в таблице 12.
Таблица 12 – Таблица выходных символов
№ п.п.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Таблица
1
2
1
1
2
1
2
1
2
1
1
1
1
2
1
Строка
1
1
27
2
2
29
3
29
4
31
5
27
3
2
28
№ п.п.
16
17
18
19
20
21
22
23
24
25
26
27
Таблица
3
1
2
1
1
2
1
2
1
1
1
1
Строка
1
32
3
34
35
2
33
4
36
27
4
30
По исходным данным, также используя таблицу кодов терминальных символов, заполняется таблица построений.
Для лучшего понимания заполнения формируемой таблицы переходов заполняется таблица построений. Обработка данных и заполнение таблицы процесс довольно трудоемкий, однако, надо понимать, что и для машины данный разбор является самой трудоемкой задачей. Здесь же процесс разбора программы максимально унифицирован. Дается возможность отследить все возможные (исходные) параметры (значения). Прервать заполнение таблицы построений можно в любой момент времени, а потом продолжить, не теряя логику переходов (построения).
Таблица построений состоит из нескольких разделов, они называются: шаги, таблица кодов лексем, имя в программе, элемент грамматики БНФ, результат сравнения, формируемая таблица переходов, выполненное действие.
В разделе «Шаги» перечисляются номера произведенных шагов. Раздел «Таблица кодов лексем» служит для отслеживания позиции в таблице кодов лексем и хранит значения таблицы и кода (или спецификатора) с которыми в дальнейшем происходит сравнение текущего элемента грамматики БНФ. Раздел «Элемент грамматики БНФ» содержит имя элемента, имя конструкции, в которую он входит, тип текущего элемента грамматики, номер таблицы, соответствующей ему, а также код (для терминальных символов), определенный по таблице кодов терминальных символов. В разделе «Формируемая таблица переходов» отслеживается текущая ячейка формируемой таблицы переходов, куда заносится формируемое значение, а также позиция следующей ячейки, с которой будет производиться работа на следующем шаге. В разделе «Выполненное действие» указывается выполненное действие.
Таблица построения предлагается как вспомогательное средство для заполнения формируемой таблицы переходов. Заполнять все шаги и ячейки в ней не обязательно, главное понять логику заполнения формируемой таблицы переходов. Приобретя опыт, в дальнейшем, можно обходиться без таблицы построений, заполняя формируемую таблицу переходов по БНФ грамматике, тексту программы, таблице кодов терминальных символов, таблице кодов лексем.
Из данных, полученных в разделе «Формируемая таблица переходов, текущая позиция» таблицы построения, заполняется формируемая таблица переходов. В результате должна получиться таблица 14.
Принятые сокращения в таблице построений.
НС – нетерминальный символ
ТС – терминальный символ
ИД – идентификатор
Лх – литерал, где х: Ц – целый тип, В – вещественный тип, С – строковый тип.
Л – литерал любого типа.
Наличие знака «–» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.
При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.
При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца – 1. Значение вносимого значения должно указывать на вторую ячейку последней пустой строки. Следующим шагом заполняется значение текущий позиции, адрес возврата и адрес следующей позиции. Например. После нахождения терминального символа начинает рассматриваться первый элемент конструкции – id. В формируемой таблице переходов последней свободной строкой является строка 2, на нее и осуществляется переход, следующая позиция указывает на строку 2, столбец 1 (шаг 2). На третьем шаге в ячейку возврата 2,1 (где 2 – номер строки, 1 – номер столбца) будет внесено значение, указывающее на ячейку 1,4, т.к. переход осуществлен из ячейки 1,3. Текущая позиция – 2,1, следующая позиция – 2,2.
При возврате возникают другие трудности. К примеру, при окончании конструкции происходит переход на пустую ячейку, затем осуществляется переход на ячейку возврата. Значение, заполненное в ячейке возврата ищется по таблице. По полученному значению осуществляется переход. Например, при окончании конструкции (шаг 20), текущей ячейкой оказывается ячейка 5,7. Затем производится переход в ячейку 5,1 (шаг 21). По таблице определяем, что адрес возврата @4,3 (значение из шага 14), т.е. перейти на четвертую строку, третий столбец.
продолжение
--PAGE_BREAK--
продолжение
--PAGE_BREAK--Продолжение таблицы 13
Шаги
Таблица кодов лексем
Имя в программе
Элемент грамматики БНФ
Результат сравнения
Формируемая таблица переходов
Выполненное действие
текущая позиция
следующая позиция
позиция
табл
код, специф
тип
имя
текущая конструкция
тип
табл
код
(для ТС)
строка
столбец
вносимое значение
строка
столбец
79
18
1
@17,3
18
2
80
21
2
2
ИД
а
id
ИД
2
+
18
2
$2,2
18
3
81
22
1
33
ТС
–
18
3
18
1
конец конструкции
82
22
1
33
ТС
–
18
1
17
3
переход
83
22
1
33
ТС
–
*
ТС
1
34
–
17
3
84
22
1
33
ТС
–
DIV
ТС
1
17
–
17
3
85
22
1
33
ТС
–
/
ТС
1
37
–
17
3
86
22
1
33
ТС
–
17
3
17
1
конец конструкции
87
22
1
33
ТС
–
17
1
16
3
переход
88
22
1
33
ТС
–
+
ТС
1
32
–
16
3
89
22
1
33
ТС
–
–
ТС
1
33
+
16
3
$1,33
16
4
90
23
2
4
ИД
с
НС
16
4
@19,2
19
1
91
23
2
4
ИД
с
19
1
@16,5
19
2
92
23
2
4
ИД
с
НС
19
2
@20,2
20
1
93
23
2
4
ИД
с
20
1
@19,3
20
2
94
23
2
4
ИД
c
id
ИД
2
+
20
2
$2,4
20
3
95
24
1
36
ТС
)
20
3
20
1
конец конструкции
96
24
1
36
ТС
)
20
1
19
3
переход
97
24
1
36
ТС
)
*
–
19
3
98
24
1
36
ТС
)
DIV
–
19
3
99
24
1
36
ТС
)
/
–
19
3
100
24
1
36
ТС
)
19
3
19
1
конец конструкции
101
24
1
36
ТС
)
19
1
16
5
переход
102
24
1
36
ТС
)
+
ТС
1
32
–
16
5
103
24
1
36
ТС
)
–
ТС
1
33
–
16
5
104
24
1
36
ТС
)
16
5
16
1
конец конструкции
105
24
1
36
ТС
)
16
1
15
4
переход
106
24
1
36
ТС
)
)
ТС
1
36
+
15
4
$1,36
15
5
107
25
1
27
ТС
;
15
5
15
1
конец конструкции
108
25
1
27
ТС
;
15
1
13
5
переход
109
25
1
27
ТС
;
*
ТС
1
34
–
13
5
110
25
1
27
ТС
;
DIV
ТС
1
17
–
13
5
111
25
1
27
ТС
;
/
ТС
1
37
–
13
5
112
25
1
27
ТС
;
13
5
13
1
конец конструкции
113
25
1
27
ТС
;
13
1
10
5
переход
114
25
1
27
ТС
;
+
ТС
1
32
10
5
115
25
1
27
ТС
;
–
ТС
1
33
10
5
116
25
1
27
ТС
;
10
5
10
1
конец конструкции
117
25
1
27
ТС
;
10
1
9
5
переход
Продолжение таблицы 13
Шаги
Таблица кодов лексем
Имя в программе
Элемент грамматики БНФ
Результат сравнения
Формируемая таблица переходов
Выполненное действие
текущая позиция
следующая позиция
позиция
табл
код, специф
тип
имя
текущая конструкция
тип
табл
код
(для ТС)
строка
столбец
вносимое значение
строка
столбец
118
25
1
27
ТС
;
9
5
9
1
конец конструкции
119
25
1
27
ТС
;
9
1
8
3
переход
120
25
1
27
ТС
;
8
3
8
1
конец конструкции
121
25
1
27
ТС
;
8
1
7
3
переход
122
25
1
27
ТС
;
;
–ТС
1
27
+
7
3
$1,27
7
4
123
26
1
4
ТС
END
7
4
7
1
конец конструкции
124
26
1
4
ТС
END
7
1
1
8
переход
125
26
1
4
ТС
END
END
ТС
1
4
+
1
8
$1,4
1
9
126
27
1
30
ТС
.
.
ТС
1
30
+
1
9
$1,30
1
10
127
1
10
1
1
конец конструкции
128
1
1
Таблица 14 – Формируемая таблица переходов
1
2
3
4
5
6
7
8
9
10
1
PROGRAM
$1,1
@2,2
VAR
$1,2
@3,2
BEGIN
$1,3
@7,2
END
$1,4
.
$1,30
2
@1,4
prog1
$2,1
;
$1,27
3
@1,6
@4,2
;
$1,27
4
@3,3
@5,2
:
$1,31
@6,2
5
@4,3
a
$2,2
,
$1,29
b
$2,3
,
$1,29
c
$2,4
6
@4,5
INTEGER
$1,5
7
@1,8
@8,2
;
$1,27
8
@7,3
@9,2
9
@8,3
a
$2,2
:=
$1,28
@10,2
10
@9,5
@11,2
+
$1,32
@13,2
11
@10,3
@12,2
12
@11,3
1
$3,1
13
@10,5
@14,2
*
$1,34
@15,2
14
@13,3
b
$2,3
15
@13,5
(
$1,35
@16,2
)
$1,36
16
@15,4
@17,2
–
$1,33
@19,2
17
@16,3
@18,2
18
@17,3
a
$2,2
19
@16,5
@20,2
20
@19,3
c
$2,4
продолжение
--PAGE_BREAK--