Шаг к созданию собственного языка программирования

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

Дисциплина создания языка программирования охватывает множество тем. Вот некоторые из компонентов, которые можно найти в реализации того или иного языка программирования:

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

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

В этой статье я остановлюсь на парсерах. В частности, я опишу синтаксический анализатор, который преобразует математическое выражение в структуру данных, называемую деревом синтаксического анализа. В языке программирования выражения используются как строительные блоки в более крупной семантической структуре. Например, в большинстве языков вы найдете выражение в каждом условном выражении «if», например:

if ( expression ) 
    statement
else
    statement

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

Цель

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

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

cos(x^2+2*pi*theta)/sqrt(a^2+b^2)

Затем он преобразует этот текст в красивую формулу вроде этой:

Живая демонстрация

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

Обзор шагов

Код начинается с анализа введенного пользователем текста в дерево синтаксического анализа. Вот как выглядит дерево синтаксического анализа для показанного выше выражения.

Затем программа использует дерево синтаксического анализа для создания выражения в формате TeX:

\frac{ \cos \left( x^2 + 2\pi\theta \right) } {\sqrt{a^2 + b^2}}

Наконец, он использует библиотеку JavaScript MathJax для визуализации выражения TeX как элегантно набранной математики в браузере.

Ограничения

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

  • Переменные латинскими буквами: от a до z и от A до Z.
  • Переменные с греческими буквами, от alpha до omega в нижнем регистре и с Alpha по Omega в верхнем регистре.
  • Числовые значения в форме целых чисел (724), чисел с плавающей запятой (4.39254) и экспоненциальной записи (6.27e+20).
  • Бинарные операторы сложения (+), вычитания (-), умножения (*), деления (/) и возведения в степень (^).
  • Операторы унарного префикса + (положительный) и - (отрицательный). Обратите внимание, что один и тот же символ может означать разные вещи в зависимости от контекста!
  • Функции косинус (cos), синус (sin), абсолютное значение (abs) и квадратный корень (sqrt). Вам будет легко добавить дополнительные функции позже, если вы захотите.
  • Использование круглых скобок () для отмены приоритета оператора.

BNF Грамматика

Нет, BNF Grammar - это не название модной сети ресторанов. BNF означает Форма Бэкуса – Наура, обозначение, которое позволяет вам определять синтаксис языка программирования. Грамматика вашего языка - важный первый шаг в создании синтаксического анализатора. Это ваша дорожная карта. Он кратко определяет, что может появиться в действующей программе. Вы будете постоянно обращаться к грамматике, когда будете писать код для вашего парсера.

Вот грамматика BNF для нашего синтаксического анализатора выражений.

expr ::= mulexpr { addop mulexpr }
addop ::= "+" | "-"
mulexpr ::= powexpr { mulop powexpr }
mulop ::= "*" | "/"
powexpr ::= "-" powexpr | "+" powexpr | atom [ "^" powexpr ]
atom ::= ident [ "(" expr ")" ] | numeric | "(" expr ")"
numeric ::= /[0-9]+(\.[0-9]*)?([eE][\+\-]?[0-9]+)?/
ident ::= /[A-Za-z_][A-Za-z_0-9]*/

Грамматика - это серия определений. Каждое определение начинается с имени типа expr, за которым следует символ ::=, что означает «определено как». Справа от каждого ::= указан синтаксис, разрешенный для концепции, названной слева от ::=.

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

mulexpr { addop mulexpr }

это означает, что выражение состоит из mulexpr, за которым следует ноль или более addop mulexpr пар. Другими словами, это все допустимые expr строки:

mulexpr
mulexpr addop mulexpr
mulexpr addop mulexpr addop mulexpr
mulexpr addop mulexpr addop mulexpr addop mulexpr

В общем, все, что заключено в {}, означает, что эта вещь может появляться любое количество раз, включая ноль.

Чтобы понять, что означают mulexpr и addop, продолжайте читать грамматику. Вы видите, что addop может быть либо буквальной строкой +, либо буквальной строкой -. Буквальный текст заключен в двойные кавычки, например: "+". Символ | представляет альтернативы: синтаксический анализатор допускает любые взаимоисключающие альтернативы, разделенные этим символом вертикальной черты.

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

Наконец, для удобства я использую регулярные выражения в стиле JavaScript, встроенные в //, для определения символов numeric и ident. Это мой собственный подход, особенно когда я пишу синтаксический анализатор на языке, поддерживающем регулярные выражения.

Токенизатор

Как только вы поймете, как написать грамматику BNF для вашего языка, следующим шагом будет создание токенизатора, который распознает токены на вашем языке. Токен - это основная единица текста на вашем языке, как атомы, которые нельзя разделить. Токены в нашем примере языка выражений - это символы пунктуации, такие как + и -, идентификаторы, такие как theta, и числовые литералы, такие как 47.259.

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

