Этюды для программистов

27. Мал золотник, или... КОМПИЛЯТОР ДЛЯ АЛГЕБРАИЧЕСКОГО ЯЗЫКА

Компилятор — это всегда большая программа. Написать его, практически на пустом месте, даже под опекой преподавателей вовсе не просто. И хотя при создании Мини ставилась цель свести все муки к минимуму, во всяком случае, в той мере, в какой это позволяло его просветительское назначение, предлагаемая задача все же оказалась самой трудной в книге. Если вы (и ваши верные друзья) не обладаете достаточной энергией и временем, то не стоит за нее и браться.

Мини — универсальный, процедурный, алгебраический язык программирования. Он уходит своими корнями в Алгол, Алгол 68 и Паскаль. Подобно этим языкам, Мини предназначен для компиляции, загрузки и выполнения на обычных ЭВМ (хорошим примером такой машины служит УМ-1, см. гл. 25). Синтаксис задается контекстно-свободной грамматикой, пригодной для разбора методами LRA). Семантика аналогична алгольной и паскалевой, и нам кажется достаточным ее неформальное описание. Квалификация читателя позволит ему домыслить все недосказанное[54]. Ниже приведены логически связанные части грамматики и их семантика.

<единица компиляции>::=<программный сегмент>

| <единица компиляции> <программный сегмент>

<программный сегмент>::= <главная программа>

| <внешняя процедура>

<Единица компиляции> — это цепочка замкнутых <программных сегментов>[55]. Каждый <программный сегмент> есть либо <главная программа>, либо <внешняя процедура>. Все сегменты <единицы компиляции> свяжет друг с другом загрузчик, однако не обязательно, чтобы все сегменты, нужные для полной загрузки, компилировались вместе. При загрузке должна присутствовать ровно одна <главная программа>.

<главная программа> ::= <заголовокпрограммы><тело программы> <конец программы>

<заголовок программы>::= PROGRAM <идентификатор>

<тело программы>::= <тело сегмента>

<конец программы>::= END PROGRAM <идентификатор>;

Каждая <главная программа> именована, и закрывающее имя должно совпадать с открывающим. <Тело программы>, подобно большинству других сгруппированных инструкций, есть <тело сегмента> и может содержать все, что обычно свойственно программам. Заметим также, что резервированные слова, идентификаторы и константы не должны разрываться на границах записей. Их следует отделять друг от друга пробелами, знаками операций, комментариями или границами записей.

<внешняя процедура> ::= <внешняя подпрограмма>

| <внешняя функция>

<внешняя подпрограмма> ::= <заголовок внешней подпрограммы>:

<тело внешней подпрограммы>

<конец внешней подпрограммы>

<внешняя функция> ::= <заголовок внешней функции>:

<тело внешней функции> <конец внешней функции>

<заголовок внешней подпрограммы> ::= EXTERNAL PROCEDURE <имя внешней процедуры>

<заголовок внешней функции>::= EXTERNAL FUNCTION <имя внешней процедуры>

<внешний тип>

<имя внешней процедуры> ::= <идентификатор>

| <идентификатор> <список внешних параметров>

<список внешних параметров>::= <заголовок внешних параметров>)

