Для распознавания нетерминального символа <read> необходимо чтобы было определение для нетерминального символа <id-list>. Это определение дается правилом 6 на рис. 4:
<id-list> ::= id { , id }
Эта нотация, означает, что конструкция, заключенная в фигурные скобки, может быть либо опущена, либо повторяться один или более число раз. Таким образом, правило 6 определяет нетерминальный символ <id-list> как состоящий из единственной лексемыid или же из произвольного числа следующих друг за другом лексемid, разделенных запятой. В соответствии с этим новым определением процедура, соответствующая нетерминальному символу <id-list>, сначала ищет лексемуid, а затем продолжает сканировать входной текст до тех пор, пока следующая пара лексем не совпадет с запятой иid. Такая запись устраняет проблему левой рекурсии.
Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. Дерево грамматического разбора оказывается неудобным в работе при работе при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно генерацией объектного кода внутреннее представление программы преобразуется в одну из соответствующих форм записи.
Примерами таких форм записи являются:
- обратная польская запись операций;
- тетрады операций;
- триады операций;
- собственно команды ассемблера.
Обратная польская запись - это постфиксная запись операций. Преимуществом ее является то, что все операции записываются непосредственно в порядке их выполнения. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрады представляют собой запись операций в форме из четырех составляющих:
<операция>(<операнд1>,<операнд2>,<результат>).
Тетрады используются редко, так как требуют больше памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя операндами.
Триады представляют собой запись операций в форме из трех составляющих: <операция>(<операнд1>,<операнд2>), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение 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
Из сформированных четверок нетрудно сгенерировать машинный код.
Создание учебного комплекса обосновано сложностью предметной области создания компиляторов и отсутствием подобного наглядного материала, позволяющего поэтапно отследить процессы, происходящие в компиляторе (работа анализаторов, заполнение таблиц).
Из описанного выше материала видно, что компиляторы имеют очень много вариантов построения, это определяет дополнительную сложность при выборе оптимальной структуры компилятора. Процесс компиляции довольно сложен и труден для восприятия в целом. Он содержит в себе множество понятий, подходов обработки, методов разбора, таблиц, формальные грамматики. Поэтому целесообразно разбиение комплекса на ряд лабораторных работ, в которых будут описаны практические методики изучения различных этапов компиляции на основе специальных обучающих программ.
На текущий момент существует множество разработок, связанных с созданием компиляторов. В основном это методические, учебные пособия по проектированию компиляторов, где рассматриваются основные принципы анализа текста программы и синтеза объектного кода. В основном в этих материалах приводятся примеры как написать оптимальную программу компиляции по скорости, используя стеки, таблицы предшествования и т.п. структуры, не позволяющие или затрудняющие передавать данные между этапами как требуется в учебном комплексе.
Работа с методическим (теоретическим) материалом подразумевает выполнение задания с дальнейшей проверкой преподавателем, что затрачивает его время и силы. Программная реализация дает возможность самому проконтролировать себя на правильность проведенного анализа или корректность синтезированного кода.
Руководство по написанию компиляторов Креншоу [5] позволяет создать свой компилятор, но его особенностью является прямой перевод считанного текста в выходной код, что не дает наглядности внутреннего представления компилятора. Этот компилятор является однопроходным, он не хранит и создает в памяти таблиц, вся обработка описывается в процедурах.
Существующие компиляторы не дают наглядное представление внутренних структур, а обычно имеют один исполняемый файл, реализующий перевод текста программы в объектный или исполняемый файл. Ставка обычно делается либо на скорость компиляции, либо на минимальный размер генерируемого файла.
Компиляторы компиляторов в основной своей массе создают лишь лексические анализаторы, оставляя дорабатывать синтаксическую часть самому программисту. При обзоре не было найдено российских разработок компиляторов компиляторов, что так же говорит о том, что при работе с существующими разработками добавится еще одна проблема – проблема языка.
Разработка является учебным комплексом, включающим в себя лабораторные работы по изучению процесса компиляции. Это программа, позволяющая без руководителя выполнять и проверять выданные задания (проверять выполненные задания). Теоретический материал для проведения лабораторной работы сформирован в методической (описательной) части.
Особенность данной разработки в том, что спроектированный компилятор построен поэтапно (модульно). Результат работы каждого из этапов может быть зафиксирован (сохранен) в виде файла с определенной структурой. Это файл с промежуточным кодом, получаемый от сканера, файл с формируемой таблицей переходов (хранит структуру дерева), файл с промежуточным кодом (тетрады), ассемблерный код. На каждом из этапов имеется возможность генерации файла отчета со структурами, с описанием и указанием ошибок, а также дополнительной служебной информацией.