Пишем свой Lisp на JavaScript
Для начала следует задать простой вопрос: для чего?
Писать свой язык программирования — практически всегда плохая идея. Так зачем нам еще один лисп? Тем более, что уже есть ClojureScript, который на данный момент является production ready и имеет кучу приятных фич. Конкурировать даже с ClojureScript — безумие, — не гворя уже о TypeScript, CoffeeScript, etc. Но язык нам нужен и не для этого!
В первую очередь мы ведь хотим разобраться с тем, как они вообще пишутся. Плюс ко всему, не обязательно писать язык «программирования», зачастую возникают задачи написать свой собственный язык разметки текста, конфигурации и так далее. Все это можно решить похожим образом.
Пожалуй, начнем
Для начала условимся, что язык программирования — это некий формализованный язык, синтаксис которого подчиняется определенным правилам. Для разбора этих правил нам нужно знать, какие вообще «слова» (т.е. единицы языка) нам могут встретиться. Это могут быть не слова в привычном понимании, это могут быть знаки пунктуации, числа, строки и так далее.
Например, в нашем языке может встретиться такая конструкция:
(+ 2 3)
В ней как минимум использовано четыре «слова». Каждое слово это так называемый token. И для начала мы должны разбить наш текст на эти самые токены. Процесс разбития нашего исходного кода на токены называется токенизацией. Пока не будем углубляться детали, давайте лучше двигаться дальше. Представим, что мы разбили весь текст на токены, далее все эти токены нам нужно распарсить для того, чтобы получить абстрактное синтаксическое дерево (AST). Для этого нам нужно написать парсер, который бы умел обрабатывать полученную последовательность токенов. Опять же, не вдаваясь в детали, перейдем к следующему шагу: компиляция/трансляция. Теперь нам нужно наше AST преобразовать либо в машинный код, либо странслировать в другой язык. В нашем случае мы будет писать транслятор из AST в JS.
Написание токенизатора, парсера и транслятора — это не такая уж тривиальная задача, а потребность в таких инструментах исторически возникала очень часто, поэтому умные люди для упрощения данной задачи разработали генераторы лексеров и парсеров. Одним из таких генераторов является Bison. Но так как мы будем писать наш лисп на JS, то воспользуемся его JS налогом — Jison
Переходим к сути
Генератор парсеров Jison довольно просто использовать, для его несть grunt, gulp и webpack плагины, которые позволяют все ваши .jison фалый транслировать в JS файлы, уже содержащие готовый парсер. Я не буду описывать здесь как вам организовать проект на базе grunt/gulp/webpack. Будем просто использовать онлайн генератор парсеров http://zaa.ch/jison/try/.
Давайте для начала разберем пример калькулятора, который есть на сайте jison.
/* description: Parses end evaluates mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ {/* skip whitespace */}
[0-9]+("."[0-9]+)?\b {return 'NUMBER';}
"*" {return '*';}
"/" {return '/';}
"-" {return '-';}
"+" {return '+';}
"^" {return '^';}
"(" {return '(';}
")" {return ')';}
"PI" {return 'PI';}
"E" {return 'E';}
<> {return 'EOF';}
/lex
/* operator associations and precedence */
%left '+' '-'
%left '*' '/'
%left '^'
%left UMINUS
%start expressions
%% /* language grammar */
expressions
: e EOF
{return $1;}
;
e
: e '+' e
{$$ = $1 + $3;}
| e '-' e
{$$ = $1 - $3;}
| e '*' e
{$$ = $1 * $3;}
| e '/' e
{$$ = $1 / $3;}
| e '^' e
{$$ = Math.pow($1, $3);}
| '-' e %prec UMINUS
{$$ = -$2;}
| '(' e ')'
{$$ = $2;}
| NUMBER
{$$ = Number(yytext);}
| E
{$$ = Math.E;}
| PI
{$$ = Math.PI;}
;
В первой части этого файла, после комментария / lexical grammar /, как раз и находится описание всех наших «слов» языка. Здесь мы можем видеть как определяется число (да, можно определять токены через регулярные выражения, но это не всегда хорошо, иногда для определения высокоуровневого токена лучше использовать комбинацию более простых токенов). Здесь есть и токены арифметических операций: сложения, умножения, вычитания и деления.
Если скопировать весь текст грамматики в онлайн генератор, затем ввести выражение 10 + 10, то мы получим результат 20. Как так получается?
Давайте разберемся с тем, что, например, определяет эта конструкция:
e
: e '+' e
{$$ = $1 + $3;}
| e '-' e
{$$ = $1 - $3;}
| e '*' e
{$$ = $1 * $3;}
| e '/' e
{$$ = $1 / $3;}
| e '^' e
{$$ = Math.pow($1, $3);}
| '-' e %prec UMINUS
{$$ = -$2;}
| '(' e ')'
{$$ = $2;}
| NUMBER
{$$ = Number(yytext);}
| E
{$$ = Math.E;}
| PI
{$$ = Math.PI;}
;
На самом деле, все очень просто, здесь мы говорим, что «e» (expression) может быть суммой двух выражений:
: e '+' e
{$$ = $1 + $3;}
...
Из этого пример уже видно, что каждое наше определение любой новой синтаксической конструкции может быть рекурсивным. В данном случае, мы говорим, что expression может быть записан так: expression + expression. Встречая такую конструкцию, парсер будет ее токенезировать и затем выполнять код, который находится в фигурных скобках: { $$ = $1 + $3}. Это обычный JS код. Необычные тут только переменные, которыми мы оперируем: $$, $1, $3.
Давайте разбираться. $$ — это результат выражения, то есть то, что будет передано дальше по дереву разбора. $1 — первый элемент конструкции, на примере записи »10 + 10», $1 — это число 10. $3 — это третий элемент конструкции. Вторым элементом был бы '+', но так как сам по себе он нам не нужен, мы просто пропускаем его и выполняем сложение двух переменных с последующим сохранением результата в $$.
Далее следуют другие pattern’ы конструкции «e». Первый pattern всегда записывается через »:», последующие же — через »|», в конце ставится »;».
%start expressions
%% /* language grammar */
expressions
: e EOF
{return $1;}
;
Вот здесь мы говорим, что весь разбор начнется с pattern’a expressions, который в свою очередь представляет одно любое выражение «e» и конец файла. В фигурных скобочках здесь нам нужно вернуть результат всего разбора. В данном случае это будет результат одного выражения.
Переходим к написанию lisp
С калькулятором мы разобрались, давайте теперь попробуем заставить работать выражение:
(+ 1 2)
Для этого давайте определим свою грамматику. Как я говорил ранее, в нашем выражении встречается как минимум 4 токена:»(»,»+», «NUMBER» и »)».
Давайте опишем это в соответствующей части файла с грамматикой:
/* description: Parses end executes mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ /* skip whitespace */
[0-9]+("."[0-9]+)?\b return 'NUMBER'
"+" return '+'
"(" return '('
")" return ')'
<> return 'EOF'
/lex
%start program
%% /* language grammar */
expr
: '(' '+' NUMBER NUMBER ')'
{ $$ = +$3 + +$4 }
;
program
: expr EOF
{return $1;}
;
Это вся грамматика, которая позволит нам складывать два числа, но сложение двух чисел… Этого как-то мало. А что, если нам нужно сложить как в лиспе N чисел:
(+ 1 2 3 4 5)
Давайте исправим нашу грамматику:
/* description: Parses end executes mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ /* skip whitespace */
[0-9]+("."[0-9]+)?\b return 'NUMBER'
"+" return '+'
"(" return '('
")" return ')'
<> return 'EOF'
/lex
%start program
%% /* language grammar */
value
: NUMBER
{ $$ = +$1}}
;
values
: value
{ $$ = [$1] }
| values value
{ $$ = $1.concat($2)}
;
expr
: '(' '+' values ')'
{ $$ = $3.reduce(function(a, b){return a +b }) }
;
program
: expr EOF
{return $1;}
;
Обратите внимание, что здесь я сначала перечисляю то, что у нас может выступать в качестве value, определяя тем самым value, а затем рекурсивно определяю values:
value
: NUMBER
{ $$ = +$1}}
;
values
: value
{ $$ = [$1] }
| values value
{ $$ = $1.concat($2)}
;
То есть, values может быть одним или N подряд идущих value. При этом, я говорю, что value в values — это массив из одного value, а уже values — это объединение предыдущих значений массива с каждым последующим.
В результате парсинга values мы получаем массив чисел, для которого просто выполняем reduce, чтобы получить значение суммы всех чисел. Теперь операция:
( + 1 2 3 4 5)
вернет 15.
Поздравляю! Мы с вами написали первую и самую простую конструкцию языка lisp. Думаю, что реализовать вычитание, умножение и деление тоже не составит для вас никакого труда. Естественно, в рамках одной статьи невозможно описать процесс разработки все языка, даже всех базовых конструкций, но! Если вы заинтересовались этой темой, то можете перейти по этой ссылке: https://github.com/daynin/tiny-lisp
Это репозиторий проекта, в котором как раз при помощи Jison разрабатывается Lisp на JS. Там уже много чего реализовано, но тем не менее, это по прежнему очень маленький проект. Если вы хотите попробовать себя в разработке языка, то этот проект вам как нельзя лучше подходит!
P.S.
Если вам интересна эта тем, то я могу превратить это в небольшой цикл статей, где бы рассказал и показал, как все же можно довести язык хотя бы того состояния, в котором он представлен по ссылке выше