<заголовок внешних параметров>::= (<внешний параметр>

| <заголовок внешних параметров>, <внешний параметр>

<внешний параметр>::= <идентификатор> <внешний тип>

| <идентификатор> <внешний тип> NAME

<внешний тип>::= <базовый тип>

<тело внешней подпрограммы>::= <тело сегмента>

<тело внешней функции>::= <тело сегмента>

<конец внешней подпрограммы>::= END EXTERNAL PROCEDURE <идентификатор>;

<конец внешней функции>::= END EXTERNAL FUNCTION <идентификатор>;

<Внешние процедуры> позволяют компилировать модули раздельно и собирать их вместе во время загрузки. При загрузке допускается лишь одна <внешняя процедура> с данным именем. <Внешние параметры> и возвращаемые <внешними функциями> значения должны иметь <базовый тип>. <Внешние параметры> передаются по значению, если они не помечены резервированным словом NAME; при наличии этого слова параметры передаются по имени. Перед <концом внешней подпрограммы> неявно располагается <инструкция возврата>, однако <внешние функции> должны завершать работу явной <инструкцией возврата> с возвращаемым значением; попытка выхода из <внешней функции> через <конец внешней функции> является семантической ошибкой, которую иногда можно обнаружить при компиляции. Единственной связью между переменными <внешней процедуры> и переменными вызывающей процедуры служит механизм передачи параметров. Однако во время сборки сегментов (например, с помощью загрузчика, подобного описанному в гл. 26) будет проверено совпадение типов формальных и фактических параметров, функций и возвращаемых значений.

Из описания <внешних процедур> усматривается несколько важных различий между Мини и современными языками. В коммерческом языке целесообразно обеспечивать средства для разделения деклараций всех видов между <программными сегментами>. На наш взгляд, усложнения, вносимые в язык такой возможностью, слишком велики по сравнению с педагогическим эффектом от их реализации: это же справедливо по отношению к расширению диапазона возможных типов параметров <внешних процедур>. С другой стороны, коммерческие языки в своем большинстве не допускают передачу параметров по имени (из соображений эффективности), в то время как студента, овладевшего механизмом передачи по имени, не смутить уже, кажется, ничем. Мини многословнее аналогичных языков, поскольку современные исследования[56] показали важность умело распределенной избыточности для исправления синтаксических ошибок. Кроме того, программист, пишущий на Мини, должен явно различать декларации подпрограмм и функций. Хотя компилятор и может самостоятельно выявить различие, язык заставляет программиста явно демонстрировать свои намерения.

Наконец, Мини позволяет полностью проверить совпадение типов во время компиляции и загрузки, следуя неписаному закону: во время выполнения нужно делать как можно меньше.

<тело сегмента>::= <раздел определения типов> <раздел декларации переменных> <раздел определения процедур> <раздел выполняемых инструкций>

<раздел определения типов>::= | <раздел определения типов> <определение типа>

<раздел декларации переменных>::= I <раздел декларации переменных> <декларация переменных>

<раздел определения процедур> ::= | <раздел определения процедур> <определение процедуры>

<раздел выполняемых инструкций>::=<выполняемая инструкция>

| <раздел выполняемых инструкций>

<выполняемая инструкция>

<Тело сегмента> состоит не менее чем из одной <выполняемой инструкции>, которой, возможно, предшествуют <определения типов>, <декларации переменных> и <определения процедур>. Область действия любого имени — вся оставшаяся часть тела данного сегмента; это имя можно использовать в следующих определениях и декларациях. Одно и то же имя нельзя декларировать или определять дважды в <теле сегмента>. Как и в Алголе, имя можно переопределить или передекларировать во внутреннем <теле сегмента>.

<определение типа>::= TYPE <идентификатор> IS <тип>

<тип>::== <базовый тип>

| <массивный тип>

| <структурный тип>

| <идентификатор типа>

<базовый тип> ::= INTEGER

| REAL

| BOOLEAN

| STRING

<массивный тип> ::= ARRAY <границы> OF <тип>

<границы>::= [<граничное выражение>] [<граничное выражение>: <граничное выражение>]

<граничное выражение>::= <выражение>

<структурный тип>::= STRUCTURE <список полей> END STRUCTURE

<список полей>::=<поле>

| <список полей>, <поле>

<поле>::== FIELD <идентификатор> IS <тип>

<идентификатор типа>::= <идентификатор>

<Определение типа> вводит для <типа> сокращение — <идентификатор>. В дальнейшем это сокращение можно использовать везде, где мог бы стоять <тип>. В набор типов входят встроенные <базовые типы>, однородные <массивные типы>, разнородные <структурные типы> и сокращения — <идентификаторы типов>. <Базовые типы> INTEGER и REAL могут отображаться на соответствующие аппаратные типы и подчиняться обычным правилам. <Базовый тип> BOOLEAN состоит всего из двух констант TRUE и FALSE. Элементами типа STRING являются цепочки литер произвольной длины, («степень произвола» может зависеть от реализации), но не менее нескольких тысяч. Массивы имеют одно измерение, однако их компоненты могут иметь произвольный тип, так что допускается декларация массива массивов массивов.... Если нижняя граница массива не задана явно, она полагается равной единице. <Граничные выражения> могут быть сколь угодно сложными, лишь бы их значение сводилось к типу INTEGER. В эти выражения могут входить только переменные, декларированные в объемлющих <телах сегментов> (но не в текущем <теле сегмента>) или в списке параметров объемлющей процедуры. Верхняя граница должна быть не меньше нижней. Там, где возможно, компилятор должен проверять это условие, однако в общем случае требуется проверка во время выполнения. Разные вхождения одинаковых <массивных типов> не рассматриваются компилятором как один и тот же <тип> при проверках совпадения типов. Чтобы допустить неоднократное использование, <массивный тип> нужно обозначить <идентификатором типа>. <Структурный тип> аналогичен записям в Паскале. <Идентификаторы> полей используются для именования элементов с <типами> полей. Поскольку определение рекурсивно, структуры могут иметь подструктуры. Конкретный <идентификатор> может именовать только одно <поле> <структурного типа>, однако допускается его использование и как имени переменной, и как имени поля другого (даже вложенного) <структурного типа>.

<декларация переменных>::= DECLARE <декларируемые имена> <тип>;

<декларируемые имена> ::== <идентификатор>

| <список декларируемых имен>>

<список декларируемых имен>::= <<идентификатор>

| <список декларируемых имен>, <идентификатор>

<Декларация переменных> наделяет <типом> <идентификаторы>, употребленные среди <декларируемых имен>. <Идентификаторы> не получают начальных значений. Имя <кроме имени поля> в <теле сегмента> может определяться или декларироваться не более одного раза.

<определение процедуры> ::= <определение подпрограммы>

|<определение функции>

|<определение внешней подпрограммы>

| <определение внешней функции>

<определение подпрограммы>::= <заголовок подпрограммы>: <тело подпрограммы> <конец подпрограммы>

<определение функции> ::= <заголовок функции>: <тело функции> <конец функции>

<определение внешней подпрограммы>::= <заголовок внешней подпрограммы>

<определение внешней функции>::=<заголовок внешней функции>;

<заголовок подпрограммы>::= PROCEDURE <имя процедуры>

<заголовок функции>::= FUNCTION <имя процедуры> <тип>

<тело подпрограммы>::= <тело сегмента>

<тело функции>::= <тело сегмента>

<конец подпрограммы>::= END PROCEDURE <идентификатор>;

<конец функции> ::= END FUNCTION <идентификатор>;

<имя процедуры>::= <идентификатор>

|<идентификатор> <список внутренних параметров>

<список внутренних параметров> ::= <заголовок внутренних параметров>)

