JavaScriptでLispを書く

まず、簡単な質問をする必要があります。何のために？

独自のプログラミング言語を書くことは、ほとんど常に悪い考えです。 それでは、なぜ別のLispが必要なのでしょうか？ さらに、ClojureScriptが既にあります。これは現在生産準備が整っており、多くの優れた機能を備えています。 ClojureScriptでさえ競争するのはおかしいです-TypeScript、CoffeeScriptなどについて話していない しかし、これには言語が必要です！

まず、それらが一般的にどのように書かれているかを理解したいと思います。 さらに、「プログラミング」言語を記述する必要はありません。多くの場合、テキスト、構成などをマークアップするために独自の言語を記述するタスクがあります。 これはすべて同様の方法で解決できます。

始めましょう

そもそも、プログラミング言語は、構文が特定の規則に従う形式化された言語であることに同意します。 これらのルールを解析するには、どのような種類の「単語」（つまり言語の単位）を満たすことができるかを知る必要があります。 通常の意味での単語ではなく、句読点、数字、文字列などです。

たとえば、私たちの言語では、このような構成が発生する場合があります。

(+ 2 3)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

少なくとも4つの「単語」が使用されています。 各単語は、いわゆるトークンです。 そして最初に、テキストをこれらのトークンに分割する必要があります。 ソースコードをトークンに分割するプロセスは、トークン化と呼ばれます。 詳細を掘り下げるまで、先に進みましょう。 すべてのテキストをトークンに分割し、抽象構文ツリー（AST）を取得するためにこれらすべてのトークンを解析する必要があると想像してください。 これを行うには、受信したトークンのシーケンスを処理できるパーサーを作成する必要があります。 繰り返しますが、詳細に入ることなく、次のステップであるコンパイル/翻訳に進みましょう。 次に、ASTをマシンコードに変換するか、別の言語に翻訳する必要があります。 この場合、ASTからJSへのトランスレーターを作成します。

トークナイザー、パーサー、およびトランスレーターの作成はそれほど簡単なタスクではなく、そのようなツールの必要性は歴史的に非常に頻繁に発生するため、賢明な人々はこのタスクを簡素化するレクサーおよびパーサージェネレーターを開発しました。 そのようなジェネレーターの1つがBisonです。 しかし、私たちはJSでlispを書くので、JS税を使用します-Jison

ポイントに行きましょう

Jisonパーサージェネレーターは非常に使いやすいです。Grunt、gulp、webpackプラグインがあり、すべての.jisonを既製のパーサーを既に含むJSファイルに変換できます。 grunt / gulp / webpackに基づいてプロジェクトを編成する方法についてはここでは説明しません。 オンラインパーサージェネレーターhttp://zaa.ch/jison/try/を使用します。

jison Webサイトにある電卓の例から始めましょう。

  /* 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';} <<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;} ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このファイルの最初の部分のコメント/ 字句文法 /の後に、言語のすべての「単語」の説明があります。 ここで、数字の決定方法を見ることができます（はい、トークンは正規表現で決定できますが、これは常に良いとは限りません。より単純なトークンの組み合わせを使用して高レベルトークンを決定する方がよい場合もあります）。 算術演算のトークンもあります：加算、乗算、減算、除算。

文法のテキスト全体をオンラインジェネレーターにコピーし、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」（式）は2つの式の合計になります。

  : e '+' e {$$ = $1 + $3;} ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この例から、新しい構文構造の定義はそれぞれ再帰的であることがすでにわかりました。 この場合、式は式+式のように記述できると言います。 このような構造に遭遇すると、パーサーはそれをトークン化し、次に中括弧内のコードを実行します：{$$ = $ 1 + $ 3}。 これは通常のJSコードです。 ここで異常なのは、操作する変数のみです：$$、$ 1、$ 3。

正しくしましょう。 $$は式の結果、つまり解析ツリーに渡されるものです。 $ 1は最初の構造要素です。たとえば、レコード「10 + 10」、$ 1は数字の10です。$ 3は3番目の構造要素です。 2番目の要素は「+」ですが、それ自体は必要ないため、単純にスキップして2つの変数の追加を実行し、結果を$$に保存します。

以下は、e構造の他のパタ​​ーンです。 最初のパターンは常に「：」で記述され、後続のパターンは「|」で記述され、最後に「;」が書き込まれます。

 %start expressions %% /* language grammar */ expressions : e EOF {return $1;} ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、分析全体がpattern'a式で始まり、これが任意の1つの式「e」とファイルの終わりを表すと言います。 中かっこでは、ここで分析全体の結果を返す必要があります。 この場合、1つの式の結果になります。

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;} ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、2つの数字を追加できる文法全体ですが、2つの数字を追加すると...これはどうにかして十分ではありません。 しかし、Lisp 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 : NUMBER { $$ = +$1}} ; values : value { $$ = [$1] } | values value { $$ = $1.concat($2)} ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、値は1つまたはN個の連続した値です。 同時に、valuesの値は1つの値の配列であり、すでに値は配列の前の値と後続の各値の結合であると言います。

値を解析した結果、数値の配列を取得します。そのために、reduceを実行してすべての数値の合計値を取得します。 今の操作：

 ( + 1 2 3 4 5)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

15を返します。

おめでとうございます！ あなたと私は、最初で最も簡単なLispの構築を書きました。 減算、乗算、除算を実装することも難しいことではないと思います。 当然、1つの記事のフレームワーク内では、すべての言語の開発プロセスを説明することはできません。 このトピックに興味がある場合は、次のリンクにアクセスしてください ： https : //github.com/daynin/tiny-lisp

これは、LispがJSで開発されたJisonの助けを借りたプロジェクトのリポジトリです。 既に多くのことが実装されていますが、それでもなお、これは非常に小さなプロジェクトです。 言語の開発を試してみたい場合は、このプロジェクトが最適です！

PS

このトピックに興味がある場合は、それを小さな記事シリーズに変えて、少なくとも上記のリンクで提示されている状態に言語をもたらす方法を教えて示すことができます