META II

META-II - A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE

BY D.V.Schorre

UCLA computing facility, University of California at Los Angeles Los Angeles, California

Предисловие к переизданию

Эта классическая статья описывает метакомпилятор, разработанный как проект Лос-Анджелесского отделения SIGPLAN, специальной группы по интересам Ассоциации вычислительной техники в области языков программирования. В опубликованном виде он содержал несколько артефактов того времени, чтобы приспособиться к ограниченному набору символов клавишного перфоратора IBM 026, за исключением их удаления, указания в тексте статьи зарезервированных слов с помощью выделения жирным шрифтом и незначительного изменения синтаксиса VALGOL-I — никаких изменений не было сделано. Оригинальная Meta-II работала на IBM 1401, машине с ограниченными возможностями по сегодняшним меркам: в частности, отсутствие режимов индексированной адресации усложняет обработку процедур в среде выполнения, которая должна быть предоставлена для демонстрационных программ.

Чтобы установить систему Meta-II, необходимо вручную скомпилировать компилятор Meta-II, приведенный в статье (само по себе поучительное упражнение), и написать интерпретатор для машины Meta-II на каком-либо подходящем языке; для проверки реализации компилятор должен скомпилировать себя в точности — если он терпит неудачу, то либо интерпретатор, либо ручная компиляция неисправны. Это упражнение открывает интересные возможности, если интерпретатор может быть закодирован на языке, который сам может быть скомпилирован Meta-II, поскольку тогда вся система может быть перенесена на новую машину с минимальными усилиями.

Несмотря на свой возраст, Meta-II остается полезным введением в синтаксически-управляемую компиляцию, и из-за простоты используемой нотации он сравнительно понятен для неспециалистов в области компьютеров. Однако он имеет ограниченное применение в контексте современных языков, поскольку не существует механизма распознавания и обеспечения типизации переменных, а распознавание значений и параметров переменных отложено до времени выполнения, что малополезно на компьютерах, где невозможно отличить элемент данных от адреса.

MMLl @ LUT 28/2/87

Введение

META-II — это язык написания компиляторов, который состоит из синтаксических уравнений, напоминающих нормальную форму Бэкуса, и в который вставляются инструкции для вывода команд языка ассемблера. Компиляторы были написаны на этом языке для VALGOL-I и VALGOL-II. Первый — это простой алгебраический язык, разработанный для иллюстрации META-II. Последний состоит из довольно большого подмножества ALGOL-60.

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

META-II не предназначен как стандартный язык, который каждый будет использовать для написания компиляторов. Скорее, это пример простого рабочего языка, который может дать хороший старт в проектировании компилятора, пишущего компилятор, подходящего для его собственных нужд. Действительно, компилятор META-II написан на своем собственном языке, поэтому его можно модифицировать.

История

Основные идеи, лежащие в основе META-II, были описаны в серии из трех статей Шмидта [1], Меткалфа [2] и Шорре [3]. Эти статьи были представлены на Национальном конгрессе A.C.M. в 1963 году. Конвенция в Денвере, и представляла собой деятельность Рабочей группы по синтаксически-направленным компиляторам Лос-Анджелесского SIGPLAN. Методы, используемые этой группой, похожи на методы Гленни [4] и Конвея [5], но отличаются в одном важном отношении. Оба этих исследователя выразили синтаксис в форме диаграмм, которые они впоследствии закодировали для использования на компьютере. В случае META-II синтаксис вводится в компьютер в нотации, напоминающей нормальную форму Бэкуса. Метод синтаксического анализа, обсуждаемый в этой статье, полностью отличается от метода, используемого Айронсом [6] и Бастьеном [7]. Все эти методы можно проследить до математического изучения естественных языков, как описано Хомским [8].

Синтаксическая нотация (уравнение)

Используемая здесь нотация похожа на метаязык отчета ALGOL-60. Символы в целевом языке представлены в виде строк символов, окруженных кавычками. Металингвистические переменные имеют ту же форму, что и идентификаторы в ALGOL, а именно, буква, за которой следует последовательность букв или цифр. Элементы записываются последовательно, чтобы указать конкатенацию, и разделяются чертой, чтобы указать чередование. Каждое уравнение заканчивается точкой с запятой. Пример синтаксического уравнения:

LOGICALVALUE = TRUE | FALSE;