<заголовок внутренних параметров> ::= (<внутренний параметр

|<заголовок внутренних параметров>, <внутренний параметр>

<внутренний параметр>::= <идентификатор> <тип>

| <идентификатор> <тип> NAME

Непосредственно в <теле сегмента> можно определить лишь одну процедуру с данным именем. Определение <внешней подпрограммы> или <внешней функции> дается только заголовком, поскольку тело <внешней процедуры> доставит та же или другая <единица компиляции>. В локальном и окончательном определении процедуры должны совпадать имя процедуры, порядок, тип и способ передачи формальных параметров; это соответствие проверит загрузчик. Напомним, что параметры <внешней процедуры> должны иметь <базовый тип>. Определение локальных процедур дается аналогично. <Внутренние параметры>, так же как и возвращаемые функциями значения, могут иметь любой <тип>. Перед <концом подпрограммы> располагается неявная <инструкция возврата>. Выход из функции должен осуществляться посредством явной <инструкции возврата>, снабженной значением. Параметры с пометкой NAME передаются по имени, остальные — по значению. Сами по себе процедуры напоминают алгольные. Рекурсия допускается в полном объеме. <Имя процедуры> нельзя использовать до его декларации.

<выполняемая инструкция>::=<инструкция присваивания>

|<инструкция вызова>

|<инструкция возврата>

|<инструкция завершения>

|<условная инструкция>

|<составная инструкция>

|<инструкция цикла>

|<инструкция выбора>

|<инструкция возобновления>

|<инструкция выхода>

|<инструкция ввода>

|<инструкция вывода>

|<пустая инструкция>

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

<инструкция присваивания>::= SET <список целей> <выражение>;

<список целей>::=<цель>

|<список целей> <цель>

<цель> ::=<переменная> <заменить на>

<заменить на>::—:=

В <инструкции присваивания> <тип> всех <целей> и <тип> присваиваемого <выражения> должен быть одним и тем же. <Цели> обрабатываются слева направо, чтобы определить адреса в памяти, и только затем вычисляется выражение, чтобы найти запоминаемое значение. Структуры и массивы можно присваивать в случае совпадения <типов>. Использование ключевого слова SET служит примером многословности Мини. Данная избыточность помогает исправлению, когда неправильно записано другое ключе вое слово (распространенная ошибка).

<инструкция вызова>::= CALL <обращение к процедуре>;

<обращение к процедуре> ::= <идентификатор процедура>

|<идентификатор процедуры> <список фактических параметров>

<идентификатор процедуры>::= <идентификатор>

<список фактических параметров> ::= <заголовок фактических параметров>)

