Компиляторы *

Привет, Хабрахабр!

Введение

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

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

Введение

Здравствуй, уважаемый хабраюзер.Я хотел бы тебе представить материал о практическом создании компилятора, который будет транслировать код, написанный на языке Cool, в код виртуальной машины CIL (Common Intermediate Language) под платформу .NET.Данный материал я решил разбить на две части из-за лени все сразу это описывать

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

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

1 декабря состоялся релиз LLVM 3.0 (Low Level Virtual Machine) — «инфраструктуры для компиляторов», которая генерирует платформонезависимый оптимизированный байткод низкого уровня (см. обзор на Хабре). LLVM используется в том числе в официальных средствах разработки для Mac OS X и iOS.

С момента выхода LLVM 2.9 прошло шесть месяцев, новшеств довольно много, в том числе новый «жадный» аллокатор регистров. Он применяет интересные способы оптимизации и способен значительно улучшить производительность кода.

Я считаю, что каждый программист должен написать свой компилятор.

Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

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

Задачей лексического анализа является разбить входную последовательность (в моем случае код на языке «Паскаль») на слова и лексемы.

Для начала я создал 5 типизированных листов для хранения данных, а именно: идентификаторов, констант, ключевых слов, разделителей и свертки. Также необходим массив разделителей

static char[] limiters = {',', '.', '(', ')', '[', ']', ':', ';', '+', '-', '*', '/', '<', '>', '@'};

и массив ключевых слов. Я ограничился одиннадцатью ключевыми словами, так как статья написана как начальный пример реализации лексического анализа языка «Паскаль» на языке C#.
Итак, массив ключевых слов:

static string[] reservedWords = { "program", "var", "real", "integer", "begin", "for", "downto", "do", "begin", "end", "writeln" };

Моему брату было 9 лет, и он очень хотел научиться программировать. Я долго думал, что бы ему такое предложить. Большинство начинало с Турбо-Паскаля. Но так как на втором курсе примата мы проходили компиляторы, то я решил написать собственный компилятор.

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

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

1) Нет литературы для обучения. Есть только список файлов с примерами.
2) Я думаю, некоторые свойства языка, такие как нестрогая типизация, не есть хорошо для первого языка программирования.

Получился 1С-подобный язык, который я сам стал использовать для автоматизации операций на компьютере. И соответственно, «нашпиговывать» его всё новыми, мыслимыми и немыслимыми функциями.

Итак, Вы собираетесь создать новый [] функциональный, [] императивный, [] объектно-ориентированный, [] процедурный, [] стековый, [] мультипарадигменный, [] быстрый, [] статически-типизированный, [] динамически-типизированный, [] чистый, [] богатый, [] не-искусственный, [] наглядный, [] простой для новичков, [] простой даже для не-программистов, [] абсолютно непостижимый язык программирования.

Не получится. И вот почему.

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

Когда в изучении языка доходишь до нетривиальных вещей, бывает полезно сместить уровень абстракции, чтобы понять, как на самом деле всё устроено. Ведь, по большому счету, любые конструкции языков сколь угодно высокого уровня сводятся к старому доброму машинному коду. Писать в объектно-ориентированном или функциональном стиле можно и на чистом C, и даже на ассемблере. Грубо говоря, любой высокоуровневый язык — это зафиксированный на уровне компилятора или интерпретатора набор синтаксических карамелек и шоколадок. Повышение уровня абстракции позволяет писать более сложные программы с меньшими усилиями, но вот понять в начале пути, что конкретно имеется в виду под наследованием или замыканием, как это всё работает и почему, гораздо легче, разобравшись, каким образом всё это реализовано.

JavaScript, как никакой другой язык, нуждается в именно таком объяснении. Функциональная природа, скрытая за Си-подобным синтаксисом, и непривычная прототипная модель наследования поначалу сильно сбивают с толку. Давайте мысленно понизим уровень JavaScript до простого процедурного, наподобие Си. Отталкиваясь от этого «недоязыка», переизобретем функциональное и объектно-ориентированное программирование.

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

