Pull to refresh

Comments 67

Мб перенести в компиляторы? Статья отличная, все по феншую. Лексер, парсер, компилятор, машина. Вот бы такую статью да не третьем курсе прочитать.
Я на втором курсе написал компилятор подмножества Оберона-2 со стековой архитектурой процедур и функций за три вечера. Там же ничего сложного, но да, ЧСВ сильно поднимается, когда запускаешь решение задачи о Ханойских башнях на «своём» языке и оно работает.
Хм, странно, у нас компиляторы были обязательным предметом то ли на третьем, то ли на четвертом курсе. Вся группа что-то свое писала. Я думал, у всех это наряду с базами данных в обязательную ВУЗовскую программу входит.
Именно так, просто у нас это было на втором курсе.
И компактно :-)
На Java с нормальным полиморфизмом и отвязкой через интерфейсы у меня около 40 классов и интерфейов на вычислитель выражений уходило :-)
Супер! Кроме одного: зачем такое позиционирование, что «самый бесполезный» и «никому не нужный»?

Очень полезный! Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.
Стремление к этому подтолкнуло многих из нас стать разработчиками, программистами, электронщиками.
Но ведь пользы от самого компилятора (от использования) — никакой. Польза от написания/разбирания принципов работы/чтения исходников/модифицирования — да, это есть. Но это что ли косвенная польза. Хотя, конечно, пост писался именно ради нее.
Ну раз ради нее, то и цель достигнута, и польза совсем не косвенная :) Спасибо за отличную статью!
Косвенная польза зачастую является самой важной ;)
И вообще, категории косвенного и явного в жизни перепутаны, но это не меняет их сути:
«Но мы знаем, что о главном не пишут в газетах, и о главном молчит телеграф»(с)
Именно. Полностью согласен. Только этого не понимают те, кто кричат налево и направо «велосипед!».

Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.

В точку!
Небольшое замечание про lcc — это один из самых кривых компиляторов, которые я когда-либо видел с точки зрения понятности кода. Там не то, что без поллитра, там без ящика водки не разберёшься.

В общем, крайне не рекомендую для начинающих.
Да, видимо не зря они его книжкой дополняют
У меня было такое ощущение, что сорсы специально так написаны, чтобы без книжки было бы вообще ничего не понятно — чтобы книжка продавалась. Но и с книжкой там жесть и мракобесие.
Так, автор в статье писал о Tiny-C, TCC и LCC это как бы разные проекты. Я чего-то пропустил?
Статья полезная, но при написании более сложного компилятора, лучше посмотреть в сторону генераторов компиляторов.
само собой, просто я не мог понять что такое, скажем, ANTLR, пока не написал свой парсер вручную с нуля.
Не знаю насколько этот компилятор ненужный в прямом смысле (для компиляции) а вот косвенно мне он очень помог. (После прочтения пришла в голову одна интересная мысль которая до прочтения как-то даже не приходила в голову.)
Статья из жанра «делай как я» :)

Статья хорошая, но без теории на мой взгляд бесполезная.
Лексер (кажется) написан правильно, но нет ни слова про конечный автомат. Нет диаграммы состояний для грамматики.
Кстати, грамматика у вас правосторонняя или она просто не формализована?
А вообще судя по такому количеству голосов у статьи, похоже пора публиковать свой компилятор модифицированного HLL/0, который мы с другом писали на 4-м курсе ;)
Тема, видимо, актуальная.
Скорее не актуальная, а редкая. Материалов такого размаха (и простоты) на эту тему не так и много, причём все они либо слишком поверхностные (на которые даже новички не смогут ответить ничего кроме «спасибо кэп») либо наоборот сильно «заумные» (опытные программисты также разве что поблагодарят кэпа, а новички же не поймут ровным счётом ничего)

Если вы сможете подобрать правильный баланс (чтоб и новички поняли, и опытные хотя бы с умилением улыбнулись) то не исключаю что плюсов хапните даже больше.
А всё от того, что разработку компиляторов по обрывочным статьям не изучить. Книга дракона не зря написана, там уж профессионалы смогли скомпоновать материал так, чтобы можно было начать читать не зная даже что такое терминал.
Там не скомпоновали, а скорее упорядочили (от простого к сложному) но когда читаешь не книгу на 1000+ страниц, а коротенькую статью, то хочется чтоб было мало, но по делу. (Чтоб и просто, и с пользой, а не цитата из какой нибудь вики с припиской «остальное учите в институте»)
При описании граматики мне кажется вы путаете operator и statement. Это же две совершенно разные вещи.
Путаете не в том смысле что у неправильное или нелогичное описание, с этим вроде всё в порядке, а вот эти два термина используются нелогично, и даже в некоторых местах меняются между собой…
увы, есть некоторая путаница, просто statement на русском звучит как «оператор». Но, к сожалению от русского слова оператор в значении «оператор сложения» я тоже отказаться не смог. Потому да, несколько нелогично.
>увы, есть некоторая путаница, просто statement на русском звучит как «оператор»