<заголовок фактических параметров>::=(<<выражение>

|<заголовок фактических параметров>, <выражение>

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

<инструкция возврата> ::= RETURN;

| RETURN <выражение>;

<Инструкция возврата> может употребляться только в процедуре. Она возвращает управление в вызывающую инструкцию, В конце подпрограммы имеется неявная <инструкция возврата>. При возврате из подпрограммы значение указывать нельзя. При возврате из функции значение указывать обязательно. Оно должно иметь тот же тип, что и функция.

<инструкция завершения>::= EXIT;

Данная инструкция вызывает нормальное завершение всей программы и возврат в супервизор. Она должна быть последней выполненной (не обязательно последней написанной) инструкцией <программы>.

<условная инструкция> ::= <простая условная инструкция>

|<метка> <простая условная инструкция>

<простая условная инструкция>::= <спецификация условия> <истинная ветвь> FI;

|<спецификация условия> <истинная ветвь> <ложная ветвь> FI;

<спецификация условия> ::= IF <выражение>

<истинная ветвь>::=THEN <тело условной инструкции>

<ложная ветвь> ::= <иначе> <тело условной инструкции>

<иначе>::= ELSE

<тело условной инструкции> ::= <тело сегмента>

В <условной инструкции> выбирается и выполняется <истинная ветвь> или <ложная ветвь> в зависимости от истинности <выражения> типа BOOLEAN. Каждая ветвь представляет собой <тело сегмента> и может содержать все необходимые определения, декларации и инструкции без дополнительных скобок. После выполнения выбранной ветви управление передается на инструкцию, следующую за условной.

<составная инструкция> ::=<простая составная инструкция>

|<метка> <простая составная инструкция>

<простая составная инструкция>::<заголовок составной инструкции> <тело составной инструкции> <конец составной инструкции>

<заголовок составной инструкции>::= BEGIN

<тело составной инструкции> ::= <тело сегмента>

<конец составной инструкции> ::= END;

|END <идентификатор>;

Другие возможности, заложенные в синтаксисе Мини, делают <составные инструкции> не особенно необходимыми. Однако <составные инструкции> полезны в сочетании с инструкциями REPEAT и REPENT. В начало составной инструкции можно поместить декларации и определения. Если после END записан <идентификатор>, он должен быть <меткой>, причем <метка> и <идентификатор> обязаны совпадать.

Рисунок 27.1. Определение на метаМини, позволяющее понять действие <инструкции цикла>. Это «определение» влечет за собой обязательное перевычисление <цели цикла>.

<инструкция цикла>::= <простая инструкция цикла>

|<метка> <простая инструкция цикла>

<простая инструкция цикла>::= <заголовок цикла> <тело цикла> <конец цикла>

<заголовок цикла>::= <для> <цель цикла> <управление> DO

<тело цикла> ::= <тело сегмента>

<конец цикла>::= END FOR;

|END FOR <идентификатор>;

<для>::= FOR

<цель цикла>::= <переменная> <заменить на>

<управление>::= <шаговое управление>

|<шаговое управление> <условное управление>

<шаговое управление> ::= <начальное значение> <шаг>

|<начальное значение> <предел>

|<начальное значение> <шаг> <предел>

<начальное значение>::= <выражение>

<шаг>::= BY <выражение>

<предел>::= ТО <выражение>

<условное управление>::= WHILE <выражение>

Проще всего объяснить поведение <инструкции цикла>, написав на «метаМини» небольшой фрагмент, заменяющий эту инструкцию. Чтобы найти результат работы <инструкции цикла>, нужно применить к ней «определение», данное на рис. 27.1. Подчеркнем, что, согласно этому определению, <цель цикла>, <предел> и <шаг> перевычисляются при каждом повторении. Предикат «существует» позволяет метаМини узнать, присутствуют ли соответствующие необязательные части в конкретной <инструкции цикла>. Если употреблен закрывающий <идентификатор>, он должен совпадать с <обязательно присутствующей> <меткой>.

В данном определении <инструкции цикла> педагог вновь победил практика. Динамическое переопределение управляющих значений унаследовано из Алгола; большинство других языков отказалось от этого по соображениям эффективности. Однако, если вы сможете реализовать динамическое определение, полученных знаний с избытком хватит на построение более простых статических циклов. Шаговый и условный циклы соединены в одной инструкции, чтобы сделать Мини поменьше; в реальном языке их можно разделить. Соблюдайте осторожность при повторной обработке <цели цикла>; если цель — это формальный параметр или элемент массива, при каждом повторении за целью могут скрываться различные переменные.

<инструкция выбора>::=<простая инструкция выбора>

|<метка> <простая инструкция выбора>

<простая инструкция выбора> ::= <заголовок инструкции выбора> <тело инструкции выбора> <конец инструкции выбора>

<заголовок инструкции выбора> ::= SELECT <выражение> OF

<тело инструкции выбора>::=<список случаев>

|<список случаев> <прочие случаи>

<конец инструкции выбора> ::= END SELECT;

|END SELECT <идентификатор>;

<список случаев> ::= <случай>

|<список случаев> <случай>

<случай> ::= <заголовок случая> <тело случая>

<заголовок случая> ::= CASE <селектор>:

<селектор>::= <заголовок селектора>)