Чтобы указать, что синтаксический элемент является необязательным, его можно чередовать со словом EMPTY. Например:

SUBSECONDARY = ’*’PRIMARY |

EMPTY; SECONDARY = PRIMARY

SUBSECONDARY;

Путем факторизации эти два уравнения можно записать как одно уравнение.

SECONDARY = PRIMARY(’*’PRIMARY | EMPTY);

В язык Meta-II встроена возможность распознавать три символа:

Идентификаторы – представлены ID,
Строки – представлены STRING,
Числа – представлены NUMBER.

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

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

Теперь у нас достаточно определяющих синтаксические особенности языка META-II, чтобы мы могли рассмотреть простой пример в деталях.

Приведенный здесь пример представляет собой набор из четырех синтаксических уравнений для определения очень ограниченного класса алгебраических выражений. Два оператора, сложение и умножение, будут представлены как + и * соответственно. Умножение имеет приоритет над сложением, в противном случае приоритет указывается скобками. Вот несколько примеров:

Синтаксические уравнения, определяющие этот класс выражений, следующие:

EX3 = ID | ’(’ EX1 ’)’;

EX2 = EX3(’*’ EX2 |

EMPTY); EX1 = EX2(’+’

EX1 | EMPTY);

EX — это сокращение от выражения. Последнее уравнение, которое определяет выражение порядка 1, считается основным уравнением. Уравнения читаются таким образом. Выражение порядка 3 определяется как идентификатор или открывающая скобка, за которой следует выражение порядка 1, за которой следует закрывающая скобка. Выражение порядка 2 определяется как выражение порядка 3, за которым может следовать звездочка, за которой следует выражение порядка 2. Выражение порядка 1 определяется как выражение порядка 2, за которым может следовать плюс, за которым следует выражение порядка 1.

Хотя последовательности можно определять рекурсивно, удобнее и эффективнее иметь специальный оператор для этой цели.

Например, мы можем определить последовательность буквы A следующим образом:

SEQA = $’A’;

Приведенные ранее уравнения переписываются с использованием оператора последовательности следующим образом:

EX3 = ID | ’(’ EX1

’)’; EX2 = EX3 $(’*’

EX3); EX1 = EX2 $(’+’

EX2);

Вывод

До этого момента мы рассматривали нотацию в META-II, которая описывает синтаксис объектного языка. Для создания компилятора команды вывода вставляются в уравнения синтаксиса. Вывод компилятора, написанного в META-II, всегда находится на языке ассемблера, но не на языке ассемблера для 1401. Он предназначен для интерпретатора, такого как интерпретатор, который я называю машиной META-II, который используется для всех компиляторов, или интерпретаторов, которые я называю машинами VALGOL-I и VALGOL-II, которые, очевидно, используются с соответствующими им исходными языками. Для каждой машины требуется свой ассемблер, но основное различие между ассемблерами заключается в таблице кодов операций. Коды констант и объявления также могут быть разными. Все эти ассемблеры имеют одинаковый формат, который показан ниже.

LABEL CODE ADDRESS

1- -6 8- -10 12- -70

Запись на языке ассемблера содержит либо метку, либо код операции длиной до трех символов, но никогда и то, и другое. Метка начинается в столбце 1 и может продолжаться до столбца 70. Если запись содержит код операции, то столбец 1 должен быть пустым. Таким образом, метки могут быть любой длины и не прикрепляются к инструкциям, а встречаются между инструкциями.

Чтобы создать вывод, начинающийся в поле кода операции, мы пишем OUT, а затем заключаем информацию, которую нужно воспроизвести, в скобки. Строка используется для буквального вывода, а звездочка — для вывода специального символа, только что найденного во входных данных. Это проиллюстрировано следующим образом:

EX3 = ID OUT(’LD’*) | ’(’ EX1 ’)’;

EX2 = EX3 $(’*’ EX3 OUT(’MLT’));

EX1 = EX2 $(’+’ EX2 OUT(’ADD’));

Чтобы вызвать вывод в поле метки, мы пишем LABEL, а затем элемент для вывода. Например, если мы хотим проверить идентификатор и вывести его в поле метки, мы пишем

ID LABEL *