Разве? А мне кажется statement на русском будет «выражение».
Я тоже так думал, но как тогда отличать expression и statement? В википедии статье statement соответствует статья «оператор».
В обращении редакции третьего русского издания Страуструпа «ЯП С++» к читателю, переводчики пишут, что statement они будут переводить как «инструкция», так как во-первых, такой перевод периодически встречается в литературе, и, во-вторых, для слова «оператор» Страуструп использовал слово «operator». Здесь конечно всё в контексте плюсов, но факт в том, что statement можно понимать и как инструкция :)
Выражение — Expression.
Statement — скорее конструкция или оператор (оператор цикла, условия).
В зависимости от контекста, да. Я подразумевал «выражение» в смысле «конструкция» :)
Понравилось. Еще интересно было бы почитать, как в подобных компилятора организовать замыкания, сборку мусора и другие современные штуки. Не планирует никто статью написать?
Вопрос не к компилятору, а скорее к виртуальной машине, под которую генерируется байт-код.
Давно мечтал написать компилятор, теперь появился еще один стимул это сделать. Спасибо за статью=)
В далекие времена, когда я учился на 1-м курсе решил устроиться на работу. В качестве тестового задания сказали написать свой интерпретатор языка Паскаль. Задача была сделана за 2 месяца, ту работу бросил, но кайф от получения такого опыта остался на всю жизнь.

Всем начинающим программистом в качестве проверки на вшивость — такая задачка — просто удовольствие!
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины
С формальной точки зрения, это не компиляция, а трансляция.
Рекомендую к прочтению «Книга Дракона-2» (Dragon Book-2) — «Компиляторы: принципы, технологии и инструменты», 2-е издание, Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман, 1184 стр., ISBN 978-5-8459-1349-4, «ВИЛЬЯМС», 2011

Это основная книга по теме разработки компиляторов
Спасибо, не знал что вышла вторая редакция.
Вот ещё интересная статья Питера Норвига о написании крохотного интерпретатора Scheme на Python. Это поможет заметить и понять общие концепции в создании трансляторов, благо код Норвига прост, понятен и мал по размеру.
Реализовали вы не компилятор, а интерпретатор (транслятор).
Перевод с одного языка на другой. Не более.
О боже, тогда javac ведь не компилятор!!11
Если серьёзно, то компилятор автора всего лишь не превращает инструкции с операндами в поток байтов, но это не делает его менее компилятором.
И вообще, «перевод с одного языка на другой»… А чем компиляторы, по-вашему, занимаются? То, что вы в своём ВУЗе реализуете подмножество x86 хардварно, ещё не делает вас спецом по теме трансляции, что прекрасно видно по вашему комментарию-придирке.
Между прочим, человек, с одной стороны, прав.

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

Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором.

С другой стороны, в той же книге дракона приводится такое определение:

Компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном, и транслирует (переводит) его в эквивалентный текст на другом языке — целевом.

Как можно видеть, определение компилятора из книги дракона эквивалентно определению транслятора, однако первые два определения транслятора и компилятора даны в соотв. с ГОСТ 19781-83.

Что касается языкового процессора Java, то в книге дракона про это также упомянуто: «Языковой процессор Java объединяет в себе и компиляцию, и интерпретацию. Исходная программа на Java может сначала компилироваться в промежуточный вид (байт-код). Затем байт-код интерпретируется виртуальной машиной.» И далее картинка, чтобы ещё больше всех запутать:



Пояснение можно найти на вики: «Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом интрепретируемом языке. Такой язык — байт-код (в случае с Java Java-байт-код) — также можно считать языком машинных команд, поскольку в качестве его интерпретатора используется виртуальная машина. Байт-код не является машинным кодом какого-либо компьютера, то есть машинным кодом в прямом смысле слова, и может переноситься на различные компьютерные архитектуры без перекомпиляции. Байт-код интерпретируется (исполняется) виртуальной машиной.»

Таким образом, дабы избежать взаимоисключающих параграфов, можно сказать, что:

1) Транслятор — программа или техническое средство, выполняющее преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
2) Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором, или в промежуточный код (байт-код Java, MSIL), предназначенный для дальнейшей интерпретации виртуальной машиной.

Однако это так я думал пару минут назад, пока не прочел это: «Важной исторической особенностью компилятора, отражённой в его названии (англ. compile — собирать вместе, составлять), являлось то, что он мог производить как трансляцию так и компоновку (то есть состоял из двух частей — транслятора и компоновщика). Это связано с тем, что раздельные трансляция и компоновка как отдельные фазы компиляции выделились значительно позже появления компиляторов. В связи с этим, вместо термина «компилятор» иногда используют термин «транслятор» как его синоним, что, правда, терминологически неправильно: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один).»

Таким образом получаем, что компилятор = транслятор + компоновщик. Хм. Истину ищите сами.

