Всем привет! В прошлый раз мы представили PizzaScript - образовательный Go-проект с открытым исходным кодом. Мы продолжаем эту статью, и встреча состоится 13 февраля, 10:00 CET. В этих материалах мы делаем обзор проекта и знакомим с ключевыми концепциями создания нового языка программирования. Мы покажем реализацию простого калькулятора с использованием Golang и RxGo. Эта статья посвящена lexer’s сценарию с ReactiveX, оставив parser и eval на потом. Эта серия статей может помочь новичкам в изучении Golang и WebAssembly и экспериментировать с живым проектом с открытым исходным кодом.

  • I Slice - Введение в PizzaScript
  • II Slice - Языки программирования
  • III срез - реактивные паттерны

Я разрезаю

- который знакомит с языком программирования PizzaScript, также известным как

испорченный язык программирования ©

PizzaScript или ps - новый крутой язык с необычной парадигмой.

Почему? Я люблю JavaScript 💛 и TypeScript 💙. Мне особенно нравятся JavaScript причуды, и я всегда хотел больше свободы, чем дает JavaScript язык.

Wat - молниеносная речь Гэри Бернхардта из CodeMash 2012

И я еще не пробовал создать свой собственный язык. Я решил это сделать, и мои цели:

  • Понять, как работают языки программирования и интерпретаторы
  • Изучите Go язык и ключевые библиотеки, например RxGo
  • Экспериментируйте с WebAssembly

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

PizzaScript 🍕 Основные характеристики

  • Классное название (и логотип, todo)!

Это, пожалуй, самая важная из всех функций. Мы гордимся своим выбором.

  • JavaScript -подобный синтаксис, своего рода
  • Переменные, целые числа, числа с плавающей запятой и строки
  • Арифметические выражения, встроенные функции
  • Первоклассные функции, замыкания
  • Динамические типы и приведения
  • Модули и стандартная библиотека
  • Потрясающие идеи и поток интерпретаторов
var h1679 = "1"
val g2788 = 2
h1679 + g2788 == "12"
g2788 + h1679 == 3
  • PizzaScript компилируется в WebAssembly, что делает его переносимой и подходящей целью для выполнения как на стороне клиента, так и на стороне сервера.

Хорошо, звучит сложно. Как мы его построим?

  • Я сам заинтересован в изучении Go языка.
  • Я тоже хотел разложить проект areactive способом. Кроме того, изучение библиотеки может помочь в освоении нового языка программирования. RxGo поможет организовать поток данных - разбить вводимый текст на токены, затем проанализировать и организовать их в структуру данных абстрактно-синтаксическое дерево.


Абстрактное синтаксическое дерево
В информатике абстрактное синтаксическое дерево (AST) или просто синтаксическое дерево - это древовидное представление абстрактного… en.wikipedia .org



  • WebAssembly - это большое дело, и мы собираемся производить модули в форматах wasm или wat.

II Slice - Языки программирования

Если вы спросите меня, язык программирования - это произведение искусства 😀. Серьезно, это огромная работа, чтобы понять, создать и поддержать его. Лично мое первое представление о языке - это образцы кода, написанные на нем. Как и в случае с PizzaScript, в этом небольшом примере показано определение функции

fun sum(var a1573: string, b7232): int {
  a1573 + b7232
}
sum(1, 2) // 12

Как видите, функции объявляются с ключевым словом fun.

Что ж, это не совсем весело 🤔

Итак, что такое язык программирования? Здесь, безусловно, нужно дать несколько определений:

  • У нас есть alphabet всех доступных символов. Написанный на нем текст по сути представляет собой строку или цепочку символов.
  • А затем у нас есть конкретный набор цепочек из alphabet. Те образуют language.

Вопрос - как указать язык? И, конечно, есть разные способы сделать это. Самый простой - перечислить в нем все цепочки. Как можно себе представить, большинство языков программирования состоят из бесконечного числа цепочек.

То есть, я с трудом могу представить, чтобы кто-то написал хотя бы две одинаковые программы на PizzaScript 🤷‍♂️

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

  • программа, которая проверяет, принадлежит ли данный текст к определенному языку,
  • или программа, которая генерирует возможные цепочки из языка
  • Grammar - это набор правил, определяющих язык, записанный в специальной форме.

Наиболее известна форма Backus–Naur.

<personal-part> ::= <initial> "." | <first-name>

Считайте каждый <personal-part> как <initial> с типами <.> или <first-name> символьных последовательностей, разделенных |. Ниже вы можете увидеть простой язык калькулятора в форме BNF.

expr ::= operand {('+' | '-' | '*' | '/') operand} ; any number of infix operations
; with no precedence
operand ::= num [+/-] | '(' expr ')' ; a number followed optionally by
; +/- or a parenthsized expression
num ::= digit {digit} ['.' {digit}]] ; numbers can be integer or real
digit ::= '0 | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Популярный генератор парсеров antlr предоставляет расширенную версию грамматики калькулятора.

Вообще говоря, эти типы грамматики могут быть переведены в компьютерные программы. А программа, которую мы собираемся построить, - это компилятор.

Итак, как работают компиляторы языков программирования?

Этой теме посвящено множество исследований, и мы лишь вкратце охватим основные идеи. Обычно программа компилятора состоит из последовательных, но независимых этапов. У каждого своя цель.

Лексический анализ отвечает за разбиение входного текста на подпоследовательности лексем. Он фильтрует разделители (например, пробелы или ;) и преобразует значимые символы в типизированные объекты, называемые токенами. Токены бывают разных типов, например, типы данных - числа, строки, определения переменных - идентификаторы, операторы - +, -, =, / и т. Д.

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

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

