Создание Парсера с Нуля

Разбор или синтаксический анализ - один из первых этапов проектирования и реализации компилятора. Хорошо продуманный синтаксис вашего языка программирования - это большая мотивация, по которой пользователи предпочтут и выберут именно ваш язык. Примечание: это практическое занятие по созданию парсера с рекурсивным спуском вручную.

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

Кроме того, реализация полностью ручного парсера с нуля позволяет понять и увидеть этот процесс изнутри, демистифицировать внутренние структуры и превратить построение парсеров в интересную инженерную задачу.

В курсе «Создание парсера с нуля» мы погружаемся в чистую практическую реализацию, создание и изучение различных аспектов парсеров.

В этом курсе вы изучите концепцию синтаксического анализа рекурсивного спуска, поймете, что такое Tokenizer и как он взаимодействует с модулем Parser, узнаете, что такое абстрактное синтаксическое дерево (AST), и как иметь разные форматы этих AST, что такое «упреждающий просмотр» и прогнозирующий синтаксический анализ и, в конечном итоге, создание синтаксического анализатора для полноценного языка программирования, подобного Java или JavaScript.

Реализация синтаксического анализатора также сделает ваше практическое использование других языков программирования более профессиональным.

Для кого этот курс?

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

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

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

Что используется для реализации?

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

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

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

Что особенного в этом курсе?

Основные особенности этих лекций:

• Кратко и прямо по делу. Каждая лекция самодостаточна, лаконична и описывает информацию, непосредственно относящуюся к теме, не отвлекаясь на посторонние материалы или доклады.
• Анимированная презентация в сочетании с редактируемыми заметками. Это облегчает понимание тем и показывает, как (и когда) связаны структуры объектов. Статические слайды просто не работают для сложного контента.
• Сессия программирования в реальном времени с заданиями. Полный исходный код, начиная с нуля, и до самого конца представлен в видеолекциях.

Что в курсе?

Курс разделен на четыре части, всего 18 лекций и множество подтем в каждой лекции. Ниже приведено содержание и учебная программа.

Часть 1: Основные выражения и Tokenizer

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

Часть 2: Структура программы

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

Часть 3. Поток управления и функции

В этой части мы реализуем переменные, присваивание, работаем с приоритетом операторов и вводим абстракцию функций. Кроме того, мы определяем управляющие структуры, такие как оператор If и итерационные циклы.

Часть 4: Объектно-ориентированное программирование

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