В дополнение к блоку символов, составляющих токен, удобно прикрепить к каждому токену еще пару частей данных:

  • Расположение токена на входе. Если вы анализируете исходный код из файла, естественный способ запомнить местоположение каждого токена - это его номер строки и номер столбца в этом файле. Если синтаксический анализатор обнаруживает синтаксическую ошибку в конкретном токене, он может затем сообщить сообщение об ошибке, которое включает номер строки и номер столбца. Это помогает пользователю определить причину проблемы. В демонстрационной программе этой статьи вводом является одна строка текста. Следовательно, каждый токен хранит во входной строке свой собственный индекс, отсчитываемый от нуля. При возникновении ошибки демонстрационная программа выделяет проблемный токен в поле ввода текста.
  • Тип токена. В моем примере синтаксического анализатора все токены классифицируются как идентификатор, оператор или число. Определение типа токена помогает синтаксическому анализатору понять, как поступать с каждым токеном, который он видит.

Итак, вот как я реализую класс Token, представляющий каждый токен во входных данных:

Для простоты класс Parser выполняет всю разметку прямо в своем конструкторе. Анализируемый текст передается в конструктор, а результирующий список из Token объектов сохраняется в this.tokenList. Логика токенизатора распознает токены с помощью регулярного выражения (reToken), которое проверяет числовые литералы или идентификаторы. Если ни один из них не совпадает, он рассматривает следующий одиночный символ, не являющийся пробелом, как токен. Таким образом, каждый пробельный символ игнорируется, и каждый непробельный символ включается в некоторый токен.

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

Создание дерева синтаксического анализа

Основной метод синтаксического анализа выражения внутри класса Parser называется Parse. Он вызывает вспомогательный метод ParseExpr, который следует правилу expr грамматики BNF. ParseExpr реализует жадный синтаксический анализатор с рекурсивным спуском, который пытается использовать как можно больше токенов, подчиняясь грамматике.

Бывают случаи, когда неверный синтаксис заставляет ParseExpr сдаться и вернуть действительное дерево синтаксического анализа для самой левой части токенов, которую он смог сопоставить с грамматикой. Вот почему Parse необходимо убедиться, что все токены были израсходованы. Если после возврата ParseExpr остались токены, это означает, что произошла синтаксическая ошибка. В этом случае Parse вызывает исключение.

Вы можете спросить, почему ParseExpr не генерирует исключение при наличии неанализируемых токенов. Это потому, что парсер - это система взаимно рекурсивных функций. Бывают случаи, когда ParseExpr нужно распознать выражение внутри другого выражения. Например, рассмотрим выделенную жирным шрифтом часть этого правила грамматики:

atom ::= ident [ "(" expr ")" ] | numeric | "(" expr ")"

Выражение может заключаться в круглые скобки внутри другого выражения. Как только синтаксический анализатор видит (, он вызывает ParseExpr для обработки выражения в круглых скобках. ParseExpr остановится, как только попадет в ), потому что этот токен не является addop. Этот токен закрывающей круглой скобки не является синтаксической ошибкой; требуется! Вот почему вам нужна дополнительная функция Parse, которая вызывается на верхнем уровне, чтобы выйти из строя, когда остаются необработанные токены.

Исключения - твои друзья

Если исключения доступны на языке программирования, который вы используете для написания синтаксического анализатора, рекомендуется воспользоваться ими. Я написал синтаксический анализатор на C, и это намного менее увлекательно. Очень быстро код становится раздуваемым из-за проверки возвращаемых значений других функций и выхода из строя, когда они указывают на ошибку. Одна альтернатива в C - использовать setjmp и longjmp, хотя это опасно по разным причинам. Создание исключений избавляет от громоздкого повторяющегося кодирования. Каждая функция в анализаторе может беспечно продолжить работу после вызова других функций, которые могут дать сбой.

Можно возразить, что исключения «дорого обходятся». Мой ответ: учтите, что исключение возникает только при синтаксической ошибке. В этом случае все равно останавливается. Пользователь должен выяснить, как исправить проблему, отредактировать код и снова запустить синтаксический анализатор. Таким образом, дополнительная миллисекунда накладных расходов на обработку синтаксической ошибки незначительна. Если исходный код имеет правильный синтаксис, накладных расходов на исключение не возникает. Возможно, код на основе исключений быстрее в случае успеха, когда производительность имеет значение, потому что ему не нужно постоянно проверять возвращаемые значения!

Написание вашего синтаксического анализатора на основе грамматики

Давайте посмотрим на функцию ParseExpr. Мне нравится включать соответствующее грамматическое правило в качестве комментария в каждую из функций синтаксического анализа правил. Это послужит удобной справкой при проверке кода. Я предлагаю вам воспользоваться моментом, чтобы убедиться, что грамматический комментарий соответствует коду под ним.

Вспомогательная функция NextTokenIs проверяет, есть ли еще по крайней мере один токен и что следующий токен входит в число опций в списке переданных ей строк. Если это так, он возвращает этот токен и переходит к следующему токену, увеличивая nextTokenIndex. В противном случае он ничего не делает и возвращает null.

