Russian Qt Forum

Добрый день,

Пишу компилятор в учебных целях для языка с поддержкой классов и объектов а-ля Java/C++. Очень интересуюсь авторитетным мнением опытных в разработке компиляторов товарищей: как лучше организовать представление объектов и переменных базовых типов программы - одним классом или двумя? Можно/нужно ли связывать их отношением наследования? Что почитать по этому вопросу? Где найти хорошие ясные примеры, например, хорошо структурированные, документированные open-source компиляторы? Подскажите, пожалуйста :)

Изначально мои рассуждения были таковы: переменные базовых типов - это конкретные ячейки в памяти. Объекты же - это  группы/объединения таких ячеек (переменных). Следовательно, это два различных понятия и объект как таковой не является переменной (ячейкой памяти), поэтому нельзя представлять их одним и тем же классом или связывать отношением наследования (то есть отношением "является"). Но с другой стороны и объекты и переменные очеют очень похожие сценарии использования: они могут встречаться в объявлениях, они могут служить возвращаемым значением функций, они могут быть аргументами функций, они могут участвовать в вычислении выражений, арифметических операциях (при условии, что класс имеет реализации соответствующих операторов), и др. Выходит, если представлять переменные и объекты двумя различными классами (скажем, SymbolVariable и SymbolObject), то всюду, где они могут быть использованы, необходимо вставлять проверки типов ("А что это - переменная или объект?"), вплоть до того, что в таблице символов придется иметь 2 отдельных набора методов: для переменных и объектов. Это очень утомительно и чревато ошибками, да и спустя дня два собственный код читать просто отвратительно - настолько он богат нагромождениями, природа которых таинственна и загадочна.

Ваши предложения, замечания и рассуждения по этому вопросу горячо приветствуются :)

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

Первое впечатление - полный дурдом :) Я конечно понимаю что прививать молодым стремление к творчеству, расширять ихние горизонты мЫшления - дело благородное. Но ...чертовски неблагодарное, так Вы рискуете получить репутацию "Чудака" (в лучшем случае).  Ладно, по существу. Что такое "компилятор"?
Может я это где-то слышал - уже и не помню, но мое понимание такое. А что пишете Вы? (неясно)

Ну я как-то в универе писал компилятор из ассемблероподобного языка в машинный код. Правда, там "объектов" не было, были только регистры и переменные в памяти.

Что мне в данной задаче непонятно - зачем представлять переменные базового типа в виде объектов? У них не может быть никаких методов, только адрес в памяти и размер.

В данном случае расширяю своё собственное мышление =)


Всё верно, именно он ) Но между исходным текстом и ассемблером ему приходится проделывать еще массу дополнительной работы, в частности он занимается сперва разбором исходного текста, созданием таблицы символов, проверкой корректности использования имен. Например, если в Javascript можно обратиться извне функции к любой её переменной как functionName.local_var, то в C/C++ компилятор должен за такое обругать. Я пишу ту часть компилятора, которая занимается разбором входного текста программы и его семантическим анализом (http://ermak.cs.nstu.ru/trans/Trans411.htm).

Вопрос в том, как представить внутри компилятора эти два различных понятия - переменные и объекты. Чтобы с ними можно было работать схожим образом, независимо от того, что они имеют различную природу. Чтобы код, работающий с ними не обрастал проверками типов, но в нужный момент каждый из них мог сказать "Эй, со мной так нельзя! Я объект, в меня нельзя писать, как в переменную!" Иными словами, чтобы эти понятия имели одинаковый интерфейс, но выполняли разные функции. Я уверен, разработчики существующих компиляторов для ООП языков уже решили эту проблему, вопрос в том, каким способом. Может они взяли какой-то шаблон проектирования, который идеально решает эту задачу или придумали что-то своё. Единственное, что пока приходит на ум, это шаблон "Декоратор" (https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%BE%D1%80%D0%B0%D1%82%D0%BE%D1%80_%28%D1%88%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD_%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%29) из книги Design Patterns, который использовался там при разработке редактора документов с графическим интерфейсом. С его помощью все элементы редактора, начиная от символов текста в содержимом документа, и заканчивая элементами управления и оформления самого редактора были представлены абстрактным классом Glyph. Таким образом, отрисовка любого элемента имела одинаковый сценарий и не требовала проверки типов. Засчет этого к любому элементу легко можно было добавлять любые элементы оформления, не изменяя сами классы, например добавить рамку, просто создав класс Border extends Glyph { ... } и вложив в него элемент, обрамляемый рамкой.

Думается мне, стоит поразмышлять именно в этом направлении...

Всё верно ) Переменные базового типа - это только ячейка в памяти. Проблема возникает тогда, когда в исходном тексте могут встречаться как объекты, так и переменные и нам нужно проверить корректность использования имен в тексте. Например, если имя m объявлено в тексте как объект, то m.func() или m.field - корректные инструкции программы. Но если m - переменная базового типа, то она не может иметь ни полей, ни методов и компиляция таких инструкций не имеет смысла. В C-подобных языках, где обходились только переменными и процедурами такая проблема возникнуть не могла: любой "метод" выглядит так:


Единственное, что нужно проверять - это соответствие типов формальных параметров процедуры типам аргументов в инструкции вызова. Однако, компилятор для языка с поддержкой объектов может встретиться и с инструкцией вызова obj.method(), которая сильно зависит от контекста. Более того, имя method может быть и не методом, а вложенным объектом, у которого перегружен оператор "()". Чудесно, в общем =)

