JavaScriptで関数型言語を作ろう(1) － 字句解析

唐突に始まりました．

普段はゲームエンジン[Tonyu System](https://qiita.com/hoge1e3/items/727caca153914e702cb8)を作ってたりします．Tonyuは変数に型づけがないので，一度は型のある言語を作りたいと思っているので，作ってみます．どうせ作るなら純粋関数型言語がいいな，と思って始めます．

一応，これくらいの機能はつける予定です．これらの概念が「何？」という方もその都度説明していくつもりです．

- レコード型
- 共用体
- 高階関数
- 遅延評価
- ジェネリクス
- 入出力

# 対象読者

- Java/C/JavaScript/TypeScriptなどの「手続き型」プログラミングはある程度経験がある方
- 開発環境（node.js，各種エディタ）のインストールが自力で行える方
- 関数型言語は触っていなくてもOKです．関数型特有の機能はその都度解説します．

# とりあえず動かしてみよう

まず，こちらにあるサンプルを動かしてみてください．

https://github.com/hoge1e3/tinyfunc/releases/tag/single-2

動かすのに必要な環境は次のものです．インストール方法は各自調べてください．

- node.js / npm
- TypeScript

zipファイルをダウンロード＆解凍したら，解凍したフォルダでコマンドラインを開き，次を実行します．

```shell
npm install
```

TypeScriptをコンパイルします

```shell
tsc
```
コンパイルできたら，次のコマンドで実行を行います．

```shell
node index.js test/single.txt
```

こんな出力が得られます．

```
0:[number] 3
1:[dot] .
2:[identifier] add
3:[lpar] (
4:[number] 2
5:[rpar] )
6:[dot] .
7:[identifier] add
8:[lpar] (
9:[number] 10
10:[rpar] )
Call {
  left:
   MemberAccess {
     left: Call { left: [MemberAccess], args: [Array] },
     name: Identifier { text: 'add' } },
  args: [ NumberLiteral { value: 10 } ] }

    const {Num}=runtime;
    return Num(3).add(Num(2)).add(Num(10));

{ value: 15, add: [Function: add] }
```

# 何が起きたのか？

まず，コマンドライン上にあった`test/single.txt`の中身を確認しましょう．

```test/single.txt
3.add(2).add(10)
```
ここの数字を書き換えてみて，もう一度`node index.js test/single.txt`
を実行すると，`{ value: 15, add: [Function: add] }`の15の値が変更されて出力されると思います．

次に，index.tsの中身を見てみましょう．★A~★Dは付け加えたものです．

```index.ts
import * as fs from "fs";
import MyTokenizer from "./lang/MyTokenizer";
import MyParser from "./lang/MyParser";
import { generate } from "./lang/CodeGen";
import * as runtime from "./lang/runtime";
import { ParseError } from "./lib/TreeTypes";
for (let i=2;i<process.argv.length;i++) {
    test(process.argv[i]);
}
function test(srcFile:string) {
    const src=fs.readFileSync(srcFile,{encoding:"UTF-8"});
    try {
        run(src);
    }catch(e) {
        if (e instanceof ParseError) {
            const r=e.pos;
            console.log(src.substring(0,r.start)+">>>>"+src.substring(r.start,r.end)+"<<<<"+src.substring(r.end));
            console.log("Parse Error:", e.message);
        } else {
            console.error(e);
        }
    }
}
function run(src:string) {
    const t=MyTokenizer(src);
    const tokens=t.tokenize();
    //★A
    tokens.forEach((token,i)=>console.log(`${i}:[${token.type}] ${token.text}`));
    const p=MyParser(tokens);
    const tree=p.parse();
    //★B
    console.log(tree);
    const js=`
    const {Num}=runtime;
    return ${generate(tree)};
    `;
    //★C
    console.log(js);
    const func=new Function("runtime", js);
    const res=func(runtime);
    //★D
    console.log(res);
}
```

#　流れ
##　字句解析

★A（`tokens.foreach...`）で出力している内容は次の部分です：

```
0:[number] 3
1:[dot] .
2:[identifier] add
3:[lpar] (
4:[number] 2
5:[rpar] )
6:[dot] .
7:[identifier] add
8:[lpar] (
9:[number] 1
10:[rpar] )
```

これは，

```test/single.txt
3.add(2).add(10)
```
の中身を「字句」という単位に分けています．これを字句解析といいます．

字句解析のプログラムは`lang/MyTokenizer.ts`にあります．

```lang/MyTokenizer.ts
import Tokenizer from "../lib/Tokenizer";
import {Token} from "../lib/TreeTypes";

export default function MyTokenizer(src:string) {
    const tokenizer:Tokenizer=new Tokenizer(src);
    function tokenize():Token[] {
        const tokens:Token[]=[];
        while(true) {
            tokenizer.skip(/^\s*/);
            if (tokenizer.eof()) return tokens;
            const token=
                tokenizer.read("number",/^[0-9]+/) ||
                tokenizer.read("lpar",/^\(/) ||
                tokenizer.read("rpar",/^\)/) ||
                tokenizer.read("dot",/^\./) ||
                tokenizer.read("comma",/^,/) ||
                tokenizer.read("identifier",/^[A-Za-z]+/) ||
                undefined;
            if (!token) throw new Error("Tokenizer error while reading "+tokenizer.head());
            else tokens.push(token);
        }
    }
    return {tokenize};
}
```

`const tokenizer:Tokenizer=new Tokenizer(src);`で`tokenizer`（字句解析器）を作成します．Tokenizerの中身は`lib/Tokenizer.ts`にありますが，中身は各自ご覧ください．ここでは，ここで使われている3つのメソッドの使い方がだけ見ておきましょう．

- `tokenizer.skip(reg)` 現在の解析位置から，正規表現`reg`に一致するパターンを読み飛ばす
- `tokenizer.read(type, reg)` 現在の解析位置から，正規表現`reg`に一致するパターンが見つかればトークン（字句）を返す．返された`Token`オブジェクトのプロパティ`type`に指定した`type`の値が入る．パターンが見つからなければ`undefined`を返す．
- `tokeninzer.eof()` 現在の解析位置が文字列の最後なら`true`

`/^[0-9]+/`や`/^\(/`などが正規表現です．詳細については各自調べてみてください．

今後，扱う字句の種類が増えるときには，このファイルの

~~~typescript
tokenizer.read("number",/^[0-9]+/) ||
tokenizer.read("lpar",/^\(/) ||
tokenizer.read("rpar",/^\)/) ||
tokenizer.read("dot",/^\./) ||
tokenizer.read("comma",/^,/) ||
tokenizer.read("identifier",/^[A-Za-z]+/) ||
~~~
の部分に追加してもらう場面が出てきます．

長くなってしまったので，今回は字句解析の部分だけで一旦終わります．
残りのステップはこんな感じで，次回以降見ていきます．

- [構文解析](https://qiita.com/hoge1e3/items/c4d4e9fcab85ccb485f2)（★Bの出力結果）
- コード生成（★Cの出力結果）：[その1](https://qiita.com/hoge1e3/items/5f1ec29732b130d68ee7) 
- 実行（★Dの出力結果）

# 理解度チェック

- このファイルの適当なところにスペースや改行を入れてみましょう．
    - 字句解析の結果が変化しないのは，どこにスペースを入れた場合になるでしょう．
    - 字句解析の結果が変化するのは，どこにスペースを入れた場合になるでしょう．（なお，字句解析の結果が変化すると大抵エラーが出ます）

```test/single.txt
3.add(2).add(10)
```
- 今度は，スペース以外の文字もでたらめに入れてみましょう．多分エラーが出ると思います．そのときエラーが次の2種類あることに気づくと思います．これらのエラーの違いは何か考えてみましょう
    - `Tokenizer error`
    - `Parse Error`


[次記事](https://qiita.com/hoge1e3/items/c4d4e9fcab85ccb485f2)