<заголовок селектора>::= <<выражение>

|<заголовок селектора>, <выражение>

<прочие случаи>::=<заголовок прочих случаев> <тело случая>

<заголовок прочих случаев> ::= OTHERWISE:

<тело случая> ::= <тело сегмента>

<Инструкция выбора> работает следующим образом.

Вычисляется <выражение> в <заголовке инструкции выбора>. Обрабатываются все <случаи>, от первого до последнего, в <списке случаев>. Для каждого <случая>, слева направо, одно за другим вычисляются <выражения> в <селекторе>. Как только <выражение> вычислено, его значение сравнивается со значением первоначального <выражения> из <заголовка инструкции выбора>. Если они равны, выполняется соответствующее <тело случая>; на этом <инструкция выбора> завершает свою работу, и управление передается на следующую < инструкцию>.

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

Типы всех выражений, используемых для выбора <случая>, должны быть одинаковы. Если в конце <инструкции выбора> употреблен <идентификатор>, он должен совпадать с <обязательно присутствующей> <меткой> <инструкции выбора>.

<инструкция возобновления>::=REPEAT <идентификатор>;

<инструкция выхода>::=REPENT <идентификатор>;

<Инструкция возобновления> вызывает возврат управления на начало объемлющего тела инструкции, помеченной <идентификатором>. Выполнение всех промежуточных объемлющих тел сегментов и инструкций, частями которых эти тела являются, завершается, как если бы произошел нормальный выход из них. Вся связанная с ними память разрушается. <Метка>, на которую выполняется переход, должна принадлежать той же процедуре, что и <инструкция возобновления>. Если не существует объемлющей инструкции с указанной меткой, <инструкция возобновления> рассматривается как семантически ошибочная. Семантика <инструкции выхода> аналогична, с той лишь разницей, что управление передается не на начало помеченной инструкции, а в точку, непосредственно следующую за помеченной объемлющей инструкцией. Заметим, что <инструкция возобновления> вызывает повторное выполнение инструкции, на начало которой передается управление.

