Компилятор для ООП-языка: какими классами представлять переменные/объекты?

[schmidt]

Добрый день,

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

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

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

[Fregloin]

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

[Igors]

Пишу компилятор в учебных целях для языка с поддержкой классов и объектов а-ля Java/C++.

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

Компилятор - это программа которая проверяет исходный текст на синтаксическую правильность и переводит его в ассемблерную форму

Может я это где-то слышал - уже и не помню, но мое понимание такое. А что пишете Вы? (неясно)

[Racheengel]

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

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

[schmidt]

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

Компилятор - это программа которая проверяет исходный текст на синтаксическую правильность и переводит его в ассемблерную форму.

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

Вопрос в том, как представить внутри компилятора эти два различных понятия - переменные и объекты. Чтобы с ними можно было работать схожим образом, независимо от того, что они имеют различную природу. Чтобы код, работающий с ними не обрастал проверками типов, но в нужный момент каждый из них мог сказать "Эй, со мной так нельзя! Я объект, в меня нельзя писать, как в переменную!" Иными словами, чтобы эти понятия имели одинаковый интерфейс, но выполняли разные функции. Я уверен, разработчики существующих компиляторов для ООП языков уже решили эту проблему, вопрос в том, каким способом. Может они взяли какой-то шаблон проектирования, который идеально решает эту задачу или придумали что-то своё. Единственное, что пока приходит на ум, это шаблон "Декоратор" из книги Design Patterns, который использовался там при разработке редактора документов с графическим интерфейсом. С его помощью все элементы редактора, начиная от символов текста в содержимом документа, и заканчивая элементами управления и оформления самого редактора были представлены абстрактным классом Glyph. Таким образом, отрисовка любого элемента имела одинаковый сценарий и не требовала проверки типов. Засчет этого к любому элементу легко можно было добавлять любые элементы оформления, не изменяя сами классы, например добавить рамку, просто создав класс Border extends Glyph { ... } и вложив в него элемент, обрамляемый рамкой.

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

[schmidt]

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

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

Код:

void proc(Struct* this, /* other params */ ...) {
/*...*/
}

Struct* obj = calloc(1, sizrof(Struct));
proc(obj, /*...*/);

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

[Old]

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

[Fregloin]

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

[schmidt]

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

Код:

  enum e_SymbolType {
    BaseTypeVariable,
    Object,
    BaseTypeName,
    ClassName,
    Label,
    Function
  }

struct Symbol {
  e_SymbolType symbol_type;

  /* ... */
}

К сожалению, копаясь в исходниках открытых компиляторов, так и не смог понять, как всё же они работают с таблицей символов. Но прояснить ситуацию очень помогли документы про DWARF (Introduction to the DWARF Debugging Format, DWARF 4 Standard) - спецификации формата отладочной информации. По сути это тоже описание компилятором всех деталей программы - переменных, функций, объектов, инструкций. В реализациях библиотек работы с DWARF нет "вшитых" в программу классов/структур, именующих каждый тип символа - центральным элементом является структура Debug Information Entry (DIE), которая может описывать что угодно - в зависимости от её роли ей назначается конкретный тэг и список атрибутов. Кстати говоря, OpenWatcom, как мне показалось из чтения его исходников, вообще не изобретает отдельных структур для своей таблицы символов, а пользуется DWARF-структурами как они есть.

Очевидно что исходный текст будет прогоняться в несколько этапов, сначала стоит проверять семантику, и выявлять грубые ошибки сразу.
Далее есть смысл уже сканировать где какие переменные, методы, классы, объекты и распихивать по мета-таблицам.
Потом уже пройтись по всем таблицам (возможно придется рекурсивно) и проверить корректность вызова/использования переменных/объектов, а так же привдений типов, уровня досутпа (public,protected,private), инициализации статических переменных и еще куча всего.
А уже после прохождения всех проверок заниматься трансляцией.

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

Код:

/* Всем известное правило языка С */
/* Без этого объявления использование в main вызовет ошибку */
void func();


void main() {
  func();
}


void func() {}

Код:

/* А в Java - можно хоть как! */
class A {
  public void main() {
    m();

    B b = new B();
    b.bf();
  }

  private void m() {}
}

class B {
  public void bf();
}

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

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

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

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

[_Bers]

Добрый день,

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

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

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

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

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

[schmidt]

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

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

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


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