Я бы рассматривал вообще все как объекты классов, включая pod типы.
char, int, float можно считать предопредленными классами с определенными арифметическими и логическими операторами.
Тогда останеться только одно понятие объект класса.

и по сути мы скатываемся к яве или шарпу )).
По поводу проверок.. наверное есть смысл делать какие то промежуточные таблицы пространсва имен и жизни переменных/объектов.
К тому же есть смысл сделать иерархию метаклассов - отдельно классы отвечающие за примитивные типы, отдельно за объектные классы, но у которых есть общий базовый функционал, как то:
-перечисление типа класса: POD тип, объектный тип, интерфейс (если это подобие явы)
-название класса
-родитель класса, для POD типа его поидее не должно быть, хотя ничто не мешает сделать их всех наследниками некоего базового Object.
-способ хранения в памяти
-способ вызова методов объектов-экземпляров
-различные методы проверок на корректность вызова и отношений с другими объектами/переменными.
В таблицах хранить места создания и использования конкретных переменных/экземпляров и их зависимости.
Очевидно что исходный текст будет прогоняться в несколько этапов, сначала стоит проверять семантику, и выявлять грубые ошибки сразу.
Далее есть смысл уже сканировать где какие переменные, методы, классы, объекты и распихивать по мета-таблицам.
Потом уже пройтись по всем таблицам (возможно придется рекурсивно) и проверить корректность вызова/использования переменных/объектов, а так же привдений типов, уровня досутпа (public,protected,private), инициализации статических переменных и еще куча всего.
А уже после прохождения всех проверок заниматься трансляцией. Для облегчения, для начала есть смысл транслировать в С++ или другой код ЯП высокого уровня. После прохождения
всех тестов и получения работоспособного когда можно переходить к ассемблеру, но задача не стоит свеч, так как вы будете ограничены ОС и версией ассемблера. + изучать форматы исполняемых файлов (а я знаю о чем говорю, так как имел дело с PE файлами винды), вобщем задача для одного человека ооочень тяжелая и не стот свеч.

По всей видимости простейшее из вариантов - хранить вместе с каждой записью в таблице символов её тип.


К сожалению, копаясь в исходниках открытых компиляторов, так и не смог понять, как всё же они работают с таблицей символов. Но прояснить ситуацию очень помогли документы про DWARF (Introduction to the DWARF Debugging Format (http://www.dwarfstd.org/doc/Debugging%20using%20DWARF.pdf), DWARF 4 Standard (http://www.dwarfstd.org/Dwarf4Std.php)) - спецификации формата отладочной информации. По сути это тоже описание компилятором всех деталей программы - переменных, функций, объектов, инструкций. В реализациях библиотек работы с DWARF нет "вшитых" в программу классов/структур, именующих каждый тип символа - центральным элементом является структура Debug Information Entry (DIE), которая может описывать что угодно - в зависимости от её роли ей назначается конкретный тэг и список атрибутов. Кстати говоря, OpenWatcom, как мне показалось из чтения его исходников (http://ftp://ftp.openwatcom.org/pub/source/open_watcom_1.9.0-src.tar.bz2), вообще не изобретает отдельных структур для своей таблицы символов, а пользуется DWARF-структурами как они есть.


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



При первом проходе мы собираем все объявления функций и классов, а вторым проходом проводим саму трансляцию - таким образом неважно, если я даже опишу функцию в другом файле, транслятор её подхватит, если он обрабатывает этот файл. Если проводить трансляцию в обычной C-style манере, то нам вполне достаточно будет одного прохода для того, чтобы отловить все ошибки семантики: достаточно хранить с каждым полем класса все его атрибуты (static, provate, const и иже с ними), а также отслеживать, где мы находимся - внутри какого класса/метода - на каждрм шаге трансляции. Это можно сделать с помощью обычного стека.

Трансляция, конечно, проходит не сразу в машинный код - этим занимается отдельный модуль - ассемблер. Front-end транслятора читает программу, проверяет синтаксис, семантику и переводит ее в т.н. промежуточное представление - сродни высокоуровневому языку, но уже без лишних деталей и готовое к прямому преобразованию в ассемблер. Кстати, по теме структурного разделения независимых частей транслятора на front-end/back-end есть интересный проект - COINS Compiler Infrastructure (http://coins-compiler.osdn.jp/international/). Это некий фреймворк со своим промежуточным представлением программы, на основе которого можно построить компилятор для любой комбинации входного языка и целевой машины - для этого нужно только написать парсер текста (front-end), который переводит программу в HIR (высокоуровневое промежуточное представление) и back-end, который перебирая HIR-структуры выдает ассемблерный код.

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

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

судя по вопросам - полная шняга у вас в голове.
читайте библию:
А. Ахо Р. Сети Дж. Ульман

"компиляторы, принципы, технологии, инструменты".

Ввши выводы - чушь полнейшая ;) Вы, вероятно, очень удивитесь, но эта книга - первая в любом толковом списке литературы и прочитал я её в первую очередь. Это так забавно выглядит, в ответ на любой вопрос просто бить огромным классическим фолиантом по голове и говорить "Если ты ничего не понял отсюда, значит в голове твоей опилки!" :)


И да, с темой я разобрался, всем спасибо за участие :)