Компилятор META-II может генерировать метки вида A01, A02, A03,...A99, B01,... Чтобы сгенерировать такую метку, используется *1 или *2. При первой ссылке на *1 в любом синтаксическом уравнении будет сгенерирована и назначена метка. Эта же метка выводится всякий раз, когда в этом выполнении уравнения ссылаются на *1. Символ *2 работает таким же образом. Таким образом, для каждого выполнения любого уравнения может быть сгенерировано максимум две разные метки. Повторные выполнения, будь то рекурсивные или инициированные извне, приводят к контролируемой последовательности сгенерированных меток. Таким образом, все синтаксические уравнения вносят вклад в одну последовательность. Теперь приведен типичный пример, в котором метки генерируются для команд ветвления.

IFSTATEMENT = ’IF’ EXP ’THEN’

OUT(’BFP’*1) STATEMENT ’ELSE’

OUT(’B ’*2) LABEL *1 STATEMENT

LABEL *2;

Коды операций BFP и B являются порядками машины VALGOL-I и обозначают "branch false and pop" и "branch" соответственно. Уравнение также содержит ссылки на два других уравнения, которые явно не указаны, а именно EXP и STATEMENT.

VALGOL-I: простой компилятор, написанный на META-II

Теперь мы готовы к примеру компилятора, написанного на META-II. VALGOL-I — чрезвычайно простой язык, основанный на ALGOL-60, который был разработан для иллюстрации компилятора META-II.

Основная информация о VALGOL-I приведена на рисунке 1 (компилятор VALGOL-I, написанный на META-II) и рисунке 2 (список запросов машины VALGOL-I). Пример программы приведен на рисунке 3. После каждой строки программы показаны команды VALGOL-I, которые компилятор производит из этой строки, а также абсолютный интерпретируемый язык, созданный ассемблером. Рисунок 4 — это вывод из примера программы. Давайте изучим компилятор, написанный на META-II (рисунок 1), более подробно. Идентификатор PROGRAM в первой строке указывает, что это основное уравнение, и что управление передается туда в первую очередь. Уравнение для PRIMARY похоже на уравнение EX3 в нашем предыдущем примере, но здесь числа распознаются и воспроизводятся с помощью команды «load literal». TERM — это то, что раньше было EX2, а EXP1 — то, что раньше было EX1, за исключением распознавания минуса для вычитания. Уравнение EXP определяет оператор отношения «равно», который выдает значение 0 или 1 путем сравнения. Обратите внимание, что это обрабатывается так же, как арифметические операторы, но с более низким приоритетом. Команды условного перехода «branch true and pop» и «branch false and pop», которые выдаются функциями, определяющими UNTILST и CONDITIONALST соответственно, будут проверять верхний элемент в стеке и выполнять переход соответственно. «Оператор присваивания», определенный уравнением для ASSIGNST, является обратным по сравнению с соглашением в ALGOL-60, т. е. место, в которое должно быть перемещено вычисленное значение, находится справа. Обратите внимание также на то, что знак равенства используется для оператора присваивания, а точка равенства (.=) используется для отношения, обсуждаемого выше. Это связано с тем, что операторы присваивания более многочисленны в типичных программах, чем операторы сравнения равенства, и поэтому для более часто встречающегося выбирается более простое представление.

Отсутствие меток операторов в VALGOL-I и VALGOL-II кажется странным большинству программистов. Это было сделано не из-за какой-либо сложности в их реализации, а из-за неприязни к меткам операторов со стороны автора. Я программировал несколько лет, не используя ни одной метки, поэтому я знаю, что они излишни как с практической, так и с теоретической точки зрения. Тем не менее, было бы слишком большим отступлением пытаться оправдать этот момент здесь. Оператор «until» был добавлен для облегчения написания циклов без меток.

«Условный» оператор похож на тот, что в ALGOL-60, но здесь требуется предложение «else». Уравнение для «ввода/вывода», IOST, включает две команды, «edit» и «print». Слова EDIT и PRINT определены таким образом, что они будут выглядеть как подпрограммы, записанные в коде. «EDIT» копирует заданную строку в область печати с первым символом в позиции печати, которая вычисляется из заданного выражения. «PRINT» напечатает текущее содержимое области печати, а затем очистит ее до пробелов. Подача команды печати без предыдущих команд редактирования приводит к записи пустой строки.