<инструкция ввода>::= INPUT <список ввода>;

<список ввода> ::= <переменная>

|<список ввода>, переменная>

<инструкция вывода>::== OUTPUT <список вывода>;

<список вывода>::= <выражение>

|<список вывода> <выражение>

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

<пустая инструкция>::=;

<метка>::=<идентификатор>:

<Пустая инструкция> не вызывает никаких действий. <Метка> — это <идентификатор>, который декларируется своим использованием и в данном <теле сегмента> не может декларироваться или определяться иначе, как имя поля.

<выражение>::= <выражение один>

|<выражение>

| <выражение один>

|<выражение> XOR <выражение один>

<выражение один>::= <выражение два>

|<выражение один> & <выражение два>

<выражение два> ::= <выражение три>

| NOT <выражение три>

<выражение три> ::= <выражение четыре>

|<выражение три> <отношение> <выражение четыре>

<выражение четыре>::= <выражение пять>

|<выражение четыре> || <выражение пять>

<выражение пять>::= <выражение шесть>

|<выражение пять> <аддитивный оператор> <выражение шесть>

|<аддитивный оператор> <выражение шесть>

<выражение шесть>::= <выражение семь>

|<выражение шесть> <мультипликативный оператор> <выражение семь>

<выражение семь>::= FLOOR (<выражение>)

|LENGTH (<выражение>)

|SUBSTR (<выражение>, <выражение>, <выражение>)

|CHARACTER (<выражение>)

|NUMBER (<выражение>)

|FLOAT (<выражение>)

|FIX (<выражение>)

|<выражение восемь>

<выражение восемь>::= <переменная>|

<константа>

|<вызов функции>

|(<выражение>)

Выражения трактуются совершенно стандартным образом. Операнды операторов ||, XOR (исключающее или), & и NOT должны иметь тип BOOLEAN. Два произвольных элемента одного типа можно сравнить посредством <отношения> равенства и неравенства. Цепочки литер можно сравнить посредством любого <отношения>. Две цепочки равны тогда и только тогда, когда они в точности одинаковы. Цепочка А меньше цепочки В, если начало А равно началу В и в А больше нет литер или очередная литера А предшествует очередной литере В в алфавитной упорядоченности. Два любых целых или вещественных числа можно сравнивать посредством любого <отношения>; если целое сравнивается с вещественным, оно неявно преобразуется в вещественное. Результат любого сравнения имеет тип BOOLEAN.