Формат ast не имеет единого стандарта для разных языков. Например, babel - популярный JavaScript transpiler (еще один интересный термин, часто используемый в контексте компилятора), который преобразует разные EcmaScript версии друг в друга, Имеет свою определенную спецификацию.

Это пример типов узлов, определенных в формате babel ast.

interface Node {
  type: string;
  loc: SourceLocation | null;
}
interface NumericLiteral <: Literal {
  type: "NumericLiteral";
  value: number;
}

AST Explorer позволяет нам увидеть, как разные языки могут быть представлены в разных ast форматах

И есть разные сценарии, которые происходят после разбора программы. Например, он может быть скомпилирован в целевые инструкции, оценен или интерпретирован.

Целью компиляции PizzaScript является WebAssembly, что означает, что мы будем производить вывод в формате wasm или wat. Наша цель - сделать переносимый язык программирования.

III срез - реактивные паттерны

А пока мы обсудили этапы обработки текста программы, а именно:

  • для разбиения текста на токены или для лексического анализа,
  • для разбора лексем или синтаксического анализа,
  • построить абстрактное синтаксическое дерево,
  • для компиляции или оценки проанализированного дерева.

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

Одна из идей, которую я всегда преследовал, заключалась в том, чтобы разложить приложение на реактивные шаблоны. В этой парадигме все данные представлены как поток асинхронных событий. И проект ReactiveX прекрасно объединяет связанные шаблоны, такие как Observable, Iterator, Functional Programming. Он позволяет использовать акторов и операторов API для объединения, преобразования и разделения потоков.

Мы выбрали Golang и будем использовать RxGo реализацию ReactiveX. Он имеет достаточную поддержку своих концепций и операторов.

Начнем с варианта использования калькулятора, и мы собираемся создать:

  • main - основной запускаемый пакет,
  • repl - считывает ввод пользователя, инициализирует всех необходимых актеров и производит вывод,
  • token - объявляет разрешенные символы и операторы PizzaScript,
  • lexer - разбивает вводимый текст на токены,
  • parser - генерирует дерево абстрактного синтаксиса программы,
  • ast - описывает ast типы,
  • eval - оценивает дерево программы и выдает результат.

Одна очень важная вещь, которую я еще не сказал. Этот проект глубоко вдохновлен Writing An Interpreter In Go by Thorsten Ball, но не только. Есть много интересных ресурсов, которыми я хотел бы поделиться во время следующих статей и мероприятий. Некоторые примеры взяты из книги и переписаны с учетом нашего интереса.

Начнем с пакета main. Он просто запускает repl общедоступный метод Start.

Пакет Repl или Read-Eval-Print-Loop implementation довольно прост.

Это цикл, который взаимодействует с пользователем. Он читает ввод и печатает вывод. Ха, давай уже запустим

$ git clone https://github.com/x-technology/PizzaScript.git
$ cd pizzascript
$ go get
$ go run main.go
Hello alex! This is the PizzaScript programming language!
Feel free to type in commands
>> 123
123
>> 1+2
3
>> 2+3
5
>> 123+2
125
>> 12*3
36

Вау, а работает ?! Как уже было сказано, мы не увидим здесь парсер и eval. Но давайте проверим самые интересные на сегодня срезы - token и lexer.

Token описывает доступные токены

Все идет нормально. Давайте также представим пакет lexer

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

Но это скорее предположение, мы рассмотрим эту тему на будущих сессиях.

Мы создаем и сохраняем Observable, созданный на основе ввода текста, и разбиваем его на отдельные символы.

Lexer должен фильтровать бессмысленные символы. С PizzaScript
s p a c e s 👽, конец строк, вкладки можно пропустить.

Оператор фильтра довольно прост - для заданного потока данных он выполняет функцию обратного вызова для каждого события и возвращает значение bool, чтобы указать, должны ли данные оставаться в потоке вывода.

Следующий шаг - объединить некоторые символы в жетоны. Примером может быть число из нескольких символов 125, что нормально. То же и с идентификаторами. Мы еще не представляем их, но это место в коде, куда нам нужно добавить их в будущем. Вот где это становится немного сложнее. С шаблоном Observable мы перебираем асинхронные события. В идеале мы стремимся не иметь побочных эффектов и изолировать нашу область видимости только от обратных вызовов операторов.

Оператор Scan во многих аспектах похож на map + reduce в приведенном выше коде. Аргумент первого обратного вызова оператора - это значение аккумулятора, возвращенное с предыдущей итерации, и результат передается в новый поток на каждой итерации. Это наш способ использования здесь техники look-ahead - мы сохраняем значение предыдущей итерации и на его основе создаем новое. Введем промежуточный тип состояния. Его цель - собрать символы в жетоны, если у них есть соответствующий атрибут. В нашем случае числа объединяются. Поскольку у нас еще нет идентификаторов, реализация почти завершена.

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

На этом наша первая попытка завершена.

Следующие шаги

В эту субботу, 13 февраля, 10:00 по центральноевропейскому времени, мы встретимся на живом заседании, чтобы узнать подробности по этому поводу. Приглашаем вас присоединиться! В следующей статье мы рассмотрим функции parser и eval. Собственно, спрашиваем ваше мнение по этому поводу.

Какой должна быть наша следующая тема для PizzaScript?

  • Подробнее о PizzaScript 🍕
  • Глубоко в парсеры, языки программирования 🎓
  • Давай уже скомпилируем его до WebAssembly 💻

Дайте нам знать в комментариях! 🙏

Мы только начали, не стесняйтесь присоединяться к нам:

И, конечно же, исходный код открыт. Мы высоко ценим любые отзывы, вклад или помощь.

Спасибо за уделенное время и приятного кодирования!