IDSEQ1 и IDSEQ даны для упрощения синтаксического уравнения для DEC (объявление). Обратите внимание в определении DEC, что ветвь дана вокруг данных.

Из определения BLOCK можно увидеть, что то, что считается составным оператором в ALGOL-60, в VALGOL-I является особым случаем блока без объявления.

В операторе определения тест для IOST предшествует тесту для ASSIGNST. Это необходимо, потому что если бы этого не было сделано, слова PRINT и EDIT были бы ошибочно приняты за идентификаторы, и компилятор попытался бы перевести операторы «ввода/вывода» так, как если бы они были операторами «присваивания». Обратите внимание, что PROGRAM — это блок, и что стандартный набор команд выводится после каждой программы. Команда «halt» останавливает машину по достижении конца самого внешнего блока, который является программой. Код операции SP генерируется после команды «halt». Это полностью 1401-ориентированный код, который служит для установки метки слова в конце программы. Он не использовался бы, если бы VALGOL-I был реализован на машине с фиксированной длиной слова.

Как был написан компилятор META-II

Теперь мы переходим к самой интересной части этого проекта и рассмотрим, как компилятор META-II был написан на своем собственном языке. Интерпретатор, называемый машиной META-II, не намного длиннее 1401 программы, чем машина VALGOL-I. Синтаксических уравнений для META-II (рисунок 5) меньше, чем для машины VALGOL-I (рисунок 1).

Компилятор META-II, который является интерпретирующей программой для машины META-II, берет синтаксические уравнения, приведенные на рисунке 5, и создает версию этой же интерпретирующей программы на языке ассемблера. Конечно, чтобы начать это, мне пришлось написать первый компилятор, пишущий компилятор, вручную. После того, как программа была запущена, она могла создавать ту же программу, что и написанная вручную. Кто-то всегда спрашивает, действительно ли компилятор создал именно ту программу, которую я написал вручную, и я должен сказать, что это была «почти» та же самая программа. Я следовал синтаксическим уравнениям и пытался написать именно то, что собирался создать компилятор. К сожалению, я забыл одну из избыточных инструкций, поэтому результаты были не совсем такими же. Конечно, когда первый машинный компилятор скомпилировал себя во второй раз, он воспроизвел себя в точности.

Первоначально написанный вручную компилятор был для языка под названием META-I. Он использовался для реализации улучшенного компилятора для META-II. Иногда, когда я хотел изменить метаязык, я не мог описать новый метаязык непосредственно в текущем метаязыке. Тогда был создан промежуточный язык — тот, который мог быть описан в текущем языке и в котором мог быть описан новый язык. Я думал, что может потребоваться изменить вывод языка ассемблера, но, похоже, всегда можно избежать этого с помощью промежуточного языка.

Список запросов машины META-II приведен на рисунке 6.

Все подпрограммы в программах META-II являются рекурсивными. Когда программа входит в подпрограмму, стек сдвигается вниз на три ячейки. Одна ячейка предназначена для адреса выхода, а две другие — для меток, которые могут быть сгенерированы во время выполнения подпрограммы. Есть переключатель, который может быть установлен или сброшен инструкциями, которые ссылаются на входную строку, и это переключатель, на который ссылаются команды условного перехода.

Первое, что есть в любой программе машины META-II — это адрес первой инструкции. Во время инициализации интерпретатора этот адрес помещается в счетчик инструкций.

VALGOL-II написаный в META-II

VALGOL-II является расширением VALGOL-I и служит иллюстрацией довольно сложного языка программирования, реализованного в системе META-II. В машине VALGOL-II есть несколько функций, которые отсутствовали в машине VALGOL-I и которые требуют некоторого объяснения. В машине VALGOL-II адреса, а также числа помещаются в стек. Они соответствующим образом помечены, чтобы их можно было различить во время выполнения.

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

Формальный параметр процедуры хранится либо как адрес, либо как значение, которое вычисляется при вызове процедуры. Команда load должна пройти через любое количество косвенных адресов, чтобы поместить адрес числа в стек. Аргумент процедуры всегда является алгебраическим выражением. Если это выражение является переменной, значением формального параметра будет адрес, вычисленный при входе в процедуру.

