Как компиляторы Си хранят информацию о типах?

Я с 16 лет увлекаюсь компиляторами

И до сих пор не прочитал ни одного приличного учебника? Ты реально безнадежен.

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

должны парсится
черезчур

Гм.

Пробовал смотреть исходники TCC

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

/* type definition */
typedef struct CType {
    int t;
    struct Sym *ref;
} CType;

/* symbol management */
typedef struct Sym {
    /* ... */
    CType type;    /* associated type */
    /* ... */
} Sym;

/* types */
#define VT_PTR              4  /* pointer */
#define VT_ARRAY       0x0020  /* array type (also has VT_PTR) */

Т.е. типы хранятся в односвязном списке

в классической литературе по компиляторам («Построение компиляторов Н.Врит»)

Классическая литература по компиляторам это драгон-бук и «Modern Compiler Implementation» Аппеля.

//мимопроходил

Да, чуть не забыл. Лоровец XVilka делал такую вот штуку: https://github.com/XVilka/cparse , можешь кастнуть его и поспрашивать.

Он там пользовался lemon ( http://www.hwaci.com/sw/lemon/lemon.html ). Хоть здесь и не любят табличные генераторы парсеров, но lemon делает довольно компактный код. На небольшой грамматике типа подмножества SQL получается несколько (единицы) килобайт бинарного i386-кода

HiSoft C compiler, CP/M

Аналогично, TurboC на MSX-DOS прекрасно помещался в 64к, правда, с оверлеями. Turbo Pascal там же и без оверлеев работал.

Сишечка в один проход не компилируется

TCC компилирует в один проход. PCC вроде тоже (не помню).

Да она на либгене есть

А как же Вирт? :)

Napilnik

своп побольше сделать и ок

И до сих пор не прочитал ни одного приличного учебника?

так ему, вероятно, недавно 17 исполнилось)

Я собираюсь его запускать на 64кб памяти

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

char *(*(**foo[][8])())[]; Не представляю как это реализовать.

как хочешь. Попробуй односвязанный список например. В чём проблема-то?

Т.е. должны парсится такие выражения:

а… Проблема в том, что ты не определился, что ты хочешь реализовать вначале: как парсить, или как хранить?

Может стоит попробовать начать писать код, а не бред на ЛОРе?

Я собираюсь его запускать на 64кб памяти.

пилять!

Напиши ты сначала нормальный прототип для нормального компьютера.

Тебе дело говорят, без явного или неявного AST ничего не выйдет. А неявное AST получится лишь после явного.

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

тип это не дерево, а список. Дерево — это выражение, в котором есть бинарные и тернарные операторы. Причём выражение отображается в код, а тип — не отображается, для x86 например любой указатель на что угодно это тупо EAX или какой другой регистр. А вот когда тип int a[], становится выражением a[17], тогда-то и появляется AST, ибо в выражении [] это уже бинарный оператор, имеющий два аргумента.

Вообще-то дерево. Тип функция имеет два потомка: тип результата и список типов аргументов. Поэтому дерево.

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

не, там один потомок: это общий список. Синтаксически в C указатели на функции эквивалентны друг другу. Т.е. если один из аргументов указатель на функцию, то не важно(с т.з. типа), является-ли этот указатель указателем на функцию возвращающую указатель на функцию, или на функцию возвращающую int. Т.е. это просто указатель на определённую функцию, и является конечным узлом в списке(листом). Это конечно так лишь при построении AST. А вот при парсинге определения типа — да, получается дерево(у извращенцев).

пилять!

Стараюсь. Я нашел закоментированные сорцы cc, вроде збс. Буду разбираться.

ну удачи. Однако 64К это явно мало. Это всё равно, что изнасиловать комара. Попробуй собаку/кошку, о результатах сообщи ☺

Тип в Си — это дерево. Не надо путать машинный язык любой архитектуры и Си. С точки зрения x86 типов вообще четыре штуки: byte, word, dword и qword.

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

это уже игра словами ИМХО. Ладно, пусть будет дерево, главное, это _другое_ дерево.

ИМХО как бы там ни было, у указателя на функцию больше одного типа-потомка (и каждый из этих потомков может сам быть указателем на функцию), и поэтому тип в Си просто by definition дерево.

То, что unsafe-преобразования из кучи типов в другую кучу типов по дефолту разрешены — вообще другой вопрос. Как и то, что все эти типы в итоге маппятся на четыре физических.

