Пишемо свій Lisp на JavaScript

image
Для початку слід поставити просте запитання: для чого?
Писати свою мову програмування — практично завжди погана ідея. Так навіщо нам ще один лисп? Тим більше, що вже є 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 'P';}
"Е" {return 'E';}
<<EOF>> {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;}
;

насправді, все дуже просто, тут ми говоримо, що "е" (expression) може бути сумою двох виразів:
: e '+' e
{$$ = $1 + $3;}
...

З цього приклад вже видно, що кожне наше визначення будь-якої нової синтаксичної конструкції може бути рекурсивным. В даному випадку, ми говоримо, що expression може бути записаний так: expression + expression. Зустрічаючи таку конструкцію, парсер буде її токенезировать і потім виконувати код, який знаходиться в фігурних дужках: { $$ = $1 + $3}. Це звичайний JS код. Незвичайні тут тільки змінні, якими ми оперуємо: $$, $1, $3.
Давайте розбиратися. $$ — це результат вираження, тобто те, що буде передано далі по дереву розбору. $1 — перший елемент конструкції, на прикладі запису "10 + 10", $1 — це число 10. $3 — це третій елемент конструкції. Другим елементом був би '+', але так як сам по собі він нам не потрібен, ми просто пропускаємо його і виконуємо додавання двох змінних з подальшим збереженням результату в $$.
Далі йдуть інші pattern'и конструкції "е". Перший pattern завжди записується через ":", наступні — через "|", в кінці ставиться ";".

%start expressions

%% /* language grammar */

expressions
: e EOF
{return $1;}
;

Ось тут ми говоримо, що весь розбір почнеться з pattern'a expressions, який в свою чергу представляє одне будь-яке вираз "е" і кінець файлу. У фігурних дужках тут нам потрібно повернути результат всього розбору. В даному випадку це буде результат одного виразу.
Переходимо до написання 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 ')'
<<EOF>> 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 ')'
<<EOF>> 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.
Якщо вам цікава ця тим, то я можу перетворити це в невеликий цикл статей, де б розповів і показав, як можна довести мову хоча б того стану, в якому він представлений за посиланням вище

Джерело: Хабрахабр
  • avatar
  • 0

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.