Транслятор с языка ассемблер
Схема работы транслятора с языка Ассемблера.
Сейчас мы рассмотрим, как транслятор преобразует входной модуль на «чистом» языке Ассемблера (уже без макросредств) в объектный модуль. Разумеется, мы изучим только общую схему этого, достаточно сложного процесса. Наша цель – рассмотреть основные принципы работы транслятора с языка Ассемблера и ввести необходимую терминологию. Более подробно этот вопрос, который относится к большой теме «Формальные грамматики и методы компиляции», Вы будете изучать в другом курсе.
Итак, как мы знаем, Ассемблер относится к классу системных программ, которые называются компиляторами [73] – переводчиками с одного алгоритмического языка на другой. Наш транслятор переводит модуль с языка Ассемблера на объектный язык. При трансляции выполняются следующие шаги.
§ Анализ входного модуля на наличие ошибок.
§ Выдача протокола работы транслятора – так называемого листинга, а также выдачу аварийных сообщений об ошибках.[74] Выдачу листинга при желании, как правило, можно заблокировать.
§ Генерация объектного модуля.
Разберём более подробно первый этап – анализ программы на наличие ошибок. Ясно, что найти ошибку можно, только просмотрев весь текст модуля, строка за строкой. Каждый просмотр текста программного модуля транслятором называется проходом. Наш транслятор с Ассемблера просматривает программу дважды, т.е. совершает два прохода. Такие трансляторы называются двухпроходными. Двухпроходная схема трансляции наиболее простая, можно, однако, усложнив алгоритм, производить трансляцию и за один проход (например, так работает транслятор с языка Турбо-Паскаль).
На первом проходе транслятор с Ассемблера, анализируя текст программы, находит многие (но не все) ошибки, и строит некоторые важные таблицы, данные из которых используются как на первом, так и на втором проходе. Вкратце алгоритм первого прохода состоит в следующем. Так как основной синтаксической единицей нашего языка является предложение Ассемблера, то рассмотрим, как происходит обработка предложений на первом проходе.
Сначала работает специальная программа, которая называется лексическим анализатором. Она разбивает каждое предложение программы на лексемы – логически неделимые единицы языка. О лексемах мы уже должны немного знать из языка Паскаль. Как и в Паскале, в языке Ассемблера существуют следующие классы лексем.
§ Имена. Как и в Паскале, это ограниченные последовательности букв и цифр, начинающиеся с буквы, при этом большие и маленькие буквы не различаются. Как мы помним, в Паскале к буквам относился также и символ подчёркивания, а в Ассемблере к буквам относятся и такие символы, как вопросительный знак, точка (правда, только в первой позиции и у служебных имён) и некоторые другие. Все имена Ассемблера делятся на служебные и имена пользователя.[75]
§ Числа. Язык Ассемблера, как и Турбо-Паскаль, допускает запись чисел в различных системах счисления (десятичной, двоичной, шестнадцатеричной и некоторых других). Не надо забывать и о вещественных числах.
§ Строки символов. Строки символов в Ассемблере ограничены либо апострофами, либо двойными кавычками. Ещё раз напомним, что в нашем упрощённом изложении алгоритма работы компилятора мы считаем, что макропроцессор, который рассматривал фактические параметры макрокоманд тоже как строки символов, ограниченных запятыми, пробелами или точной с запятой, уже закончил свою работу.
§ Разделители. Как и в Паскале, лексемы перечисленных выше классов не могут располагаться в тексте программы подряд, между ними обязательно должна находиться хотя бы одна лексема-разделитель. К разделителям относятся знаки арифметических операций, почти все знаки препинания, пробел и некоторые другие символы.
§ Комментарии. Эти лексемы не влияют на выполнения алгоритма, заложенного в программу, они переносятся в листинг, а из анализируемого текста удаляются. Исключением являются макрокомментарии, которые начинаются с двух символов ‘;;’, как мы знаем, такие комментарии не переносятся в листинг.
В качестве примера ниже показано предложение Ассемблера, каждая лексема в нём выделена в прямоугольник:
На этапе лексического анализа выявляются лексические ошибки, когда некоторая группа символов не может быть отнесена ни к одному из классов лексем. Примеры лексических ошибок:[76]
Все опознанные (правильные) лексемы записываются в специальную таблицу лексем. Это делается в основном для того, чтобы на втором проходе уже двигаться по программе по лексемам, а не по отдельныс составляющим их символам, что позволяет существенно ускорить просмотр программного модуля.
После разбиения предложения Ассемблера на лексемы начинается второй этап обработки предложения – этап синтаксического анализа. Этот этап выполняет программа, которая называется синтаксическим анализатором. Алгоритмы синтаксического анализа весьма сложны, и здесь мы не будем их рассматривать, это, как уже упоминалось, тема отдельного курса. Если говорить совсем коротко, то синтаксический анализатор пытается из лексем построить более сложные конструкции предложения: поля метки, кода операции и операндов. Особое внимание на этом этапе уделяется в программе именам пользователя, они заносятся синтаксическим анализатором в специальную таблицу имён. Вместе с каждым именем в эту таблицу заносятся и атрибуты (свойства) имени. Всего в Ассемблере у имени пользователя различают четыре атрибута, ниже перечислены эти атрибуты (не у каждого имени есть все из них).
§ Атрибут сегмента Segment. Этот атрибут имеет формат i16, он задаёт адрес начала того сегмента, в котором описано имя, делённый на 16.
§ Атрибут смещения Offset, он также имеет формат i16 и задаёт смещение имени от начала того сегмента, в котором оно описано. Атрибуты Segment и Offset могут иметь только имена, определяющие области памяти и метки команд.
§ Атрибут типа Type. С этим атрибутом имени мы уже знакомы, для переменных он равен длине переменной в байтах, а для меток равен –1 и –2 для близкой и дальней метки соответственно. Все остальные имена имеют тип ноль (в некоторых учебниках по Ассемблеру это трактуется как отсутствие типа, при этом говорится, что у таких имён атрибута Type нет).
§ Атрибут значения Value. Этот атрибут определён только для имён сегментов, а также для констант и переменных периода генерации.
Приведём примеры описаний имён, которые имеют первые три из перечисленных выше атрибутов:
B equ A
C: mov B,1
D equ C
А теперь примеры имён, у которых есть только атрибут Value (и атрибут Type = 0):
N equ 100
M equ N+1
P equ K
Data segment
Рассмотрим теперь пример маленького, синтаксически правильного, но, вообще говоря, бессмысленного программного модуля, для которого построим таблицу имён пользователя:
Data segment
A dw 19
Data ends
Code segment
extrnX:far
mov ax,Data
mov cx,R
jmp L
call X
L: ret
Code ends
На рис. 13.1 показана таблица имён, которая построится синтаксическим анализатором при просмотре программы до предложения
mov ax,Data
включительно. Атрибуты, которые не могут быть у данного имени, отмечены прочерком.
Как мы уже знаем, значения некоторых имён неизвестны на этапе компиляции, эти значения мы проставили в нашей таблице как i16=?. Для каждого заносимого в таблицу имени, кроме атрибутов, ещё запоминается и место в предложении, на котором встретилось имя. В Ассемблере имя пользователя может располагаться в поле метки (тогда это определение имени) и в поле операндов (тогда это использование имени).
Итак, теперь синтаксический анализатор рассматривает предложение
mov cx,R
и заносит в таблицу имён имя R. Про это имя ещё ничего неизвестно, поэтому и все поля атрибутов в таблице имеют неопределённые значения:
После полного просмотра программы синтаксический анализатор построит таблицу имён, показанную на рис. 13.2.
Имя | Segment | Offset | Type | Value |
Data | ––– | ––– | I16=? | |
A | Data | ––– | ||
B | Data | ––– | ||
Code | ––– | ––– | I16=? | |
X | i16=? | i16=? | -2 | ––– |
R | ––– | ––– | -14 | |
L | Code | -1 | ––– | |
Рис. 13.2. Вид таблицы имён после анализа всей программы. |
На этапе синтаксического анализа выявляются все синтаксические ошибки в программе, например:
mov ax,bl; Несоответствие типов
add A,A+2; Несуществующий формат команды
sub cx; Мало операндов
и т.д. Используя таблицу имён, синтаксический анализатор легко обнаруживает ошибки следующего вида:
1. Неописанное имя. Имя встречается только в поле операндов и не встречается в поле метки.
2. Дважды описанное имя. Одно и то же имя дважды (или большее число раз) встретилось в поле метки.[77]
3. Описанное, но не используемое имя. Это предупредительное сообщение может выдаваться некоторыми «продвинутыми» Ассемблерами, если имя определено в поле метки, но ни разу не встретилось в поле операндов (видимо, программист что-то упустил).
Кроме того, синтаксический анализатор может обнаружить и ошибки, относящиеся к модулю в целом, например, превышение максимальной длины некоторого сегмента.
На этом мы завершим наше краткое знакомство со схемой трансляции исходного модуля с языка Ассемблера на объектный язык.
Дата добавления: 2015-10-05 ; просмотров: 928 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Дональд Кнут: про ассемблер, транслятор и грамотное программирование
«Literate programming (грамотное программирование) — отношение к компьютерным программам, как к литературе: компьютерная программа пишется не столько для компьютера, сколько для людей, чтобы люди могли ее прочитать. И поскольку я пишу программы, то я, в некотором роде, учитель.»
«Давайте изменим традиционные приоритеты в создании программ: вместо представления о нашей задаче как о создании инструкций «Что делать?» для компьютера сконцентрируемся на объяснении другим людям описаний нашего видения того, что под управлением программы должен делать компьютер.»
![]()
Коротко рассказываем о гибкой методологии разработки программного обеспечения (Agile), которую мы используем на проектах в EDISON Software Development Centre.
Literate programming (66/97)
Тем временем, я также определился с точной версией TeX и самой концепцией грамотного программирования. Позвольте мне немного вернуться назад к истории об утилитах «спутывания» и «распутывания» (Weave and Tangle). Вообще, я думаю, что наибольшей пользой от занятия печатным делом была идея создания того, что зовется «грамотным программированием».
Мне нравится учить. Я не просто обучаю компьютер, я учу читателей моих программ. Надеюсь, что однажды будут присуждать Пулитцеровскую премию за самую грамотную программу и т.д.
Я начал этот эксперимент, потому что один мой друг, Профессор Хоар из Оксфорда, сказал: «Дон, люди даже не читают компьютерные программы».
Издательство Оксфордского Университета было заинтересовано в публикации некоторых компьютерных программ, в качестве примеров как правильно они должны быть написаны.
И вместо каких-то непонятных файлов, которые люди должны еще и прочитать, это была бы в своем роде литература, как, например, музыкальная нотация. Люди же публикуют партитуры симфоний, а не просто слушают их. Так почему мы не можем опубликовать компьютерные программы? И его идея засела у меня в голове, но в то же время она пугала меня, ведь настоящие уже созданные компьютерные программы полны компрометаций. Профессор компьютерных наук не мог допустить этого.
Можно написать маленькую программу и сравнить ее с маленькими драгоценными камнями, но когда речь идет о большой программе, то мы, конечно, можем притвориться, что это драгоценность, но это бы не было таковым. И я не думаю, что многие создатели программ были бы рады тому, что другие люди прочитают их работы в том виде, в котором это было доступно тогда. И я начал думать, как бы написать программу так, чтобы и людям нравилось читать ее.
Так, очевидно, и появилась эта идея грамотного программирования, я нашел формат, в котором мог бы представить программу другим людям, более того, я как создатель этой программы, мог понять ее лучше. И так я дошел до этой системы, в которой мог написать программу на этом языке программирования, затем из этой одной программы я создал еще две — одна конвертировалась из языка описания WEB-сервисов Паскаль, а другая — из языка описания WEB-сервисов в документ, который я мог прочитать благодаря верстке, перекрестным ссылкам и понятным изложениям.
Эта система очень обрадовала меня. Я писал программы в CWEB — это «потомок» оригинальной WEB-система, и это доставляет мне нескончаемое счастье писать программы в таком виде, который я нахожу наиболее подходящим.
Donald E. Knuth: Literate Programming
Learning about Symbolic Optimum Assembly programs (23/97)
Я с семьей ездил в летний лагерь «Линвуд» на неделю, который расположен на берегу озера Эри. И мы снова были там пару лет назад, чтобы освежить воспоминания. Итак, провели две недели на берегу озера. Я играл в теннис со своими дядями и все в таком духе, но я также взял с собой несколько примеров компьютерных программ, о которых я был наслышан. И у меня было немного свободного времени тем летом, чтобы ознакомиться с ними. И, на самом деле, эти программы оказали огромное влияние на мою будущую жизнь.
Одна из программ называлась ассемблер — она позволяла писать программы, используя не машинный язык, а более символический. Это многое упрощало… Я имею ввиду, что, когда я начал писать программы, я все писал в цифрах, и если мне надо было добавить цифру в участок 1 к цифре, расположенной в участке 2, то я должен был записать что-то в роде 20,0,0,1. Мне приходилось выписывать все эти цифры, вбивать их в карты, и только потом использовать в работе — это все, что я знал о программировании на тот момент.
Но та программа была новшеством для того времени, и она позволяла писать программы более простым методом. Вместо того, чтобы выбирать число для каждого участка в программе, я мог дать ему название, и аппарат уже сам определял какое число соотносится с этим названием. Но в те времена, компьютеры не могли хорошо справляться с буквами, они были рассчитаны на работу с цифрами, но можно было использовать заглавные буквы. С этим ассемблером можно было применять до пяти букв на одно слово.
(Примечание от safinaskar: «Этот ассемблер позволял использовать метки»)
Я точно помню, как я использовал это для своей программы «крестики-нолики», и мне пришлось придумывать, какое слово из пяти букв будет определять определенный участок программы. И я вспоминаю с восторгом, как я играл в крестики-нолики, и как в момент выигрыша программа переходила на участок БИНГО. Я использовал это слово из пяти букв Б, И, Н, Г, О для этого участка программы.
Да, я тогда узнал об ассемблере и научился кодировать. Я использовал это в работе, но в то же время я задавался вопросом: «Как это работает? Что вообще происходило внутри, и как соотносилось слово БИНГО с цифрой? Как аппарат сразу это понимал?» У меня был листинг для этой программы под названием SOAP 2 от Стэна Поли из IBM. я собой у меня также был листинг программы под названием «Транслятор» (IT-Internal Translator) — это новая программа, которая была создана 4 людьми в Карнеги, Университет Карнеги-Меллон. Этот транслятор использовал алгебраический язык, а не машинный. И это задолго до того, как появился Фортран или другие языки программирования высокого уровня. Я же говорю о 1956,1957 годах.
И суть была такова, что вы можете написать X=A+B, ну, на самом деле так нельзя было написать, ведь не было возможности использовать символ «+», так что мы писали, X1, Z, X2, S, X3, где S обозначало «+», и буква Z использовалась вместо «=», а каждая переменная как Х1, Х2, Х3 или чем-то похожим. Но теме не менее, вы могли ввести алгебраическую формулу в карту, и потом аппарат уже определял из этого, как вычислить A+B или что вам нужно сделать.
Вместо того, чтобы обозначать цифрами или символами, там были алгебраические символы. И можно было просто перевести программу на компьютер, и тут же загорались огоньки, и спустя некоторое время вы получали аппарат с компьютерным языком программирования. Магия. Я не мог понять, как это вообще работает, так что я достал копию программы, которую они использовали для написания этого транслятора, и у меня появилась копия программы SOAP
The Internal Translator (24/97)
Я принес это с собой, и провел ночи, изучая и пытаясь выяснить, как же работает программа. И, да, мне удалось… Сначала я выяснил, как транслятор работает, как именно он переводит алгебраическую формулу в инструкции. Но дальше все было сделано ужасно. В программе были ошибки. Каждый раз деля что-либо, у создателей едва получалось довести до конца.
Я тогда обратился к программе SOPE, той, что от Стэна Поли — эта программа была точная, невероятная, словно вы слушаете симфонию. Все соединялось так гармонично, и этот код был простым. Я сказал тогда: «Хотел бы я писать программы, как это делает этот парень». И тот второй код от других разработчиков, он был громоздким и топорным. «А ведь я могу написать лучше, чем это».
Поэтому я и несколько моих друзей написали улучшенную версию и назвали ее RUNCIBLE, ведь у каждой программы в то время должен был быть акроним, и это значило что-то вроде «Исправленный Объединенный Новый Составитель Основного языка» (Revised Unified New Compiler IT Basic Language Extended) или как-то так. У нас было несколько причин, чтобы так назвать программу, но мы хотели переделать тот алгебраический язык, привести в более упорядоченный вид, и затем мы смогли немного улучшить программу, и при это уместиться в те же 10кбайт.
Вот так я провел свое первое лето в Компьютерном Центре. И потом, уже после того как программа RUNCIBLE была написана, мы также… я также написал инструкцию по эксплуатации для этой программы, и удивительно, эту инструкцию использовали как руководство для студентов на следующий год. И я оказался в довольно необычном положении: на одном из занятий использовали как раз ту самую книгу, которую я написал, будучи на втором курсе.
И RUNCIBLE, мы обновили эту программу следующим летом, добавили туда кучу всяких мелочей, уместив их в 10кбайт. Но у нас все еще была плавающая точка и другие вещи, над которыми нужно было работать… Поэтому мы снова решили сделать улучшенную версию. И так я написал SOAP 3. Знаете, мне нравилась программа SOAP 2 от IBM. Я написал SOAP 3, которая основывалась на SOAP 2, и в дальнейшем ее мы использовали как ассемблер для улучшения программного обеспечения. И Кейс позволял примерно дюжине студентов писать программы, которые бы в дальнейшем использовались другими студентами или факультетами.
Фред Уэй, директор этой программы, был очень прозорливым, он доверял студентам, и позволял нам…ну, мы здорово проводили время, разговаривая друг с другом обо всем этом. Мы так же получали ежемесячный журнал Ассоциации вычислительной техники в 1958. тогда мы увидели, что люди с всего света публиковали свои идеи как писать программы, и мы тогда поняли, что уже тоже знаем все эти вещи и даже больше.
Так моей второй публикацией, после Potrzebie System для Mad Magazine, стала статья о RUNCIBLE: превращение формул в машинный код. Я отправил свою статью в журнал Ассоциации вычислительной техники, который тогда только начал печататься. Я тогда был очень наивным, не понимал, как правильно печататься в научных журналах. Да, я видел журналы, знал, что туда можно отправить статью, но не имел никакого понятия о значении. Мне важна была сама история, поэтому я и написал.
Я считал себя докладчиком, представителем этих ребят из Компьютерного Центра Кейса, с которыми я вместе работал над созданием RUNCIBLE. И я написал статью о методах, который мы использовали для RUNCIBLE, но нигде в статье я не упомянул имен этих ребят, и я не знал, что получу сумму, за эти идеи, я просто хотел их описать.
Только позднее я все это понял, узнал об условностях. А в тот момент, я просто написал статью. И мы подготовили этот материал правильно, когда статья уже была опубликована, как часть моего собрания сочинений несколько лет назад.
Читать еще
1. Family history
2. Learning to read and school
3. My mother
4. My parents’ finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with…
32. Finding a solution to an open problem about projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the.
39. The successful first release of The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether I’d made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the…
59. Converting Volume Two to TeX
60. Writing a users’ manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain any rights to TeX and transcribed it to…
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of «The Art of Computer.
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86. Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject