Предлагаю всем желающим совместную разработку компилятора языка C (ANSI) в целях самообразования и (или) практической выгоды (на поздних этапах).
У меня нет абсолютно никакого опыта совместных проектов, потому с удовольствием попрактикуюсь 

Во-первых, разработка будет открытой и все исходники будут размещаться на каком-нибудь Google-Code.
Во-вторых, я не знаю, каким образом происходит обсуждение проекта среди его участников, так что подскажите на этот счет 
Цель - написать (в идеале) полноценный компилятор языка Си, или некоторое его (по возможности наиболее полное) подмножество. Переднего и заднего плана (front-end, back-end).

Высказывайтесь. Очередная банальность и велосипед о трех колесах.

Это сообщение отредактировал(а) TheVoid - 27.6.2009, 00:39

Если нет опыта проектов, то задача великовата для тебя. Это звучит примерно как, "А не написать ли мне роман "Война и мир" примерно как у Толстого?"

Поищи, в сети есть исходники готовых бесплатных компиляторов. Почитай, разберись. Сделай несколько простых проектов. Ну а потом уже...

ассемблер знаешь? если нет то тебе там делать нечего. а почему ANSI, а не C99?

Это сообщение отредактировал(а) DEADHUNT - 30.6.2009, 11:28

Нет, речь шла о совместных проектах.
Не спрашивал даже "а как же мне написать свой язык программирования". Опыт программирования имеется, чтобы не задавать таких вопросов.




Знание маш. кодов потребуется на поздних этапах компиляции - непосредственно, генерации кода. Чтобы не ударить лицом в грязь, изучаю книгу тов-ща Кипа Ирвина "Язык ассемблера для процессоров Интел".



Личные предпочтения.

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

Это сообщение отредактировал(а) DEADHUNT - 30.6.2009, 22:01

Начальный этап: препроцессирование, разбивка на токены, заполнение таблицы символов. Выходные данные: деревья или "четверки". Уже потом, оптимизация и, непосредственно, код.

Это сообщение отредактировал(а) TheVoid - 30.6.2009, 22:25

Завел собственный Блог, где буду делиться подробностями реализации компилятора. Комментарии приветствуются.
Надеюсь, кто-нибудь проявит интерес и отпишется...

Это сообщение отредактировал(а) TheVoid - 10.7.2009, 23:16

хорошо что всё такие есть люди которым интересно разрабатывать компилятор. похоже ты действительно ничего не понимаешь в построении компиляторов, поскольку сложность утверждений if, while, for практически одинаковая. а если думаешь потом писать компилятор C++ то в первую очередь задумайся о сканере, что бы решать разные не однозначности.

Это сообщение отредактировал(а) DEADHUNT - 12.7.2009, 17:14

Дополню.
Лучше начни писать не компилятор, а визуальную надстройку на компилятор. Для начала, чтобы логические блоки (if, for ...) были ограничены разноцветными областями.

Навыки программирования графики и особенно таких компиляторов в скором времени будут сильно востребованы.

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

Нет, я правда не профессионал на этом поприще. Я только учусь.



И что из этого утверждения следует? 



Нет, я не настолько псих   



Решим. Как только лбом упремся в это дело.


Не-а, это не входит в мои приоритеты.



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



А мне казалось, что идея Си - не сковывать программиста, а наоборот, позволить делать ему все, что только заблагорассудиться... Здесь до сих пор спорят о вкусах и личных предпочтениях? Мрак.

Ребят, меня правда не надо упрекать или критиковать (до фени мне это), если решите что-нибудь "по существу" (с) сказать, буду признателен за советы и помощь.

Это сообщение отредактировал(а) TheVoid - 12.7.2009, 18:40

в С нету не однозначностей, особенно по стандарту C99(где уже запретили default-int и соответственно конструкции вида main(){...}), значит отпадает необходимость в сканере с откатом. как разбор будет происходить? LL(k), LR(k) анализатор(или ещё что-то в этом духе) или рекурсивный спуск? как препроцессор будет работать? и вообще очень советую начинать конструирование компилятора начиная с первой страницы стандарта(много для себя откроешь! знаю по себе).

Это сообщение отредактировал(а) DEADHUNT - 12.7.2009, 19:07

Что есть «сканер»?

Лежит у меня на рабочем столе, только читаю редко, английский не настолько хорошо знаю.

О том, как будет все происходит я напишу в следующих статьях 

теория компиляции - один из базовых предметов любого инженера разработки ПО.
обычно компиляцию изучают после формальных языков и автоматов.
Желательно понимать как устроен современный компилятор.

Кроме этого для экспериментов есть несколько готовых инструментов лексического анализа, напр. flex (наследник lex-а) и синтактического анализа, как напр. Bison (наследник YaCC-а).

удачи.


Это сообщение отредактировал(а) bilbobagginz - 12.7.2009, 19:47

TheVoid > есть интересные идеи по новому очищенному диалекту Си. Вот некоторые из них:
 - точные типы данных (соответственно поддержка только стандартных архитектур);
 - модульная структура, соответственно отказ от include (чтобы не париться с include guard, не пересканировать тонны заголовков для каждого исходника);
 - сложный (возможно lisp-подобный) препроцессор (но как органичная часть языка), позволяющий вызывать собственные функции (написанные на этом же языке) во время компиляции;
 - пресловутый контроль на выход за пределы массива (возможно, с возможностью отказа от него для финальной сборки);
 - некоторые дополнительные возможности (включая, инициализация массивов переменной длины (чего нету в в старом распространённом Си-стандарте), анонимная инициализация массивов и структур, ...);

Самому нет времени этим заниматься (я болею не компиляторами, а распределёнными средами / ОС), но с удовольствием бы принял участие в обсуждении. Пока вынужден работать с Си, за неимением лучшей альтернативы... вот высказываю пожелания... 

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

Чем отличается от Java или C#?

Это сообщение отредактировал(а) beroal - 15.7.2009, 23:19

разработка уже свернулась?

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

интересно будет посмотреть как ты хотя бы препроцессор реализуешь.

А вы разрабатывали грамматики для С компилятора? Не в курсе где можно их посмотреть.   

а лучше С++

Это сообщение отредактировал(а) Killerman - 28.8.2009, 18:46

а по его исходникам не видно?
если невидно тогда - нет.

почему, всех так тянет писать именно компиляторы, что в этом интересного? лучше-бы вы написали интерпретатор языка С++, что-бы можно было использовать REPL(Read Eval Print Loop) во время написания кода  

интересно чем это лучше?

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

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

для этого есть typeid

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

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

А компилятор С++ я создавать не собираюсь, во всяком случае не для перевода на ассемблер и интерпритатор тоже, ну точно не для С++.

Добавлено через 5 минут и 36 секунд
2 DEADHUNT
И вообще не понимаю, как можно на основании исходников компилятора увидить его грамматику. Если его синтаксический анализатор строиться и работает на основе сгенерированных таблиц, помтроенных из грамматик генератором компиляторов. А из этих таблиц грамматику вытащить нереально.   

различают типы разборов(основные):
    рекурсивный спуск или детерминированный алгоритм низходящего разбора (как в данном случае),
    детерминированный алгоритм восходящего разбора,
    LL(k) анализатор,
    LR(k), LALR(k) анализаторы(можно сгенерировать с помощью lex + yacc).
только последние два используют "управляющие таблицы" которые создаются на основе грамматики.
     

Это сообщение отредактировал(а) DEADHUNT - 9.9.2009, 15:05

ну для С++ нужны 2-ва последних.

это кто тебе сказал? я например первый использую(g++ кстати тоже первый способ)

рекурсивный спуск (LL)? так оно токо для простеньких грамматик.

Добавлено через 1 минуту и 20 секунд
и возьни много. убирать левую рекурсию. Убирать е-правила.
А LR очень наглядно работает.

рекурсивный спуск(если не знаешь что такое посмотри в книжке) != LL(k)
по твоему кроме LL/LR анализаторов больше никак нельзя провести синтаксический анализ(и без всяких Эрли и Коко-Янгера-Косами(CYK))?

Я пользуюсь тем чем умею. LL мне не подходит.
О Эрли и Коко-Янгера-Косами(CYK) не слышал или не сшышал под таким названием. Это что, методы рекурсивного спуска? и без левой рекурсии??

А вот, нашел метод (CYK). Ну так тут грамматику нужно преобразоввывать к нормальной форме Хомского. Толку мне с нее потом.

Короче вопрос ушел от темы похоже.   


Это сообщение отредактировал(а) Killerman - 11.9.2009, 15:22

поэтому в gcc ничего этого не используется. рекурсивный спуск: http://en.wikipedia.org/wiki/Recursive_descent_parser

Это сообщение отредактировал(а) DEADHUNT - 11.9.2009, 15:59

и какой там метод?

а работы начались хотя бы ? или все разговоры затихли на теме рекурсии ?

Начались. Можно даже сказать, идут полным ходом. 
Блог не обновлялся длительное время, позже займусь этим. За одно опубликую исходники.

Это сообщение отредактировал(а) TheVoid - 18.9.2009, 11:27

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

вручную  , да и вообше front-end не самая сложная часть компилятора, намного сложнее сделать хорошо оптимизирующий back-end(basic-blocks, control flow graph, DJ graph, data-flow analysis, SSA, register interference graph,...).

Это сообщение отредактировал(а) DEADHUNT - 18.9.2009, 13:42

Так, сейчас читаю труды Свердлова - "Языки программирования и методы трансляции", интересно изложено, впитывается организмом лучше, чем Дракон 
Но у меня возникли трудности с грамматикой моего языка (не в смысле моего собственного, а того подмножества Си, что я выбрал) : не знаю, правильно ли набросал. Вот:



По идее, на текущем этапе заполняется таблица имен и создается ситаксическое дерево, которое я заменю четверками. Буду признателен за комментарии (а то я что-то ничего не спрашиваю, как-то молча все стряпаю и обижаюсь, что никому нет дела  )


Это сообщение отредактировал(а) TheVoid - 18.9.2009, 20:45

а семантических правил ещё нету?

Нет, к контекстному анализу еще не дошел. Вообще, раньше всегда обламывался с Таблицей имен - не знал, как правильно организовать.

К счастью, нашел отличную тулзу VisualBNF - она поможет решить вопросы с грамматикой. 

а в чём проблема, список не мог организовать(лучше hash таблицу)?

Это еще когда писал компилятор Паскаля на Делфи, чего-то там со вложенными процедурами не разобрался.
Ну, сейчас-то я примерно понимаю, как это должно выглядеть.

можно стэк списков.

Это сообщение отредактировал(а) DEADHUNT - 18.9.2009, 22:43

TheVoid, так для С++ есть стандартизированная грамматика (то о чем я спрашивал раньше), не надо ничего выдумывать.

DEADHUNT, как это вручную сделать компилятор? не понимаю. какими методами. через LR синтаксис вручную сделать нереально. а семантику можно и вручную.

Killerman, в учебных целях я занят реализацией ANSI C (см. первый пост). Логично, что 
 
сюда не катит.

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

реально, только вначале на листке надо будет составлять автоматные таблицы, а вообще я не говорил про LL/LR, я говорил про http://en.wikipedia.org/wiki/Recursive_descent_parser, не верится посмотри исходникики g++.

DEADHUNT, не знаю, там токо 2-ве строчки про этот метод:
A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.

и все.

LR для С++ вручную не получится, так как там таблица будет дето 3000 X 100. если не больше

Добавлено через 9 минут и 38 секунд
Хотя в принципеесли оптимизировать, может быть и 3000Х20. но это всеравно не для ручной работы

Это сообщение отредактировал(а) Killerman - 19.9.2009, 08:24

зато пример парсера есть.

ты хоть понимаешь что такое управляющая LR(1) таблица? строки состояния, столбцы входные аванцепочки. как ты собрался оптимизировать аванцепочки с 100 до 20?  

DEADHUNT, я понимаю.  имею некоторый опыт. там идет оптимизация терминалов.

TheVoid, все же С++, это не просто цыклы или там списки присвоений.
там гемора хватает. хотябы с шаблонами. а ты делаешь не С++ и даже не С.

написал бы - хочу создать свой функциональный язык. и все

Это сообщение отредактировал(а) Killerman - 19.9.2009, 20:45

терминалы нельзя оптимизировать. например терминалы a-z, A-Z как ты оптимизируешь, A-Z выкинешь? оптимизировать можно путём удаления эквивалентных состояний(у которых одинаковые "ядра" в LALR) и получить столько же состояний сколько в SLR анализаторе.

А что такое a-z, A-Z ? это не терминал никакой.

Добавлено через 32 секунды
вот почитай. полезная статья http://www.arbinada.com/main/node/54

Добавлено через 4 минуты и 13 секунд
кстати по этой ссылке http://en.wikipedia.org/wiki/Recursive_descent_parser написано:

Recursive descent parsers are particularly easy to implement in functional languages such as Haskell, Lisp or ML.

чето не вижу что оно такое же хорошее для сложный языков

A-Z - имелись ввиду как терминальные символы(из них идентификаторы состоят, просто для примера)
S -> aBcd
B -> Sa | e
в этой грамматике нетерминальные символы {S, B}, терминальные {a, c, d}

и вообще в том примере по этой же ссылке грамматика не леворекурсионная. в EBNF форме.
там такие приколы как:

S:= S+M не прокатят

Добавлено через 1 минуту и 50 секунд

ну здесь конечно никак.

это просто контекстно-свободная грамматика, только чтобы показать где терминалы, а где нетерминалы.

Ух, блин, что за дебаты.



Я написал вполне четко: вначале - подмножество Си, затем полный ANSI C.

где-то валялась эта старая книга ANSI C, с не слишким подробным описанием C. лучше C99 к тому же уже разрабатывают C99-1X

Руководствуюсь, в основном, K&R, хотя на полке пылится Шилдт со своим "Полным описанием С" (С99). Да нет, конечно, мне не претят новые веяния, обновленные стандарты и прочее, только хочу сейчас сосредоточиться на базовых вещах, я ведь учусь в первую очередь.

Это сообщение отредактировал(а) TheVoid - 20.9.2009, 11:42

я имел ввиду в электронном виде, C99 вообще-то здесь находится http://www.open-std.org/JTC1/SC22/WG14/

Это сообщение отредактировал(а) DEADHUNT - 20.9.2009, 00:02

DEADHUNT, пожалуйста, расскажите о семантических правилах - что это и куда привинчивается, желательно с абстрактным примером.

Книга-книгой, но а вдруг я что-то понял неправильно.

Это сообщение отредактировал(а) TheVoid - 20.9.2009, 11:44

приведи пример, в документации к yacc всё описано(много разных тонкостей).

Yacc-ом я не пользуюсь, все вручную.


По грамматике строится нисходящий синтаксический анализатор, народе





Хм... в общем-то я и не представляю, что делать дальше 

Это сообщение отредактировал(а) TheVoid - 20.9.2009, 12:59

тогда ты наверное год будешь LR списки высчитывать(чтобы таблицы Action, Goto затем построить), потом где нибудь ошибёшься, ну и дальнейшее расширение станет не возможным(надо будет поновой таблицу строить, оптимизировать, ...), ну и самое главное не выйдет у тебя анализатор.

вроде с умом начинал препроцессор делать, а теперь....

Добавлено через 1 минуту и 48 секунд

значит рекурсивный спуск(без использования LL/LR/... анализаторов), зачем только тогда грамматику составлять?

Возможно, я чего-то не понял, но... В смысле - зачем?
Для рекурсивного нисходящего парсера нужны правила, по которым будут строится "парсящие процедуры", по терминологии Википедии. Я смотрю на правила и по ним пишу соответствующие функции. 

типо того, только зачем их составлять если всё это описано в стандарте(в разделе grammar summary находятся полная грамматика)?

Грамматика подмножества != Полная грамматика

выбрасывай из полной грамматики что тебе надо.

Это сообщение отредактировал(а) DEADHUNT - 20.9.2009, 15:00

Итак, по упрощенной грамматике написал синтаксический анализатор. Текущее состояния сего чуда инженерной мысли - допуск /отказ входного файла. Причем, анализ поверхностный: имена переменных не вносятся в таблицу символов, соответственно, не проверяется, были ли они объявлены ранее или нет.
Меня интересует следующие: как прикрутить семантический анализ?

Вот, кое-что из исходного кода, посмотрите и скажите, насколько он плох:

у тебя даже нигде не идёт распознание типов(type specifier), так-что тебе и проверять нечего.

Чего-чего? Это к синтаксическому анализу вообще относится или к чему?

кто относится?

Понятно.
Короче говоря, вопрос решен, всем спасибо, все свободны.

а не увидел p_Type(), почему возвращает void? должна тип возвращать

О, а вот это другой вопрос. Функции-нетерминалы что-то должны возвращать и принимать, да?

причём здесь грамматика, сам уже думай где что должно возвращаться. просто при разборе decl_specifier тебе надо знать type_specifier(а ты его не знаешь). и вообше где у тебя структура которая описывает тип?

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

ты просто синтаксическую проверку делаешь(и то не правильно), а надо ещё информацию о типе собирать. про тип имеется:

Как правильно?

Пока что тип у меня вмещается в int, так как указателей, структур и прочего нет. Что есть:
TYPE_ERROR
TYPE_VOID
TYPE_UCHAR
TYPE_CHAR
TYPE_USHORT
TYPE_SHORT
TYPE_UINT
TYPE_INT
TYPE_FUNCTION

просто у тебя не допускается даже такой тип как:
long unsigned, ...
функция - тоже составной(сложный) тип, так как имеет возвращаемый тип, параметры, и дополнительные атрибуты.