сабжевый вопрос «как хранит?». Вот когда он хранит тип «указатель на функцию», то хранит он только _одно_ значение(во время построения AST). Т.е. если в нетривиальном выражении встретился указатель на функцию (что само по себе UB, ну да и ладно), то в AST вписывается лишь значение этого указателя. Всё потому, что с указателями на функцию _ничего_ нельзя делать(в рантайме), только разименовывать.

А обычные указатели можно вычитать, и ещё к ним можно прибавлять ptrdiff_t. Указатель на указатель в рантайме можно разименовывать дважды, т.ч. только указатели не на функции обрабатываются AST, а указатели на функции в AST это константы.

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

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

А при чём тут значения вообще? AST — это одно. А то дерево, которое получается при парсинге type specifier — это вообще другое.

типы хранятся в односвязном списке

Перечитал intelfxa, мысленно согласился, посмотрел еще раз в tcc.h и tccgen.c, и таки да, тип хранится в дереве. В struct Sym есть еще struct Sym *next, *prev;, если тип VT_FUNC, там хранятся аргументы.

То есть для простых случаев типа «указатель на массив указателей на char» это вырождается в односвязный список, а как только встречается функция - древенеет.

А при чём тут значения вообще? AST — это одно.

я про значения типа. ну например у меня есть int* ptr;, и когда компилятор будет строить AST и его обрабатывать (а это важная и долгая часть работы), то он будет знать что такое ptr, и какие операции с ним допустимы. Я так думал, что это и есть суть вопроса ТСа: как сохранять свойства(тип) переменной ptr?

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

зачем это ТСу с его 64К памяти? Ему-бы простой int/unsigned/pointer реализовать…

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

Однако 64К это явно мало.

Turbo C на MSX-1 видел?

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

Опять некомпетентные школьники со своим сверхценным мнением о нужности или ненужности?

Представь, например, FPGA, куда надо засунуть побольше soft cores, и раздать им блочную память. По 4к на ядро, например.

Или ASIC, на котором 100 маленьких-маленьких ядер без кэша, с одним общим контроллером памяти на всех и 64к SRAM памяти у каждого ядра.

Ты со своим «ненужно» обосрешься такие архитектуры проектировать и кодить под них. А вот у ТС еще есть шанс, когда подрастет и поумнеет.

своп побольше сделать и ок

Куда ты собрался свопить?

ТС не поумнеет, если продолжит задавать на форуме такие вопросы. ТС поумнеет, если сам станет искать на них ответы.

нет. А разве тогда был TurboC? Я его видел только на IBM-PC-*.

Опять некомпетентные школьники со своим сверхценным мнением о нужности или ненужности? Представь, например…

А зачем там компилятор?

Был Turbo C, правда, с оверлеями.

Был Turbo Pascal, вполне полноценный.

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

Представь, например, FPGA, куда надо засунуть побольше soft cores

вот и говорю: зачем на этом запускать компилятор?

Ты со своим «ненужно» обосрешься такие архитектуры проектировать и кодить под них

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

ещё один неосилятор понятия JIT-компиляции

Ололошечки, дурень, осилишь рассказать неосилятору, чем это JIT компиляция отличается от любой другой?

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

https://en.wikipedia.org/wiki/Just-in-time_compilation

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

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

зато есть такое преимущество, что JIT-компиляция проводится в рантайме, что позволяет использовать набор команд конкретного процессора

забыл добавить: для микроконтроллеров это преимущество тоже не работает

и в каком jit код оптимизируется аналогично gcc -march=native -mtune=native, те со всеми simd, шедулингом команд и пр

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

Да кого колышат твои микроконтроллеры? Я про до-хера-параллельные системы говорю. И тут преимущество такое, что промежуточный код компактный и его дешевле тянуть из внешней памяти, а нативный код жирный. И «распаковывать» (то есть, компилировать) надо уже на месте, где памяти мало у каждого ядра, но зато она сцуко своя.

Да в любом, который на LLVM основан.

Да кого колышат твои микроконтроллеры?

вообще-то, всех. хотя бы потому, что без микроконтроллеров ваши «до-хера-параллельные системы» работать не будут: половина сотрудников до рабочих мест тупо не доедет, а те, кто доедет, код набивать будет иголочкой на перфокартах)

И тут преимущество такое,

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

Аледятел, сам же справедливо вещал, что в микроконтроллере компилятор не нужен. Фигли ты к ним прицепился?

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