Добро пожаловать в Главу 5 учебника «Создание языка программирования с LLVM». Предыдущие главы (1-я, 2-я, 3-я и 4-я) описывали реализацию простого языка программирования Kaleidoscope и включение в него поддержки генерации LLVM IR, а также последующей оптимизации и JIT-компиляции. К сожалению, в текущем виде Kaleidoscope почти бесполезен: он не имеет никакого потока управления, за исключением вызовов и возвратов. Это означает, что в коде не может быть условных переходов, что значительно ограничивает язык программирования. В этой главе мы расширим Kaleidoscope, добавив в него выражение if/then/else и простой цикл "for".

Добро пожаловать в Главу 4 учебника «Создание языка программирования с LLVM». Предыдущие главы (1-я, 2-я и 3-я) описывали реализацию простейшего языка программирования и добавление в него ​​поддержки генерации LLVM IR. В этой главе описаны две новых техники: добавление поддержки оптимизатора и добавление поддержки JIT-компилятора. Эти дополнения продемонстрируют как получить хороший, эффективный код для нашего языка программирования Kaleidoscope.

Добро пожаловать в Главу 3 учебника «Создание языка программирования с LLVM». В этой главе мы рассмотрим, как преобразовать AST (Абстрактное Синтаксическое дерево), построенное в Главе 2, в LLVM IR. Она расскажет вам о некоторых аспектах работы LLVM, а также продемонстрирует, насколько он прост в использовании. Вы увидите, что гораздо больше труда потребовалось на лексический и синтаксический анализ, чем на непосредственное создание кода LLVM IR.

Обратите внимание: код из этой главы требует наличия LLVM 2.2 или более поздней версии. С версиями по LLVM 2.1 включительно этот код работать не будет. Также стоит отметить, что вам стоит использовать версию этого учебника, которая соответствует вашему релизу LLVM: вы можете использовать документацию, которая прилагается к официальным выпускам или посетить страницу с релизами на llvm.org.

Добро пожаловать в Главу 2 учебника «Создание языка программирования с LLVM». В этой главе мы увидим, как использовать лексический анализатор, созданный в Главе 1, чтобы построить полный синтаксический анализатор для нашего языка Kaleidoscope. После того, как у нас будет готов парсер, мы будем строить Abstract Syntax Tree (AST) (Абстрактное синтаксическое дерево).

Добро пожаловать в учебник «Создание языка программирования с LLVM». Этот учебник знакомит вас с созданием простейшего языка программирования, и при этом показывает, каким оно может быть легким и интересным, а также даёт вам начальные знания, которые вы затем сможете применить на других языках программирования. Код в этом учебнике также может быть использован в качестве стартовой площадки для ваших творений с помощью LLVM.

Целью данного учебника является постепенное представление нашего языка, описание его пошагового создания. Это позволит нам охватить достаточно широкий спектр вопросов проектирования языков и использования LLVM, попутно показывая и объясняя код без огромного количества ненужных деталей.

Возрадуйтесь братия и сестры! Очередной релиз несомненно одного из самых значимых проектов был выпущен на свободу. Итак 25 марта версия 4.6 увидела свет.

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

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

Ну а если серьёзно, как-то раз у нас на работе кто-то в шутку предложил написать гоп-язык, чтобы программистом мог себя почувствовать себя любой. Начинать конструкции со слова «чо» и всё такое. Тут надо заметить, что, не встретив на своём жизненном пути образования в области computer science, я пропустил все те интересные курсы по построению компиляторов, формальным грамматикам и прочим вкусностям, которые вкушают нормальные студенты на втором-третьем курсе. Книга Вирта по построению компиляторов хотя и добавила мне знания всяких умных терминов типа БНФ, но практической пользы не принесла ­— ни одного компилятора я так и не написал. Поэтому задача оказалась для меня довольно интересной.
Если вы старше 18 лет, адекватно воспринимаете обсценную лексику нашего родного языка и вам интересно, с чего начать, добро пожаловать под кат.