Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 56
Меня побьют если я напомню про картинку с совой?
Напомните, я точно не побью :)
ну и не в курсе такой каринки
ну и не в курсе такой каринки
deleted
День 15. Я далеко продвинулся в реализации компилятора и он работает на удивление хорошо. Нетривиальные программы, например эта — решающая задачу о восьми ферзях, компилируются и запускаются.
За пятнадцать дней. Воистину суровые люди работают в google. Впрочем, судя по записям, автор использовал готовые решения.
Буду утешать себя тем, что автор, скорее всего, использовал уже готовый компилятор…
И при этом он все рано пишет, что «Фабрис Беллар, создатель ТСС, — гений», а он, значит, так — балуется просто)
что касается готового компилятора, то как минимум парсер он писал сам. В комментарии к этому дневнику он пишет что сейчас не стал бы заморачиваться и использовал бы yacc
что касается готового компилятора, то как минимум парсер он писал сам. В комментарии к этому дневнику он пишет что сейчас не стал бы заморачиваться и использовал бы yacc
Почитал немного код на гите. Он делает разбор с закосом под функциональные языки… Между прочим, я вот подумал — не так уж это и страшно, если в соответствие каждому из элементов языка ставится функция, выполняющая разбор этого элемента и через все эти вызовы пробрасывается структура для генерации AST.
Прочитал ваш комментарий и задумался: а как иначе-то можно? Я только с «закосом под функциональные языки» парсеры и пишу.
Я думаю, что автор просто пишет компилятор не первый раз в жизни, и видимо неплохо знаком с ассемблером. Написать компилятор для примитивного языка похожего на C не так уж сложно – всего-то нужно реализовать токенизатор+парсер и транслятор без каких-либо оптимизаций. Если вы уже знакомы с принципами реализации парсеров и неплохо знаете ассемблер, то это будет скорее монотонная работа. Таинством это воспринимается только до первого раза. :)
Я думаю, что автор просто пишет компилятор не первый раз в жизни, и видимо неплохо знаком с ассемблером. Написать компилятор для примитивного языка похожего на C не так уж сложно – всего-то нужно реализовать токенизатор+парсер и транслятор без каких-либо оптимизаций. Если вы уже знакомы с принципами реализации парсеров и неплохо знаете ассемблер, то это будет скорее монотонная работа. Таинством это воспринимается только до первого раза. :)
Прочитал ваш комментарий и задумался: а как иначе-то можно?
Я написал генератор парсеров на основе недетерменированного конечного автомата (на самом деле даже нечто ещё более навороченное — уже третий месяц никак не добью статью на хабру по этой тему). На эту тему много публикаций на хабре есть.
На самом деле, функциональный подход к разбору, как я понимаю, сводится к записи структуры всё того же автомата, просто в виде вызовов функций.
это будет скорее монотонная работа
Да, монотонность работы часто наблюдается пока идет описание грамматики и начальное её покрытие реализацией парсера\компилятора\интерпретатора\генератора\….
Типа, как в этом дневнике — скукотища: вот первая 1000 строк, вот вторая… ага, вот свет в конце тоннеля уже виден… и, наконец, 100% покрытие спецификации языка.
Но, когда такая рутинная работа завершена и наступает фаза полномасштабных испытаний, неожиданно начинают выявляться «чудеса-чудесные».
И вроде грамматику описал в точном соответствии со спецификацией языка и кусочки реализации четко подгонял, чтобы они правильно отрабатывали в любом порядке для любого исходного текста на входе…
но, нет… и в описании грамматики и в реализации начинают проявляться самые неожиданные блохи…
и вот тут начинается настоящее творчество…
А, реализация хорошей обработки некорректного исходного текста это вообще всегда очень нетривиальная задача.
Разработчику попроще, если разрабатывается реализация для какго-нибудь «известного и стабильного» языка, а если ещё и язык новый, то точно о монотонности и не вспомните даже на начальном этапе. Особенно на фоне «живой» спецификации языка.
Не преувеличивайте. Где суровость-то? Времени у него много, вот что. :-)
читается как роман
Я не уловил мотивов движущих этой разработкой. Известно, что настоящий программист должен написать себе редактор, даже мой редактор правлен под меня на уровне ядра кода. А что, настоящий_настоящий программист должен раз в жизни написать себе компилятор?
Простите, а можно где-то посмотреть список вещей, которые должен сделать настоящий программист?)
Разумеется можно))
- Посадить дерево
- ...etc
Не удержусь… здесь
И эта ссылка есть в статье
И эта ссылка есть в статье
Во-первых это интересно, какие ещё мотивы вам нужны?
Интересно — это веский мотив, но он не приведен ни в дневнике, ни в Readme на github. Отсюда освистанный вопрос.
Есть в HACKING.md:
I accept small patches, but because this is my hobby project to learn about compilers, it's unlikely to accept large patches.
А что, настоящий_настоящий программист должен раз в жизни написать себе компилятор?
Это обычное задание ВУЗовского курса «теория языков программирования и трансляции». Реализация компилятора/транслятора для некоего простого языка программирования.
Тут явно что-то не так:
в оригинале:
Тут используется понятие «стековая машина» (stack machine), про которые пишут немного тут, например. Виртуальная машина Java, например, стековая машина. Поэтому фразу лучше перевести как "Он компилирует исходные программы в код стековой машины, которая использует системный стек в качестве стека" (или вроде того).
Он компилирует программы на стеке, используя стек машины как стек
в оригинале:
It compiles source programs onto a stack machine that uses the machine stack as the stack
Тут используется понятие «стековая машина» (stack machine), про которые пишут немного тут, например. Виртуальная машина Java, например, стековая машина. Поэтому фразу лучше перевести как "Он компилирует исходные программы в код стековой машины, которая использует системный стек в качестве стека" (или вроде того).
По законам жанра Andrey2008 должен написать про это статью ;)
Фабрис Беллар — голова, это да. За формат BPG по крайней мере. За 40 дней соорудить компилирующий сам себя код — достижение разве что для студента.
А вы, видимо, можете похвастаться и не такими успехами в области компиляторов и программирования? Если для вас компилятор для С за 40+ дней это «достижение для студента», то можно ли увидеть ваши достижения?
Лет 20 назад мог бы аналогичный «дневник» опубликовать, «как я написал yacc за 40 дней». К сожалению не мог тогда предвидеть, что вдруг потребуется предъявлять доказательства крутизны, поэтому сырцы для вас не сохранил. :)
Подобные парсеры это реально студенческий уровень, вот вам весь Си на 2х страницах: http://www.quut.com/c/ANSI-C-grammar-y.html
Подобные парсеры это реально студенческий уровень, вот вам весь Си на 2х страницах: http://www.quut.com/c/ANSI-C-grammar-y.html
вот вам весь Си на 2х страницах
Так там только грамматика — без собственно компилятора.
О том и речь — грамматика мала. Например, в БНФ нотации ANSI C занимает 300 строк, Паскаль — 192, Delphi 7(Object Pascal) — 1006.
Язык — это не только грамматика. Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода. В общем, работы много и эта работа требует довольно обширных знаний: надо знать ABI, знать алгоритмы оптимизации. Да хотя бы ту же спецификацию C надо знать, а она побольше двух страниц. Может, эта работа и не сильно сложная, если знать, как её сделать, но довольно объёмная. И то, что автор уложился в 40 дней характеризует его как человека, который может быстро писать много кода и потом не утонуть в нём.
Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода
Вы почитайте, как это сделано в данном компиляторе — на самом простом уровне.
И то, что автор уложился в 40 дней характеризует его как человека, который может быстро писать много кода и потом не утонуть в нём.
Автор уложился в 40 дней реализуя подмножество без оптимизации.
Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода.Вы статью-то вообще читали? Там нет никаких оптимизация, а семантика и кодогенерация слиты в одну сущность. Нечто вроде Turbo Pascal'я, хотя, скорее всего, ещё примитивнее.
надо знать ABI,Какой ABI? Вы о чём?
знать алгоритмы оптимизации.Нет там оптимизации. От слова «совсем». Даже структур, которые обычно используются оптимизаторами нет. Совсем.
Да хотя бы ту же спецификацию C надо знать, а она побольше двух страниц.Для чего её нужно знать? Чтобы потом не реализоывать? На 40й день компилятор компилировал только сам себя! На 73й он отказался от идеи довести компилятор «до ума» и научить его компилировать хотя бы TCC!
Прочитайте же наконец статью!
А вы прочитайте мой комментарий. Я пишу о том, что язык — это не только грамматика и далее по тексту. То есть о том, что по объёму грамматики судить о сложности языка некорректно. А также о том, что нужно всё же иметь какие-то знания, чтобы писать трансляторы.
Да, я знаю, что там нет оптимизаций, так как об этом написано на страничке его проекта на GitHub. Я упомянул оптимизации как пример элемента, не относящегося к грамматике, для иллюстрации сложностей, скрывающихся за её пределами.
Я о двоичном интерфейсе приложений. Конечно, если реализовывать сферический язык в вакууме, то он не нужен. В частности, автор упоминает AMD64 ABI в дневнике и ссылается на него на страничке на GitHub.
Верно, нет. Я и не пишу, что она там есть. Я лишь пишу, что для реализации языка программирования она пригодилась бы. Согласны?
Чтобы реализовать какой-то язык, нужно знать спецификацию. Не так ли? Ещё раз напомню, что в первых предложениях говорится о трансляции вообще, так как комментарий, на который я отвечал, расширил контекст обсуждения.
На 40-й день у него было несколько тысяч строк покрытого тестами кода работающего транслятора, который успешно работал с подмножеством языка C. По-моему, для домашнего проекта довольно неплохо и хорошо характеризует автора, о чём я и написал.
Может, конечно, я и непонятно выразился в чём-то, но к чему такой эмоциональный ответ?
Там нет никаких оптимизация, а семантика и кодогенерация слиты в одну сущность. Нечто вроде Turbo Pascal'я, хотя, скорее всего, ещё примитивнее.
Да, я знаю, что там нет оптимизаций, так как об этом написано на страничке его проекта на GitHub. Я упомянул оптимизации как пример элемента, не относящегося к грамматике, для иллюстрации сложностей, скрывающихся за её пределами.
Какой ABI? Вы о чём?
Я о двоичном интерфейсе приложений. Конечно, если реализовывать сферический язык в вакууме, то он не нужен. В частности, автор упоминает AMD64 ABI в дневнике и ссылается на него на страничке на GitHub.
Нет там оптимизации. От слова «совсем». Даже структур, которые обычно используются оптимизаторами нет. Совсем.
Верно, нет. Я и не пишу, что она там есть. Я лишь пишу, что для реализации языка программирования она пригодилась бы. Согласны?
Для чего её нужно знать? Чтобы потом не реализоывать?
Чтобы реализовать какой-то язык, нужно знать спецификацию. Не так ли? Ещё раз напомню, что в первых предложениях говорится о трансляции вообще, так как комментарий, на который я отвечал, расширил контекст обсуждения.
На 40й день компилятор компилировал только сам себя! На 73й он отказался от идеи довести компилятор «до ума» и научить его компилировать хотя бы TCC!
На 40-й день у него было несколько тысяч строк покрытого тестами кода работающего транслятора, который успешно работал с подмножеством языка C. По-моему, для домашнего проекта довольно неплохо и хорошо характеризует автора, о чём я и написал.
Может, конечно, я и непонятно выразился в чём-то, но к чему такой эмоциональный ответ?
Это действительно не так сложно. Я сам писал транслятор (на прямых методах) и виртуальную полу-стековую машину для языка программирования, который используется у нас внутри компании. Не 40 дней, что-то около 45-50. С возможжностью подстройки под разные платформы, встраивание, разрешение связей при загрузке.
Но согласитесь, что это объёмная работа. Я тоже писал компилятор (вернее транслятор в язык ассемблера для x86). Когда знаешь алгоритмы и под рукой есть книжка с драконом, это в самом деле не rocket science, но я помню, убил на него много времени. Точно не помню, но тоже месяца полтора, если не ошибаюсь. При этом язык был проще C.
Работа большая, но если учитывать, что уровень реализации — простой (без оптимизаций, все в одном модуле, без промежуточных представлений и т.д.), то ореол серьезности, который окружает написание транслятора, несколько ярче, чем сама работа. Особенно для тех, кто никогда подобного не делал. Если есть хорошая спецификация языка, и ты его знаешь, то алгоритмы разрабатываются быстро. Если задаться целью строить не академический табличный транслятор, то и того проще.
И без такой книжки можно обойтись. В свое время мне хватило «Трансляции ЯП» Вайнгартена лохматого 77 года.
Когда знаешь алгоритмы и под рукой есть книжка с драконом, это в самом деле не rocket science, но я помню, убил на него много времени
И без такой книжки можно обойтись. В свое время мне хватило «Трансляции ЯП» Вайнгартена лохматого 77 года.
ореол серьезности, который окружает написание транслятора, несколько ярче, чем сама работа
Это да. «Ты придумал свой язык?! Круто!»
Если задаться целью строить не академический табличный транслятор, то и того проще.
Ну да, скормил тому же ANTLR описание своего DSL, и всего делов. Полчаса на что-то не сильно сложное, если грамматика готовая есть. Но тогда и статьи не получилось бы. :)
Не знаю, как вам, а мне этот дневник было интересно читать, так как я когда-то сам через что-то похожее проходил.
Не знаю, как вам, а мне этот дневник было интересно читать, так как я когда-то сам через что-то похожее проходил.
Мне тоже. Когда-то мой транслятор вырос из expression evaluator'а, который был необходим, чтобы на лету делать кое-какие вычисления. Потом возникла мысль дописать и остальное поверх той же ВМ, которая реализовала выполненный парсинг выражений, потому что после разборки выражений последовательное выполнение операторов реализовывалось легко, не считая мелочей вида непредопределенных на данный момент меток/функций, которые появятся только там, внизу.
Только если это суровый челябинский студент.
Или финский. Не забывайте чем себя небезызвестный Линус развлекал.
А компиляторы… какой-нибудь Форт примитивный пишется за неделю (как и здесь: некоторое самокомпилирующееся подмножество, не полный ANS FORTH, конечно), а данный компилятор не сильно далеко от него ушёл: та же самая стековая машина, прямая компиляция без промежуточных представлений… когда-то подобные вещи люди вообще на бумажке писали и сразу в машинный код переводили… конечно это было до появления таких сложных языков как C…
А компиляторы… какой-нибудь Форт примитивный пишется за неделю (как и здесь: некоторое самокомпилирующееся подмножество, не полный ANS FORTH, конечно), а данный компилятор не сильно далеко от него ушёл: та же самая стековая машина, прямая компиляция без промежуточных представлений… когда-то подобные вещи люди вообще на бумажке писали и сразу в машинный код переводили… конечно это было до появления таких сложных языков как C…
Еще стоит учесть, что не полноценный (с полным покрытием синтаксиса) компилятор за 40 дней был написан, а такой, который мог сам себя транслировать. Т.е. если мы используем некоторый ограниченный набор инструкций при кодировании компилятора (не считая ряда заголовочных файлов), то задача упрощается.
захватывающее повествование, даже интересней чем про катю криптовалютчика.
Судя по фразе «В любом случае я должен признать, что я человек с большим количеством свободного времени», это рассказ из серии «как я провёл отпуск».
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я написал компилятор C за 40 дней