Сколько проходов должно быть у транслятора?
ВведениеВ общем случае вопрос, вынесенный в заголовок, не имеет смысла. Число проходов (т.е. число просмотров исходного текста программы) может зависеть от языка, от назначения транслятора и тому подобных вещей. Кроме этого, если Вы сами не разрабатываете и не сопровождаете транслятор, то вообще какая Вам разница, сколько у него проходов? Ведь Ваши программы от этого не меняются? Правда, исходя из умозрительных соображений, чем больше проходов, тем потенциально выше может быть качество трансляции. И если бы не было возражений против медленной работы транслятора, возможно число проходов исчислялось бы многими десятками. Говорят, когда-то были трансляторы, число проходов которых было равно числу разработчиков, поскольку каждый делал свою независимую часть. Однако ещё больше влияли на это небольшие с современной точки зрения ресурсы тогдашних компьютеров: приходилось разбивать транслятор на части так, чтобы каждая из них могла целиком поместиться в памяти.Постепенно стала преобладать точка зрения, что все языки должны быть построены по принципу «сначала опиши, затем используй». Это позволяет транслятору выполнить единственный просмотр исходного текста, а значит можно иногда даже не хранить результат анализа всей программы в промежуточном виде и максимально ускорить процесс трансляции, учитывая, что большинство современных программных модулей имеют значительные размеры исходного текста, в основном из-за «заголовочных» файлов. Язык с двухпроходным трансляторомАвтор относится к возможно небольшой группе программистов, которая не придерживается принципа «сначала опиши, затем используй». Честно говоря, много лет я даже не задумывался об этом, поскольку в работе использовал язык PL/1 [1], причем так получилось, что переход на этот язык у меня совпал с переходом на персональные компьютеры. У современного поколения программистов об этом языке смутные представления, в основном сводящиеся к мифу, что язык был очень сложным (что смешно звучит в сравнении с теперешними системами программирования), и к «прикольному» выражению типа IF IF=THEN THEN ELSE=THEN; ELSE THEN=ELSE; якобы свидетельствующему о тупости разработчиков, усложнивших транслятор, допускающий такое.С моей точки зрения разработчики PL/1 были вовсе не тупы. Наоборот, язык продуман и логичен, поскольку именно он был следующей ступенью развития первого системного (целостного) языка — Алгола. И кстати, придуманные остряками «прикольные» выражения нисколько не усложняют транслятор, поскольку не нарушают простую структуру языка. В 1987 году был принят новый стандарт, исправивший не очень удачный механизм умолчаний, но сохранивший базовый принцип «описание может быть и до, и после использования». Этот принцип и определяет минимально необходимое число проходов транслятора. Разработчики PL/1 исходили из того, что транслятор будет просматривать исходный текст не менее двух раз. О прототипах функцийКогда-то прочитав статью Эберхарда Штурма [2], я очень удивился необходимости иметь в языке Си так называемые прототипы функций, если сама функция (т.е. её тело) следует ниже в тексте программы. Разве самостоятельно транслятор не может узнать свойства такой функции? Конечно, может. Например, вот фрагмент транслятора с PL/1, который выполняет такое действие. Я понимаю, что данный фрагмент (да ещё со следами дисассемблирования) сходу трудно понять. Просто оцените его размер и поверьте, что он работает, после того, как разобран заголовок и тело процедуры. В результате автоматически создается аналог оператора описания (т.е. тот самый прототип) и добавляется в общую таблицу объектов программы.
;======= СОЗДАНИЕ ПРОТОТИПА В ВИДЕ DCL ENTRY(...) RETURNS(...); =======
;---- СОЗДАЕМ ЭЛЕМЕНТ В ХЭШ ДЛЯ ВОЗВРАТА ЗНАЧЕНИЯ ----
SHR B PTR [EBP]-4,1 ;FUNCTION ?
JNB @
CALL C330C ;СОЗДАЛИ ЭЛЕМЕНТ ДЛЯ ВОЗВРАТА ЗНАЧЕНИЯ
POP ESI ;ТЕКУЩИЙ АДРЕС В СТЕКЕ
MOV EDI,EBX
PUSH ESI
MOVSD ! MOVSD ;ПЕРЕПИСАЛИ ХАРАКТЕРИСТИКУ FUNCTION
CALL C3449 ;ЗАКРЫЛИ НОВЫЙ ЭЛЕМЕНТ
;------------ СОЗДАНИЕ ВСЕХ ОБЪЕКТОВ-ФОРМАЛЬНЫХ ПАРАМЕТРОВ ------------
@: POP EAX ;ВЫБРОСИЛИ БОЛЕЕ НЕНУЖНЫЙ АДРЕС
XOR EAX,EAX ;ОПЯТЬ ВСТАЛИ НА ПЕРВЫЙ ПАРАМЕТР
MOV X1800,AL ;БУДЕМ ТОЛЬКО СОЗДАВАТЬ ЭЛЕМЕНТЫ ХЭШ
JMPS M4229
;---- ЦИКЛ СОЗДАНИЯ ОБЪЕКТОВ-ФОРМАЛЬНЫХ ПАРАМЕТРОВ ----
M41C8:MOV EBX,X17D2 ;АДРЕС ПРОЦЕДУРЫ СВЕРХУ
PUSH EAX ;НОМЕР ОЧЕРЕДНОГО ПАРАМЕТРА
MOV EAX,[EBX+EAX*4]+10 ;КООРДИНАТА ПАРАМЕТРА
;---- ДЛЯ НЕОПИСАННОГО ПАРАМЕТРА СОЗДАЕМ ПУСТОЙ ЭЛЕМЕНТ ----
OR EAX,EAX ;ПАРАМЕТР ОПИСАН ?
JNZ @
CALL C3448 ;ПРОСТО СОЗДАЕМ ПУСТОЙ ЭЛЕМЕНТ
JMPS M421A
;---- ДЛЯ ОПИСАННОГО ПАРАМЕТРА СОЗДАЕМ ЭЛЕМЕНТЫ ХЭШ ----
@: ADD EAX,EBX ;АБСОЛЮТНЫЙ АДРЕС
MOV EDI,OFFSET X17D4
STOSD ;МЕСТО ПАРАМЕТРА СВЕРХУ
MOV EAX,OFFSET X17DC ;КЛАСС ПАМЯТИ PARAMETR
STOSD ;ФОРМАЛЬНО КЛАСС ПАМЯТИ PARAMETR
AND D PTR [EAX],0 ;ДЛЯ ИЗБЕЖАНИЯ ПЕРЕПОЛНЕНИЙ
PUSH 1 ;ДЛЯ ПАРАМЕТРОВ ТОЛЬКО ВЫДЕЛЯЕМ ХЭШ
CALL C3A6B ;ТА ЖЕ ПРОЦЕДУРА ВЫДЕЛЕНИЯ ПАМЯТИ
;---- ПРОДОЛЖАЕМ ЦИКЛ ОБРАБОТКИ ----
M421A:POP EAX ;ВОССТАНОВИЛИ НОМЕР ТЕКУЩЕГО ПАРАМЕТРА
INC EAX ;УВЕЛИЧИЛИ НОМЕР ПАРАМЕТРА
M4229:DEC B PTR [EBP]-1
JNS M41C8 ;ЗА СЛЕДУЮЩИМ ПАРАМЕТРОМ
LEAVE
RET
Причем здесь используется та же процедура занесения объекта в таблицу, что и при разборе обычных операторов описания. Поэтому и фрагмент короткий — всего-то три десятка ассемблерных команд. Неужели создатели языка Си не могли придумать что-то подобное этим жалким 30 командам в своем трансляторе и избавить программистов от необходимости писать прототипы? Да, не могли. Потому, что в этом трансляторе просмотр исходного текста происходит два раза, а разработчики Си исходили из того, что трансляция Си-программы будет проходить за один просмотр исходного текста. Встретив обращение к функции транслятор уже должен знать, что это такое. Даже если сама функция идет несколькими строчками ниже.
Преимущества двух проходовОказывается, число проходов транслятора влияет не только на скорость трансляции, но и на сам язык. Если иметь более одного прохода, многие вещи упрощаются, а принцип «сначала опиши, а затем используй» становится необязательным. Кстати, попробуйте выполнить этот принцип, если у Вас есть две рекурсивные подпрограммы, каждая из которых вызывает другую.Но, может быть, дополнительный проход это всегда слишком медленно и лучше уж терпеть некоторые неудобства вроде «лишних» описаний? Сомнительно. Приведенный в пример транслятор с двумя проходами имеет среднюю скоростью 528 байт (или 17 строк исходного текста при моем стиле программирования) в секунду на каждый мегагерц тактовой частоты процессора [3]. Т.е. даже на скромном компьютере с процессором в 1 ГГц двухпроходная трансляция идет со скоростью полмегабайта текста (или 17000 строк) в секунду. При этом так называемая «предтрансляция» заголовочных файлов не используется, хотя в некоторых заголовочных файлах имеется специальный признак, показывающий транслятору, что в данном файле есть только одни описания. В таких случаях транслятор на втором проходе не просматривает эти файлы, поскольку вся информация из них уже занесена в общую таблицу на первом проходе. Но самое главное, два прохода транслятора при анализе программы позволяют организовать весь процесс трансляции оптимальным с моей точки зрения образом. На первом проходе транслятор ищет в исходном тексте информацию, так сказать, специально приведенную для него программистом (т.е. описания) и составляет общую таблицу всех объектов анализируемой программы. Ресурсы современных компьютеров легко позволяют хранить такую таблицу целиком в памяти. Затем транслятор на втором проходе приступает собственно к тому, что обычно подразумевается под трансляцией программы. При этом в каждой точке программы он теперь «понимает», что имел в виду программист, поскольку к этому моменту уже имеет полный список всех объектов программы. Т.е. из-за первого прохода никаких разночтений и двусмысленностей уже нет и, таким образом, потенциально упрощается сам язык. Возможность размещения описаний объектов после их использования лишь одно из проявлений такого упрощения. Я надеюсь, понятно, что речь идет только о проходах на первой фазе трансляции — анализе программы. Синтез программы (генерация кода) может иметь свои проходы, но это, как говорится, отдельная тема. Также должно быть понятно, что рассматриваются только процедурные языки, поскольку языки некоторых других классов могут требовать принципиально иной организации процесса трансляции. А при такой организации на первом проходе для того, чтобы разобрать описания приходится разбирать и всю структуру программы, поскольку необходимо различать константы, комментарии, возможно, вложенные блоки описаний (например, PL/1, как и Алгол, имеет блочную структуру) и т.п. Но все-таки это не полноценный анализ исходного текста, а сокращенный, поскольку после выделения конструкций языка в тексте, большая их часть просто пропускается, что существенно ускоряет работу. Поэтому я первый проход даже называю «половинным» и таким образом считаю, что использую «полуторапроходный» транслятор. Интересно, что в данном случае прослеживается аналогия с транслятором с ассемблера RASM [4], который я также использую. Классический транслятор с ассемблера как раз имеет два прохода: на первом разбираются конструкции и подсчитываются их адреса. К концу прохода получается полная таблица переменных и меток с адресами. На втором проходе уже генерируются команды, в которые подставляются адреса используемых переменных и меток. Так вот, в ассемблере RASM также имеется дополнительный «половинный» проход, на котором просто ищутся все переменные (т.е. ищется, в каких секциях программы они расположены). На следующем, уже так сказать «настоящем» проходе, подсчитываются адреса переменных с учетом секций и возможных дополнительных байтов префиксов. В результате переменные в RASM можно описывать и в конце программы (как и в PL/1), а не обязательно в начале, как во многих других ассемблерах. При этом дополнительный «половинный» проход очень слабо ощутим на общей скорости работы транслятора. Недостатки дополнительного проходаХватает ли одного дополнительного просмотра исходного текста, чтобы устранить все сложности? Очевидно, что нет. Например, если вернуться к PL/1, то в первоначальном варианте (фирмы IBM) транслятор ещё имел препроцессор как отдельный этап обработки текста. В используемом мною трансляторе отдельного препроцессора нет, но два его самых полезных оператора %INCLUDE и %REPLACE оставлены. В результате переименованные с помощью %REPLACE константы должны находиться в программе раньше мест их использования, т.е. начинает действовать изложенный выше строгий принцип описаний. Но все-таки это гораздо меньшее неудобство, чем тот же принцип, примененный вообще ко всем описаниям в программе.Справедливости ради следует отметить, что, несмотря на дополнительный проход, транслятору с PL/1 все равно приходится иметь ещё и довольно хитрый механизм «подсматривания вперед» только для того, чтобы разобрать начало оператора присваивания или метку, поскольку эти конструкции могут начинаться с произвольного имени. Цель такого «подсмотра» — добраться до ближайшего символа равенства (тогда это присваивание) или до двоеточия (тогда это метка). При этом обычный разбор «не знает», что исходный текст уже немного прочитан далее. Предварительный просмотр, «забежав вперед», затем направляет транслятор или на разбор метки, или на разбор левой части присваивания. Попутное использование дополнительного проходаПоскольку на первом проходе все равно приходится разбирать общую структуру программы удобно здесь же выполнить и некоторую попутную обработку, например, разобрать и записать все форматы ввода-вывода. А программисту можно выдавать сообщения о грубых ошибках общей структуры программы, не откладывая это на следующий этап детального анализа. Например, в используемом мною трансляторе есть специальный ключ запуска, выдающий на первом проходе программу с указанием в строках исходного текста глубины вложенности блоков, обозначаемой буквами a, b, c, и т.д. Таким приемом легко искать потерянные «операторные скобки» и операторы END: правильная программа должна начаться с «а» и этой же буквой и окончиться. Ошибки структуры быстро находятся даже при наличии ошибок в операторах и конструкциях языка, которые на первом проходе по существу только пропускаются. При этом ошибки автоматически разделяются на более грубые (первый проход) и менее грубые (второй проход). В свою очередь, это позволяет в трансляторе точнее диагностировать ошибки и уменьшать число наведенных ошибок.Разбор блочной структурыДля приводимого в пример транслятора с PL/1 первый проход — это ещё и этап анализа блочной структуры программы и определения областей «видимости» переменных и подпрограмм. Возможно потому, что я всю свою жизнь имел дело с языками с блочной структурой, я совершенно не представляю, как без неё можно обходиться. Например, я не понимаю, почему она изначально не было реализована в языке Си. По-моему, если бы в трансляторе Си был предусмотрен дополнительный проход, то реализация блочной структуры (и областей видимости переменных) почти ничего не стоила бы. Ведь границы блоков не пересекаются, значит, если заносить имена в таблицу транслятора по мере нахождения описаний в тексте программы, они так и лягут в таблицу «кучками», т.е. поблочно. Кстати, для PL/1 как раз это не совсем так, поскольку здесь описания могут идти в любом месте блока. Например, в программе могут идти описания, затем внутренний блок со своими описаниями, а затем продолжатся описания текущего блока. Поэтому транслятору с PL/1 на первом проходе приходится описания внутренних блоков сдвигать в конец таблицы, а когда текущий блок закончится, обратно передвигать их, но уже за описаниями текущего блока. В конце концов, в общей таблице все устанавливается в строгом порядке: сначала описания самого внешнего блока, затем описания вложенных в него блоков и т.д. Таким образом, если описание имени встречается в нескольких блоках, оно и в таблице транслятора запишется в нескольких местах с указанием, к какому блоку оно относится. А сам блок в таблице характеризуется одним числом — «вложенностью». Самый внешний блок имеет вложенность ноль, а самый «вложенный» — самое большое значение. Обеспечение видимости переменных и подпрограмм означает для транслятора поиск на втором проходе имени в «кучках» с вложенностью блоков меньше текущей. И все. Незначительные затраты в трансляторе на такую обработку даже для языка PL/1 с его расположением описаний где угодно, с лихвой окупаются получаемым удобством блочной структуры, позволяющей легко объединять части в единую программу, не заботясь о случайном совпадении имен. При этом простота реализации обусловлена всего лишь наличием отдельного прохода. ЗаключениеПодведем итоги. Я придерживаюсь мнения, что на современном уровне развития компьютеров (т.е. при существующих типичных ресурсах памяти и быстродействия) рационально разрабатывать трансляторы с процедурных языков не менее двух раз просматривающих исходный текст программы. Главной целью первого просмотра должно быть получение максимальной информации об объектах программы, в основном из описаний. Тогда это позволяет на втором просмотре, т.е. собственно при анализе операторов программы уже иметь полную таблицу всех объектов и избегать разных неоднозначностей. Разделение анализа текста на процедурном языке сначала на разбор «описательной», а затем «выполняемой» частей вполне естественно и позволяет располагать эти части в тексте программы в любом удобном для программиста порядке. Однопроходная схема трансляции, возможно, и имела некоторые преимущества во времена слабых ресурсов и быстродействия компьютеров, но в текущих условиях вряд ли является оправданной. Приведенный как пример двухпроходный транслятор с языка PL/1 имеет вполне приемлемую скорость, несмотря на дополнительный проход, который к тому же выполняется быстрее за счет пропуска большой части конструкций в тексте программы.И уж тем более неоправданными являются любые ограничения в языках, связанные с предположениями, что транслятор с этого языка должен просматривать исходный текст только один раз. Затраты на организацию дополнительного прохода стали слишком несущественными, чтобы из-за них отказываться от преимуществ предварительного просмотра всей программы. Поэтому сейчас правило описывать все в программе до использования объективно не является необходимым. Литература1. Караваев Д.Ю. К вопросу о совершенствовании языка программирования. RSDN Magazine #4, 20112. G.U.I.D.E. & SHARE Europe Joint Conference (10-13 October 1994, Vienna, Austria) «Power vs. Adventure — PL/I and C». Eberchard Sturm. Munster, Germany. http://www.uni-muenster.de/ZIV.EberhardSturm/PL1andC.html 3. Караваев Д.Ю. «Идеальный транслятор». Журнал Downgrade #5, 2012, dgmag.in 4. Караваев Д.Ю. О специальных макросредствах в трансляторе с языка ассемблера. RSDN Magazine #3, 2012 Автор: Д.Ю.Караваев. 29.05.2014 Опубликовано: 2018.08.26, последняя правка: 2019.01.29 14:27
Отзывы✅ 2018/10/08 14:00, Неслучайный читатель #0 Лично мне видится неочевидная взаимосвязь числа проходов компилятора с одной стороны и разделения интерфейса и реализации с другой стороны.Существуют однопроходовые компиляторы. Они налагают некоторые требования на язык: в нём функции, методы классов, сами классы и структуры должны быть описаны до того, как они потребуются. Т.е. нельзя, к примеру, вызвать некую функцию до того, как она была описана. Если нет предварительных описаний, то компиляция в один проход в принципе невозможна, ведь программа может иметь в себе сущности, взаимно рекурсивные. Например, класс A ссылается на класс B, а тот, в свою очередь, на A. Двухпроходовый компилятор снимает эту проблему: в первом проходе выявляются все описания, а во втором — подставляются. Это даёт некоторые удобства: в таком случае совсем необязательно сначала что-то описывать, т.е. делать двойную работу. К тому же, описав некоторую сущность, при повторном (хотя и более детальном) описании можно допустить ошибку. Например, декларация функции содержит один набор аргументов, а реализация — другой. Однократность снимает некоторые проблемы. Двухпроходовая компиляция несколько медленнее однопроходовой. С другой стороны, скорость компиляции на современных компьютерах — не самая насущная проблема. Некоторой скоростью можно поступиться, если экономится труд программиста, если ему не приходится что-то описывать дважды, пусть даже в первый раз — в сокращённом виде. Но есть другая грань в программировании. Правилом хорошего тона считается разделение интерфейса и реализации. Это логично. Интерфейс часто является публичной частью; если реализацию можно подправить «малой кровью», то изменение интерфейса оказывает далеко не локальное влияние. К чему может привести изменение публичного интерфейса какого-то класса, если он применяется во множестве проектов по всему миру? К головной боли разработчиков. А вот реализацию можно пилить без особых последствий. Интерфейс может (даже должен) находиться отдельно от реализации, т.е. #include <интерфейс 1>Но это как раз то, что позволяет компилятору быть однопроходовым. Т.е. сама жизнь подталкивает к компиляции в один проход. Хотя, конечно, можно найти лазейки, меняющие картину мира. Например, компилятор может обойти файлы проекта, выявить описания функций, методов, структур и классов, выявить публичные и самостоятельно сформировать модуль или файл с интерфейсами. Но это «сбоку» от классического пути. ✅ 2018/10/30 15:59, Александр Коновалов aka Маздайщик #1 Многопроходность и отделение интерфейса от реализации, это всё-таки две разные вещи. Хоть в языках Си и Си++ для обоих целей используется один и тот же механизм.Объявление функции в файле говорит транслятору о том, что эта функция где-то определена с такой-то сигнатурой. А где определена — ниже по тексту или в другом файле — это деталь. Если транслятор многопроходный, то предварительные объявления функций ниже по тексту не нужны. Но остаются нужны объявления функций, которые определены в независимо транслируемом файле — или в другом исходнике, или в уже скомпилированной библиотеке. Более того, в некотором файле может реализовываться некоторый громадный алгоритм, требующий кучи отдельных подпрограмм, но при этом в интерфейс будет выноситься одна или несколько простых функций. Для функций интерфейса объявление в заголовочном файле нужно (оно нужно пользователям интерфейса), для вспомогательных функций реализации в случае многопроходного транслятора их писать не надо. ✅ 2018/11/02 23:23, Неслучайный читатель #2 Да, конечно, при раздельной трансляции нужны объявления функций. Но всё-таки есть неочевидная связь между числом проходов и разделением интерфейса и реализации. Вот вы видите перед собой двух человек: один из них в очках и галстуке, а другой — в рабочей робе. Кто из них профессор? Вам будет легко угадать :)Написать автору можно на электронную почту |
Продолжение цикла и выход из него