Одно могу сказать точно, интерпретатор != транслятор, как утверждает sig.
Минусуйте сколько хотите. Я «съел собаку» на теории компиляции и способен рассуждать на любую тему относительно данной дисциплины.
К тому же, помимо написания «компилятора» как вы его гордо называете, я писал микропрограммы для машинных команд, из которых формировалась целевая программа генератором кода. Эта программа в дальнейшем запускалась на виртульной СМ ЭВМ 85 годов.
upd:
И еще, «минусовщики», отписывайтесь в комментариях — народ должен знать вас в лицо.
Надеюсь, я буду единственным, чтобы не засорять более тему спорами. Для таких придирчивых, как вы, могу пояснить, что я имел ввиду не грибные споры, а разговорные.
Так вот, всё это замечательно, что вы вот такой крутой и писали микрокоманды, но вот какого лешего вы прицепились к автору топика? Даже не поблагодарили за хороший пост после этого. В посте ставилась задача — написать простой компилятор и уложиться в разумный объём. Задача выполнена. ОК, может, автор применил слегка неправильную терминологию. Но вот это ваше презрительное «не более» совершенно неуместно. Пока всё выглядит так, словно съеденная вами собака сбежала с кафедры терминологии и демагогии.
У вас уже выборы начались, что вы так яростно мне крестики ставите возле моих постов?
Компилятор это и есть переводчик с одного языка на другой.
Спасибо за стаатью. Почитал вчера вечером за чашечкой кофе ваше творение. То, что было нужно.
Автору респект не только за статью но и за ее позиционирование! Действительно от компилятора в прямом смысле толку мало, но именно для того, чтобы понять как все устроено и надо писать свои велосипеды. Я написал свой компилятор-транслятор на 5 курсе. Осталось подсадить дерево и вырастить сына.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки.
Простые смертные студенты специальности «программное обеспечение вычислительной техники и автоматизированных систем» постигают и осиливают написание компилера си-лайт на 4ом курсе.
Тут всё зависит от уровня преподов и студентов. Например, я учил преподов программированию, а не они — меня. Какие уж тут компиляторы. У вас было лучше, рад за вас (честно).
У меня есть идеи по реализации custom процессора в FPGA, есть ли кто-нибудь кому интересно реализовать компилятор под него? just for fun, естественно…
> Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

Напишите отладчик. Вот это уже действительно challenge ;)
Таки на карму-рейтинги мне всё равно, но если проминусовавший будет пробегать, попрошу аргументировать точку зрения, по поводу дебаггеров.
Вы так «аппетитно» написали, что мне захотелось тоже написать компилятор (на основе Вашего, но на LabVIEW). И это может получиться забавно — компилятор текстового языка на языке графическом.
>Это, наверное, самый сложный компонент нашего компилятора

В Real-World компиляторах, кстати, как правило — самый простой(не парсер конкретно, а вообще, часть, отвечающая за разбор).

Про грамматику надо было сказать. Грамматика, вроде бы, сводится к LL(1), значит надо было этот момент объяснить, переписать её соответствующим образом, и в коде сделать нормальный предикативный анализатор, а не какое-то его ad-hoc подобие, как сейчас.

Кстати, настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.
>предикативный
«предиктивный», всмысле

в 3 ночи голова не работает :)
> настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.

А оптимизации?
ну для высокоуровневых оптимизаций лучше подходит какое-то внутреннее представление типа flow graph
Еще про грамматики можно пару слов, какие бывают и в чём различия?

[i]сейчас начал читать TAPL, до книги дракона не добирался еще.[/i]
А в TAPL разве есть про компиляторы?

Грамматики бывают разные, но если говорить про контекстно-свободные, то LL(k) грамматики это такие, для которых можно построить LL(k) анализатор, то есть парсер, разбирающий токены слева направо(первая L) сверху вних и строящий левый вывод(вторая L), заглядывающий вперед на k токенов, и, соответственно, работающий за линейное время и не требующий бэктрекинга. LL(1) парсер это, например, рекурсивно нисходящий предиктивный парсер, или аналогичный автомат со стеком.

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

LL(1) грамматика не допускает левой рекурсии, так как это означает бесконечный цикл в анализаторе, и, кроме того, к правильной LL(1) грамматике должен быть применен left-factoring.

Пример, LL(1) для классических S-выражений:

expression -> STRING
              | SYMBOL
              | NUMBER
              | QUOTE expression
              | LEFT_PAREN parenExpression

parenExpression -> RIGHT_PAREN
                   | expression restParenExpression

restParenExpression -> RIGHT_PAREN
                       | DOT expression RIGHT_PAREN
                       | expression restParenExpression



Спасибо за ответ, внесу в закладки.

В TAPL про компиляторы ничего толком пока нету, он весь про типы. Но чтобы писать свои компиляторы и проводить ресёрчи в области ЯП необходимо знать основы, имхо.
От чего же «примитивный и никому не нужный компилятор», следующим шагом в изучении можно и переписать его код на TinyC сделав его самодостаточным.
Only those users with full accounts are able to leave comments. Log in, please.