Теперь описывается работа команды load. Она заставляет заданный адрес быть помещенным на вершину стека. Если содержимое этого верхнего элемента оказывается другим адресом, то он заменяется этим другим адресом. Это продолжается до тех пор, пока верхний элемент в стеке не станет адресом чего-то, что не является адресом. Это позволяет формальным параметрам ссылаться на другие формальные параметры на любую глубину. [Это нетривиальное упражнение на машине, где невозможно определить, является ли сохраненное слово данными или другим адресом. Большинство современных компиляторов генерируют соответствующий код, не прибегая к вычислениям во время выполнения, поскольку требования выражения известны вместе с относительным расположением (в терминах лексических уровней) данных во время компиляции.]

Между целыми и действительными числами не делается различий. Целое число — это просто действительное число, цифры справа от десятичной точки которого равны нулю. Переменные изначально имеют значение, называемое «undefined», и любая попытка использовать это значение будет обозначена как ошибка.

Оператор присваивания состоит из любого количества левых частей, за которыми следует правая часть. Для каждой левой части компилируется последовательность команд, которая помещает адрес на вершину стека. Правая часть компилируется в последовательность инструкций, которая оставляет на вершине стека либо число, либо адрес числа. После инструкции для правой части следует последовательность команд сохранения, по одной для каждой левой части. Первая команда этой последовательности — «сохранить и сохранить», а остальные — «обычные» команды сохранения. «Сохранение и сохранение» помещает число, которое находится на вершине стека (или на которое ссылается адрес на вершине стека) в регистр, называемый SAVE. Затем он сохраняет содержимое SAVE в адресе, который хранится в следующей за верхней позиции стека. Наконец, он выталкивает из стека два верхних элемента, которые он использовал. Число, однако, остается в SAVE для использования следующими командами сохранения. Большинство операторов присваивания имеют только одну левую часть, поэтому «обычные» команды сохранения производятся редко, в результате чего число, помещенное в SAVE, редко используется снова.

Метод вызова процедуры можно объяснить со ссылкой на иллюстрации 1 и 2. Аргументы, которые находятся в стеке, перемещаются на свое место [в переменную память] в верхней части процедуры. Если количество аргументов в стеке не соответствует количеству аргументов в процедуре, указывается ошибка. «Флаг» в стеке работает следующим образом. В машине VALGOL-II есть регистр флага. Чтобы установить флаг в стеке, содержимое этого регистра помещается на вершину стека, затем адрес слова над вершиной стека помещается в регистр флага. Первоначально и всякий раз, когда в стеке нет флагов, регистр флага содержит пробелы. В других случаях он содержит адрес слова в стеке, который находится прямо над самым верхним флагом. Непосредственно перед выполнением инструкции вызова регистр флага [устанавливается так, чтобы он] содержал адрес слова в стеке, который находится на два выше слова, содержащего адрес процедуры, которая должна быть выполнена. Инструкция вызова берет аргументы из стека, начиная с того, который хранится прямо над флагом, и продолжая до вершины стека. Аргументы перемещаются в соответствующие места в верхней части вызываемой процедуры. Выдается сообщение об ошибке, если количество аргументов в стеке не соответствует количеству мест в процедуре. Наконец, старый адрес флага, который находится чуть ниже адреса процедуры в стеке, помещается в регистр флага. Адрес выхода заменяет адрес процедуры в стеке, и все аргументы, а также флаг, выталкиваются. Есть всего два кода операции, которые влияют на регистр флага. Код «load flag» помещает флаг в стек, а код «call» извлекает его.

Библиотечная функция «WHOLE» усекает действительное число. Она не преобразует действительное число в целое, поскольку между ними не делается различий. Она заменяет рекомендуемую функцию «ENTIER» в первую очередь потому, что усечение требует меньше машинных инструкций для реализации. Кроме того, усечение, по-видимому, используется чаще. Процедуру ENTIER можно определить в VALGOL-II следующим образом:

PROCEDURE ENTIER(X);

IF 0 .L= X

THEN

WHOLE(X)

ELSE

IF WHOLE(X) .= X

THEN

ELSE

WHOLE(X)-1

"For" оператор в VALGOL-II отличается от ALGOL. Требуется ровно один элемент списка. Часть "step...until" элемента обязательна, но часть "while" может быть добавлена для немедленного завершения цикла при наступлении некоторого условия. Итерация продолжается до тех пор, пока значение переменной меньше или равно максимуму, независимо от знака приращения. Иллюстрация 3 является примером типичного "for" оператора. Блок-схема этого оператора приведена на иллюстрации 4.

