Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 68
Мб перенести в компиляторы? Статья отличная, все по феншую. Лексер, парсер, компилятор, машина. Вот бы такую статью да не третьем курсе прочитать.
Я на втором курсе написал компилятор подмножества Оберона-2 со стековой архитектурой процедур и функций за три вечера. Там же ничего сложного, но да, ЧСВ сильно поднимается, когда запускаешь решение задачи о Ханойских башнях на «своём» языке и оно работает.
Ну, не всё по феншую, зато всё понятно.
Супер! Кроме одного: зачем такое позиционирование, что «самый бесполезный» и «никому не нужный»?
Очень полезный! Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.
Стремление к этому подтолкнуло многих из нас стать разработчиками, программистами, электронщиками.
Очень полезный! Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.
Стремление к этому подтолкнуло многих из нас стать разработчиками, программистами, электронщиками.
Но ведь пользы от самого компилятора (от использования) — никакой. Польза от написания/разбирания принципов работы/чтения исходников/модифицирования — да, это есть. Но это что ли косвенная польза. Хотя, конечно, пост писался именно ради нее.
Ну раз ради нее, то и цель достигнута, и польза совсем не косвенная :) Спасибо за отличную статью!
Косвенная польза зачастую является самой важной ;)
И вообще, категории косвенного и явного в жизни перепутаны, но это не меняет их сути:
«Но мы знаем, что о главном не пишут в газетах, и о главном молчит телеграф»(с)
И вообще, категории косвенного и явного в жизни перепутаны, но это не меняет их сути:
«Но мы знаем, что о главном не пишут в газетах, и о главном молчит телеграф»(с)
Именно. Полностью согласен. Только этого не понимают те, кто кричат налево и направо «велосипед!».
В точку!
Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.
В точку!
Небольшое замечание про lcc — это один из самых кривых компиляторов, которые я когда-либо видел с точки зрения понятности кода. Там не то, что без поллитра, там без ящика водки не разберёшься.
В общем, крайне не рекомендую для начинающих.
В общем, крайне не рекомендую для начинающих.
Статья полезная, но при написании более сложного компилятора, лучше посмотреть в сторону генераторов компиляторов.
Не знаю насколько этот компилятор ненужный в прямом смысле (для компиляции) а вот косвенно мне он очень помог. (После прочтения пришла в голову одна интересная мысль которая до прочтения как-то даже не приходила в голову.)
Статья из жанра «делай как я» :)
Статья хорошая, но без теории на мой взгляд бесполезная.
Лексер (кажется) написан правильно, но нет ни слова про конечный автомат. Нет диаграммы состояний для грамматики.
Кстати, грамматика у вас правосторонняя или она просто не формализована?
Статья хорошая, но без теории на мой взгляд бесполезная.
Лексер (кажется) написан правильно, но нет ни слова про конечный автомат. Нет диаграммы состояний для грамматики.
Кстати, грамматика у вас правосторонняя или она просто не формализована?
А вообще судя по такому количеству голосов у статьи, похоже пора публиковать свой компилятор модифицированного HLL/0, который мы с другом писали на 4-м курсе ;)
Тема, видимо, актуальная.
Тема, видимо, актуальная.
Скорее не актуальная, а редкая. Материалов такого размаха (и простоты) на эту тему не так и много, причём все они либо слишком поверхностные (на которые даже новички не смогут ответить ничего кроме «спасибо кэп») либо наоборот сильно «заумные» (опытные программисты также разве что поблагодарят кэпа, а новички же не поймут ровным счётом ничего)
Если вы сможете подобрать правильный баланс (чтоб и новички поняли, и опытные хотя бы с умилением улыбнулись) то не исключаю что плюсов хапните даже больше.
Если вы сможете подобрать правильный баланс (чтоб и новички поняли, и опытные хотя бы с умилением улыбнулись) то не исключаю что плюсов хапните даже больше.
При описании граматики мне кажется вы путаете operator и statement. Это же две совершенно разные вещи.
Путаете не в том смысле что у неправильное или нелогичное описание, с этим вроде всё в порядке, а вот эти два термина используются нелогично, и даже в некоторых местах меняются между собой…
Путаете не в том смысле что у неправильное или нелогичное описание, с этим вроде всё в порядке, а вот эти два термина используются нелогично, и даже в некоторых местах меняются между собой…
увы, есть некоторая путаница, просто statement на русском звучит как «оператор». Но, к сожалению от русского слова оператор в значении «оператор сложения» я тоже отказаться не смог. Потому да, несколько нелогично.
>увы, есть некоторая путаница, просто statement на русском звучит как «оператор»
Разве? А мне кажется statement на русском будет «выражение».
Разве? А мне кажется statement на русском будет «выражение».
Я тоже так думал, но как тогда отличать expression и statement? В википедии статье statement соответствует статья «оператор».
В обращении редакции третьего русского издания Страуструпа «ЯП С++» к читателю, переводчики пишут, что statement они будут переводить как «инструкция», так как во-первых, такой перевод периодически встречается в литературе, и, во-вторых, для слова «оператор» Страуструп использовал слово «operator». Здесь конечно всё в контексте плюсов, но факт в том, что statement можно понимать и как инструкция :)
Выражение — Expression.
Statement — скорее конструкция или оператор (оператор цикла, условия).
Statement — скорее конструкция или оператор (оператор цикла, условия).
Понравилось. Еще интересно было бы почитать, как в подобных компилятора организовать замыкания, сборку мусора и другие современные штуки. Не планирует никто статью написать?
Давно мечтал написать компилятор, теперь появился еще один стимул это сделать. Спасибо за статью=)
В далекие времена, когда я учился на 1-м курсе решил устроиться на работу. В качестве тестового задания сказали написать свой интерпретатор языка Паскаль. Задача была сделана за 2 месяца, ту работу бросил, но кайф от получения такого опыта остался на всю жизнь.
Всем начинающим программистом в качестве проверки на вшивость — такая задачка — просто удовольствие!
Всем начинающим программистом в качестве проверки на вшивость — такая задачка — просто удовольствие!
Вот кстати, кому интересно напомню ссылку на потрясающий, на мой взгляд, цикл лекций на эту тему
habrahabr.ru/blogs/programming/99162/
habrahabr.ru/blogs/programming/99162/
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машиныС формальной точки зрения, это не компиляция, а трансляция.
Рекомендую к прочтению «Книга Дракона-2» (Dragon Book-2) — «Компиляторы: принципы, технологии и инструменты», 2-е издание, Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман, 1184 стр., ISBN 978-5-8459-1349-4, «ВИЛЬЯМС», 2011
Это основная книга по теме разработки компиляторов
Это основная книга по теме разработки компиляторов
Вот ещё интересная статья Питера Норвига о написании крохотного интерпретатора Scheme на Python. Это поможет заметить и понять общие концепции в создании трансляторов, благо код Норвига прост, понятен и мал по размеру.
Реализовали вы не компилятор, а интерпретатор (транслятор).
Перевод с одного языка на другой. Не более.
Перевод с одного языка на другой. Не более.
О боже, тогда javac ведь не компилятор!!11
Если серьёзно, то компилятор автора всего лишь не превращает инструкции с операндами в поток байтов, но это не делает его менее компилятором.
И вообще, «перевод с одного языка на другой»… А чем компиляторы, по-вашему, занимаются? То, что вы в своём ВУЗе реализуете подмножество x86 хардварно, ещё не делает вас спецом по теме трансляции, что прекрасно видно по вашему комментарию-придирке.
Если серьёзно, то компилятор автора всего лишь не превращает инструкции с операндами в поток байтов, но это не делает его менее компилятором.
И вообще, «перевод с одного языка на другой»… А чем компиляторы, по-вашему, занимаются? То, что вы в своём ВУЗе реализуете подмножество x86 хардварно, ещё не делает вас спецом по теме трансляции, что прекрасно видно по вашему комментарию-придирке.
Между прочим, человек, с одной стороны, прав.
Транслятор — программа или техническое средство, выполняющее трансляцию программы, т.е. преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором.
С другой стороны, в той же книге дракона приводится такое определение:
Компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном, и транслирует (переводит) его в эквивалентный текст на другом языке — целевом.
Как можно видеть, определение компилятора из книги дракона эквивалентно определению транслятора, однако первые два определения транслятора и компилятора даны в соотв. с ГОСТ 19781-83.
Что касается языкового процессора Java, то в книге дракона про это также упомянуто: «Языковой процессор Java объединяет в себе и компиляцию, и интерпретацию. Исходная программа на Java может сначала компилироваться в промежуточный вид (байт-код). Затем байт-код интерпретируется виртуальной машиной.» И далее картинка, чтобы ещё больше всех запутать:
Пояснение можно найти на вики: «Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом интрепретируемом языке. Такой язык — байт-код (в случае с Java Java-байт-код) — также можно считать языком машинных команд, поскольку в качестве его интерпретатора используется виртуальная машина. Байт-код не является машинным кодом какого-либо компьютера, то есть машинным кодом в прямом смысле слова, и может переноситься на различные компьютерные архитектуры без перекомпиляции. Байт-код интерпретируется (исполняется) виртуальной машиной.»
Таким образом, дабы избежать взаимоисключающих параграфов, можно сказать, что:
1) Транслятор — программа или техническое средство, выполняющее преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
2) Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором, или в промежуточный код (байт-код Java, MSIL), предназначенный для дальнейшей интерпретации виртуальной машиной.
Однако это так я думал пару минут назад, пока не прочел это: «Важной исторической особенностью компилятора, отражённой в его названии (англ. compile — собирать вместе, составлять), являлось то, что он мог производить как трансляцию так и компоновку (то есть состоял из двух частей — транслятора и компоновщика). Это связано с тем, что раздельные трансляция и компоновка как отдельные фазы компиляции выделились значительно позже появления компиляторов. В связи с этим, вместо термина «компилятор» иногда используют термин «транслятор» как его синоним, что, правда, терминологически неправильно: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один).»
Таким образом получаем, что компилятор = транслятор + компоновщик. Хм. Истину ищите сами.
Одно могу сказать точно, интерпретатор != транслятор, как утверждает sig.
Транслятор — программа или техническое средство, выполняющее трансляцию программы, т.е. преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором.
С другой стороны, в той же книге дракона приводится такое определение:
Компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном, и транслирует (переводит) его в эквивалентный текст на другом языке — целевом.
Как можно видеть, определение компилятора из книги дракона эквивалентно определению транслятора, однако первые два определения транслятора и компилятора даны в соотв. с ГОСТ 19781-83.
Что касается языкового процессора Java, то в книге дракона про это также упомянуто: «Языковой процессор Java объединяет в себе и компиляцию, и интерпретацию. Исходная программа на Java может сначала компилироваться в промежуточный вид (байт-код). Затем байт-код интерпретируется виртуальной машиной.» И далее картинка, чтобы ещё больше всех запутать:
Пояснение можно найти на вики: «Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом интрепретируемом языке. Такой язык — байт-код (в случае с Java Java-байт-код) — также можно считать языком машинных команд, поскольку в качестве его интерпретатора используется виртуальная машина. Байт-код не является машинным кодом какого-либо компьютера, то есть машинным кодом в прямом смысле слова, и может переноситься на различные компьютерные архитектуры без перекомпиляции. Байт-код интерпретируется (исполняется) виртуальной машиной.»
Таким образом, дабы избежать взаимоисключающих параграфов, можно сказать, что:
1) Транслятор — программа или техническое средство, выполняющее преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
2) Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором, или в промежуточный код (байт-код Java, MSIL), предназначенный для дальнейшей интерпретации виртуальной машиной.
Однако это так я думал пару минут назад, пока не прочел это: «Важной исторической особенностью компилятора, отражённой в его названии (англ. compile — собирать вместе, составлять), являлось то, что он мог производить как трансляцию так и компоновку (то есть состоял из двух частей — транслятора и компоновщика). Это связано с тем, что раздельные трансляция и компоновка как отдельные фазы компиляции выделились значительно позже появления компиляторов. В связи с этим, вместо термина «компилятор» иногда используют термин «транслятор» как его синоним, что, правда, терминологически неправильно: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один).»
Таким образом получаем, что компилятор = транслятор + компоновщик. Хм. Истину ищите сами.
Одно могу сказать точно, интерпретатор != транслятор, как утверждает sig.
Минусуйте сколько хотите. Я «съел собаку» на теории компиляции и способен рассуждать на любую тему относительно данной дисциплины.
К тому же, помимо написания «компилятора» как вы его гордо называете, я писал микропрограммы для машинных команд, из которых формировалась целевая программа генератором кода. Эта программа в дальнейшем запускалась на виртульной СМ ЭВМ 85 годов.
upd:
И еще, «минусовщики», отписывайтесь в комментариях — народ должен знать вас в лицо.
К тому же, помимо написания «компилятора» как вы его гордо называете, я писал микропрограммы для машинных команд, из которых формировалась целевая программа генератором кода. Эта программа в дальнейшем запускалась на виртульной СМ ЭВМ 85 годов.
upd:
И еще, «минусовщики», отписывайтесь в комментариях — народ должен знать вас в лицо.
Надеюсь, я буду единственным, чтобы не засорять более тему спорами. Для таких придирчивых, как вы, могу пояснить, что я имел ввиду не грибные споры, а разговорные.
Так вот, всё это замечательно, что вы вот такой крутой и писали микрокоманды, но вот какого лешего вы прицепились к автору топика? Даже не поблагодарили за хороший пост после этого. В посте ставилась задача — написать простой компилятор и уложиться в разумный объём. Задача выполнена. ОК, может, автор применил слегка неправильную терминологию. Но вот это ваше презрительное «не более» совершенно неуместно. Пока всё выглядит так, словно съеденная вами собака сбежала с кафедры терминологии и демагогии.
Так вот, всё это замечательно, что вы вот такой крутой и писали микрокоманды, но вот какого лешего вы прицепились к автору топика? Даже не поблагодарили за хороший пост после этого. В посте ставилась задача — написать простой компилятор и уложиться в разумный объём. Задача выполнена. ОК, может, автор применил слегка неправильную терминологию. Но вот это ваше презрительное «не более» совершенно неуместно. Пока всё выглядит так, словно съеденная вами собака сбежала с кафедры терминологии и демагогии.
Компилятор это и есть переводчик с одного языка на другой.
Спасибо за стаатью. Почитал вчера вечером за чашечкой кофе ваше творение. То, что было нужно.
Автору респект не только за статью но и за ее позиционирование! Действительно от компилятора в прямом смысле толку мало, но именно для того, чтобы понять как все устроено и надо писать свои велосипеды. Я написал свой компилятор-транслятор на 5 курсе. Осталось подсадить дерево и вырастить сына.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки.
Простые смертные студенты специальности «программное обеспечение вычислительной техники и автоматизированных систем» постигают и осиливают написание компилера си-лайт на 4ом курсе.
Простые смертные студенты специальности «программное обеспечение вычислительной техники и автоматизированных систем» постигают и осиливают написание компилера си-лайт на 4ом курсе.
В топике не хватает ссылки на PLY (Python Lex-Yacc).
У меня есть идеи по реализации custom процессора в FPGA, есть ли кто-нибудь кому интересно реализовать компилятор под него? just for fun, естественно…
> Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
Напишите отладчик. Вот это уже действительно challenge ;)
Напишите отладчик. Вот это уже действительно challenge ;)
Вы так «аппетитно» написали, что мне захотелось тоже написать компилятор (на основе Вашего, но на LabVIEW). И это может получиться забавно — компилятор текстового языка на языке графическом.
>Это, наверное, самый сложный компонент нашего компилятора
В Real-World компиляторах, кстати, как правило — самый простой(не парсер конкретно, а вообще, часть, отвечающая за разбор).
Про грамматику надо было сказать. Грамматика, вроде бы, сводится к LL(1), значит надо было этот момент объяснить, переписать её соответствующим образом, и в коде сделать нормальный предикативный анализатор, а не какое-то его ad-hoc подобие, как сейчас.
Кстати, настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.
В Real-World компиляторах, кстати, как правило — самый простой(не парсер конкретно, а вообще, часть, отвечающая за разбор).
Про грамматику надо было сказать. Грамматика, вроде бы, сводится к LL(1), значит надо было этот момент объяснить, переписать её соответствующим образом, и в коде сделать нормальный предикативный анализатор, а не какое-то его ad-hoc подобие, как сейчас.
Кстати, настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.
>предикативный
«предиктивный», всмысле
в 3 ночи голова не работает :)
«предиктивный», всмысле
в 3 ночи голова не работает :)
> настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.
А оптимизации?
А оптимизации?
Еще про грамматики можно пару слов, какие бывают и в чём различия?
[i]сейчас начал читать TAPL, до книги дракона не добирался еще.[/i]
[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-выражений:
Грамматики бывают разные, но если говорить про контекстно-свободные, то 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
От чего же «примитивный и никому не нужный компилятор», следующим шагом в изучении можно и переписать его код на TinyC сделав его самодостаточным.
Ваш код уничтожил все мои разработки. Браво. Продолжайте в том же духе
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пишем примитивный и никому не нужный компилятор