Процедуры

13. Процедуры

ВВЕДЕНИЕ

Наконец-то мы принимаемся за хорошую главу!

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

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

Эти возможности, которые будут обсуждены в следующих двух главах, так сказать отделят мужчин от игрушек. "Настоящие" языки имеют более одного типа данных и они поддерживают вызовы процедур. Более чем любые другие, именно эти две возможности дают языку большую часть его характера и индивидуальности. Как только мы предоставим их, наши языки, TINY и его преемники, перестанут быть игрушками и получат характер настоящих языков, пригодных для серьезного программирования.

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

ПОСЛЕДНЕЕ ОТКЛОНЕНИЕ

Эта глава была необычайно трудной для меня. Причина не имеет никакого отношения непосредственно к теме... я знал, о чем хотел рассказать уже какое-то время, и фактически я представил большинство из этого на Software Development '89,  в феврале. Больше это имело отношение к подходу. Позвольте мне объяснить.

Когда я впервые начал эту серию, я сказал вам, что мы будем использовать некоторые "приемы" чтобы упростить себе жизнь и позволить нам получить общее представление не вдаваясь слишком подробно в детали. Среди этих приемов была идея рассмотрения отдельных частей компилятора в отдельные моменты времени, т.е. выполнения экспериментов, использующих Cradle как основу. Когда, например, мы исследовали выражения мы работали только с этой частью теории компиляции.     Когда мы исследовали управляющие структуры, мы писали различные программы, все еще основанные на Cradle, для выполнения этой части. Мы включили эти понятия в полный язык довольно недавно. Эти методы служили нам действительно очень хорошо и привели нас к разработке компилятора для TINY версии 1.3.

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

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

Вы должны понять, что то, чем мы здесь занимаемся немного уникально. Существует ряд статей, таких как статьи по Small C от Кейна и Хендрикса, которые представляли законченный компилятор для одного языка или другого. Это другое. В этой обучающей серии вы наблюдаете за моей разработкой и реализацией и языка и компилятора в реальном режиме времени.

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

Это оказалось тяжелым делом! В конце концов я понял, что глупо было и пытаться.  Достигнув столького используя идею маленьких экспериментов, основанных на одно-символьных токенах и простых, специализированных программах, я отказался от них в пользу работы с полным компилятором.  Это не сработало.

Поэтому мы собираемся возвратиться к своим корням, так сказать. В этой и следующей главах я буду снова использовать одно-символьные токены для исследования концепции процедур, освобожденный от другого багажа, накопленного нами на предыдущих уроках. Фактически, я даже не буду пытаться  в конце этого урока объединить конструкции в компилятор TINY. Мы оставим это на потом.

В конце концов на этот раз  вам не понадобится что-то большее,  так что давайте не будем больше тратить времени зря и двинемся вперед.

ОСНОВЫ

Все современные центральные процессоры предоставляют прямую поддержку вызовов процедур и 68000 не исключение. Для 68000 вызов - BSR (PC-относительная версия) или JSR, и возвращение RTS. Все что мы должны сделать это организовать для компилятора выдачу этих команд в соответствующих местах.

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

ОСНОВА ДЛЯ ЭКСПЕРИМЕНТОВ

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

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

    <ident> = <ident>

Другими словами, единственным допустимым выражением является одиночное имя переменной. Нет никаких управляющих конструкций... единственным допустимым утверждением является присваивание.

Большую часть программы составляют просто подпрограммы из стандартного Cradle. Я показал ее здесь полностью только для того, чтобы быть уверенным что все мы начинаем с одного места:

program Calls; 
 
{ Constant Declarations } 
const TAB = ^I; 
      CR  = ^M; 
      LF  = ^J; 
 
{ Variable Declarations } 
var Look: char;              { Lookahead Character } 
var ST: Array['A'..'Z'] of char; 
 
{ Read New Character From Input Stream } 
procedure GetChar; 
begin 
   Read(Look); 
end; 
 
{ Report an Error } 
procedure Error(s: string); 
begin 
   WriteLn; 
   WriteLn(^G, 'Error: ', s, '.'); 
end; 
 
{ Report Error and Halt } 
procedure Abort(s: string); 
begin 
   Error(s); 
   Halt; 
end; 
 
{ Report What Was Expected } 
procedure Expected(s: string); 
begin 
   Abort(s + ' Expected'); 
end; 
 
{ Report an Undefined Identifier } 
procedure Undefined(n: string); 
begin 
   Abort('Undefined Identifier ' + n); 
end; 
 
{ Report an Duplicate Identifier } 
procedure Duplicate(n: string); 
begin 
     Abort('Duplicate Identifier ' + n); 
end; 
 
{ Get Type of Symbol } 
function TypeOf(n: char): char; 
begin 
     TypeOf := ST[n]; 
end; 
 
{ Look for Symbol in Table } 
function InTable(n: char): Boolean; 
begin 
   InTable := ST[n] <> ' '; 
end; 
 
{ Add a New Symbol to Table } 
procedure AddEntry(Name, T: char); 
begin 
     if Intable(Name) then Duplicate(Name); 
     ST[Name] := T; 
end; 
 