Рисунок 7 представляет собой листинг компилятора VALGOL-II, написанного на META-II. Рисунок 8 представляет собой список заказов машины VALGOL-II. Пример программы для получения определителя приведен на рисунке 9.

Резервное копирование против отсутствия резервного копирования

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

С помощью резервного копирования можно описывать языки, которые невозможно описать без резервного копирования.

Даже для языка, который можно описать без резервного копирования, синтаксические уравнения часто можно упростить, если разрешено резервное копирование.

Преимущества, заявленные для отсутствия резервного копирования, следующие:

Синтаксический анализ выполняется быстрее.

Можно сказать, будут ли работать синтаксические уравнения, просто изучив их, не разбирая многочисленные примеры.

Тот факт, что сложные языки, такие как ALGOL и COBOL, могут быть реализованы без резервного копирования, указывается разными людьми, включая Conway [5], и они знают о преимуществах в скорости такого подхода. Я не видел упоминаний о втором преимуществе отсутствия резервного копирования, поэтому объясню это более подробно.

В основном, пишутся чередования, в которых каждый элемент начинается с другого символа. Тогда компилятор не может пойти по неправильному пути. Это усложняется из-за использования «EMPTY». За необязательным элементом никогда не может следовать что-то, начинающееся с того же символа, с которого он начинается.

Описанный выше метод — не единственный способ обработки резервного копирования. Стоит рассмотреть варианты, поскольку может быть найден способ, который будет иметь преимущества как резервного копирования, так и отсутствия резервного копирования.

Дальнейшее развитие языков META

Как упоминалось ранее, META-II не представлен как стандартный язык, а как отправная точка, из которой пользователь может разработать свой собственный язык META. Термин «язык META» с «META» заглавными буквами используется для обозначения любого языка написания компиляторов, разработанного таким образом.

Язык, который Шмидт [1] реализовал на PDP-1, был основан на META-I. Теперь он реализовал улучшенную версию этого языка для машины Бекмана.

Рутман [9] реализовал LOGIK, компилятор для моделирования по битам, на 7090. Он использует язык META для компиляции булевых выражений в эффективный машинный код. Шнайдер и Джонсон [10] реализовали META-3 на IBM 7094 с целью создания компилятора ALGOL, который генерировал бы эффективный машинный код. Они планируют язык META, который будет подходить для любого языка с блочной структурой. Этому языку написания компиляторов дали название META-4 (произносится как метафора).

References

Schmidt, L., "Implementation of a Symbol Manipulator for Heuristic Translation", 1963 ACM Natl. Conf., Denver, Colo.
Metcalfe, Howard, "A parameterized Compiler Based on Mechanical Linguistics", 1963 ACM Natl. Conf., Denver, Colo.
Schorre, Val, "A Syntax-Directed SMALGOL for the 1401", 1963 ACM Natl. Conf., Denver, Colo.
Glennie, A., "On the Syntax Machine and the Construction of a Universal Compiler", Tech. Report No. 2, Contract NR 049-141, Carnegie Inst. of Tech., July 1960.
Conway, Melvin E., "Design of a Separable Transition-Diagram Compiler", Comm. ACM, July 1963.
Irons, E.T., "The Structure and Use of the Syntax-Directed Compiler", Annual Review in Automatic Programming, The Macmillan Co., New York.
Bastian, Lewis, "A Phrase-Structured Language Translator", AFCRL-Rept-62-549, Aug. 1962.
Chomsky, Noam, "Syntax Structures", Mouton and Co., Publishers, The Hague, Netherlands.
Rutman, Roger, "LOGIK, A Syntax Directed Compiler for Computer Bit-Time Simulation", Master Thesis, UCLA, Au- gust 1964.
Schneider, F.W., and G.D. Johnson, "A Syntax-Directed Compiler-Writing Compiler to Generate Efficient Code", 1964 ACM Natl. Conf., Philadelphia.

XXXXXXXX Function header

XXXXXXXX

XXXXXXXX Transferred values

XXXXXXXX of arguments

00000000 Blank word to mark ‘the end of the arguments

XXXXXXXX Function body. Branch

XXXXXXXX commands cause control

XXXXXXXX to go around any data

