упражнении 5.19 главы 5, получает входные данные с клавиатуры. Она должна быть модифицирована для чтения из файла, чтобы уметь запускать программы, полученные с помощью нашего компилятора.

Компилятор Простотрона выполняет два прохода для преобразования программы на ЯП в программу на ЯМП. При первом проходе создается таблица символических имен (объект), в которой каждый номер строки (тоже объект), имя переменной (объект) и константа (объект) программы на ЯП хранится со своим типом и соответствующим местом расположения в результирующем коде ЯМП (таблица символических имен детально рассматривается ниже). Первый проход генерирует также объекты соответствующих инструкций ЯМП для каждого оператора ЯП. Как мы увидим позже, если программа ЯП содержит операторы, которые передают управление какой-либо строке программы, то в результате первого прохода в программе на ЯМП могут иметься некоторые незавершенные инструкции. Второй проход компилятора завершает ранее незавершенные инструкции и выводит результирующую программу на ЯМП в файл.

файл на ЯП

Рис. 15.24. Написание, компиляция и выполнение программы на ЯП

Первый проход

Компилятор начинает работу с чтения в память первого оператора программы на ЯП. Эта строка должна быть разделена на отдельные лексемы (т.е. смысловые части оператора) для дальнейшей обработки и компиляции (для упрощения этой задачи может быть использована стандартная библиотечная функция strtok). Вспомните, что каждый оператор начинается с номера строки, после которого следует команда. После того, как компилятор разбивает оператор на лексемы, те лексемы, которые являются номером строки, переменной или константой, помещаются в таблицу символических имен. Следует отметить, что номер строки помещается в таблицу символических имен только в случае, если он является первой лексемой в операторе. Объект symbolTable (таблица символических имен) является массивом объектов типа tableEntry, представляющих каждый символ в программе. Па число символов, которые могут появиться в программе, ограничений не существует. Следовательно, таблица символических имен symbolTable для конкретной программы может быть довольно большой по объему. Давайте

создадим таблицу символических имен symbolTable на 100 элементов. Вы можете увеличить или уменьшить ее размер после того, как программа заработает.

Каждый объект tableEntry содержит три элемента. Элемент symbol является целым, содержащим или код ASCII имени переменной (вспомним, что имена переменных являются одиночными символами), или номер строки, или константу. Элемент type является одним из следующих символов, указывающих на тип элемента symbol: С - константа, L - номер строки и V - переменная. Элемент location содержит ячейку памяти (адрес) Простотрона (от 00 до 99), на которую ссылается данный объект tableEntry. Память Простотрона является массивом из 100 целых чисел, в котором хранятся инструкции ЯМП и данные. Если tableEntry является номером строки, то location указывает элемент массива в памяти Простотрона, в котором начинается инструкция ЯМП для этого оператора ЯП. Для tableEntry, являющихся переменными и константами, location указывает элемент массива в памяти Простотрона, в котором эта переменная или константа хранится. Переменные и константы размещаются в памяти Простотрона, начиная с последней ячейки по направлению к первой ячейке: первая переменная или константа хранится в ячейке 99, следующая - в ячейке 98 и т.д.

Таблица символических имен играет решающую роль в преобразовании программ на ЯП в программы на ЯМП. В главе 5 мы узнали, что инструкция ЯМП представляет собой четырехзначное число, состоящее из двух частей: кода операции и операнда. Код операции определяется командой ЯП. Например, команда ЯП input соответствует коду операции ЯМП 10 (читать), а команда print - коду 11 (записать). Операнд - это ячейка памяти, содержащая данные, с которыми работает операция (например, операция с кодом 10 читает значение с клавиатуры и заносит его в ячейку памяти, заданную операндом). Компилятор просматривает symbol-Table и ищет для каждого символа соответствующую ячейку памяти Простотрона, которая и используется для окончательного оформления команды ЯМП.

Компиляция каждого оператора ЯП зависит от его команды. Например, после того, как номер строки оператора rem помещается в таблицу символических имен, остальные символы оператора комментариев компилятор игнорирует, так как они предназначены только для пояснений операторов программы. Операторы input, print, goto и end соответствуют командам ЯМП read, write, branch (для указанной ячейки) и halt. Операторы, содержащие эти команды ЯП, непосредственно преобразуются в соответствующие инструкции ЯМП (заметим, что оператор goto может содержать пока неразрешенную ссылку, если указанный номер строки ссылается на один из последующих операторов в файле программы на ЯП; это иногда называют ссылкой вперед).

Когда оператор goto компилируется с неразрешенной ссылкой, инструкция ЯМП должна быть помечена флагом, чтобы при втором проходе компилятора программа завершила эту инструкцию.

Флаги хранятся в массиве flags из 100 элементов типа int, в котором каждому элементу задано начальное значение -1. Если ячейка памяти, на которую ссылается номер строки в программе на ЯП, еще неизвестна, (т.е., если ее нет в таблице символических имен), то номер этой строки заносится в массив flags в элемент с индексом, соответствующим незавершенной команде. Операнд незавершенной команды устанавливается временно на 00. Например, оператор безусловного перехода, делающий ссылку вперед, оставляется равным -1-4000 до второго прохода компилятора, который скоро будет рассмотрен.

Компиляция операторов if/goto и let является более сложной, чем компиляция других операторов, поскольку это единственные операторы, которые соответствуют более, чем одной инструкции ЯМП. Для оператора if/goto компилятор должен генерировать код проверки условия и код передачи управления в зависимости от результатов проверки. К тому же эта передача управления может быть неразрешенной ссылкой. Каждая из операций отношения может быть смоделирована с помощью команд ЯМП перехода по нулю (branchzero) и перехода по отрицательному значению (branchnegative).

Для оператора let компилятор создает код выполнения произвольных арифметических операций с комплексными числами, содержащими целые переменные и константы. Выражения должны отделять каждый операнд от символа операции пробелами. В упражнениях 15.12 и 15.13 представлены алгоритмы преобразования инфиксного выражения в постфиксное и вычисления постфиксного выражения, используемые компиляторами для вычисления выражения. Прежде, чем разрабатывать компилятор, вам следует выполнить эти два упражнения. Когда компилятор встречает выражение, он преобразует его из инфиксной записи в постфиксную, а затем вычисляет постфиксное выражение.

Как компилятор может создавать машинный код для вычисления выражения, содержащего переменные? Алгоритм расчета постфиксного выражения можно модифицировать так, чтобы компилятор не производил вычисление выражения, а генерировал бы инструкции ЯМП. Чтобы ввести это добавление в компилятор, необходимо модифицировать алгоритм вычисления постфиксного выражения, введя в него поиск встречающихся в выражении переменных и констант в таблице (или вставку их в таблицу, если их там еще нет), определение соответствующей ячейки памяти, связанной с этой переменной или константой, и размещение в стеке адреса этой ячейки памяти (вместо значения константы, как это было в исходном алгоритме). Когда в постфиксном выражении встречается операция, то из вершины стека выталкиваются два адреса и генерируется инструкция ЯМП, использующая эти адреса как операнды. Результат каждого подвыражения временно сохраняется в памяти и адрес этой временной ячейки помещается обратно в стек, чтобы вычисление постфиксного выражения могло продолжаться. Когда вычисление постфиксного выражения завершено, адрес результата, является единственным оставшимся эле-