Pull to refresh

Простой интерпретатор с нуля на Python (перевод) #1

Python *
Sandbox
Tutorial


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


В этом цикле статей я попытаюсь захватить часть этой простоты путем написания простого интерпретатора для обычного императивного языка IMP (IMperative Language). Интерпретатор будет написан на Питоне, потому что это простой и широко известный язык. Также, питон-код похож на псевдокод, и даже если вы не знаете его [питон], у вас получится понять код. Парсинг будет выполнен с помощью простого набора комбинаторов, написанных с нуля (подробнее расскажу в следующей части). Никаких дополнительных библиотек не будет использовано, кроме sys (для I/O), re (регулярные выражения в лексере) и unittest (для проверки работоспособности нашей поделки).
Читать дальше →
Total votes 28: ↑25 and ↓3 +22
Views 42K
Comments 14

Простой интерпретатор с нуля на Python #2

Python *
Translation
Tutorial


В предыдущей статье мы рассматривали сам язык IMP и основную структуру интерпретатора. Также, мы тщательно рассмотрели лексер. В этой статье мы будем писать небольшой парсер для нашего языка. Он будет извлекать AST (abstract syntax tree) из списка токенов, сгенерированных лексером. Библиотека комбинатора будет независимая, то есть с помощью нее можно будет написать парсер для любого языка.


Что такое комбинаторы парсеров?

Есть очень много способов написать парсер. Самым простым и быстрым способом сделать это являются комбинаторы.

Вы можете считать парсер функцией, которая принимает поток токенов. Если успешно, то парсер будет «съедать» немного токенов из потока. Функция вернет часть финального AST вместе с остальными токенами. Комбинатор — это функция, которая производит парсер, как его результат, обычно после приема одного или нескольких анализаторов (парсеров) в качестве входных данных, отсюда и название — «комбинатор». Вы можете использовать комбинаторы для создания законченного парсера для языка, как IMP, путем создания множества маленьких парсеров для каждой части языка.
Читать дальше →
Total votes 28: ↑26 and ↓2 +24
Views 16K
Comments 0

Простой интерпретатор с нуля на Python #4

Python *
Translation
Tutorial


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


Давайте подумаем, как обычно исполняются программы. В любой момент времени есть некоторые «точки контроля», которые указывает на то, какое выражение программа собирается выполнить дальше. Когда следующее выражение исполняется, оно модифицирует состояние программы, путем улучшения «точки контроля» и изменения значений переменных.
Читать дальше →
Total votes 30: ↑28 and ↓2 +26
Views 14K
Comments 1

Простой интерпретатор с нуля на Python (часть 3)

Python *
Sandbox
image


Разъяснение к публикации
Пользователь @duse ранее выкладывал переводы двух предыдущих статей, явно намереваясь перевести всю серию. Так как тема меня очень интересует, а новых переводов нет, обратился к первоисточнику. С английским не очень силён, чтобы не терять суть, стал переводить на русский. Так и родился этот перевод. Прошу прощения у @duse в случае, если мне стоило ещё чуточку потерпеть. Но для сообщества в любом случае должна быть польза.


Таким образом, мы написали лексер библиотеку комбинатора парсеров для нашего интерпретатора. В этой части, мы создадим структурные данные абстрактного синтаксического дерева (AST), и напишем парсер, используя нашу библиотеку комбинаторов, которые переводят список токенов, возвращенных лексером, в абстрактное синтаксическое дерево (AST). После того, как мы распарсим AST, запустить программу будет очень просто.

Читать дальше →
Total votes 26: ↑24 and ↓2 +22
Views 15K
Comments 1

Вычисление факториала на числах Чёрча

Abnormal programming *JavaScript *Functional Programming *
Доброго дня, друзья!

Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.

Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти).

Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:

var fact = function (n) {
  if (n === 0) return 1;
  return n * fact(n - 1);
};


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

Готовы?
Ну тогда поехали.
Total votes 51: ↑51 and ↓0 +51
Views 25K
Comments 47

Изучение комбинаторных парсеров с Rust

Programming *System Programming *Rust *
Sandbox

Привет, Хабр! Представляю вашему вниманию перевод статьи "Learning Parser Combinators With Rust".


Эта статья учит основам комбинаторных парсеров людей, которые уже знакомы с Rust. Предполагается, что никаких других знаний не требуется, а всё, что не имеет прямого отношения к Rust, а также некоторые неожиданные аспекты его использования, будут объяснены. Эта статья не поможет вам выучить Rust, если вы его ещё не знаете, и в этом случае, вы, вероятнее всего, не поймёте комбинаторные парсеры хорошо. Если вы хотите изучить Rust, я рекомендую книгу "Язык программирования Rust".

Читать дальше →
Total votes 43: ↑43 and ↓0 +43
Views 8.6K
Comments 17

Атомная война в эпоху Великого Комбинатора

Programming *System Analysis and Design *Designing and refactoring *Systems engineering
Достоевский дал миру Великого Инквизитора с его «зачем же ты пришел нам мешать?».
Ильф и Петров — Великого Комбинатора.
Та эпоха уже закончилась, эта — еще не началась.
Читать дальше →
Total votes 23: ↑15 and ↓8 +7
Views 3.8K
Comments 11

ICFP Contest 2020 от идеи до воплощения. Как организовать контест и выжить

Контур corporate blog Abnormal programming *Sport programming *Functional Programming *


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

Читать дальше →
Total votes 47: ↑47 and ↓0 +47
Views 4.6K
Comments 12