XXXXXXXX stored in this area. Ends

XXXXXXXX with a "return" command.

Illustration 1: Storage Map for VALGOL-II Procedures

XXXXXXXX

XXXXXXXX Arguments in reverse order

XXXXXXXX

XXXX Flag

XXXXXXXX Address of procedure

Illustration 2: Map of the Stack Before Executing a Procedure Call Instruction

FOR I = 0 STEP 1 UNTIL N DO

[statement]

SET Set switch for first time through

A91

LD 1

FLP } Test for first

BFP A92 } time through.

LDL 0 } Initialise

SST } variable.

B A93

A92

LDL 1 } Increment

ADS } variable.

A93

RSR }

LD N } Compare variable

LEQ } to maximum.

A94

BFP A94 }

[statement]

RST } Reset switch for not 1st time through B A91

Illustration 3: Compilation of a Typical "for statement" in VALGOL-II

Space for Illustration 4 (flowchart)

Illustration 4: Flow-chart of the "for statement" Given in Illustration 3

[VALGOL-I is changed slightly to use integer rather than real variables.]

.SYNTAX PROGRAM

PRIMARY = .ID .OUT(’LD ’ *) | .NUMBER .OUT(’LDL’ *) | ’(’ EXP ’)’ ; TERM = PRIMARY $(’*’ PRIMARY .OUT(’MLT’) | ’/’ PRIMARY .OUT(’DIV’) ) ; EXP1 = TERM $(’+’ TERM .OUT(’ADD’) | ’-’ TERM .OUT(’SUB’) ) ;

EXP = EXP1 ( ’.=’ EXP1 .OUT(’EQU’) | .EMPTY) ; ASSIGNST = EXP ’=’ .ID .OUT(’ST ’ *) ;

UNTILST = ’.UNTIL’ .LABEL *1 EXP ’.DO’ .OUT(’BTP’ *2) ST .OUT(’B ’ *1) .LABEL *2 ;

CONDITIONALST = ’.IF’ EXP ’.THEN’ .OUT(’BFP’ *1) ST ’.ELSE’ .OUT(’B ’ *2) .LABEL *1 ST .LABEL *2 ; IOST = ’EDIT’ ’(’ EXP ’,’ .STRING .OUT(’EDT’ *) ’)’ | ’PRINT’ .OUT(’PNT’) ;

IDSEQ1 = .ID .LABEL * .OUT(’BLK 1’) ; IDSEQ = IDSEQ1 $(’,’ IDSEQ1) ;

DEC = ’.INTEGER’ .OUT(’B ’ *1) IDSEQ .LABEL *1 ;

.END T(VALGOL1,V1,META2) 4/1/87

Figure 1: The VALGOL-I Compiler Written in META-II

MACHINE CODES

LD aaa LOAD Put the contents of the address aaa on top of the stack.

LDL number LOAD LITERAL Put the given number on top of the stack.

ST aaa STORE Store the number which is on top of the stack into the address aaa and pop up the stack.

ADD ADD Replace the two numbers which are on top of the stack with their sum.

SUB SUBTRACT Subtract the number which is on top of the stack from the number which is next to the top, then replace them by the difference.

MLT MULTIPLY Replace the two numbers which are on top of the stack with their product.

DIV DIVIDE Divide the number which is on top of the stack into the number which is next to the top, and replace them by the quotient. The remainder is discarded.

EQU EQUAL Compare the two numbers on the top of the stack. Replace them by 1 if they are equal, or by 0 if not.

B aaa BRANCH Branch to the address aaa

BFP aaa BRANCH FALSE AND POP Branch to the address aaa if the top number on the stack is 0, otherwise continue in sequence. In either case, pop up the stack.BTP aaa BRANCH TRUE AND POP Branch to the address aaa if the top number is not 0.

EDT string EDIT Move the given string into the print buffer so that its first character falls on the print position given by the number on the top of the stack.

PNT PRINT Print the contents of the print buffer, followed by a line feed. Clear the buffer.

HLT HALT Return to the operating system.

CONSTANT AND CONTROL CODES

SP n SPACE Reserve n blank spaces in memory.

BLK nnn BLOCK Reserve a block for the storage of nnn numbers.

END END End of the program.

Figure 2: Order List of the VALGOL-I Machine ...

META II

Report Page