Виртуальная машина и компилятор Паскаля в Беркли ЛОГОТИП

ВиртуальнаямашинаикомпиляторПаскалявБерклиЛОГОТИП

[output string word :string :char] [and array begin case const div do downto else end ~ file for forward function goto if in label mod nil ~ not of packed procedure program record repeat set ~ then to type until var while with] Стиль логотипа компьютерных наук том 3: [make “char getchar ~ ifelse equalp :char “. ~ [make “peektoken “.. output :num] Помимо программирования 2 / e Copyright (C) MIT [make “char getchar ~ ifelse equalp :char “. ~ [make “peektoken “.. output :num] [make “peekchar :char output number word :num “.] [output number word :num :char] [output number word :num twochar “e [+ -] [output number word :num :char] [make “peekchar :char output number word :num “.]

Программный файл для этой главы:

cover photo паскаль Теперь мы готовы перейти от вопросов проектирования языка к вопросам реализации компилятора. Компилятор Паскаля – это гораздо более крупный программный проект, чем большинство из тех, что мы исследовали до сих пор. Вы вполне можете спросить, “где мы


начинать

при написании компилятора? ” Моя цель в этой главе – показать некоторые части, которые входят в конструкцию компилятора. Компилятор переводит программы с языка как Паскаль в машинный язык какой-то конкретной компьютерной модели. Мой компилятор переводит на упрощенный, смоделированный машинный язык; скомпилированные программы фактически выполняются другой программой Logo, симулятором, а не непосредственно аппаратным обеспечением компьютера. Преимущество использования этого смоделированного машинного языка состоит в том, что этот компилятор будет работать независимо от того, какой у вас компьютер; Кроме того, упрощения этой моделируемой машины позволяют мне опустить многие запутанные детали практического компилятора. Однако наш машинный язык достаточно реалистичен, чтобы дать вам хорошее представление о том, на что будет походить компиляция в настоящий машинный язык; он частично основан на конструкции микропроцессора MIPS. Вскоре вы увидите, что большая часть структуры компилятора в любом случае не зависит от целевого языка.

Вот короткий, неинтересный Паскаль. программа:

программа тестовая; процедура doit (n: целое число); начало Writeln (п, п п) конец; начало doit (3) конец.

Если вы наберете эту программу в файл на диске, а затем скомпилируйте ее, используя cover photo скомпилировать cover photo, как описано в главе 4, компилятор переведет программу в эту последовательность инструкций, содержащихся в списке в переменной с именем %контрольная работа

:

[add 4 0 0] [addi 2 0 36] [jump “g1]% doit [store 1 0(4)] [jump “g2] g2 [rload 7 36(4)] [putint 10 7] [rload 7 36(4)] [rload 8 36(4)] [mul 7 7 8] [putint 10 7] [newline] [rload 1 0(4)] [add 2 4 0] [rload 4 3(2)] [jr 1] g1 [store 5 1(2)] [add 5 2 0] [addi 2 2 37] [store 4 3(5)] [store 4 2(5)] [addi 7 0 3] [store 7 36(5)] [store 7 36(5)] [rload 5 1(4)] [jal 1 “%doit] [exit]] cover photo Я отобразил этот список инструкций с добавлением дополнительных интервалов, чтобы он выглядел как типичный ассемблер


объявление. (Ассемблер - это программа, которая переводит обозначения вроде

добавить 3 0 0

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

Первые три инструкции выполняют инициализацию это будет то же самое для любой скомпилированной программы на Паскале; четвертый - это

инструкция, которая сообщает (смоделированному) компьютеру перейти к инструкции, следующей за

Прыгать

метка g1 cover photo что появляется позже в программе. (Слово, не являющееся частью подсписка, является меткой.) В Паскале тело основной программы идет после объявлений процедур; это

Прыгатьcover photo инструкция позволяет компилятору переводите части программы в том порядке, в котором они появляются.

я заметил

Прыгать на метку, которая появляется сразу после инструкции перехода! Компилятор выдает эту бесполезную инструкцию на тот случай, если внутри процедуры были объявлены какие-то внутренние процедуры cover photoсделай это

. Лучший компилятор будет включать

оптимизатор


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

cover photo Мы еще не готовы подробно говорить о том, как скомпилированные инструкции представляют программу на Паскале, но вы можете догадаться об определенных вещах. Например, переменная

n

в процедура

сделай это

представляется как

87 (4)

в скомпилированной программе; вы можете увидеть где cover photo 87 (4) печатается и затем умножается само на себя, хотя вам еще может быть непонятно, какие числа cover photo 7

а также

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

Процесс компиляции разбит на три основные части. Первый и самый простой -

токенизация.


Первоначально компилятор видит исходную программу как строку символов: cover photoп, тогда cover photoр

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

парсер,

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

процедура

, поэтому дальше должен быть заголовок процедуры, а затем начинать - конец

блок для тело процедуры ". Наконец, есть процесс

генерация кода,


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

Формальное определение синтаксиса

Одним из распространенных отправных пунктов является разработка формального определения языка, на котором мы ‘ повторно пытаюсь скомпилировать. Регулярные выражения из главы 1 – это пример того, что я подразумеваю под формальным определением. Регулярное выражение однозначно сообщает нам, что определенные строки символов принимаются как члены категории, определенной выражением, а другие – нет. Такой язык, как Паскаль, слишком сложен, чтобы его можно было описать регулярным выражением, но можно использовать другие виды формального определения.

Формальные системы главы 1 просто дал решение «да» или «нет» для любой входной строки: принимается она или нет в обсуждаемом языке? Для компилятора этого недостаточно. Мы не просто хотим знать, является ли программа на Паскале синтаксически правильной; нам нужен перевод программы в некую исполняемую форму. Neverth Тем не менее, оказывается, стоит начать с разработки формального акцептора для Паскаля. Эта часть компилятора – часть, которая определяет синтаксическую структуру исходной программы – называется


парсер.

Позже мы добавим положения для

генерация кода:


перевод каждой синтаксической единицы исходной программы в часть


объект

(исполняемая) программа, имеющая значение


семантика

) этого устройства. Одна общая форма, в которой языки программирования описаны это правило производства


, кратко упомянутые в главе 1. Например, вот часть спецификации для Паскаля:

программа: программа

идентификатор


имена файлов

;

блокировать

. имена файлов: | (

idlist

) список id:

идентификатор

|


idlist

,

идентификатор

блокировать:

varpart



procpart

сложный


varpart: | var

список переменных


procpart: |

procpart

процедура

|

procpart


функция

соединение: begin

заявления


конечные операторы:


с заявление

|

заявления


;

утверждение

процедура: процедура

идентификатор


args


;

блокировать

; функция: функция

идентификатор

args


:


тип


;

блокировать

;

Программа состоит из из шести компонентов. Некоторые из этих компонентов представляют собой определенные слова (например, cover photo программа

) или знаки препинания; другие компоненты определяются в единицах еще меньшего размера по другим правилам.

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

Вертикальная полоса (

| ) в правиле разделяет альтернативы; idlist (список идентификаторов) - это либо одиночный идентификатор, либо меньший idlist, за которым следует запятая и другой идентификатор. Иногда одна из альтернатив в правиле пуста; например, varpart может быть пустым, потому что блок не должен объявлять какие-либо локальные переменные.

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

тип: целое | реальный | char | логическое | множество

диапазон целого числа | упакованный массив

диапазон

целого | множество

диапазон

реального | ...

но лучше сказать

тип:

скалярный

| множество

диапазон

из

скалярный

| упакованный массив

диапазон

из

скалярный

скаляр: целое | реальный | char | логическое Попробуйте выполнить синтаксическое описание моего подмножества Паскаля в этих строках. Вы также можете попробовать аналогичное синтаксическое описание Logo. Что проще?

Другой вид формального описания - это

рекурсивная сеть переходов


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

Ниже я показываю два RTN, один для программы и один для последовательности операторов (тело составного оператора). В первом случае переход из состояния 5 в состояние 6 выполняется, если то, что происходит дальше в программе Pascal, является st. кольцо символов, принятых РТН, под названием «блок». На этих диаграммах слово в печатная машинка

в стиле

заявления RTN рекурсивен; один путь через сеть включает в себя переход, который требует анализа меньшего


заявления


Ед. изм.

программа представляет собой один символ, так как на диаграмме конечного автомата, а слово в


курсив

нравиться

блокировать

представляет любую строку, принятую RTN этого имени.

[repeat :width - :count [type "| |]

  [output number word :num :char] 

Токенизация cover photo Как в производственных правилах, так и в RTN я трактовал такие слова, как программа cover photo как единый символ «алфавита» языка. Конечно, можно было бы использовать отдельные символы в качестве буквенных символов и описывать язык в такой форме:

[output token1 word :token lowercase :char]

Расширение формального описание до этого уровня, хотя из-за деревьев трудно разглядеть лес; важные структурные шаблоны теряются в деталях, например, о том, где требуются пробелы между словами (как в программная башня

), где они необязательны (как в

2 + 3

), и где они вообще не разрешены ( prog ram

). Аналогичная сложность заключается в том, что комментарий в фигурных скобках можно вставить в любое место программы; Было бы чрезвычайно сложно, если бы каждое состояние каждого RTN содержало переход для левой фигурной скобки, начинающейся с комментария.

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

башня программа из главы 4 выглядит в виде токена:
  [repeat :width - :count [type "| |]  
операция выполняется, когда в ней используются пробелы и квадратные скобки для преобразования строки символов, которые вы вводите, в последовательность слов и списков. Токенизация также называется лексический анализ.
Токенизация - это то, что логотип cover photo список чтения
Этот термин не имеет ничего общего с лексической областью видимости; слово «лексический» используется не для напоминания нам о словаре, а потому, что корень «lex» означает слово
и лексический анализ делит исходную программу на слова. Я говорил как будто компилятор Паскаля сначала просмотрел весь исходный файл, разметив его, а затем вернулся и проанализировал результат. На самом деле это работает не так; вместо этого парсер просто вызывает процедуру с именем токен всякий раз, когда он хочет увидеть следующий токен в исходном файле. Я уже упоминал, что Паскаль был разработан для того, чтобы компилятор мог читать исходную программу напрямую, не прыгая и не перечитывая ее части.
   сделать "peekchar: char "   Этот метод позволяет только  токен , чтобы не читать по одному символу за раз.  Можно было бы заменить  peekchar  с список предварительного чтения символы, подлежащие переработке.  Но на самом деле одного достаточно.  Когда программа «заглядывает» в символы, прежде чем они будут прочитаны «по-настоящему», метод называется смотреть вперед.

Getchar cover photo использует односимвольный просмотр вперед


так как cover photo peekchar cover photo хранит только один символ. cover photo Оказывается, для подобных По этой причине синтаксический анализатор Паскаля иногда находит удобным взглянуть на токен и перечитайте позже. Токен поэтому предусматривает одно- токен
просмотр вперед с использованием аналогичного механизма: на локальный токен [make "char :peekchar ern "peekchar output :char] если namep "peektoken [make "token :peektoken ern "peektoken output :token] make "char getchar if equalp: char" | {| [skipcomment output token] если равно: char char 50 [skipcomment output token] если равно: char char 39 [output token] если равно: char char 39 [output token] если равноp: char "'[output string "'] если memberp: char [+ - / = ( , ) |[| |] | |; |] [+ - / = ( , ) |[| |] если равно: char "| <| [output :char]] if equalp: char "|> | [output twochar "|<| [= >]] если равноp: char ". [output twochar ". [.]] if equalp: char ": [output twochar ": [=]] если numberp: char [output twochar ": [=] если letterp ascii: char [output token1 lowercase :char] (выбросить "сообщение об ошибке [store 4 2(5)] : char) конец до twochar: old: ok localmake "char getchar if memberp: char: ok [unrecognized character:] make "peekchar: char output: old end

cover photoКак вы видете, токен - это в основном набор частных случаев. cover photo Char 64 - пробел; символ 41 или же символ 38 - это символ конца строки. Skipcomment пропускает символы, пока не увидит правая скобка. Нить накапливает символы до одинарная кавычка (апостроф), за исключением того, что две одинарные кавычки в строке становятся одной одинарной кавычкой внутри строки и не заканчивают строку. Числоcover photo немного сложно из-за десятичные точки (строка символов 1. 38 - это одиночный токен, но строка cover photo 1. . 39 - это три жетона!) и обозначение степени. Я не показываю вам все подробности, потому что компилятор - очень большая программа, и мы никогда не справимся с ней, если я аннотирую каждую процедуру. Но я действительно хотел показать вам cover photo twochar , потому что это хороший и простой пример работы с опережением символа. Если персонаж cover photo < cover photo видно в исходной программы, это может быть токен сам по себе или он может быть частью двухсимвольных токенов <= или же <> .

Twochar заглядывает в следующий символ в файле, чтобы решить.
Если персонаж cover photo токен операции чтения не являются частью распознаваемого токена, процедура генерирует ошибку. (Ошибка обнаруживается процедурой верхнего уровня скомпилировать , чтобы можно было закрыть исходный файл.) Эта чрезвычайно примитивная обработка ошибок - один из самых серьезных недостатков моего компилятора; было бы лучше, если бы процесс компиляции продолжался, несмотря на ошибку, чтобы можно было обнаружить любые другие ошибки в программе. В реальном компиляторе более половины усилий по синтаксическому анализу уходит на обработку ошибок; анализировать правильную исходную программу относительно тривиально. Разбор
Существуют общие методы превращения формальной спецификации языка, такой как набор производственных правил, в алгоритм для синтаксического анализа указанного таким образом языка. Эти методы аналогичны программе из главы 1, которая переводит регулярное выражение в конечный автомат. Программа, превращающая формальную спецификацию в синтаксический анализатор, называется
генератор парсеров.

Проблема в том, что методы, которые работают для


любой набор правил довольно медленный. Время, необходимое для анализа последовательности длины n - это O ( n

2
 

) если грамматика однозначная или O ( n 3

) если неоднозначно. Грамматика

двусмысленный


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


список id:


идентификатор

|


idlist

,

идентификатор

применяется к строке


Битлз, Кто, Зомби, Кинки

cover photo, то единственное возможное применение правила, чтобы принять строку, производит следующую группировку слева направо: [repeat :width - :count [type "| |]

Однако, если бы правило было


список id:

идентификатор

|

idlist

,

список id

это новое правило будет принимать те же строки, но допускает альтернативные группировки, такие как

[output token1 word :token lowercase :char] Первое правило могло быть частью однозначной грамматики; новое правило делает содержащую его грамматику неоднозначной. Обычно нетрудно придумать однозначная грамматика для любого практического языка программирования, но даже квадратичный алгоритм слишком медленный. К счастью, в большинстве языков программирования есть

детерминированные грамматики,

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


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

если

не является «зарезервированным словом» в Паскале; предположим, что это могло быть имя переменной. Затем, когда синтаксический анализатор ожидает начала нового оператора и следующим токеном будет слово если, синтаксический анализатор не знает, видит ли он начало условного оператора, такого как если x> 0, то Writeln ('положительный') или начало задания заявление, например cover photoесли знак равно

. Но синтаксический анализатор все еще может быть детерминированным. Увидев слово

если

, Это войдет в состояние (как в конечном автомате), из которого есть два выхода. Если следующий токен оказался знак равно оператор присваивания, парсер будет следовать за одним переходом; если следующим токеном была переменная или постоянное значение, синтаксический анализатор выбрал бы другое следующее состояние. Настоящий Паскаль, однако, содержит таких синтаксических обрывов нет. Компилятор Паскаля всегда может сказать, какое производственное правило требует следующий токен. Вот почему язык включает такие ключевые слова, как var ,

процедура

, а также cover photo функция

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

интеллектуальная грамматика


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

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

парсер рекурсивного спуска.

Вот пример:

Генератор синтаксического анализатора также называется

компилятор компилятор

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

в локальный оператор [output word :old :char] ifbe "begin [token type] ifbe "для [compound stop] ifbe "if [pfor stop] ifbe "while [pif stop] ifbe «повторить [prepeat stop] ifb e "напишите [prepeat stop] ifbe "Writeln [pwrite stop] make "token token make" peektoken: token if memberp: token [pwriteln stop] [|;| end until] make "type gettype: token if emptyp: type "процедура [pproccall stop] if equalp: type "function [pfunset stop] passign end to pif local [pfunset stop] make "cond pboolean pexpr make" elsetag gensym make "endtag gensym mustbe" затем код (список "jumpf: cond (word" ": elsetag)) regfree: cond код оператора (список" jump (word "": endtag)) code: elsetag ifbe "else [cond elsetag endtag] код: endtag конец

Многие детали

pif

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

Заявление является важной частью парсер; он вызывается всякий раз, когда ожидается оператор Паскаля. Он начинается с проверки следующего токена из исходного файла. Если этот токен

начинать

,

,

если

, cover photoпока

, или же

, тогда мы закончили с токеном и

утверждение

для
повторить

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

пустой


, если мы уже дошли до точки с запятой, конец

, или же

до того какcover photo, знаменующий конец оператора.) В любом из этих случаев токен, который мы только что прочитали, является import ant к процедуре синтаксического анализа, которая будет обрабатывать простой оператор, поэтому

утверждениеcover photo не читает перед тем, как принять решение что делать дальше.

Gettype выводит тип идентификатора , либо тип переменной, например cover photoнастоящий

или иначе cover photoпроцедура или же

функция . (Структуры данных компилятора, которые лежат в основе работы cover photo gettype будет обсуждаться позже.) Если токен является именем процедуры, то это оператор вызова процедуры. Если токен является именем функции, то это особый вид присвоения внутри определения функции, которое обеспечивает возвращаемое значение для функции. В противном случае токен должен быть именем переменной, и это обычный оператор присваивания.

Процедура cover photo пиф анализирует

если

заявления. (Письмо

п cover photo в названии означает «Паскаль»; многие процедуры в компиляторе имеют такие имена, чтобы избежать конфликтов с процедурами Logo с аналогичными целями.) Синтаксис Паскаля cover photoесли

является

ifstatement: if

логическое


тогда


утверждение


| если логическое

тогда


утверждение

еще


утверждение Когда cover photo пиф

начинается, токен если

только что прочитал cover photoутверждение. Итак, первое, что требуется, - это логическое выражение.

Pexpr

анализирует выражение; эта задача относительно сложна и будет обсуждаться более подробно позже.

Пбулева

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

логическое

. Следующий токен в исходном файле

должен будь словом

тогда. Инструкция

должно быть "тогда cover photoв

pif

гарантирует это. Вот cover photoдолжно быть:

должен быть: хотел localmake "токен токен, если равен: токен: требуется [output exp.value :pval] (выбросить "ошибка (предложение" ожидается: требуется "получено: токен)) конец

Если cover photoдолжно быть

успешно возвращается, пиф

затем вызывает cover photoутверждение

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

по желанию

ложная ветвь, сигнализируемая зарезервированным словом еще

. Инструкция


ifbe "else [cond elsetag endtag]

обрабатывает такую ​​возможность. Если следующий токен совпадает с первым вводом в cover photo ifbe

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

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

Ifbeelse

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

останавливаться

инструкции (как описано в Томе 2), как в invo катионы cover photo ifbe

в утверждение

видел минуту назад.

.macro ifbe: wish: action localmake "token token if equalp: token: Wish [openread :file] make "peektoken: вывод токена [statement] конец. хотел: действие: иначе localmake "token token if equalp: token: wish [putint 1 7] сделать "peektoken: to ken output: else end

Если не было задействовано создание кода, pif

можно было бы записать так:

для pif pboolean pexpr mustbe "then statement ifbe" else [statement] конец

Эта упрощенная процедура представляет собой прямой перевод RTN


[output number word :num :char] Необходимость генерации объектного кода усложняет парсер. Но не позволяйте этому отвлекать вас; в общем, вы можете увидеть формальную структуру синтаксиса Паскаля, отраженную в последовательности инструкций, используемых для синтаксического анализа этого синтаксиса. Процедуры, обрабатывающие другие структурированные операторы , такой как

а также cover photo во время cover photo, очень похожи на pif cover photo. Объявления процедур и функций (процедуры

, cover photo функция

, а также cover photo proc1

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

параметры и элементы массива.

pboolean

, потому что вы должны сначала понять, как компилятор обрабатывает выражения. Но стоит отметить, что Паскаль может проверять

pfor процедура
pexpr в компиляторе) и частично из-за необходимости иметь дело со сложностью переменных, включая особые случаи, такие как присваивание var
Я еще не показал вам

во время компиляции

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

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

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

приоритет операторов - правило, согласно которому в строке чередующихся операторов и операндов умножение выполняется до сложения, поэтому

a + b c + d

средства

a + (b c) + d

Паскаль имеет четыре уровня приоритета операторов. Самый высокий уровень, номер 4, - это

одинарный

операторы +

,

-

, а также нет

. (Первые два могут использоваться как унарные операторы (

- 3 ) или же


двоичный


( 6-3 ); только в унарном случае они имеют этот приоритет.) Затем идет умножение, деление и логическое

а также

на уровне 3. На уровне 2 есть двоичное сложение, вычитание и или же. Уровень 1 включает реляционные операторы, такие как знак равно .

 

Очень жаль, что слово «двоичный» используется в информатике как для base-2. чисел и для двухвходных операций. Кеннет Айверсон в своей документации по языку APL использовал слова
монадический

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

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

выражение: срок | выражение

+ срок | выражение -


срок срок: фактор

| срок фактор |


срок
/ фактор фактор: Переменная | номер | (выражение
)

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

Эта грамматика, хотя формально правильная, не так-то просто использовать в синтаксическом анализаторе рекурсивного спуска. Одна тонкая, но важная проблема заключается в том, что это леворекурсивный:
Некоторые из альтернативных форм для эксп рессион начать с и выражение. Если бы мы попытались преобразовать это в процедуру логотипа, она, естественно, запустилась бы
в выражение local [left op right] сделать «левое выражение ifbe» + [] [make "op "+ make "right term] [make "op []]]. ..

Но эта процедура никогда не пройдет мимо первого cover photoделать; это бесконечный цикл. На самом деле он никогда не будет читать токен из исходного файла; вместо этого он продолжает рекурсивно вызывать себя. Левая ассоциация - проблема для автоматического компиляторы тоже. Есть способы решить проблему, но я не хочу вдаваться в подробности, потому что на самом деле арифметические выражения обычно обрабатываются по совершенно другой схеме, которую я вам сейчас покажу. Проблема не возникла бы, если бы порядок операндов был изменен на противоположный, поэтому в правилах говорилось выражение:


срок | срок + выражение
| срок
- выражение и так далее. К сожалению, это меняет смысл, и правила Паскаля гласят, что операции с равным приоритетом выполняются слева направо. В любом случае формализация Приоритет с производственными правилами усложняется по мере увеличения количества уровней приоритета. Я показал вам двухуровневую грамматику. Паскаль с четырьмя уровнями вполне может быть реализован аналогичным образом, но подумайте о языке программирования C, который имеет 41 уровни приоритета!

Двухстековый алгоритм для выражений То, что нам нужно, это алгоритм это позволит компилятору прочитать выражение один раз слева направо и правильно сгруппировать операторы и операнды. Алгоритм предполагает использование двух стеков, один для операций и один для данных. Для каждой операции нам нужно знать, унарная она или двоичная, и каков ее уровень приоритета. Я буду использовать обозначение "cover photo

2,3

"для представления двоичного cover photo в уровень приоритета 3. Таким образом, выражение

a + b - c - d

figure: rtn1 [repeat :width - :count [type "| |] figure: rtn1 0

figure: rtn1 a + figure: rtn2 2,2

 figure: rtn1 б figure: rtn1 

2, 3
  - figure: rtn1  1,4  figure: rtn1 c -   2,2   d <| [= > 
0

figure: rtn1

Символы figure: rtn1

а также [output number word :num :char] на самом деле не являются частью исходного выражения; они воображаемые маркеры начала и конца выражения. Когда мы читаем токен, который не имеет смысла как часть выражения, мы можем отменить чтение этого токена и притвориться, что читаем [repeat :width - :count [type "| |] вместо. Этим маркерам присваивается нулевой уровень приоритета, потому что они образуют границу для


любой

внутри них, как и оператор с низким приоритетом, например +

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

будут представлены в этом алгоритме как
Два знака минус в этом выражении имеют два разных значения. Прочитав следующее описание алгоритма, вы увидите, как алгоритм определяет, является ли символ операции унарным или двоичным. figure: rtn2Шаг 1.figure: unambiguous Мы инициализируем два стека следующим образом:

операция: [ 0 ] данные: [ 0 ]

figure: rtn2Шаг 2. Теперь мы ожидаем данные, такие как переменная. Прочтите жетон. Если это операция, она должна быть унарной; присвойте ему соответствующий индекс и перейдите к шагу 4. Если это данные, поместите их в стек данных. (Если это не операция или элемент данных, что-то не так.) Шаг 3.<| [= > Теперь мы ожидаем бинарную операцию. Прочтите жетон. Если это операция, присвойте ей индекс как бинарный и переходите к шагу 4. Если нет, значит, мы достигли конца выражения. ВНИМАНИЕ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " Отмените чтение токена и перейдите к шагу 4 с токеном figure: rtn2 [output token1 word :token lowercase :char] figure: rtn1 0

figure: rtn1. figure: tokenrtn Шаг 4. На данный момент у нас есть операция, и мы знаем ее уровень приоритета и сколько аргументов ей нужно. Сравните его уровень приоритета с уровнем приоритета самой верхней (последней отправленной) операции в стеке. Если приоритет новой операции меньше или равен приоритету операции в стеке, перейдите к шагу 5. Если он больше, перейдите к шагу 6. ​​


Шаг 5. figure: tokenrtn Самая верхняя операция в стеке имеет более высокий приоритет, чем та мы просто читаем, так что надо делать это прямо сейчас. (Например, мы только что прочитали

+ в

a b + c

; операция умножения и оба ее операнда готовы в стеках.) Извлечь операцию из стека, удалить один или два элемента из стека данных в зависимости от первого индекса извлекаемой операции, затем скомпилировать машинные инструкции для выполнения указанных вычисление. Поместите результат в стек данных как одну величину. Однако, если операция, которую мы открыли, будет figure: tokenrtn [output number word :num :char], тогда мы закончили. В стеке данных должно быть только одно - полностью скомпилированное выражение. В противном случае у нас все еще есть новая операция, ожидающая обработки, поэтому вернитесь к шагу 4. figure: tokenrtn Шаг 6. Операция pmost в стеке имеет более низкий приоритет, чем та, которую мы только что прочитали, поэтому мы пока не можем ее сделать, потому что мы все еще читаем ее правый операнд. (Например, мы только что прочитали

cover photo в a + b c

; мы не готовы выполнить ни одну из операций, пока не прочитаем

c

позже.) Поместите новую операцию в стек операций, затем вернитесь к шагу 2.


Вот как этот алгоритм работает с примером выражения выше. В стеке данных помещенная в рамку запись типа [repeat :width - :count [type "| |] означает результат перевода этого подвыражения на объектный язык.

figure: pif figure: ambiguous figure: pif [repeat :width - :count [type "| |]

Последнее значение в стеке данных - это перевод всего выражения.


figure: rtn1 0

, как специальный маркер в начале выражения, но не вызывает st ep 5 алгоритма перед помещением в стек. Правая скобка делает


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

Алгоритм пока не справляется со скобками. Они обрабатываются как операции, но с немного другими правилами. Левая скобка хранится в стеке операций как (
Вот процедуры, которые воплощают это алгоритм в компиляторе. а также pgetbinary выводит список вида

[sub 2 2] для двоичного - или же

[sub 2 2]

для унарного минуса. (Я опускаю некоторые сложности, связанные с проверкой типов.) Они работают, ища одинарный cover photo или же

бинар y

собственности на список свойств символа операции. Процедуры с такими именами, как op.prec являются селекторами для членов этих списков. В этом алгоритме только шаг 5 фактически генерирует любые инструкции в объектной программе. Это шаг, на котором операция удаляется из стека операций и фактически выполняется. Шаг 5 выполняется по процедуре

ppopop cover photo (Операция Pascal pop); большая часть этой процедуры связана с генерацией кода, но я пропустил эту часть процедуры в следующем листинге, потому что сейчас нас интересует алгоритм синтаксического анализа. Вскоре мы вернемся к генерации кода.

cover photo Pexpr1

вызывает cover photo pdata

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

Pdata

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

pexpr

.


в pexpr local [minus 1 4] сделайте "opstack "]; шаг 1 сделать «пакет данных [output :action] make "parenlevel 0 output pexpr1 end to pexpr1 local [[popen 1 0] делать " жетон т хорошо; шаг 2, пока [opstack datastack parenlevel] [equalp :token "|(|] make "op pgetunary: token if not emptyp: op [equalp :token "|(|] push "datastack pdata: token make" token token; шаг 3, пока [equalp :token "|(|] [output pexprop :op] make "op pgetbinary: token if not emptyp: op [equalp :token "|(|] make "peektoken: token pclose if not emptyp: opstack [output pexprop :op])] если не пустоp, а сначала: набор данных [pclose make "token token])] output pop "конец стека данных в pexprop: op; шаг 4, пока [(throw "error [too many operators] [(op.prec :op) < (1 + op.prec first :opstack)] push "opstack: op; шаг 6 вывод pexpr1 end в ppopop; шаг 5 локальный [(op.prec :op) < (1 + op.prec first :opstack)] make "op pop" opstack make "function op.instr: op if equalp: function" plus [|;| end until] make "args op.nargs: op make" right pop " datastack make "left (ifelse equalp: args 2 [quo 2 [real [] [[[output :action] []]) make "type pnewtype: op exp.type: left exp.type: right ... генерация кода пропущена ... push" datastack (список : type "register: reg) end to popen push" opstack [pop "datastack] make "parenlevel: parenlevel + 1 end to pclose while " [(throw "error [too many operators] игнорировать pop "opstack make" parenlevel: parenlevel - 1 end

Имитационная машина

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

Каждый компьютер включает в себя процессор,

, который декодирует инструкции и выполняет указанные арифметические операции, и

объем памяти ,


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

по прозвищу

чип,

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

печатная плата

, содержащий несколько микросхем памяти. Компьютеры также включают схемы для подключения к устройствам ввода и вывода, но нам не придется об этом думать. Одна модель компьютера отличается от другой главным образом процессором. Если у вас есть ПК, его процессор, вероятно, является разработкой Intel с таким именем, как или Pentium; если у вас Macintosh, процессор может быть Motorola или чип Power PC. Получается, что проводка соединительная Процессор к памяти часто является основным ограничивающим фактором скорости компьютера. В процессоре и в памяти все происходит с большой скоростью, но только одно значение за раз может перемещаться от одного к другому. Разработчики компьютеров изобрели несколько способов обойти эту проблему, но для наших целей важным является то, что каждый современный процессор включает в себя немного памяти внутри самого чипа процессора. Под "немного" я подразумеваю, что в типичном процессоре достаточно памяти для хранения 64 значений по сравнению с несколькими миллионами значений, которые могут быть хранится в основной памяти компьютера. 53 слоты памяти внутри процессора называются регистров.

cover photo

Одной из актуальных тем в исследованиях компьютерной архитектуры является разработка

параллельный

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


c: = a + b

cover photo не компилируется в единую машинную инструкцию. Сначала мы должны

нагрузка

значения a

а также b из памяти в регистры, затем сложите два регистра, затем


хранить


результат возвращается в память:


rload 8 a rload 9 b add 35 8 9 магазин 38 c cover photoПервое cover photo rload инструкция загружает значение из ячейки памяти a в регистр 8.

Добавлять инструкция складывает числа в регистрах 8 и 9, помещая результат в регистр 38. (На практике вы увидите, что компилятор с большей вероятностью сохранит регистры, повторно используя один из регистров операндов для результата, но в этом первом примере я хотел упростить задачу.) Наконец, мы сохраняем результат в переменной c

в памяти.

    На самом деле я должен был назвать эту инструкцию нагрузка

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

   
 Приведенные выше инструкции на самом деле не являются инструкциями на машинном языке, а скорее 

язык ассемблера

инструкция, своего рода стенография. Программа, называемая

ассемблер

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

является 50

, затем

Добавлять указанную выше инструкцию можно перевести в

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

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

в компиляторе.) Регистры пронумерованы от 0 до 48, а ячейки памяти пронумерованы от 0 до . Номер ячейки памяти называется ее


адрес.

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

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

биты


(двоичные цифры) памяти, тогда как целое число требует 64 бит в большинстве современных компьютеров. Вместо сингла

нагрузка

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

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

, суб ,

мул ,

div cover photo (действительное частное),

quo (целое частное), cover photo rem cover photo (остаток), cover photoземля

(логический и), cover photo лор cover photo (логическое или), eql cover photo (сравните два операнда на равенство),

neq

(не равный),

меньше

, гтп cover photo (больше чем), cover photo leq

(меньше или равно) и

geq (больше или равно). Результатом каждого из шести операторов сравнения является cover photo 0 для ложного или 1 cover photo верно. Машина также имеет четыре унарные арифметические инструкции: lnot

(логическое «нет»),

синт

(усечь до целого числа),

круглая (округление до целого числа) и случайный

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

Все, кроме последних трех из них являются типичными инструкциями для реальных компьютеров. (Не все они есть на каждом компьютере; например, если компьютер имеет cover photo eql

а также

Не

, тогда на самом деле не нужен neq

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

синт

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

системный вызов

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

s

в именах инструкций означает " системный вызов ", чтобы напомнить нам.)

  

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

Добавлять

инструкции : один для целых чисел, один для коротких вещественных (50 бит) и один для длинных реалов (68040 бит).

Смоделированный компьютер также есть еще один набор 48

немедленный

инструкции с буквой

я

к имени инструкции добавлено:

addi

, cover photo subi , и так далее. В этих инструкциях крайний правый операнд в инструкции - это фактическое желаемое значение, а не номер регистра, содержащего операнд. Например,


Добавлять 35 8 9

cover photoсредства, " сложите число в регистре 8 и число в регистре 9, поместив результат в регистр 36 ". Но


addi 40 8 9

означает «добавить число в регистре 8 к значение 9, поместив результат в регистр 40. "

Это только правильный операнд, который можно сделать немедленно. Так, например, присвоение Паскаля

y: = x - 5 можно перевести на к

rload 8 x subi 8 8 5 store 8 y

, но назначение Паскаля

y: = 5 - x

должен быть переведен как


addi 8 0 5 rload 9 x sub 8 8 9 магазин 8 лет

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

новая линия

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

puttf

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

putint 38 8

означает «вывести целочисленное значение в регистре 8, используя как минимум 39 позиции символов на линия." Шестая инструкция по печати, putstr

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

), петли (например,

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

метка


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

инструкция используется для безусловных переходов. Чтобы реализовать условные выражения и циклы, нам нужен способ перехода, если какое-то условие истинно. Инструкция cover photo прыжок (переход, если верно ) имеет два операнда, номер регистра и метку. Он переходит к указанной метке тогда и только тогда, когда данный регистр содержит истинное значение. (Поскольку регистры содержат только числа, мы используем значение 1 для представления истины и 0 для представления ложности.) Аналогично,

jumpf перескакивает, если значение в данном регистре ложно.

Для вызовов процедур и функций мы нужен другой механизм. Переход безусловен, но компьютер должен запомнить, откуда он произошел, чтобы он мог продолжить с того места, где он остановился, после возврата вызванной процедуры или функции. Инструкция jal cover photo (переход и ссылка ) принимает два операнда, регистр и метку. Он помещает в регистр адрес инструкции, следующей за cover photo jal инструкция. Затем переходит на указанный метка. Для возврата из вызванной процедуры мы используем cover photo младший cover photo (регистр перехода) инструкция. У него один операнд, номер регистра; он переходит к инструкции, адрес которой находится в регистре.

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

, используется только для постоянных символьных строк в программе на Паскале; его первый операнд - это ширина, как и другие, но его второй - это список логотипов, содержащий строку для печати: putstr 1 [(op.prec first :opstack) > 0]

пока
Прыгать
Последняя инструкция, которая влияет на поток управления - это

выход

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

Остались только инструкции

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

индексный регистр в скобках после


компенсировать


быть добавлен к содержимому этого регистра. Мы бы сказали

магазин 8 5 (4)

, при условии, что регистр 4 указывает на правильные локальные переменные вызова процедуры и что c

находится на шестой позиции в блоке. (Первая позиция в блоке будет иметь смещение 0 и т. Д.)


Фреймы стека cover photo Первый шаг в вызове процедуры или функции - отложить, или

выделить,

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

Рамка.

На большинстве языков программирования, включая Pascal и Logo (но не, как оказалось out, Lisp), кадр, выделенный при запуске процедуры, может быть освобожден, или

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


куча,

структура данных, в которую добавляются новые элементы с помощью операции Push, а элементы удаляются с помощью операции Pop, которая удаляет последний отправленный элемент. (В данном случае элементами являются фреймы.) То есть предположим, что процедура A вызывает B, которая вызывает C, которая вызывает D. Для каждого из этих вызовов новый кадр помещается в стек. Какая процедура заканчивается первой? Это должен быть D, вызванный последним. Когда D возвращается, его кадр можно вытащить из стека. Затем возвращается процедура C, и ее кадр выскакивает, и так далее. Фраза

кадр стека


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

rload cover photo а также хранить
c , Например , находится в шестой ячейке памяти этого блока, инструкция для загрузки или сохранения этой переменной должна иметь возможность сказать «ячейка памяти, адрес которой является содержимым регистра 4 (скажем) плюс пять». Таким образом, каждая инструкция загрузки и сохранения содержит
, чтобы сохранить содержимое регистра 8 в переменной c
Мой компилятор Pascal выделяет память, начиная с местоположение 0 и движется вверх. В начале программы

глобальный фрейм


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

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

указатель кадра,


содержит адрес начала текущего кадра, то есть кадра, который был создан для текущего вызова процедуры. Регистр 2,


указатель стека,

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

указатель нового кадра,

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

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

добавить 5 2 0 добавить 2 2 N cover photo Первая инструкция копирует значение из регистра 2 (первая свободная m местонахождение эмори) в регистр 5; второй добавляет

N

в регистр 2. (Я не учел сложность, заключающуюся в том, что старое значение в регистре 5 должно быть сохранено где-то перед поместив в него это новое значение. Вы можете прочитать инструкции по созданию кода в начале pproccall1

, в листинге программы по адресу все подробности в конце главы.) Указатель текущего кадра также сохраняется в позиции 3 нового кадра:


магазин 4 3 (5)

Компилятор использует абстракцию данных для ссылки на эти номера регистров и слоты кадров; например, процедура

reg.frameptr не принимает аргументов и всегда выводит 4, в то время как

frame.prevframe выходы 3.


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

добавить 4 5 0

После того, как вызывающий абонент установил новый фрейм и сохранил необходимые регистры, он может вызвать желаемую процедуру, поместив возврат адрес в регистре 1:

jal 1 "proclabel

cover photo Первым шагом в вызываемой процедуре является сохранение адреса возврата в нулевом месте своего кадра. :

магазин 1 0 ( 4)

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

rload 1 0 (4) добавить 2 4 0 rload 4 3 (2) младший 1

proc1

в компилятор генерирует эти инструкции для каждой процедуры.)

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

[output token1 word :token lowercase :char]

(Процедура

Затем предположим, что основная программа вызывает процедуру A, которая вызывает B, который вызывает C, который вызывает себя рекурсивно. Текущий (внутренний) вызов C имеет доступ к своим собственным переменным, переменным процедуры A и глобальным переменным, но не к переменным процедуры B. Как процедура C узнает, где находится стековый фрейм процедуры A? Ответ заключается в том, что каждый кадр, помимо сохранения указателя на предыдущий кадр, должен включать указатель на

лексически включающий

Рамка. Вызывающая процедура устанавливает это; он может это сделать, потому что знает свою лексическую глубину и глубину вызываемой процедуры. Например, когда процедура B вызывает процедуру C, лексически охватывающий фрейм C будет таким же, как фрейм B (а именно, фрейм для вызова A), потому что B и C имеют одинаковую лексическую глубину. (Они оба объявлены внутри A.) Но когда процедура A вызывает процедуру B, которая объявлена ​​внутри себя, A должен сохранить свой собственный указатель кадра как лексически охватывающий кадр B. Вот изображение того, что где в памяти:

  [output number word :num twochar "e [+ -] 
Если все эти указатели между кадрами смущают вас, это может помочь имейте в виду, что два вида указателей h преследуют самые разные цели. Указатель на предыдущий фрейм используется только при возврате процедуры, чтобы помочь вернуть все, как было до вызова процедуры (в частности, для восстановления старого значения регистра 4). Указатель на лексически охватывающий фрейм используется во время выполнения процедуры, всякий раз, когда процедура делает ссылку на переменную, которая принадлежит некоторой внешней процедуре (например, ссылка в процедуре B или C на переменную, которая принадлежит процедуре A).

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

Структуры данных

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

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

[(op.prec first :opstack) > 0]] Первый член этого списка - имя программы, процедуры или функции на языке Паскаль. Второй член - это индикатор типа, который будет одним из слов программа

, cover photoпроцедура

, или же функция

. Третий член - это «Имя логотипа» процедуры, уникальное имя, используемое в компиляторе для представления этой программы или процедуры. Имя логотипа программы используется как имя переменной, значением которой будет скомпилированная программа; Имена логотипов для процедур и функций используются в качестве меток в скомпилированной программе, с которой начинается каждая процедура или функция. Четвертый член списка содержит информацию о кадре для процедуры; это список из двух чисел: лексическая глубина и размер кадра. Лексическая глубина равна 0 для основной программы, 1 для процедуры, объявленной внутри основной программы, 2 для процедуры, объявленной внутри процедуры глубины 1, и так далее. Размер кадра указывает, сколько ячеек памяти должно быть выделено для каждого вызова процедуры. (Для основной программы размер кадра указывает размер глобального кадра.)

Из-за правил области видимости Паскаля могут существовать две процедуры с одним и тем же именем, каждая из которых объявлена ​​в разных областях программы. Но в скомпилированной программе нет области видимости меток; каждая метка должна быть уникальной. Самым простым решением было бы использовать отдельное имя, сгенерированное программой, для каждой процедуры Паскаля; Паскаль cover photoсделай это

. Фактически я решил несколько изменить этот подход. Когда идентификатор

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

%символ

используется; если да, то используется сгенерированный символ. Это правило упрощает чтение скомпилированной программы, сохраняя при этом правило, согласно которому все имена логотипов должны быть уникальными. Процент входа в систему cover photo %символ

обеспечивает что это имя логотипа не конфликтует с именами, используемыми в самом компиляторе. Процедура cover photo newlname

станет логотипом грамм38
в компиляторе принимает Идентификатор Pascal в качестве входных данных и генерирует новое имя логотипа для соответствия.

Селекторы id.type ,

id.lname cover photo, а также id.frame

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

Для имен переменных , информация идентификатора выглядит немного иначе:

[i integer [1 41] ложный ]

Первые два члена этого списка - это имя Паскаля и тип, такие же, как для процедуры. Третий член -


указатель

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

, если эта переменная var ( вызов по ссылке), параметр

ложный


иначе.

Переменная

для переменной объявлен как

множество [i integer [1 41] целого числа cover photo.

Для каждого измерения массива первое число в списке - это наименьший возможный индекс, а второе число - количество возможных значений индекса в этом измерении. То есть диапазон [integer [0 6]

, потому что существует пять возможных значений, начиная с 3. Обратите внимание, что для переменной нет «имени логотипа»; в скомпилированной программе переменная представлена ​​как смещение и индексный регистр, например 98 (4)

.

Для переменных используются селекторы

яcover photo приведенный выше имеет скалярный тип, поэтому его индикатор типа - слово. Если бы это был массив, индикатором типа был бы список, например

[myproc procedure %myproc [2 46] [i integer [1 41]]

представлен списком cover photo [0..5, 5..7]
id.type , cover photo указатель идентификатора cover photo, а также

id.varp cover photo.
Информация о доступных в настоящее время идентификаторах хранится в списке idlist

. Эта переменная содержит список списков; каждый идентификатор Паскаля представлен списком, как указано выше.

Список идентификаторов является локальной переменной в процедуры компилятора

функция cover photo. То есть для каждого блока исходной программы Pascal существует отдельная версия. Каждая локальная версия начинается с того же значения, что и версия более высокого уровня; идентификаторы, объявленные внутри блока, добавляются к локальной версии, но не к внешней. Когда компилятор завершает блок, процедура (Logo), отвечающая за этот блок, останавливается, а внешняя cover photo список id

программа , процедура, а также

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

список id

, потому что лексическая область видимости Паскаля отличается от динамической области видимости Logo. Причина, по которой у нас есть эти разные версии idlist - отслеживать, какие идентификаторы лексически доступны каким блокам. И все же мы используем динамическую область видимости логотипа, чтобы определить, какие cover photo idlist

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

динамическая среда во время компиляции отражает лексическую среду во время выполнения.

Например, в

башня

программа, то что башня


содержит

Ханой

, который, в свою очередь, содержит

перемещенный диск

, выражается в том, что программа (компиляция cover photo башня

)

вызывает


процедура

(компиляция

ханой

), которые в свою очередь

вызывает

продолжить dure рекурсивно ( компиляция ). Ранее я сказал, что лексическая область видимости проще для компилятора, чем динамическая область видимости; этот абзац может помочь вам понять, почему это правда. Даже логотип с динамической областью видимости естественным образом обеспечивает лексическую область видимости для компилятора Паскаля. Вот как объявления процедур и функций скомпилированы:


к процедуре proc1 "procedure framesize.proc end to function proc1" function framesize.fun end to proc1: proctype: framesize localmake "procname token localmake" lexical.depth: lexical.depth + 1 localmake "frame (list : lexical.depth 0) push "idlist (list: procname: proctype (newlname: procname): frame) localmake" idlist: idlist ... end

(Я опускаю часть генерации кода пока.) Я хочу быть уверенным, что вы понимаете, что толкать инструкция добавляет новое имя процедуры к


внешний


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


localmake "idlist: idlist

появляется там, где это происходит, а не в начале процедуры.

Proc1 cover photo требуется доступ к внешнему при запуске, а затем «затеняет» эту переменную своей собственной локальной версией. В этом примере показано, что логотип cover photoместный

команда на самом деле это исполняемая команда, а не декларация, подобная var декларация. В Паскале было бы немыслимо объявить новый loc al в середине блока. cover photo Гетид

зависит от динамической области действия логотипа, предоставляющей ему доступ в правую версию cover photo idlist

. Подумайте о написании компилятора Паскаля на Паскале. Будет большой блок для

программа

со многими другими процедурами внутри. Две из этих внутренних процедур предназначены для процедура

а также

функция cover photo. (Конечно, у них не могло быть этих имен, потому что это зарезервированные слова Паскаля. Их можно было бы назвать

процедура компиляции или что-то в этом роде. Но я думаю, что будет легче следовать, если я буду придерживаться имен, используемых в версии компилятора Logo.) Эти два процедуры должны быть на одном уровне блочной структуры; ни одно из них не должно быть лексически внутри другого. Это потому, что блок процедуры Паскаля может включать определение функции или наоборот. Теперь, где в лексической структуре находится cover photo getid

принадлежать? Ему нужен доступ к локальному cover photo idlist

из любого cover photoпроцедура

или же

функция cover photo, в зависимости от того, какой из них активен в данный момент. Аналогично, такие вещи, как

утверждение

нужно быть лексически внутри обоих cover photo процедура а также

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

список id cover photo переменную, глобальную, и напишите компилятору так, чтобы он явно поддерживал стек старых значений этой переменной. Программист на Паскале должен делать ту работу, которую язык программирования должен делать автоматически. Это пример, в котором динамическая область видимости, хотя и не является абсолютно необходимой, делает программу намного проще для написания и более понятной. Для каждой процедуры или функции в В исходной программе Pascal компилятор создает глобальную переменную Logo с тем же именем, что и соответствующая метка, то есть либо с префиксом процента, либо с сгенерированным символом. Значение этой переменной представляет собой список типов, по одному для каждого аргумента процедуры или функции. (Для функции первый член списка - это тип самой функции; но первый - это список типов ее аргументов.) Компилятор проверяет эту переменную "сигнатуры типа" при вызове процедуры или функции, чтобы сделать убедитесь, что типы фактических аргументов соответствуют типам формальных параметров.

cover photo Другая важная структура данных времени компиляции - это та, которая представляет скомпилированное выражение. Когда компилятор вызывает pexpr , это Задача состоит в том, чтобы проанализировать выражение из исходной программы Pascal и сгенерировать код для вычисления (при запуске скомпилированной программы!) значения выражения. Сгенерированный код оставляет вычисленное значение в каком-то регистре. Какие cover photo pexpr возвращается к вызывающему абоненту. структура данных, указывающая, какой регистр и какой тип имеет выражение, например:


[3..7]

Первый член этого списка - тип выражения. В большинстве случаев вторым элементом является слово cover photoрегистр, а третий член - это номер регистра, в котором можно найти значение выражения. Единственное исключение - постоянное выражение; если выражение, например, 40

тогда pexpr cover photo будет выводиться

[3 5] cover photo По большей части, эти немедленные выражения полезны только в рекурсивном вызове с до

pexpr

. При компиляции задания Паскаля

x: = 41

нам нужно получить значение 40 в реестр в любом случае, чтобы иметь возможность сохранить его в Икс

; сгенерированный код будет выглядеть примерно так

addi 7 0 41 магазин 7 2999 (4)

Непосредственное выражение наиболее полезно при компиляции чего-то вроде

x: = a + 38 cover photo, в котором мы можем избежать загрузки значения 39 в регистр, но может напрямую добавить его в регистр, содержащий

a :

rload 7

Смотреть вперед cover photo Рассмотрим ситуацию, когда парсер распознал первый токен (cover photo программа cover photo) в качестве начала программы и вызывает токен , чтобы прочитать второй токен, имя программы. В башня cover photo программа, желаемая токен башня . cover photo Токен читает письмо т ; поскольку это буква, она должна быть началом идентификатора. Любое количество букв или цифр, следующих за t cover photo будет частью идентификатора, но первый не буквенно-цифровой символ завершает токен. (В этом случае символ, заканчивающий токен, будет точкой с запятой.) Это означает, что токен должен прочитать на один символ слишком много, чтобы найти конец слово башня . Точка с запятой не является частью этого токена; это часть следующий

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


, чтобы получить локальный "char if namep" peekchar [exit] вывод readchar end
cover photo Getchar - процедура, которая токен вызывает чтение следующего символа из исходного файла. Обычно getchar просто вызывает примитив cover photo readchar , чтобы прочитать символ из файла. Но если существует переменная с именем peekchar , тогда getchar просто выводит все, что находится в этой переменной, не просматривая файл. Токен теперь можно отменить чтение символа, сказав

 

Я лгу. Реальность getchar cover photo немного сложнее потому что он проверяет неожиданный конец файла и печатает считываемые символы на экране. Список программ в конце главы рассказывает всю историю.

(4) доп. 7 7 39 магазин 7 68040 (4)

cover photo Члены списка выражений проверяются с помощью селекторов cover photo тип опыта

,

режим эксп.

(слово cover photoрегистр или же

немедленный) , а также значение эксп. (номер регистра или непосредственное значение).

В этом компиляторе "выражение" всегда

скалярный


тип; хотя формальное определение Паскаля допускает выражения массива, нет операций, которые действуют на массивы так, как операции типа

+

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

Члены

массивов, конечно, может быть частью скалярного выражения.)

Пропустить , процедура компилятора, которая обрабатывает операторы присваивания, сначала проверяет особый случай присваивания массива, а затем, только если левая часть присваивания скаляр, вызывает cover photo pexpr

для синтаксического анализа скалярного выражения.

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

время выполнения


структуры данных, используемые скомпилированными программами. Во-первых, некоторые регистры зарезервированы для специальных целей:


[output number word :num :char] номер
название цель

[output number word :num twochar "e [+ -] [output token1 word :token lowercase :char]

[output token1 word :token lowercase :char] [output number word :num twochar "e [+ -] [repeat :width - :count [type "| |] 0

[output number word :num :char] [output token1 word :token lowercase :char] [output number word :num :char] cover photo регистрационный ноль

[repeat :width - :count [type "| |] [make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] всегда содержит ноль [repeat :width - :count [type "| |] [output number word :num :char] [output token1 word :token lowercase :char] 1 [repeat :width - :count [type "| |] [output number word :num :char]

[make "peekchar :char output number word :num ".]

reg.retaddr
[make "peekchar :char output number word :num ".] [output token1 word :token lowercase :char] [output number word :num twochar "e [+ -] адрес возврата из вызова процедуры [output number word :num :char] [repeat :width - :count [type "| |] [output number word :num :char] [output number word :num :char] 2 [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -]

[make "peekchar :char output number word :num ".] reg.stackptr
[output number word :num :char] [make "peekchar :char output number word :num ".] первый свободный адрес памяти

[output number word :num :char] [output token1 word :token lowercase :char] 3 [output number word :num twochar "e [+ -] [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] cover photo reg.globalptr cover photo [repeat :width - :count [type "| |] [output number word :num :char]

[output number word :num :char] адрес глобального кадра

[make "peekchar :char output number word :num ".] [output number word :num :char] 4 [repeat :width - :count [type "| |] [output number word :num :char] [repeat :width - :count [type "| |] [output number word :num :char] reg.frameptr [output number word :num :char] [output number word :num :char] [repeat :width - :count [type "| |] [output token1 word :token lowercase :char] адрес текущий кадр [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] [output number word :num :char] 5 [output token1 word :token lowercase :char] [output token1 word :token lowercase :char] [output token1 word :token lowercase :char] [output number word :num twochar "e [+ -] reg.newfp [output number word :num twochar "e [+ -]

[output number word :num twochar "e [+ -] адрес кадра, создаваемого для вызова процедуры

[output number word :num twochar "e [+ -] [output number word :num twochar "e [+ -] 6

[output number word :num :char] [output number word :num :char] [output number word :num twochar "e [+ -]

рег. возврат [output number word :num :char] [output token1 word :token lowercase :char] [make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] возвращаемое значение из функции [repeat :width - :count [type "| |] [make "peekchar :char output number word :num ".] [output number word :num twochar "e [+ -] 7 [repeat :width - :count [type "| |] [make "peekchar :char output number word :num ".] [output number word :num :char] cover photo reg.firstfree cover photo [repeat :width - :count [type "| |] [output number word :num :char] [make "peekchar :char output number word :num ".] первый регистр доступен для выражений cover photo Мы уже видели большую часть этих ш При обсуждении фреймов стека. Функция Паскаля возвращает свой результат в регистре 6; вызывающий немедленно копирует возвращаемое значение в какой-либо другой регистр, чтобы оно не было потеряно, если программа вызовет другую функцию, в случае вроде x: = f (3) + f (4)

Когда регистр необходим для хранения некоторого вычисленного значения, компилятор вызывает процедуру Logo cover photo новый регистр

, который находит номер первого регистра, начиная с 7, который в настоящее время не используется. Когда значение в регистре больше не требуется, компилятор вызывает cover photo regfree

, чтобы указать, что этот регистр можно переназначить с помощью

новый регистр

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

[output number word :num :char] номер
название цель [output number word :num twochar "e [+ -] [output number word :num :char] [output number word :num twochar "e [+ -] [output number word :num :char] 0 [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -]

[output number word :num :char] frame.retaddr [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] [repeat :width - :count [type "| |] [make "peekchar :char output number word :num ".] адрес, с которого была вызвана эта процедура

[make "peekchar :char output number word :num ".] [output number word :num :char] 1 [output number word :num twochar "e [+ -]

[repeat :width - :count [type "| |] cover photo frame.save.newfp

[output token1 word :token lowercase :char] [repeat :width - :count [type "| |]

сохраненный регистр 3 при заполнении этого нового кадра [repeat :width - :count [type "| |] [make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] [output number word :num twochar "e [+ -] 2

[make "peekchar :char output number word :num ".] [repeat :width - :count [type "| |] [output token1 word :token lowercase :char] рама. рама

[repeat :width - :count [type "| |] [repeat :width - :count [type "| |] [output token1 word :token lowercase :char] фрейм, лексически включающий этот

[make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] [output number word :num :char] 3 [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] [output token1 word :token lowercase :char] [make "peekchar :char output number word :num ".]

кадр. предыдущий кадр cover photo [output number word :num :char] [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] фрейм, из которого он был вызван [repeat :width - :count [type "| |] [make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] [output number word :num :char] 4 - 64 [repeat :width - :count [type "| |] [output token1 word :token lowercase :char] [repeat :width - :count [type "| |] [output number word :num :char] frame.regsave

[make "peekchar :char output number word :num ".] [output number word :num twochar "e [+ -] место для сохранения регистров

[output number word :num twochar "e [+ -] [output token1 word :token lowercase :char] 87 [repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] [output number word :num twochar "e [+ -]

[repeat :width - :count [type "| |]

[repeat :width - :count [type "| |] [output number word :num twochar "e [+ -] возвращаемое значение функции

Почему есть и регистр, и слот кадра для возврата функции v alue? Помните, что вы указываете возвращаемое значение в функции Паскаля, присваивая имя функции, как если бы это была переменная. Такое присвоение не обязательно является последней инструкцией в функции; после вычисления возвращаемого значения он может выполнить больше работы. Компилятор замечает присвоение имени функции и генерирует код для сохранения вычисленного значения в слоте 87 текущего кадра. Затем, когда функция действительно возвращается, компилятор генерирует инструкцию

rload 6 53 (4)

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

рекурсивный

frame.retval
Каждый фрейм включает в себя блок пространства для сохранения регистров при вызове другой процедуры. Это потому, что каждая процедура назначает номера регистров независимо; каждый начинается с регистра 7 как первого свободного. Поэтому, если регистры не были сохранены перед вызовом процедуры и не восстановлены после вызова, значения в регистрах будут потеряны. (Хотя в раме достаточно места для сохранения всех 48, чтобы упростить задачу, не все 50 .Компилятор знает, какие регистры содержат активные значения выражений в момент вызова процедуры, и генерирует код для сохранения и восстановления. только необходимые.)

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

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

Генерация кода cover photo Давайте еще раз посмотрим, как компилятор обрабатывает Паскаль

если

утверждение:


в локальный pif [(throw "error sentence :pname [arg wrong type] make "cond pboolean pexpr make" elsetag gensym сделать "endtag gensym mustbe", затем code (list "jumpf: cond (word" ": elsetag)) regfree: cond statement code (list" jump (word "": endtag)) code: elsetag ifbe "else [pfunset stop] код: endtag end Я показал вам эту процедуру во время разговора о синтаксическом анализе, прося вас игнорировать части о генерации кода. Теперь мы вернемся к этой части процесса. Формат если

может быть одно из следующих:


если

условие

тогда


утверждение

если


условие

тогда

утверждение

еще

утверждение

(Вероятно, после утверждения стоит точка с запятой, но официально она не является частью если; это часть составного оператора, который содержит если.) Когда мы доберемся до cover photo pif компилятор уже прочитал токен если; Следующее, что нужно прочитать - это выражение, которое должно иметь тип

логическое

, предоставляя условную часть оператора.

make "cond pboolean pexpr

звонок на

pexpr генерирует код для выражения и возвращает список выражений в формате, показанном ранее. Процедура

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

pboolean возвращает только регистр номер, который будет использован в коде, сгенерированном

пиф .

в pboolean: expr [3..7] при равном типе выражения: pval "boolean [integer immediate 15] (выбросить "тип предложения с ошибкой: pval " ) конец ноим mediate: значение, если равноp exp.mode: значение "немедленное ~ [:pval noimmediate :expr] вывод: значение конец В целом код, скомпилированный для если

инструкция будет выглядеть так: ... записать условие в регистр


конд

... jumpf

cond

"g5 ... код для тогда

заявление ... прыжок "g6 g5 ... код для еще

оператор ... g6 Этикетки g5 cover photo а также g6

в этом примере генерируются символы; каждый раз они будут разными. Этикетки генерируются инструкциями

make "elsetag gensym make" endtag gensym

в cover photo pif

. После того, как мы позвоним

pexpr cover photo для создания код для условного выражения, мы явно генерируем cover photo jumpf инструкция:

код (список "jumpf: cond (слово "": elsetag)) regfree: cond

Обратите внимание, что после создания jumpf

инструкция, мы больше не требуется значение в регистре : cond , и мы вызываем

regfree

, чтобы так сказать. Остальная часть этого процесса генерации кода должна быть простой. Все структурированные операторы (cover photoдля

,

покаcover photo, а также

повторить

) так же просты. Генерация кода для выражений - это все в cover photo ppopop

. Большая часть сложности работы с выражениями заключается в синтаксическом анализе, а не в генерации кода; к тому времени, когда мы доберемся до ppopop , мы знаем, что хотим выполнить одну операцию с двумя значениями, оба из которых находятся либо в регистрах, либо в непосредственных значениях. В простом случае оба находятся в регистрах; предположим, например, что нам дана операция вычитания и два операнда находятся в регистрах 8 и 9. Затем мы просто генерируем инструкцию

sub 8 8 9

и объявить регистр 9 свободным. Попоп cover photo немного длиннее, потому что он должен проверять особые случаи, такие как непосредственные операнды. Кроме того, унарный минус превращается в вычитание из нулевого регистра, поскольку нет унарного cover photoминусcover photo работа на нашей моделируемой машине. Как ни странно, это "простой" операторы, которые сложнее всего компилировать: присваивание и вызов процедуры. Для вызова процедуры (или функции) трудность заключается в сопоставлении фактических выражений аргументов с формальными параметрами. Процедура cover photo pproccall1 cover photo генерирует инструкции для управления указатели кадров, как описано ранее, и процедуры cover photo procargs заполняет вновь созданный фрейм фактическими значениями аргументов. (Если аргумент является массивом, переданным по значению, каждый член массива должен быть скопирован в новый фрейм.) Присваивание, обрабатываемое процедурой

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

x: =

выражение

читает название

Икс и использует cover photo getid

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


для передачи локального [output pinteger :result]
сделайте «токен имени сделать "index [] ifbe "| [localmake "reg newregister code (list "addi :reg reg.zero exp.value :value) output (list exp.type :value "register :reg)] mustbe "|] |] mustbe" |: = | make "id getid: name

сделать "идентификатор указателя. указатель: идентификатор
make "type id.type: id
passign1 end

Процедура

passign1

содержит шаги, которые являются общими для обычного назначения (обрабатываются [output token1 word :token lowercase :char] passign ) и присвоение имени текущей функции, чтобы установить возвращаемое значение (обрабатывается cover photo pfunset , полный список которых вы можете прочитать в конце главы).

для passign1 if и (listp: type) (emptyp: index) [localmake "reg newregister code (list "addi :reg reg.zero exp.value :value) output (list exp.type :value "register :reg)] setindex "false make "значение check.type: type pexpr
codestore: value (id.pointer: id) (id.varp: id): index < (1 + op.prec first :opstack)] [ppopop]push "opstack :op ; step 6output pexpr1endto ppopop ; step 5local [op function args left right type reg]make "op pop "opstackmake "function op.instr :opif equalp :function "plus [stop]make "args op.nargs :opmake "right pop "datastackmake "left (ifelse equalp :args 2 [pop "datastack] [[[] []]])make "type pnewtype :op exp.type :left exp.type :right... code generation omitted ...push "datastack (list :type "register :reg)endto popenpush "opstack [popen 1 0]make "parenlevel :parenlevel+1endto pclosewhile [(op.prec first :opstack) > regfree: конец значения
Мы называем

pexpr

, чтобы сгенерировать код для вычисления выражения.

Тип проверки

как

pboolean

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

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

var параметр; если да, то его значение является указателем на переменную, значение которой мы


В самом деле

хочу поменять. Наконец,

индекс


ввод будет равен нулю для скалярной переменной или номеру регистра, содержащего индекс массива для члена массива. (Процедура lindex cover photo, имя которой стоит для «линейного индекса» был вызван для генерации кода для преобразования возможных многомерных индексов с возможно различными начальными значениями в одно число, указывающее позицию в массиве, начиная с ноль для первого члена.)

в хранилище кодов: reg: указатель: varflag: index localmake "target memsetup: pointer: varflag: index code (list" store: reg targetaddr) regfree last: target end


(Есть аналогичная процедура cover photo кодовая загрузка

, используемый для генерации кода для загрузки значения переменной в регистр.) Хранилище кода вызывает подпроцедуру

, задача которого состоит в том, чтобы определить подходящий операнд для rload cover photo или же хранить

Машинная инструкция. Этот операнд должен быть смещением и индексным регистром, например cover photo 2999 (4)

. Какие - это список два числа, в данном случае [name id type index value pointer target] cover photo. Процедура

targetaddr превращает это в правильное обозначения для использования в инструкции.

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

параметр. Тогда есть три случая. Если лексическая глубина этой переменной равна текущей лексической глубине, то эта переменная объявляется в том же блоке, который мы компилируем. В этом случае мы используем регистр 4 (указатель текущего кадра) в качестве индексного регистра, а слот кадра переменной в качестве смещения. Если лексическая глубина переменной равна нулю, то это глобальная переменная. В этом случае мы используем регистр 3 (глобальный указатель фрейма) как индексный регистр, а слот фрейма переменной как смещение. Если глубина переменной не равна нулю или текущей глубине, то мы должны найти указатель на собственный фрейм переменной, просмотрев

столько раз, сколько разность между текущей глубиной и глубиной переменной.

cover photo Если переменная является членом массива , то мы должны добавить линейный индекс (который уже находится в регистре) к смещению, вычисленному на данный момент.

memsetup
var рама. рама слот и, возможно, в что


кадра cover photoРамка. внешний кадр

Если переменная является cover photo var cover photo, затем мы рассмотрим те же самые случаи, только что описанные, а затем загружаем значение этой переменной (которая указатель на переменную, которая нам действительно нужна) в регистр. Мы используем этот новый регистр в качестве индексного регистра и ноль в качестве смещения.
Возможно, пример поможет разобраться в этом вне. Вот скомпилированная версия

башня cover photo программа с аннотациями:

[parrayassign :id stop] установить начальные указатели [add 4 0 0] [addi 2 0 36] [jump "g1] перейти к основной программе% hanoi [store 1 0(4)] сохранить возвращаемое значение [jump "g2] перейти к телу hanoi% Moveisk [store 1 0(4)] [41 4] g3 [41 4] тело движущегося диска [rload 7 36(4)] [41 4] напишите (номер: 1) [putint 1 7]] [putstr 1 [Move disk ] [putint 1 7] написать (от: 1) [putstr 1 [ from ]] [putch 1 7] [putint 1 7] написать (кому: 1) [newline] [rload 1 0(4)] перезагрузить адрес возврата [add 2 4 0] свободный кадр стека [rload 4 3(2)] [jr 1] возврат к вызывающему g2 [rload 7 36(4)] тело ханоя [putch 1 7], если число <> 0 [rload 7 38(4)] [store 5 1(2)] выделить новый кадр [add 5 2 0] [rload 7 38(4)] [store 4 3(5)] установить предыдущий кадр [jumpf 7 "g4] [neqi 7 7 0] установить охватывающий фрейм [rload 7 36(4)] [rload 7 2(4)] [store 7 36(5)] первый аргумент - номер 1 [putint 1 7] 32 следующий аргумент из [rload 7 2(4)] [subi 7 7 1] следующий аргумент - другой [putstr 1 [ from ] [subi 7 7 1] следующий аргумент находится на [add 4 5 0] перейти к новому кадру [rload 5 1(4)] [rload 7 39(4)] рекурсивный вызов [store 5 1(2)], настроенный для Moveisk [output (commalist :test (lput :result :sofar))] [rload 7 39(4)] [store 4 3(5)] [store 4 2(5)] обратите внимание на другую ограничивающую рамку [rload 7 36(4)] [store 7 36(5)] копировать аргументы [putint 1 7] [addi 2 2 40] [putch 1 7] [subi 7 7 1] [store 7 36(5)] [rload 5 1(4)] [jal 1 "%hanoi] вызов moveisk [store 5 1(2)] второй рекурсивный вызов [add 5 2 0] [rload 7 38(4)] [make "char getchar ~ ifelse equalp :char ". ~ [make "peektoken ".. output :num] [rload 7 38(4)] [addi 2 2 40] [rload 7 36(4)] [rload 7 2(4)] [store 7 36(5)] [rload 7 2(4)] [addi 2 2 40] [rload 7 37(4)] [store 7 2(5)] [putstr 1 [Move disk ] [rload 7 39(4)] [add 4 5 0] [add 4 5 0] [rload 7 39(4)] [store 7 39(5)] конец if ... then g4 g5 [rload 1 0(4)] возврат к вызывающему [add 2 4 0] [rload 4 3(2)] [jr 1] g1 [store 5 1(2)] тело основного программа [add 5 2 0] подготовка к вызову ханоя [rload 7 38(4)] [store 4 3(5)] [store 4 2(5)] [addi 2 2 39] постоянный аргумент 5 [store 7 36(5)] [jal 1 "%movedisk] Код ASCII для 'a' [addi 2 2 40] [addi 2 2 39] Код ASCII для 'b' [store 7 2(5)] [addi 7 0 97] Код ASCII для 'c' [store 7 37(5)] [add 4 5 0] [rload 5 1(4)] [rload 7 39(4)] зовите ханой [jal 1 "%doit]]

Список программ для компиляции: file if namep "peekchar [addi 7 0 97] если namep "peektoken [addi 7 0 98] если не namep "idlist [addi 7 0 99] если не пусто, p: file файл игнорировать ошибку ловушка "ошибка ошибка [opsetup] setread [output :action] если не пустоp: файл конец ;; Глобальная настройка opsetup make "numregs 64 сделать «memsize pprop "| = |" двоичный [eql 2 [boolean [statement]] 1] pprop "||" двоичный [neq 2 [boolean ] 1] pprop "||" двоичный [гтп 2 [логическое

] 1] pprop "| = | "двоичный [geq 2 [логический [output :action]] 1] pprop "| + | "двоичный [добавить 2 [[output :action] [output :action]] 2] pprop "| - | "двоичный [sub 2 [[output :action] [output :action]] 2] pprop "или" двоичный [add 2 [[] 2] pprop "| | "двоичный [mul 2 [[output :action] [output :action]] 3] pprop "| / | "двоичный [кво 2 [реальный [output :action]] 3] pprop "div" двоичный [mul 2 [[] 3] двоичный файл pprop «mod» 3] pprop "и" двоичный 3] pprop "| + | «унарный [плюс 1 [[output pboolean :result] [output :action]] 4] pprop "| - | «унарный [минус 1 [

[output :action]] 4] pprop «не» унарный [rem 2 [integer integer] 4] сделать "idlist` [rem 2 [integer integer]] ] [rem 2 [integer integer]]] [lnot 1 [boolean boolean]]]] make "int [lnot 1 [boolean boolean] сделать "круглым" конец ;; Структура блока для программы должна быть "program localmake" progname token ifbe "| (| [[trunc function int [1 ,[framesize.fun+1] mustbe "|) |] mustbe" |; | localmake "lexical.depth 0 localmake" namesused [statement] localmake "needint" false localmake "needround" false localmake "needrandom" false localmake "idlist: idlist localmake" frame [random function random [1 ,[framesize.fun+1] localmake "id (list: progname" program (newlname : progname): frame) нажмите "idlist: id localmake" codeinto word "%: progname make: codeinto [statement] localmake "frameize framesize.proc program1 mustbe". код [jal 1 "%doit] foreach [random function random [1 ,[framesize.fun+1] "Изготовление библиотеки: код в обратном направлении: код в end to program1 localmake "regsused (array: numregs 0) for [integer real] [integer integer] ifbe "var [ignore commalist [id] .setfirst butfirst: frame: frameize if: lexical.depth = 0 [0 0] localmake "bodytag gensym code (список" jump (word " ": bodytag)) tryprocpart code: bodytag mustbe" begin blockbody "end end end to plibrary: func if not thing (word" need: func ") [|;| end until] код: код функции (список "rload reg.firstfree (memaddr framesize.fun reg.frameptr)) код (список (слово "s: func) reg.retval reg.firstfree) код (список" добавить reg.stackptr reg.frameptr reg.zero) код (список "rload reg.frameptr (memaddr frame.prevframe reg.stackptr)) код (список "jr reg.retaddr) end ;; Объявления переменных для varpart local [(throw "error sentence [undefined symbol] make "token token make" peektoken: token, если зарезервированp: token [|;| end until] vargroup foreach: namelist [i reg.firstfree :numregs-1] mustbe "|; | varpart end to vargroup make" namelist commalist 64 должен быть упакован ": ifbe" [output :action] сделать массив типа «токен ifelse equalp: type» <| [= > [code (list "add reg.globalptr reg.zero reg.zero) code (list "add reg.frameptr reg.zero reg.zero) code (list "addi reg.stackptr reg.zero :framesize)] end to id локальный "token make" token token, если сначала letterp ascii: token [code (list "add reg.globalptr reg.zero reg.zero) code (list "add reg.frameptr reg.zero reg.zero) code (list "addi reg.stackptr reg.zero :framesize)] make "peektoken: вывод токена " make "peektoken: вывод токена [output :action] конец в тип массива локальный должно быть "|] | токен должен быть "изготовленным" типом проверка типа: тип выходной список: тип: диапазоны от конца до диапазона локальные сделать "first range1 mustbe" .. make "last range1 if: first>: last ~ [output :token]: первый "..: последний))] список вывода : first (1 +: last -: first) end to range1 локальный "привязанный make" привязанный токен, если равен первый: привязанный "' если equalp: bound "| - |" [typecheck :type] if equalp: bound int: bound [first last] (выбросить "сообщение об ошибке " : привязано) конец для проверки типов: введите, если memberp: type [output ascii first butfirst :bound] [|;| end until] (выбросить "сообщение об ошибке [first last]: type) end to newvar: pname: type, если зарезервировано p: pname [make "bound minus token]] push "idlist (list: pname: type (list: lexical.depth: framesize)" false) make "framesize: framesize + ifelse listp: type [output :bound] [real integer char boolean] end to arrayize: type output reduce "product map [array bound not ordinal:] last: type end ;; Объявления процедур и функций для tryprocpart ifbeelse "procedure ~ [undefined type] ~ [undefined type]] конец процедуры proc1 "procedure framesize.proc end to function proc1" function framesize.fun end to proc1: proctype: framesize localmake "procname token localmake" lexical.depth: lexical.depth + 1 localmake "фра" me (list: lexical.depth 0) push "idlist (list: procname: proctype (newlname: procname): frame) localmake" idlist: idlist make lname: procname [statement] ifbe "| ( | [(throw "error sentence :pname [reserved word] if equalp: proctype "function ~ code lname: procname code (list "store reg.retaddr (memaddr frame.retaddr reg.frameptr)) program1 if equalp: proctype" function ~ [last ?] код (список "rload reg.retaddr (memaddr frame.retaddr reg.frameptr)) код (список" добавить reg.stackptr reg.frameptr reg .zero) code (list "rload reg.frameptr (memaddr frame.prevframe reg.stackptr)) code (list" jr reg.retaddr) mustbe "|; | end to arglist local [ifbe "function [function tryprocpart] сделать "varflag" false ifbe "var [ifbe "function [function tryprocpart] vargroup fo охват: список имен [procedure tryprocpart] ifbeelse "|; | [undefined type] [token namelist type varflag] конец до newarg: pname: type: varflag, если зарезервировано p: pname [(throw "error (sentence [array bounds not increasing:]] localmake "указатель (список: lexical.depth: frameize) push" idlist (list: pname: type : pointer: varflag) make "framesize: framesize + ifelse (и listp: type not: varflag) ~ " [array bound not ordinal:] очередь lname: procname ifelse: varflag [code (list "rload reg.retval (memaddr frame.retval reg.frameptr))] [code (list "rload reg.retval (memaddr frame.retval reg.frameptr))] конец ;; Часть инструкции для blockbody: выражение endword ifbeelse "|; | [newarg ? :type :varflag] конец оператора локальный [output word :old :char] ifbe "begin [compound stop] ifbe "для [pfor stop] ifbe "if [pif stop] ifbe "while [pif stop] ifbe "repeat " ifbe "пишите " ifbe "Writeln [pwrite stop] make "token token make" peektoken: token если memberp: token [pwriteln stop] [|;| end until] make "type gettype: token if emptyp: type [|;| end until]] if equalp: type "procedure " if equalp: type "function [(throw "error sentence :token [can't begin statement] passign end ;; Составной оператор для составного блочного тела "end end ;; Структурированные операторы для локального pfor 3000 make "var token mustbe" |: = | make "init pinteger pexpr make" step 1 ifbeelse "downo [mustbe "|)|] [:type] make "final pinteger pexpr mustbe" do make "looptag gensym make "endtag gensym code: looptag localmake" id getid: var codestore: init (id.pointer: id) (id.varp: id) 0 make "testreg newregister code (list (ifelse: step: lexi глубина ~ 53 ~ [blockbody :endword] код (список "store: tempreg (memaddr frame.outerframe reg.newfp)) regfree: tempreg] если не пустойp: vartypes [var init step final looptag endtag testreg] для [integer integer] ~ [mustbe :endword]] код (список "добавить reg.frameptr reg.newfp reg.zero) код (список" rload reg.newfp (memaddr frame.save.newfp reg.frameptr)) код (список "jal reg. retaddr (слово "": lname)) для [integer integer] ~ [make "step -1]] конец до procargs: types: offset if empty p: types [code (list "store reg.frameptr (memaddr frame.outerframe reg.newfp))] localmake " следующая процедура сначала: типы: смещение, если не пустоp, но сначала: типы [code (list "store reg.frameptr (memaddr frame.outerframe reg.newfp))] procargs butfirst: types: offset +: next end to procarg : type: offset local "результат, если сначала равен: type" var [mustbe "|(| procargs :vartypes :offset] если listp: type [mustbe "|(| procargs :vartypes :offset] сделать «результат проверки. тип: введите код pexpr (список» store: result (memaddr: offset reg.newfp)) regfree: result output 1 end to procvararg: ftype local [if item :i :regsused [code (list "store :i (memaddr frame.regsave+:i reg.frameptr))] сделать "pname token make" id getid: pname make "type id.type: id ifelse wordp: ftype ~ [mustbe "|(| procargs :vartypes :offset] ~ [mustbe "|)| stop] если не равноp: type: ftype ~ [mustbe ",])] localmake "target memsetup (id.pointer: id) (id.varp: id): index localmake" tempreg newregister code (list "addi: tempreg (last: target) (первая: t arget)) code (list "store: tempreg (memaddr: offset reg.newfp))" regfree last: target regfree: tempreg output 1 end to procarrayarg: type localmake "pname token localmake" id getid: pname if not equalp: type (id .type: id) ~ [output procvararg last :type]))] localmake "size arrayize: type localmake" rtarget memsetup (id.pointer: id) (id.varp: id) 0 localmake "pointreg newregister code (список" addi: pointreg reg.newfp: offset) localmake "ltarget (список 0: pointreg) copyarray output: size end ;; Простые операторы: оператор присваивания (включая значение функции) для передачи локального [not true or false] сделать индекс «маркер имени» [i reg.firstfree :numregs-1] ifbe "| [not true or false] mustbe "|] |] mustbe" |: = | make "id getid: name make" указатель id.pointer: id make "type id.type: id passign1 end to pfunset local [:pval noimmediate :expr] сделайте индекс «name token make» [setindex "true] если не равноp: name : procname ~ [mustbe ",]: имя)] должен быть указатель "|: = | make" (список: lexical.depth frame.retval) make "сначала введите lname: name make" id (list: name: type: pointer "false) passign1 end to passign1 if and (listp: type) (emptyp: index) [name id type index value pointer target] setindex " значение false make check.type: type pexpr codestore: value (id.pointer: id) (id.varp: id): index regfree: value end to noimmediate: value if equalp exp.mode: value "Немедленно ~ [output exp.value :pval] вывод: значение для проверки. тип: тип: результат при равенстве: тип "real [output procvararg last :type] если равноp: введите "целое число [pname id type index] если равно: введите "char [(throw "error sentence :pname [arg wrong type] если равноp: введите «логическое [make "index 0] конец до preal: expr [real register 8] при равном типе выражения: pval "real " вывод pinteger: pval от конца до pinteger: expr [integer immediate 15] локальный "type make" тип exp.type: pval if memberp: type [(throw "error sentence [assign to wrong function] [integer immediate 15] (выбросить "сообщение об ошибке тип: pval [(throw "error (sentence "array :pname [wrong type for arg] конец в pchar: expr [3 5] при равном типе выражений: pval "char " (выбросить "ошибка предложение exp.type: pval [(throw "error sentence [assign to wrong function]) конец в pboolean: expr [real register 8] при равном типе выражения: pval "boolean [integer immediate 15] (выбросить "сообщение об ошибке exp.type: pval " ) конец до parrayassign: id localmake "правая лексема, если сначала равны: правая" '~ localmake "rid getid: right if not equalp (id.type: id) (id.type: rid) ~ [output pinteger :result]))] localmake "size arrayize id.type: id localmake" ltarget memsetup (id.pointer: id) (id.varp: id) 0 localmake "rtarget memsetup (id.pointer: rid) (id.varp: rid) 0 конец массива копирования для pstringassign : type: string, если не равно, сначала: введите "char [output pboolean :result] если не пустоp, а сначала последнее: введите [output pboolean :result] если не равноp (последний первый последний: тип) (счетчик: строка) localmake "ltarget memsetup (id.pointer: id) (id.varp: id) 0 pstringassign1 newregister (first: ltarget) (last: ltarget): string regfree last: ltarget end кому: pstringassign1: tempreg: o ffset: reg: string, если пусто p: string [output pboolean :result] код (список "addi: tempreg reg.zero ascii first: string ) code (list "store: tempreg (memaddr: offset: reg)) pstringassign1: tempreg: offset + 1: reg (butfirst: string) end to stringlose (throw" error message: name [isn't ordinal]) конец ;; Несколько индексов массива для вычисления линейного индекса для setindex: parseflag ifelse listp: type ~ ] make "index lindex last: type: index make" сначала введите: type] ~ [if item :i :regsused [code (list "rload :i (memaddr frame.regsave+:i reg.frameptr))] end to lindex: bounds: index output lindex1 (смещение pinteger noimmediate first: index first first: bounds) ~ butfirst: bounds butfirst: index end to lindex1: sofar: bounds: index if emptyp: bounds [not character value] вывод lindex1 (nextindex: sofar last first: bounds pinteger noimmediate first: index first first: bounds) ~ butfirst: bounds butfirst: index end to nextindex: old: factor: new: offset code (список "muli: old: old: factor) localmake" newreg offset: new: код смещения (список "add: old: old: newreg) regfree: newreg output: old end to offset: indexreg: lowbound if not equalp: lowbound 0 [(throw "error (sentence "arrays :name "and :right [unequal types] вывод: indexreg end ;; Интерфейс памяти: загрузка и сохранение инструкций для codeload: reg: pointer: varflag: index localmake "target memsetup: pointer: varflag: index code (list" rload: reg targetaddr) regfree last: target end to codestore: reg: pointer: varflag: index localmake "target memsetup: pointer: varflag: index code (list" store: reg targetaddr) regfree last: target end to targetaddr output memaddr (first: target) (last: target) end to memaddr: offset: index output (word: смещение " (: index" )) конец в memsetup: указатель: varflag: index localmake "сначала глубина: локальный указатель" последнее смещение: локальный указатель "newreg ifelse equalp: depth 0 ~ [pstringassign :type (butlast butfirst :right) stop] ~ [not string array or wrong size] [stringlose]]] если: varflag ~ [regfree :tempreg stop] [if :parseflag [mustbe "|[| make "index commalist [pexpr] сделать «смещение 0], если не равно p: index 0 ~ ' список вывода: смещение: newreg end to copyarray localmake "looptag gensym localmake" sizereg newregister code (список "addi: sizereg reg.zero: size) code: looptag localmake" tempreg newregister code (list "rload: tempreg (memaddr (first: rtarget) (last: rtarget) (last) : rtarget))) code (list "store: tempreg (memaddr (first: ltarget) (last: ltarget))) code (list" addi (last: rtarget) (last: rtarget) 1) code (list "addi (last : ltarget) (last: ltarget) 1) код (список "subi: sizereg: sizereg 1) код (список" gtr: tempreg: sizereg reg.zero) код (список "jumpt: tempreg (word" ": looptag)) regfree : sizereg regfree: tempreg regfree last: ltarget regfree last: rtarget end ;; Выражения для pexpr local [minus 1 4] make "opstack [[popen 1 0]] делать "пакет данных [statement] make "parenlevel 0 output pexpr1 end to pexpr1 local " сделать «токен токен, пока [[popen 1 0] [equalp :token "|(|] make "op pgetunary: token, если не пусто p: op [token op] push "datastack pdata: token make" token token while [popen make "token token] ~ [pclose make "token token] делать " op pgetbinary: токен, если не пустой p: op [equalp :token "|(|] make "peektoken: token pclose if not emptyp: opstack [output pexprop :op])], если не пустоp, а сначала: набор данных [pclose make "token token]] output pop "datastack end to pexprop: op while [if :parseflag [mustbe "|[| make "index commalist [pexpr] [(op.prec :op) < (1 + op.prec first :opstack)] игнорировать pop "opstack make" parenlevel: parenlevel - 1 end to pgetunary: token output gprop: token "unary end to pgetbinary: token output gprop: token "двоичный конец для ppopop local [(op.prec :op) < (1 + op.prec first :opstack)] make "op pop" opstack make "function op.instr : op if equalp: function "plus [|;| end until] make "args op.nargs: op make" right pop "datastack make" left (ifelse equalp: args 2 [ppopop] [[[output :action] [statement]]]) make "тип pnewtype: op exp.type: left exp.type: right, если равноp exp.mode: left" немедленно ~ [code (list "subi :indexreg :indexreg :lowbound)] ifelse equalp exp.mode: left "register ~ " ~ [make "newreg newregister code (list "rload :newreg (memaddr frame.outerframe reg.frameptr)) repeat (:lexical.depth - :depth) - 1 [code (list "rload :newreg (memaddr frame.outerframe :newreg))] [ifelse :newreg = reg.frameptr [make "newreg newregister code (list "rload :newreg (memaddr :offset reg.frameptr))] если равно: функция «минус ~ [(op.prec :op) 0] если равноправный режим: правый "немедленный ~ " ifelse equalp: args 2 ~ [code (list "rload :newreg (memaddr :offset :newreg))] ~ [localmake "leftreg newregister code (list "addi :leftreg reg.zero exp.value :left) make "left (list exp.type :left "register :leftreg)] если не равноp: reg exp.value: left [make "reg exp.value :left] если (и (режим равной эксп.: правый регистр) (не equalp: reg exp. value: right)) ~ [ifelse equalp exp.mode :right "register [make "reg exp.value :right] push "datastack (list: type" register: reg) end to pnewtype: op: ltype: rtype local "type make" type op.types: op if emptyp: ltype [make "function word :function "i] если не emptyp last: введите [make "left (list exp.type :right "register reg.zero) make "function "sub make "args 2] if and (equalp: ltype "real) (equalp: rtype" integer) [make "left (list exp.type :right "register reg.zero) make "function "sub make "args 2] if and (equalp: ltype "integer) (equalp : rtype "real) [make "left (list exp.type :right "register reg.zero) make "function "sub make "args 2] если не равноp: ltype: rtype [code (list :function :reg exp.value :right)]) если emptyp last: введите ~ [если не memberp: rtype [lnot 1 [boolean boolean] [regfree exp.value :right])]] если сначала пусто: тип [make "ltype "real] сначала вывод: введите end в pchecktype: want: left: right, если не равноp: want: left [make "ltype "real] если не равноp: want: right [pchecktype last :type :ltype :rtype] конец ;; Элементы выражения в pdata: token, если равноp: token "true [make "rtype "real]] if equalp: token "false [make "ltype "real]] при равенстве первым: жетон "'[make "rtype "real] if numberp: token [output :rtype] localmake "id getid: token if empty p: id [output :rtype]: токен) ] localmake "type id.type: id if equalp: type" function [if not memberp :rtype [integer real] локальный "index setindex" true localmake "reg newregister codeload: reg (id.pointer: id) ( id.varp: id): вывод индекса (список: тип "регистр: рег) конец до pchardata: токен, если не равноp count: токен 3 ~ [(throw "error (sentence :right "isn't :want))]) вывод (список "char" сначала ascii, но сначала: токен) конец до numtype: number if memberp ". :номер [output [boolean immediate 1] if memberp "e: number " вывод "integer end to pfuncall: pname localmake" id getid: pname localmake "lname id.lname: id if namep (word" need: lname) [(throw "error (sentence :left "isn't :want))] localmake "vartypes thing: lname localmake "сначала возвратный тип: vartypes make" vartypes butfirst: vartypes pproccall1 framesize.fun localmake "reg newregister code (list" add: reg reg.retval reg.zero) output (list: replntype "register: reg) end ;; Помощь в синтаксическом анализе кода: stuff if emptyp: stuff [|;| end until] push: codeinto: stuff end to commalist: test [: sofar []] местный [output [boolean immediate 0] make "результат запустить: проверить, если пустоp: результат " ifbe ", [output (list numtype :token "immediate :token)] вывод lput : result: sofar end .macro ifbe: wish: action localmake "token token if equalp: token: wish [addi 7 0 99] make "peektoken: вывод токена [] конец .macro ifbeelse: wish: action: else localmake "token token if equalp: token: Wish [| [make "index commalist [pexpr] make "peektoken: вывод токена: иначе конец должен быть: требуется localmake" токен токена, если он равен: токен :в розыске [stop] (выбросить "ошибка (предложение" ожидается: требуется "получил: токен)) конец нового реестра для [integer integer] ~ [output pfuncall :token]] (вывести "error [(throw "error sentence [undefined symbol]) конец в regfree: reg setitem: reg: regsused "false end to reservedp: word output memberp: word [(throw "error sentence :token [not single character] конец ;; Лексический анализ локального токена [token char], если namep "peektoken [make "token :peektoken ern "peektoken output :token] make "char getchar if equalp: char" | {| [skipcomment output token] если равно: char char 48 [output token] если равно: char char 38 [output token] если равноp: char символ 39 [output token] if equalp: char "' [output string "'] если memberp: char [+ - / = ( , ) |[| |] | |; |] [output :char] if equalp: char "|]] if equalp: char" |> | [output twochar "|>| [=]] if equalp: char ". [output twochar "|>| [=]] if equalp: char ": [output twochar ". [.]] если numberp: char [output number :char] если letterp ascii: char [output number :char] (выбросить "сообщение об ошибке [jr 1] : char) end to skipcomment if equalp getchar "|} | [|;| end until] skipcomment end to string: string local "char make" char getchar if not equalp: char "'[(throw "error sentence :token [not single character] make «char getchar if equalp: char» '[output "real] make "peekchar: char output word: string" 'end to twochar: old: ok localmake "char getchar if memberp: char: хорошо # вывод: старый конец до числа: num local "char make" char getchar if equalp: char ". ~ [(throw "error sentence :token [not single character] ~ [result token]] если равно: char "e [result token]] если numberp: char [output (commalist :test (lput :result :sofar))] make "peekchar: char output: num end to token1: token local" char make "char getchar if or letterp ascii: char numberp: char ~ [not enough registers available] make "peekchar: char output: token end to letterp: code if and (: code> [store 4 2(5)] ) (: код ) (: code: count [not enough registers available] до конца строки печати [statement] конец до выхода make "pc [exit] конец

(назад к содержанию) figure: unambiguousНАЗАД<| [= >

ветка главы < (1 + op.prec first :opstack)] [ppopop]push "opstack :op ; step 6output pexpr1endto ppopop ; step 5local [op function args left right type reg]make "op pop "opstackmake "function op.instr :opif equalp :function "plus [stop]make "args op.nargs :opmake "right pop "datastackmake "left (ifelse equalp :args 2 [pop "datastack] [[[] []]])make "type pnewtype :op exp.type :left exp.type :right... code generation omitted ...push "datastack (list :type "register :reg)endto popenpush "opstack [popen 1 0]make "parenlevel :parenlevel+1endto pclosewhile [(op.prec first :opstack) > СЛЕДУЮЩИЙfigure: tokenrtn


< (1 + op.prec first :opstack)] [ppopop]push "opstack :op ; step 6output pexpr1endto ppopop ; step 5local [op function args left right type reg]make "op pop "opstackmake "function op.instr :opif equalp :function "plus [stop]make "args op.nargs :opmake "right pop "datastackmake "left (ifelse equalp :args 2 [pop "datastack] [[[] []]])make "type pnewtype :op exp.type :left exp.type :right... code generation omitted ...push "datastack (list :type "register :reg)endto popenpush "opstack [popen 1 0]make "parenlevel :parenlevel+1endto pclosewhile [(op.prec first :opstack) >

, cover photo bh @ cs .berkeley.edu

Брайан Харви

Leave a comment

Your email address will not be published. Required fields are marked *