ParseExpr итеративно ищет mulexpr термины, разделенные операторами + или -, вызывая ParseMulExpr для обработки правила mulexpr в грамматике. Чем больше добавленных / вычтенных mulexpr терминов он находит, тем глубже и глубже строится дерево.

Остальные правила грамматики реализованы аналогично.

Классы выражений

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

Каждый узел выражения также содержит токен, который представляет его в исходном тексте. Например, в выражении a+b корневой узел дерева синтаксического анализа содержит маркер +, а дочерние элементы этого корневого узла являются выражениями a и b как листовые узлы (узлы с нулевыми дочерними элементами).

Все классы, производные от Expression, имеют одинаковую внутреннюю структуру данных. Этот набор классов существует для переопределения функций-членов ради генерации вывода TeX, как мы увидим дальше.

Использование дерева синтаксического анализа

Каждый класс, производный от Expression, содержит функцию-член с именем PrettyMath. Его задача - генерировать строку, содержащую код TeX. Например, класс Expression_Function обрабатывает узлы в дереве синтаксического анализа для функций abs, sqrt, sin и cos. Он знает, что синтаксис TeX различается в зависимости от того, какая из этих функций появляется.

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

Приоритет оператора

В выражении некоторые операторы должны оцениваться раньше других. Например, в a*b+c*d обычно умножаются a и b, затем c и d, а затем последними добавляются произведения a*b и c*d. Мы говорим, что умножение имеет более высокий приоритет, чем сложение.

Приоритет неявно определяется грамматикой в ​​зависимости от того, как правила вложены. Дело в том, что

expr ::= mulexpr { addop mulexpr }

определяется с точки зрения

mulexpr ::= powexpr { mulop powexpr }

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

Приоритет оператора также учитывается при генерации вывода TeX, как показано в следующей функции для выяснения, нужны ли круглые скобки вокруг каждого дочернего выражения:

Ассоциативность

Наряду с приоритетом операторов важно понимать ассоциативность. Для инфиксных бинарных операторов (операторов, которые появляются между двумя аргументами, например + в a+b) длинные цепочки одного и того же оператора могут быть левоассоциативными или правоассоциативными.

Левые ассоциативные операторы группируются слева направо. Это наиболее важно при вычитании и делении, где важен порядок. Например: a-b-c-d интерпретируется как ((a-b)-c)-d. Это вытекает из грамматики с помощью простой итерации с помощью правил грамматики «ноль или более» с использованием фигурных скобок, как в

expr ::= mulexpr { addop mulexpr }

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

Правоассоциативные операторы группируются справа налево. Единственный правоассоциативный бинарный оператор в этой грамматике - это оператор возведения в степень ^. Когда парсер видит a^b^c^d, мы хотим, чтобы он интерпретировал эту строку как a^(b^(c^d)). Грамматика использует рекурсию, а не итерацию, чтобы убедиться, что правая сторона глубже в результирующем дереве синтаксического анализа. См. Выделенную жирным шрифтом часть следующего правила.

powexpr ::= "-" powexpr | "+" powexpr | atom [ "^" powexpr ]

Точно так же унарные префиксные операторы + и - в определении powexpr используют рекурсию с правой стороны для обеспечения правоассоциативности.

Помимо выражений

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

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

Зачем делать это безумие?

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

Однако есть и другие замечательные причины для создания языка программирования. У вас может быть особая потребность в компактном и элегантном языке в существующей программной системе. Многие текстовые редакторы, электронные таблицы и системы САПР имеют встроенные языки сценариев, которые позволяют пользователям создавать свои собственные макросы или пользовательские приложения.

Теперь я понимаю программирование на более глубоком уровне после создания и использования моих собственных языков программирования. Компиляторы и интерпретаторы больше не кажутся загадочными. Я также впечатлен огромным объемом работы и талантов, которые были вложены в надежные и широко распространенные языки, такие как C #, JavaScript и Python.

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

Упражнения для читателя

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

  • Преобразуйте входное выражение в синтаксис LISP. Например, если задано 3*x+47/y в качестве входных данных, сгенерируйте выходные данные (+ (* 3 x) (/ 47 y)).
  • Измените грамматику, синтаксический анализатор и генератор TeX, чтобы разрешить функцию любого количества аргументов, разделенных запятыми: max(a, b, c, ...).
  • Учитывая дерево синтаксического анализа, напишите код, который создает другое дерево синтаксического анализа, которое является частной производной первого дерева синтаксического анализа по переменной x. Считайте все остальные переменные константами. Например, преобразовать (x^3+5)^2 в 2*(x^3+5)*3*x^2.
  • Добавьте упрощение выражения, которое устраняет ненужную сложность выражения. Например, он может преобразовать 1*x+0*y-7*x в -6*x. Это упражнение даст вам представление о том, что оптимизатор делает внутри компилятора.
  • Создайте двухмерный графопостроитель, который отображает выражение относительно независимой переменной x.

использованная литература

  1. Полный исходный код, использованный в этой статье, доступен по адресу: https://github.com/cosinekitty/parser.
  2. Вот живая демонстрация парсера, который работает в вашем браузере: https://doncross.net/parser/