Операндами <аддитивных операторов> и <мультипликативных операторов> могут быть только целые и вещественные значения. Если целые операнды сочетаются с вещественными, перед выполнением операции целые преобразуются в вещественные. В операции MOD нельзя использовать вещественные числа; при выполнении операций MOD и деления целых чисел частное выбирается так, чтобы остаток был неотрицательным. Операндами оператора конкатенации || обычно служат цепочки литер; результат также является цепочкой. Операнды других базовых типов перед выполнением конкатенации преобразуются в цепочки, соответствующие их представлению при выводе.

Функция FLOOR преобразует вещественный параметр в вещественное число, равное целому, не превосходящему параметр. Результатом функции LENGTH является целое число, равное длине цепочки-параметра. Первый параметр функции SUBSTR — цепочка; результатом служит подцепочка, начальная литера которой обозначена вторым целочисленным параметром (счет идет от нуля), а длина задана третьим целочисленным параметром. Функция CHARACTER преобразует целочисленный параметр в цепочку из одной литеры, имеющей в алфавите данный номер. Функция NUMBER выдает в качестве целочисленного результата номер, который имеет в алфавите первая литера цепочки-параметра. Функция FLOAT преобразует целочисленный параметр в вещественный результат, a FIX преобразует вещественный параметр в целочисленный результат. Выполнение функций SUBSTR, FIX и CHARACTER может закончиться ошибкой.

<переменная>::= <идентификатор>

|<переменная>, <идентификатор>

|<переменная> [<выражение>]

<Переменная> — это либо просто <идентификатор>, либо <переменная> с последующим именем поля, либо <переменная> с индексом. Разумеется, все <переменные> должны быть декларированы. <Идентификатор> — терминальный элемент синтаксиса. Он обязан начинаться с большой или малой буквы, за которой может следовать произвольное число букв или десятичных цифр. Резервированные слова нельзя использовать в качестве <идентификаторов>. Как резервированные слова, так и <идентификаторы> должны отделяться от других неоператорных лексем, по крайней мере, одним пробелом, комментарием или литерой перевода строки. Лексемы не могут пересекать границ записей.

<константа> ::= <целая константа>

|<вещественная константа>

|<булева константа>

|<цепочечная константа>

<булева константа>::= TRUE

|FALSE