{ Check an Entry to Make Sure It's a Variable } 
procedure CheckVar(Name: char); 
begin 
     if not InTable(Name) then Undefined(Name); 
     if  TypeOf(Name)  <>  'v'  then    Abort(Name  +  ' is not a 
variable'); 
end; 
 
{ Recognize an Alpha Character } 
function IsAlpha(c: char): boolean; 
begin 
   IsAlpha := upcase(c) in ['A'..'Z']; 
end; 
 
{ Recognize a Decimal Digit } 
function IsDigit(c: char): boolean; 
begin 
   IsDigit := c in ['0'..'9']; 
end; 
 
{ Recognize an AlphaNumeric Character } 
function IsAlNum(c: char): boolean; 
begin 
   IsAlNum := IsAlpha(c) or IsDigit(c); 
end; 
 
{ Recognize an Addop } 
function IsAddop(c: char): boolean; 
begin 
   IsAddop := c in ['+', '-']; 
end; 
 
{ Recognize a Mulop } 
function IsMulop(c: char): boolean; 
begin 
   IsMulop := c in ['*', '/']; 
end; 
 
{ Recognize a Boolean Orop } 
function IsOrop(c: char): boolean; 
begin 
   IsOrop := c in ['|', '~']; 
end; 
 
{ Recognize a Relop } 
function IsRelop(c: char): boolean; 
begin 
   IsRelop := c in ['=', '#', '<', '>']; 
end; 
 
{ Recognize White Space } 
function IsWhite(c: char): boolean; 
begin 
   IsWhite := c in [' ', TAB]; 
end; 
 
{ Skip Over Leading White Space } 
procedure SkipWhite; 
begin 
   while IsWhite(Look) do 
      GetChar; 
end; 
 
{ Skip Over an End-of-Line } 
procedure Fin; 
begin 
   if Look = CR then begin 
      GetChar; 
      if Look = LF then 
         GetChar; 
   end; 
end; 
 
{ Match a Specific Input Character } 
procedure Match(x: char); 
begin 
   if Look = x then GetChar 
     else Expected('''' + x + ''''); 
     SkipWhite; 
end; 
 
{ Get an Identifier } 
function GetName: char; 
begin 
   if not IsAlpha(Look) then Expected('Name'); 
   GetName := UpCase(Look); 
     GetChar; 
     SkipWhite; 
end; 
 
{ Get a Number } 
function GetNum: char; 
begin 
   if not IsDigit(Look) then Expected('Integer'); 
   GetNum := Look; 
     GetChar; 
     SkipWhite; 
end; 
 
{ Output a String with Tab } 
procedure Emit(s: string); 
begin 
   Write(TAB, s); 
end; 
 
{ Output a String with Tab and CRLF } 
procedure EmitLn(s: string); 
begin 
   Emit(s); 
   WriteLn; 
end; 
 
{ Post a Label To Output } 
procedure PostLabel(L: string); 
begin 
   WriteLn(L, ':'); 
end; 
 
{ Load a Variable to the Primary Register } 
procedure LoadVar(Name: char); 
begin 
     CheckVar(Name); 
     EmitLn('MOVE ' + Name + '(PC),D0'); 
end; 
 
{ Store the Primary Register } 
procedure StoreVar(Name: char); 
begin 
     CheckVar(Name); 
     EmitLn('LEA ' + Name + '(PC),A0'); 
   EmitLn('MOVE D0,(A0)') 
end; 
 
{ Initialize } 
procedure Init; 
var i: char; 
begin 
     GetChar; 
     SkipWhite; 
     for i := 'A' to 'Z' do 
          ST[i] := ' '; 
end; 
 
{ Parse and Translate an Expression } 
{ Vestigial Version } 
procedure Expression; 
begin 
     LoadVar(GetName); 
end; 
 
{ Parse and Translate an Assignment Statement } 
procedure Assignment; 
var Name: char; 
begin 
     Name := GetName; 
     Match('='); 
     Expression; 
     StoreVar(Name); 
end; 
 
{ Parse and Translate a Block of Statements } 
procedure DoBlock; 
begin 
     while not(Look in ['e']) do begin 
          Assignment; 
          Fin; 
   end; 
end; 
 
{ Parse and Translate a Begin-Block } 
procedure BeginBlock; 
begin 
     Match('b'); 
     Fin; 
     DoBlock; 
     Match('e'); 
     Fin; 
end; 
 
{ Allocate Storage for a Variable } 
procedure Alloc(N: char); 
begin 
     if InTable(N) then Duplicate(N); 
   ST[N] := 'v'; 
     WriteLn(N, ':', TAB, 'DC 0'); 
end; 
 
{ Parse and Translate a Data Declaration } 
procedure Decl; 
var Name: char; 
begin 
   Match('v'); 
     Alloc(GetName); 
end; 
 
{ Parse and Translate Global Declarations } 
procedure TopDecls; 
begin 
     while Look <> 'b' do begin 
      case Look of 
        'v': Decl; 
      else Abort('Unrecognized Keyword ' + Look); 
          end; 
          Fin; 
     end; 
end; 
 
{ Main Program } 
begin 
     Init; 
     TopDecls; 
     BeginBlock; 
end. 

 

 

 

Обратите внимание, что у нас есть таблица идентификаторов и есть логика для проверки допустимости имени переменной. Также стоит обратить внимание на то, что я включил  код, который вы видели ранее для поддержки пробелов и переносов строк. Наконец заметьте, что основная программа ограничена как обычно операторными скобками BEGIN-END.

Если вы скопировали программу в Turbo, первым делом нужно откомпилировать ее и удостовериться что она работает. Сделайте несколько объявлений а затем блок begin. Попробуйте что-нибудь вроде:

    va             (для VAR A)

    vb             (для VAR B)

    vc             (для VAR C)

    b              (для BEGIN)

    a=b

    b=c

    e.             (для END.)

Как обычно, вы должны сделать некоторые преднамеренные ошибки и проверить, что программа правильно их отлавливает.

ОБЪЯВЛЕНИЕ ПРОЦЕДУРЫ

Если вы удовлетворены, как работает наша маленькая программа, тогда пришло время поработать с процедурами. Так как мы еще не говорили о параметрах мы начнем с рассмотрения только таких процедур которые не имеют списка параметров.

Для начала, давайте рассмотрим простую программу с процедурой и подумаем о коде который мы хотели бы увидеть для нее сгенерированным:

    PROGRAM FOO;

   .
    .
    PROCEDURE BAR;                     BAR:
    BEGIN                                   .
    .                                       .
    .                                       .

    END;                                    RTS

    BEGIN { MAIN PROGRAM }             MAIN:
    .                                       .
    .                                       .
    FOO;                                    BSR BAR
    .                                       .

    .                                       .

    END.                                    END MAIN

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

Ключ к работе с телом процедуры - понимание того, что хотя процедура может быть очень длинной, ее объявление в действительности не отличается от объявления переменной. Это просто еще один вид объявлений. Мы можем записать БНФ:

    <declaration> ::= <data decl> | <procedure>

Это означает, что можно легко изменить TopDecl для работы с процедурами. Как насчет синтаксиса процедуры? Хорошо, вот предлагаемый синтаксис, который по существу такой же, как и в Pascal:

    <procedure> ::= PROCEDURE <ident> <begin-block>

Здесь практически не требуется никакой генерации кода., кроме генерации внутри блока begin. Мы должны только выдать метку в начале процедуры и RTS в конце.

Вот требуемый код:

{ Parse and Translate a Procedure Declaration } 
procedure DoProc; 
var N: char; 
begin 
     Match('p'); 
     N := GetName; 
     Fin; 
     if InTable(N) then Duplicate(N); 
     ST[N] := 'p'; 
     PostLabel(N); 
     BeginBlock; 
     Return; 
end;

 

 

 

Обратите внимание, что я добавил новую подпрограмму генерации кода Return, которая просто выдает инструкцию RTS. Создание этой подпрограммы "оставлено как упражнение студенту".

Для завершения этой версии добавьте следующую строку в оператор Case в DoBlock.

    'p': DoProc;

Я должен упомянуть, что эта структура для объявлений и БНФ, которая управляет ей, отличается от стандартного Паскаля. В определении Паскаля от Дженсена и Вирта  объявления переменных и, фактически, все виды объявлений, должны следовать в определенном порядке, т.е. метки, константы, типы, переменные, процедуры и основная программа. Чтобы следовать такой схеме, мы должны разделить два объявления и написать в основной программе что-нибудь вроде:

    DoVars;

    DoProcs;

    DoMain;

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

Испытайте эту новую версию. Заметьте, что мы можем объявить так много процедур, как захотим (до тех пор, пока не исчерпаем одно-символьные имена!) и все метки и RTS появятся в правильных местах.

Здесь стоит заметить, что я не разрешаю вложенные процедуры. В TINY все процедуры должны быть объявлены на глобальном уровне, так же как и в C. На Форуме Компьютерных Языков на CompuServe по этому поводу возникла порядочная дискуссия. Оказывается, существует значительная расплата сложностью которая должна быть заплачена за роскошь использования вложенных процедур. Более того, эта расплата платится во время выполнения, так как должен быть добавлен дополнительный код, который будет выполняться каждый раз когда процедура вызывается. Я также охотно верю что вложение это не очень хорошая идея просто на том основании, что я видел слишком много злоупотреблений этой возможностью. Прежде, чем сделать следующий шаг, также стоит обратить внимание на то, что "основная программа" в ее текущем состоянии незавершена, так как она не имеет метки и утверждения END. Давайте исправим эту небольшую оплошность:

{ Parse and Translate a Main Program } 
procedure DoMain; 
begin 
     Match('b'); 
     Fin; 
     Prolog; 
     DoBlock; 
     Epilog; 
end; 
 
. 
. 
. 
 
{ Main Program } 
begin 
     Init; 
     TopDecls; 
     DoMain; 
end.

 

 

 

Обратите внимание, что DoProc и DoMain не совсем симметричны. DoProc использует вызов BeginBlock тогда как DoMain нет. Это из-за того, что начало процедуры определяется по ключевому слову  PROCEDURE (в данном случае сокращенно 'p'), тогда как основная программа не имеет никакого другого ключевого слова кроме непосредственно BEGIN.

И это ставит интересный вопрос: почему?

Если мы посмотрим на структуры C программы, мы обнаружим, что все функции совсем одинаковы, за исключением того, что основная программа идентифицируется по своему имени "main". Так как функции C могут появляться в любом порядке, основная программа так же может быть в любом месте модуля компиляции.

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

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

    BEGIN { of MAIN }

Это всегда казалось мне немного клуджем. Возникает вопрос: Почему обработка основной программы должна так отличаться от обработки процедур? Теперь, когда мы осознали, что объявление процедур это просто... часть глобальных объявлений... не является ли основная программа также просто еще одним объявлением?

Ответ - да, и обрабатывая ее таким способом мы можем упростить код и сделать его значительно более ортогональным. Я предлагаю использовать для идентификации основной программы явное ключевое слово PROGRAM (Заметьте, что это означает, что мы не можем начать с него файл, как в Паскале). В этом случае наша БНФ становится:

   <declaration> ::= <data decl> | <procedure> | <main program>

    <procedure> ::= PROCEDURE <ident> <begin-block>

    <main program> ::= PROGRAM <ident> <begin-block>

Код также смотрится намного лучше, по крайней мере в том смысле, что DoMain и DoProc выглядят более похоже:

{ Parse and Translate a Main Program } 
procedure DoMain; 
var N: char; 
begin 
     Match('P'); 
     N := GetName; 
     Fin; 
     if InTable(N) then Duplicate(N); 
     Prolog; 
     BeginBlock; 
end; 
 
. 
. 
. 
 
{ Parse and Translate Global Declarations } 
procedure TopDecls; 
begin 
     while Look <> '.' do begin 
      case Look of 
            'v': Decl; 
            'p': DoProc; 
            'P': DoMain; 
          else Abort('Unrecognized Keyword ' + Look); 
          end; 
          Fin; 
     end; 
end; 
 
{ Main Program } 
begin 
     Init; 
     TopDecls; 
     Epilog; 
end.

 

 

 

Так как объявление основной программы теперь внутри цикла TopDecl, возникают некоторые трудности. Как мы можем гарантировать, что она - последняя в файле? И выйдем ли мы когда либо из цикла? Мой ответ на второй вопрос, как вы можете видеть, - в том, чтобы вернуть нашего старого друга точку. Как только синтаксический анализатор увидит ее дело сделано.

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

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

ВЫЗОВ ПРОЦЕДУРЫ

Если вы удовлетворены работой программы, давайте обратимся ко второй половине уравнения... вызову.

Рассмотрим БНФ для вызова процедуры:

    <proc_call> ::= <identifier>

с другой стороны БНФ для операции присваивания:

    <assignment> ::= <identifier> '=' <expression>

Кажется у нас проблема. Оба БНФ утверждения с правой стороны начинаются с токена <identifier>. Как мы предполагаем узнать, когда мы видим идентификатор, имеем ли мы вызов процедуры или операцию присваивания? Это похоже на случай, когда наш синтаксический анализатор перестает быть предсказывающим и действительно это точно такой случай. Однако, оказывается эту проблему легко решить, так как все, что мы должны сделать - посмотреть на тип идентификатора, записанный в таблице идентификаторов. Как мы обнаружили раньше, небольшое локальное нарушение правила предсказывающего синтаксического анализа может быть легко обработано как специальный случай.

Вот как это делается:

{ Parse and Translate an Assignment Statement } 
procedure Assignment(Name: char); 
begin 
     Match('='); 
     Expression; 
     StoreVar(Name); 
end; 
 
{ Decide if a Statement is an Assignment or Procedure Call } 
procedure AssignOrProc; 
var Name: char; 
begin 
     Name := GetName; 
     case TypeOf(Name) of 
          ' ': Undefined(Name); 
          'v': Assignment(Name); 
          'p': CallProc(Name); 
          else Abort('Identifier ' + Name + 
                                   ' Cannot Be Used Here'); 
     end; 
end; 
 
{ Parse and Translate a Block of Statements } 
procedure DoBlock; 
begin 
     while not(Look in ['e']) do begin 
          AssignOrProc; 
          Fin; 
   end; 
end;  

 

 

Как вы можете видеть, процедура Block сейчас вызывает AssignOrProc вместо Assignment. Назначение этой новой процедуры просто считать идентификатор, определить его тип и затем вызвать процедуру, соответствующую этому типу. Так как имя уже прочитано, мы должны передать его в эти две процедуры и соответственно изменить Assignment. Процедура CallProc - это просто подпрограмма генерации кода:

 

{ Call a Procedure } 
procedure CallProc(N: char); 
begin 
     EmitLn('BSR ' + N); 
end;

 

Хорошо, к этому моменту у нас есть компилятор, который может работать с процедурами. Стоить отметить, что процедуры могут вызывать процедуры с любой степенью вложенности. Так что, даже хотя мы и не разрешаем вложенные объявления, нет ничего, чтобы удерживало нас от вложенных вызовов, точно так, как мы ожидали бы на любом языке. Мы получили это и это было не слишком сложно, не так ли?

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

ПЕРЕДАЧА ПАРАМЕТРОВ

Снова, все мы знаем основную идею передачи параметров, но давайте просто для  надежности разберем ее заново.

Вообще, процедуре предоставляется список параметров, например:

    PROCEDURE FOO(X, Y, Z)

В объявлении процедуры параметры называются формальными параметрами и могут упоминаться в теле процедуры по своим именам. Имена, используемые для формальных параметров в действительности произвольны. Учитывается только позиция. В примере выше имя 'X' просто означает "первый параметр" везде, где он используется.

Когда процедура вызывается, "фактические параметры" переданные ей, связаны с формальными параметрами на взаимно-однозначном принципе.

БНФ для синтаксиса выглядит приблизительно так:

    <procedure> ::= PROCEDURE <ident> '(' <param-list> ')' <begin-block>

    <param_list> ::= <parameter> ( ',' <parameter> )* | null

Аналогично, вызов процедуры выглядит так:

    <proc call> ::= <ident> '(' <param-list> ')'

Обратите внимание, что здесь уже есть неявное решение, встроенное в синтаксис. Некоторые языки, такие как Pascal и Ada разрешают списку параметров быть необязательным. Если нет никаких параметров, вы просто полностью отбрасываете скобки. Другие языки, типа C и Modula-2, требуют скобок даже если список пустой.     Ясно, что пример, который мы  только что привели, соответствует первой точке зрения. Но, сказать правду, я предпочитаю последний. Для одних процедур решение кажется должно быть в пользу "без списочного" подхода. Оператор

    Initialize; ,

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

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

В любом случае, Никлаус Вирт разработал и Pascal и Modula-2. Я оправдаю его и полагаю что он имел веские причины для изменения правил во втором случае!

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

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

{ Process the Formal Parameter List of a Procedure } 
procedure FormalList; 
begin 
     Match('('); 
     if Look <> ')' then begin 
          FormalParam; 
          while Look = ',' do begin 
               Match(','); 
               FormalParam; 
          end; 
     end; 
     Match(')'); 
end;

 

 

 

В процедуру DoProc необходимо добавить строчку для вызова FormalList:

{ Parse and Translate a Procedure Declaration } 
procedure DoProc; 
var N: char; 
begin 
     Match('p'); 
     N := GetName; 
     FormalList; 
     Fin; 
     if InTable(N) then Duplicate(N); 
     ST[N] := 'p'; 
     PostLabel(N); 
     BeginBlock; 
     Return; 
end;

 

 

 

Сейчас код для FormalParam всего лишь пустышка, который просто пропускает имена переменных:

{ Process a Formal Parameter } 
procedure FormalParam; 
var Name:  char; 
begin 
     Name := GetName; 
end; 

 

 

 

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

{ Process an Actual Parameter } 
procedure Param; 
var Name:  char; 
begin 
     Name := GetName; 
end; 
 
{ Process the Parameter List for a Procedure  Call } 
procedure ParamList; 
begin 
     Match('('); 
     if Look <> ')' then begin 
          Param; 
          while Look = ',' do begin 
               Match(','); 
               Param; 
          end; 
     end; 
     Match(')'); 
end; 
 
{ Process a Procedure Call } 
procedure CallProc(Name: char); 
begin 
     ParamList; 
     Call(Name); 
end; 

 

 

 

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

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

СЕМАНТИКА ПАРАМЕТРОВ

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

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

Есть два основных способа передачи параметров:

Различия лучше всего видны в свете небольшого исторического обзора.

Старые компиляторы Фортрана передавали все параметры по ссылке. Другими словами, фактически передавался адрес параметра. Это означало, что вызываемая подпрограмма была вольна и считывать и изменять этот параметр, что часто и происходило, как будто это была просто глобальная переменная. Это был фактически самый эффективный способ и он был довольно простым, так как тот же самый механизм использовался во всех случаях с одним исключением, которое я кратко затрону.

Хотя имелись и проблемы. Многие люди чувствовали, что этот метод создавал слишком большую связь между вызванной и вызывающей подпрограммой.     Фактически, это давало подпрограмме полный доступ ко всем переменным, которые появлялись в списке параметров.

Часто нам не хотелось бы фактически изменять параметр а только использовать его как входные данные. К примеру, мы могли бы передавать счетчик элементов в подпрограмму и хотели бы затем использовать этот счетчик в цикле DO. Во избежание изменения значения в вызываемой программе мы должны были сделать локальную копию входного параметра и оперировать только его копией. Некоторые программисты на Фортране фактически сделали практикой копирование всех параметров, исключая те, которые должны были использоваться как возвращаемые значения. Само собой разумеется, все это копирование победило добрую часть эффективности, связанной с этим методом.

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

Предположим, у нас есть подпрограмма:

    SUBROUTINE FOO(X, Y, N)

где N - какой-то входной счетчик или флажок. Часто нам бы хотелось иметь возможность передавать литерал или даже выражение вместо переменной, как например:

    CALL FOO(A, B, J + 1)

Третий параметр не является переменной, и поэтому он не имеет никакого адреса. Самые ранние компиляторы Фортрана не позволяли таких вещей, так что мы должны были прибегать к ухищрениям типа:

    K = J + 1

    CALL FOO(A, B, K)

Здесь снова требовалось копирование и это бремя ложилось на программистов. Не хорошо.

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

Пока все хорошо. Даже если подпрограмма ошибочно изменила значение анонимной переменной, кто об этом знал или кого это заботило? При следующем вызове она в любом случае была бы рассчитана повторно.

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

    CALL FOO(A, B, 4)

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

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

Чтобы увидеть, как это работает, вообразите, что мы вызываем подпрограмму FOO как в примере выше, передавая ей литерал 4. Фактически, что передается - это адрес литерала 4, который сохранен в литерном пуле. Этот адрес соответствует формальному параметру K в самой подпрограмме.

Теперь предположите, что без ведома программиста подпрограмма FOO фактически присваивает K значение -7. Неожиданно, литерал 4 в литерном пуле меняется на -7. В дальнейшем, каждое выражение, использующее 4, и каждая подпрограмма, в которую передают 4, будут использовать вместо этого значение -7! Само собой разумеется, что это может привести к несколько причудливому и труднообъяснимому поведению. Все это дало концепции передачи по ссылке плохое имя, хотя, как мы видели, в действительности это была комбинация проектных решений, ведущая к проблеме.

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

Частично из-за этого подводного камня Фортрана и частично просто из-за уменьшенной связи, современные языки типа C, Pascal, Ada и Modula 2 в основном передают скаляры по значению.

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

Сначала может показаться, что это немного неэффективно из-за необходимости копировать параметр. Но запомните, что мы в любом случае окажемся перед необходимостью выбирать какое-то значение, является ли оно непосредственно параметром или его адресом. Внутри подпрограммы, использование передачи по значению определенно более эффективно, так как мы устраняем один уровень косвенности. Наконец, мы видели раньше, что в Фортране часто было необходимо в любом случае делать копии внутри подпрограммы, так что передача по значению уменьшает количество локальных переменных. В целом, передача по значению лучше.

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

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

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

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

ПЕРЕДАЧА ПО ЗНАЧЕНИЮ

Давайте просто попробуем некоторые нехитрые вещи и посмотрим, куда они нас приведут. Давайте начнем со случая передачи по значению. Рассмотрим вызов процедуры:

    FOO(X, Y)

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

    MOVE X(PC),-(SP)    ; Push X

    MOVE Y(PC),-(SP)    ; Push Y

    BSR FOO             ; Call FOO

Это конечно не выглядит слишком сложным!

Когда BSR выполнен центральный процессор помещает адрес возврата в стек и переходит к FOO. В этой точке стек будет выглядеть следующим образом:

              .

              .

              Значение X (2 bytes)

              Значение Y (2 bytes)

      SP -->  Адрес возврата (4 bytes)

Так что значения параметров имеют адреса с фиксированными смещениями от указателя стека. В этом примере адреса такие:

    X:  6(SP)

    Y:  4(SP)

Теперь рассмотрим, на что могла бы походить вызываемая процедура:

    PROCEDURE FOO(A, B)

    BEGIN

      A = B

    END

(Помните, что имена формальных параметров произвольные... учитываются только позиции).

Желаемый код мог бы выглядеть так:

    FOO: MOVE 4(SP),D0

         MOVE D0,6(SP)

         RTS

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

Давайте начнем с объявления новой таблицы:

    var Params: Array['A'..'Z'] of integer;

Нам также необходимо отслеживать, сколько параметров имеет данная процедура:

    var NumParams: integer;

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

{ Initialize Parameter Table to Null } 
procedure ClearParams; 
var i: char; 
begin 
  for i := 'A' to 'Z' do 
    Params[i] := 0; 
  NumParams := 0; 
end; 

 

 

 

Мы поместим обращение к этой процедуре в Init и также в конец DoProc:

{ Initialize } 
procedure Init; 
var i: char; 
begin 
     GetChar; 
     SkipWhite; 
     for i := 'A' to 'Z' do 
          ST[i] := ' '; 
     ClearParams; 
end; 
 
. 
. 
. 
 
{ Parse and Translate a Procedure Declaration } 
procedure DoProc; 
var N: char; 
begin 
     Match('p'); 
     N := GetName; 
     FormalList; 
     Fin; 
     if InTable(N) then Duplicate(N); 
     ST[N] := 'p'; 
     PostLabel(N); 
     BeginBlock; 
     Return; 
     ClearParams; 
end;

 

 

 

Обратите внимание, что вызов внутри DoProc гарантирует, что таблица будет чиста, когда мы в основной программе.

Хорошо, теперь нам нужны несколько процедур для работы с таблицей. Следующие несколько функций являются по существу копиями InTable, TypeOf и т.д.:

 

{ Find the Parameter Number } 
function ParamNumber(N: char): integer; 
begin 
     ParamNumber := Params[N]; 
end; 
 
{ See if an Identifier is a Parameter } 
function IsParam(N: char): boolean; 
begin 
     IsParam := Params[N] <> 0; 
end; 
 
{ Add a New Parameter to Table } 
procedure AddParam(Name: char); 
begin 
     if IsParam(Name) then Duplicate(Name); 
     Inc(NumParams); 
     Params[Name] := NumParams; 
end;

 

 

 

Наконец, нам понадобятся некоторые подпрограммы генерации кода:

{ Load a Parameter to the Primary Register } 
procedure LoadParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 4 + 2 * (NumParams - N); 
     Emit('MOVE '); 
     WriteLn(Offset, '(SP),D0'); 
end; 
 
{ Store a Parameter from the Primary Register } 
procedure StoreParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 4 + 2 * (NumParams - N); 
     Emit('MOVE D0,'); 
     WriteLn(Offset, '(SP)'); 
end; 
 
{ Push The Primary Register to the Stack } 
procedure Push; 
begin 
     EmitLn('MOVE D0,-(SP)'); 
end; 

 

 

 

(Последнюю подпрограмму мы уже видели прежде, но ее не было в этой остаточной версии программы.)

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

Давайте начнем с обработки формальных параметров. Все что мы должны сделать - добавить каждый параметр в таблицу идентификаторов параметров:

 

{ Process a Formal Parameter } 
procedure FormalParam; 
begin 
     AddParam(GetName); 
end;  

 

Теперь, что делать с формальными параметрами, когда они появляются в теле процедуры? Это требует немного больше работы. Мы должны сначала определить, что это формальный параметр. Чтобы сделать это, я написал модифицированную версию TypeOf:

{ Get Type of Symbol } 
function TypeOf(n: char): char; 
begin 
     if IsParam(n) then 
          TypeOf := 'f' 
     else 
          TypeOf := ST[n]; 
end;

 

 

 

(Обратите внимание, что так как TypeOf теперь вызывает IsParam, возможно будет необходимо изменить ее местоположение в программе.)

Мы также должны изменить AssignOrProc для работы с этим новым типом:

{ Decide if a Statement is an Assignment or Procedure Call } 
procedure AssignOrProc; 
var Name: char; 
begin 
     Name := GetName; 
     case TypeOf(Name) of 
          ' ': Undefined(Name); 
          'v', 'f': Assignment(Name); 
          'p': CallProc(Name); 
          else  Abort('Identifier ' + Name +  '  Cannot  Be  Used Here'); 
     end; 
end;

 

 

 

Наконец, код для обработки операции присваивания и выражения должен быть расширен:

{ Parse and Translate an Expression } 
{ Vestigial Version } 
procedure Expression; 
var Name: char; 
begin 
     Name := GetName; 
     if IsParam(Name) then 
          LoadParam(ParamNumber(Name)) 
     else 
          LoadVar(Name); 
end; 
 
{ Parse and Translate an Assignment Statement } 
procedure Assignment(Name: char); 
begin 
     Match('='); 
     Expression; 
     if IsParam(Name) then 
          StoreParam(ParamNumber(Name)) 
     else 
          StoreVar(Name); 
end;

 

 

 

Как вы можете видеть, эти процедуры обработают каждое встретившееся имя переменной или как формальный параметр или как глобальную переменную, в зависимости от того, появляется ли оно в таблице идентификаторов параметров. Запомните, что мы используем только остаточную форму Expression. В конечной программе изменения, показанные здесь, должны быть добавлены в Factor а не Expression.

Осталось самое простое. Мы должны только добавить семантику в фактический вызов процедуры, что мы можем сделать с помощью одной новой строки кода:

 

{ Process an Actual Parameter }

procedure Param;
begin
     Expression;
     Push;

end;

 

Так вот. Добавьте эти изменения в вашу программу и испытайте ее. Попробуйте объявить одну или две процедуры, каждая со списком формальных параметров. Затем сделайте какие-нибудь присваивания, используя комбинации глобальных и формальных параметров. Вы можете вызывать одну процедуру из другой, но вы не можете объявлять вложенные процедуры. Вы можете даже передавать формальные параметры из одной процедуры в другую. Если бы мы имели здесь полный синтаксис языка, вы могли бы также читать и выводить формальные параметры или использовать их в сложных выражениях.

ЧТО НЕПРАВИЛЬНО?

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

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

Самая явная оплошность в том, что он неправильный! Если вы оглянетесь на код для вызова процедур, вы увидите, что вызывающая подпрограмма помещает каждый фактический параметр в стек перед тем, как она вызывает процедуру. Процедура использует эту информацию, но она не изменяет указатель стека. Это означает, что содержимое все еще остается там когда мы возвращаемся. Кто-то должен очистить стек или мы скоро окажемся в очень трудной ситуации!

К счастью, это легко исправить. Все, что мы должны сделать - это увеличить указатель стека когда мы закончим.

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

Я предпочитаю разрешить очистку в вызывающей программе, так что вызываемая процедура должна только выполнить возврат. Также это кажется немного более сбалансированным так как именно вызывающая программа первой "засорила" стек. Но это означает, что вызывающая программа должна запоминать сколько элементов помещено в стек. Чтобы сделать проще, я изменил процедуру ParamList на функцию, возвращающую количество помещенных байт:

{ Process the Parameter List for a Procedure  Call } 
function ParamList: integer; 
var N: integer; 
begin 
     N := 0; 
     Match('('); 
     if Look <> ')' then begin 
          Param; 
          inc(N); 
          while Look = ',' do begin 
               Match(','); 
               Param; 
               inc(N); 
          end; 
     end; 
     Match(')'); 
     ParamList := 2 * N; 
end;

 

 

 

Процедура CallProc затем использует его для очистки стека:

{ Process a Procedure Call } 
procedure CallProc(Name: char); 
var N: integer; 
begin 
     N := ParamList; 
     Call(Name); 
     CleanStack(N); 
end;

 

 

 

Здесь я создал еще одну подпрограмму генерации кода:

{ Adjust the Stack Pointer Upwards by N Bytes } 
procedure CleanStack(N: integer); 
begin 
     if N > 0 then begin 
          Emit('ADD #'); 
          WriteLn(N, ',SP'); 
     end; 
end;

 

 

 

ОК, если вы добавили этот код в ваш компилятор, я думаю вы убедитесь, что стек теперь под контролем.

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

    PROCEDURE FOO(A, B)

    BEGIN

         A = A + B

    END

Код, сгенерированный нехитрым синтаксическим анализатором, мог бы быть:

    FOO: MOVE 6(SP),D0       ; Извлечь A

         MOVE D0,-(SP)       ; Сохранить его
         MOVE 4(SP),D0       ; Извлечь B
         ADD (SP)+,D0        ; Добавить A

         MOVE D0,6(SP)       : Сохранить A

         RTS

Это было бы неправильно. Когда мы помещаем первый аргумент в стек, смещения для двух формальных параметров больше не 4 и 6, я 6 и 8. Поэтому вторая выборка вернула бы снова A а не B.

Но это не конец света. Я думаю, вы можете видеть, что все, что мы должны делать - изменять смещение каждый раз, когда мы помещаем в стек и что фактически и делается если ЦПУ не имеет поддержки других методов.

К счастью, все же, 68000 имеет такую поддержку. Поняв, что этот ЦПУ мог бы использоваться со многими компиляторами языков высокого уровня, Motorola решила добавить прямую поддержку таких вещей.

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

Команда LINK из набора инструкций 68000 позволяет вам объявить такой указатель кадра и установить его равным указателю стека и все это в одной команде.     Фактически, она делает даже больше чем это. Так как этот регистр может использоваться для чего-то еще в вызывающей процедуре, LINK также помещает текущее значение регистра в стек. Вы можете также добавить значение к указателю стека чтобы создать место для локальных переменных.

В дополнение к LINK есть UNLK, которая просто восстанавливает указатель стека и выталкивает старое значение обратно в регистр.

С использованием этих двух команд код для предыдущего примера станет:

    FOO: LINK A6,#0

         MOVE 10(A6),D0      ; Извлечь A
         MOVE D0,-(SP)       ; Сохранить его
         MOVE 8(A6),D0       ; Извлечь B
         ADD (SP)+,D0        ; Добавить A
         MOVE D0,10(A6)      : Сохранить A

         UNLK A6

         RTS

Исправить компилятор для генерации этого кода намного проще чем объяснить. Все, что нам нужно сделать - изменить генерацию кода в DoProc. Так как из-за этого код становится немного больше одной строки, я создал новые процедуры, схожие с процедурами Prolog и Epilog, вызываемыми DoMain:

{ Write the Prolog for a Procedure } 
procedure ProcProlog(N: char); 
begin 
     PostLabel(N); 
     EmitLn('LINK A6,#0'); 
end; 
 
{ Write the Epilog for a Procedure } 
procedure ProcEpilog; 
begin 
     EmitLn('UNLK A6'); 
     EmitLn('RTS'); 
end;

 

 

 

Процедура DoProc теперь просто вызывает их:

{ Parse and Translate a Procedure Declaration } 
procedure DoProc; 
var N: char; 
begin 
     Match('p'); 
     N := GetName; 
     FormalList; 
     Fin; 
     if InTable(N) then Duplicate(N); 
     ST[N] := 'p'; 
     ProcProlog(N); 
     BeginBlock; 
     ProcEpilog; 
     ClearParams; 
end;

 

 

 

В заключение, мы должны изменить ссылки на SP в процедурах LoadParam и StoreParam:

{ Load a Parameter to the Primary Register } 
procedure LoadParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 8 + 2 * (NumParams - N); 
     Emit('MOVE '); 
     WriteLn(Offset, '(A6),D0'); 
end; 
 
{ Store a Parameter from the Primary Register } 
procedure StoreParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 8 + 2 * (NumParams - N); 
     Emit('MOVE D0,'); 
     WriteLn(Offset, '(A6)'); 
end;

 

 

 

(Заметьте, что вычисление Offset изменяется чтобы учесть дополнительное сохранение A6.)

Это все что требуется.  Попробуйте и посмотрите как вам это нравится.

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

Все еще остается только одна небольшая проблема:

У нас нет способа возвратить результат в вызывающую программу!

Но это, конечно, не ограничение генерируемого нами кода, а ограничение, свойственное протоколу передачи по значению. Обратите внимание, что мы можем использовать формальные параметры любым способом внутри процедуры. Мы можем вычислять для них новое значение, использовать их как счетчики циклов (если бы мы имели циклы!) и т.д. Так что код делает то, что предполагается. Чтобы решить эту последнюю проблему мы должны рассмотреть альтернативный протокол.

ПЕРЕДАЧА ПО ССЫЛКЕ

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

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

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

    FOO(X, Y)

оттранслировать в:

    PEA X(PC)           ; Сохранить адрес X

    PEA Y(PC)           ; Сохранить адрес Y

    BSR FOO             ; Вызвать FOO

Это просто вопрос небольших изменений в Param:

 

{ Process an Actual Parameter }

procedure Param;
begin
     EmitLn('PEA ' + GetName + '(PC)');

end;

 

(Обратите внимание, что при передачей по ссылке мы не можем использовать выражения в списке параметров, поэтому Param может просто непосредственно считывать имя).

На другой стороне, ссылки на формальные параметры должны получить один уровень косвенности:

    FOO: LINK A6,#0

         MOVE.L 12(A6),A0    ; Извлечь адрес A
         MOVE (A0),D0        ; Извлечь A
         MOVE D0,-(SP)       ; Сохранить
         MOVE.L 8(A6),A0     ; Извлечь адрес B
         MOVE (A0),D0        ; Извлечь B
         ADD (SP)+,D0        ; Добавить A
         MOVE.L 12(A6),A0    ; Извлечь адрес A
         MOVE D0,(A0)        : Сохранить A

         UNLK A6

         RTS

Все это может быть обработано с изменениями в LoadParam  and StoreParam:

 

{ Load a Parameter to the Primary Register }

procedure LoadParam(N: integer);
var Offset: integer;
begin
     Offset := 8 + 4 * (NumParams - N);
     Emit('MOVE.L ');
     WriteLn(Offset, '(A6),A0');
     EmitLn('MOVE (A0),D0');

end;

 

{ Store a Parameter from the Primary Register }

procedure StoreParam(N: integer);
var Offset: integer;
begin
     Offset := 8 + 4 * (NumParams - N);
     Emit('MOVE.L ');
     WriteLn(Offset, '(A6),A0');
     EmitLn('MOVE D0,(A0)');

end;

 

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

    ParamList := 4 * N;

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

Теперь мы научились обрабатывать параметры использую передачу по значению и передачу по ссылке. В реальном мире, конечно, мы хотели бы иметь возможность работать с обоими методами. Однако пока мы не можем этого сделать, потому что у нас еще не было урока по типам.

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

Это, фактически, будет одним из различий между TINY и KISS. В следующей версии TINY мы будем использовать передачу по ссылке для всех параметров. KISS будет поддерживать оба метода.

ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ

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

И снова здесь мы стоим перед выбором: статическое или динамическое хранение?

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

Нам это легко сделать, используя уже имеющийся механизм распределения. Помните, однако, что локальные переменные могут иметь те же самые имена, что и глобальные переменные. Мы так или иначе должны согласиться с этим, назначая уникальные имена для этих переменных.

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

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

Альтернативой является динамическое хранение, при котором память распределяется в стеке точно также как и для переданных параметров. Для это мы уже имеем готовый механизм. Фактически, те же самые подпрограммы, которые работают с переданными (по значению) параметрами в стеке, могут так же легко работать и с локальными переменными... генерируемый код тот же самый. Назначение смещения в инструкции 68000 LINK сейчас такое: мы можем использовать его для регулировки указателя стека при выделении места для локальных переменных. Динамическое хранение, конечно, по существу поддерживает рекурсию.

Когда я впервые начал планировать TINY, я должен признаться имел предубеждение в пользу статического хранения. Просто потому, что старые FORTRAN программы  были чрезвычайно эффективны... ранние компиляторы FORTRAN производили качественный код, который и сейчас редко сопоставим с современными компиляторами. Даже сегодня данная программа, написанная на FORTRAN, вероятно превзойдет, ту же самую программу, написанную на C или Pascal, иногда с большим отрывом. (Вот так! Что вы скажете на это заявление!)

Я всегда полагал, что причина имела отношение к двум основным различиям между реализациями Фортрана и другими языками: статическое хранение и передача по ссылке. Я знаю, что динамическое хранение поддерживает рекурсию, но мне всегда казалось немного странным желание мириться с более медленным кодом, который в 95% случаев не нуждается в рекурсии, только для того чтобы получить эту возможность когда она понадобится. Идея состоит в том, что со статическим хранением вы можете использовать не косвенную а абсолютную адресацию, которая должна привести к более быстрому коду. \

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

    MOVE 8(A6),D0

имеет тоже самое время выполнения, что и

    MOVE X(PC),D0.

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

Так как такое использование локальных переменных так хорошо соответствует схеме передачи параметров по значению, мы будем использовать эту версию транслятора для иллюстрации (я надеюсь вы сохранили копию!).

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

Давайте начнем с создания новой переменной Base:

    var Base: integer;

Мы будем использовать эту переменную вместо NumParams для вычисления смещения стека. Это подразумевает изменение двух ссылок на NumParams в LoadParam и StoreParam:

 

{ Load a Parameter to the Primary Register } 
procedure LoadParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 8 + 2 * (Base - N); 
     Emit('MOVE '); 
     WriteLn(Offset, '(A6),D0'); 
end; 
 
{ Store a Parameter from the Primary Register } 
procedure StoreParam(N: integer); 
var Offset: integer; 
begin 
     Offset := 8 + 2 * (Base - N); 
     Emit('MOVE D0,'); 
     WriteLn(Offset, '(A6)'); 
end;

 

 

 

Идея состоит в том, что значение Base будет заморожено после того, как мы обработаем формальные параметры и не будет увеличиваться дальше когда новые, локальные, переменные будут вставлены в таблицу идентификаторов.  Об этом позаботится код в конце FormalList:

 

{ Process the Formal Parameter List of a Procedure } 
procedure FormalList; 
begin 
     Match('('); 
     if Look <> ')' then begin 
          FormalParam; 
          while Look = ',' do begin 
               Match(','); 
               FormalParam; 
          end; 
     end; 
     Match(')'); 
     Fin; 
     Base := NumParams; 
     NumParams := NumParams + 4; 
end; 

 

 

 

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

Все что мы должны сделать дальше - это установить семантику объявления локальных переменных в синтаксическом анализаторе. Подпрограммы очень похожи на Decl и TopDecls:

 

{ Parse and Translate a Local Data Declaration } 
procedure LocDecl; 
var Name: char; 
begin 
   Match('v'); 
     AddParam(GetName); 
     Fin; 
end; 
 
{ Parse and Translate Local Declarations } 
function LocDecls: integer; 
var n: integer; 
begin 
     n := 0; 
     while Look = 'v' do begin 
          LocDecl; 
          inc(n); 
     end; 
     LocDecls := n; 
end; 

 

 

 

Заметьте, что LocDecls является функцией, возвращающей число локальных переменных в DoProc.

Затем мы изменим DoProc для использования этой информации:

{ Parse and Translate a Procedure Declaration } 
procedure DoProc; 
var N: char; 
      k: integer; 
begin 
     Match('p'); 
     N := GetName; 
     if InTable(N) then Duplicate(N); 
     ST[N] := 'p'; 
     FormalList; 
     k := LocDecls; 
     ProcProlog(N, k); 
     BeginBlock; 
     ProcEpilog; 
     ClearParams; 
end;

 

(Я сделал пару изменений, которые не были в действительности необходимы. Кроме небольшой реорганизации я переместил вызов Fin в FormalList а также в LocDecls. Не забудьте поместить его в конец FormalList.)

Обратите внимание на изменения при вызове ProcProlog. Новый параметр - это число слов (не байт) для распределения памяти. Вот новая версия ProcProlog:

{ Write the Prolog for a Procedure } 
procedure ProcProlog(N: char; k: integer); 
begin 
     PostLabel(N); 
     Emit('LINK A6,#'); 
     WriteLn(-2 * k) 
end;

 

 

 

Сейчас должно работать. Добавьте эти изменения и посмотрите как они работают.

ЗАКЛЮЧЕНИЕ

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

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