<Целая константа> — это непрерывная цепочка десятичных цифр. Она должна отделяться от других неоператорных лексем по крайней мере одним пробелом, комментарием или литерой перевода строки. <Вещественная константа> — это непрерывная цепочка десятичных цифр, за которой вплотную следует точка и, возможно, еще одна цепочка десятичных цифр. В остальном <вещественные константы> подчиняются тем же правилам, что и <целые константы>. <Цепочечная константа> начинается и кончается двойной кавычкой "; между ними могут стоять любые литеры, кроме двойной кавычки. Чтобы включить в цепочку двойную кавычку, ее следует записать дважды. Например, """" — цепочка ровно из одной двойной кавычки. В остальном <цепочечная константа> ведет себя аналогично <идентификаторам>. В частности, она не может содержать литер перевода строки.

<вызов функции>::= <идентификатор функции> ( )

|<идентификатор функции> <список фактических параметров>

<идентификатор функции>::= <идентификатор>

<Идентификатор функции> — это обычный <идентификатор>, употребленный в некотором определении функции. При вызове функций без параметров следует пользоваться первой альтернативой в <вызове функции>.

<отношение>::= <

|>

|=

|<=

|>=

|<>

<аддитивный оператор>::=+

|-

<мультипликативный оператор>::=*

|/

|MOD

С точки зрения разделения лексем операторами также считаются :, ;, (, ), , , [,], &, |, II, := и не считаются XOR, NOT и MOD. Комментарии начинаются с сочетания литер /*, продолжаются любой цепочкой, не содержащей */, и заканчиваются литерами */. Комментарии могут располагаться везде, где допускаются разделяющие пробелы. Комментарии выполняют роль разделителей.

Приводимая ниже программа иллюстрирует некоторые черты языка Мини. Чрезвычайно трудно в нескольких строках воспользоваться всеми возможностями, однако программа Эратосфен позволяет ощутить дух Мини. Ее можно использовать и как тест для компиляторов, поскольку выводимая информация очевидна, а вычисления нетривиальны. Пожалуй, единственным трюком (заимствованным из Алгола) является использование управляющих значений цикла для проведения вычислений в функции integersqrt. Вот текст программы. [57]

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

Тема. Напишите компилятор с Мини, порождающий перемещаемый объектный код для ЭВМ УМ-1 или другой вычислительной машины (см. гл. 25). Проверьте ваш компилятор, написав на Мини несколько программ, скомпилировав их, загрузив с помощью загрузчика УМ (см. гл. 26) и выполнив на ЭВМ УМ-1. Удостоверьтесь, что компилятор допускает все синтаксически и лексически правильные программы и отбраковывает все неправильные (семантические ошибки могут прервать компиляцию программы, правильной в других отношениях). При обработке ошибок не требуется исправлять ошибки или продолжать компиляцию, но необходимо точно указать причину и место ошибки. Листинг можно печатать без всяких хитростей — вам хватит других забот. Тщательно документируйте ход выполнения работы и встретившиеся трудности.

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

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

Вполне вероятно, что проект останется незавершенным. Поэтому целесообразно наметить очередность реализации различных возможностей языка. Если порядок выбран правильно, конечный продукт станет подмножеством Мини. Начните с реализации отдельных {программных сегментов). Внутри них попытайтесь реализовать (выражения), основные типы инструкций, внутренние процедуры, декларации переменных с (базовыми типами). Пожалуй, труднее всего сгенерировать код для (инструкции цикла); оставьте это напоследок. На начальной стадии вам придется написать подпрограммы для вывода перемещаемого объектного кода; постарайтесь, чтобы ими было легко воспользоваться в дальнейшем.

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

Инструментовка. Пишите компилятор на каком-либо процедурном языке высокого уровня. Язык XPL как раз и предназначен для конструирования компиляторов. Сноболом пользоваться не следует, поскольку на этом языке компиляторы реализуются слишком легко и вы не получите необходимой подготовки.

Двоим, троим или четверым на 10 недель. Каждый участник независимо отвечает за одну тестовую программу на Мини.

Грис (Gries D.). Compiler Construction for Digital Computers. Wiley, New York, NY, 1971. [Имеется перевод: Грис Д. Конструирование компиляторов для цифровых вычислительных машин. — М.: Мир, 1975.]

Выдающаяся книга по реализации компиляторов. В ней описано все о простых компиляторах и даны указания по сложным. Правда, остались недостаточно освещенными таблично-управляемые методы разбора LR(k), но этот пробел с избытком покрывают другие упоминаемые здесь книги. Если вы уже выбрали язык для компиляции, Грис покажет, как ее провести.

Мак-Киман, Хорнинг, Уортмен (McKeeman W. M., Horning J. J. Wortman D. В.), A Compiler Generator. Prentice-Hall, Englewood Cliffs, NJ, 1970.

В книге описывается язык XPL и его использование для конструирования компиляторов, В качестве иллюстрации метода приведен компилятор с XPL, написанный на XPL. В первых изданиях использовался ныне устаревший таблично-управляемый метод разбора SMSP, однако в следующих изданиях подробно обсуждается разбор LR(k). К сожалению, опубликованный листинг не претерпел изменений в сторону LR(k). He вошел и табличный генератор Де Ремера SLR(k). Книга может служить руководством по JCPL.

Николс (Nickholls J. E.). Тhe Structure and Design of Programming Languages. Addison-Wesley, Reading, MA, 1975. Пратт (Pratt T. W.) Programming Languages Design and Implementation. Prentice Hall, Englewood Cliffs, NJ, 1975. [Имеется перевод: Пратт Т. Языки программирования: разработка и реализация. — М.: Мир, 1979.]

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

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода я компиляции. Т. 1, 2. — Пер. с англ. — М.: Мир, 1978.