JavaScriptで関数型言語を作ろう(2)

[前記事](https://qiita.com/hoge1e3/items/814bc0c5b55fa24c6168)で解説したプログラムは，

~~~test/single.txt
3.add(2).add(10)
~~~
というプログラムに対して

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

という結果を出力しました．

前回最後に解説した「字句解析」では，`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] 1
10:[rpar] )
~~~

↑の出力では字句を`[種類] 内容`という形式で表示しています．これらはプログラムからは`Token`オブジェクトでアクセスします。「種類」を`type`，「内容」を`text`というプロパティでアクセスできます．なお、`Token`オブジェクトは`lib/TreeTypes.ts`内で定義されています。

# 構文解析

今回は，前回のプログラム(`index.ts`)の★Bで出力されている↓の部分を生成しているプログラム`lang/MyParser.ts`についてみて行きます．

~~~
Call {
  left:
   MemberAccess {
     left: Call { left: [MemberAccess], args: [Array] },
     name: Identifier { text: 'add' } },
  args: [ NumberLiteral { value: 1 } ] }
~~~


~~~lang/MyParser.ts
import Parser from '../lib/Parser';
import { ValueExpression, NumberLiteral, Identifier, Call, MemberAccess } from './Expressions';
import { Token } from '../lib/TreeTypes';

export default function MyParser(tokens:Token[]){
	const parser:Parser=new Parser(tokens);//★E
	function parse() {
		try {
			const res=parseExpression();
			if (!parser.eot()) throw parser.parseError("Not EOF");
			return res;
		} catch (e) {
			if (parser.maxParseError) throw parser.maxParseError;
			else throw e;
		}
	}
	function parseExpression():ValueExpression {
		return parseApplication();
	}
	function parseElement():ValueExpression {
        if (parser.nextTokenIs("number")) return parseNumberLiteral();
        if (parser.nextTokenIs("identifier")) return parseIdentifier();
		throw parser.parseError();
	}
	function parseApplication():ValueExpression {
		let res=parseElement();
        while(true) {
            if (parser.nextTokenIs("lpar")) {
        		parser.readToken("lpar");
        		const args:ValueExpression[]=[parseExpression()];
        		parser.readToken("rpar");
        		res=new Call(res, args);
            } else if (parser.nextTokenIs("dot")) {
                parser.readToken("dot");
        		const ident=parseIdentifier();
        		res=new MemberAccess(res, ident);
            } else break;
        }
		return res;
	}
	function parseNumberLiteral():NumberLiteral {
		const t=parser.readToken("number");
		return new NumberLiteral(parseFloat(t.text));
	}
	function parseIdentifier():Identifier {
		const t=parser.readToken("identifier");
		return new Identifier(t.text);
	}
	return {parse};
}
~~~

## Parserの作成

Parser(`lib/Parser.ts`)は構文解析を行うための基本的な機能を提供します．トークンの配列`tokens`を渡して作成します．

~~~typescript
const parser:Parser=new Parser(tokens);//★E
~~~

`Parser`には次のメソッドがあります．

- `parser.eot()` トークンの最後まで読み終わっていれば`true`
- `parser.nextTokenIs(type)` 次に読めるトークンの種類が`type`であれば`true`．（トークンの最後まで読み終わっている場合は`false`）
- `parser.readToken(type)` 次に読めるトークンの種類が`type`であればそのトークンを読み進め，そのトークンを`Token`オブジェクトとして返す．トークンの種類が`type`でなければ`ParseError`を投げる
- `parser.parseError(message?)` `ParseError`(構文解析エラー)を投げる．

`lang/MyParser.ts`には，parse****という関数がいくつか定義されています．

## parseExpression 

`parseExpression`は日本語にすると「式を構文解析する」という意味です．この連載で作る言語は，プログラム本体は１つの式で表されます（え，2つ以上の計算をしたかったらどうするの，という話はこの後詳しくやっていきます）

で、parseExpressionは今のところparseApplicationを呼んでいるだけなので、次へ。

## parseApplication

Applicationと言っても、スマホアプリとかのアレとはあまり関係なくて、ここでは「適用」と訳してください。このネーミングがいいのかどうかは微妙です。
適用とはどういうことかというと、JavaScriptでおなじみの

~~~
object.x
~~~

という式における `.x` の部分が、`object`に対して、`.x`という動作（プロパティ`x`を読み出す）を「適用」しています。

また、

~~~~
f(x)
~~~~

という式は、`f`という関数オブジェクトに対して、`(x)`という動作（`(x)`を引数として関数を呼び出す）を「適用」しています。

また、これらを組み合わせて

~~~
object.f(x)
~~~
という式もよく見かけますが、これは、`object`に対して、`.f`という動作を「適用」して、それによって読み出された関数オブジェクトに対して`(x)`を「適用」する、というように、適用を複数回行う場合もあります。

先ほどから出ているこの式は

~~~test/single.txt
3.add(2).add(10)
~~~

`3`に対して、`.add`、`(2)`、`.add`、`(10)`を順に適用したことになります。

さて、parseApplicationの中身を見てみよう……と思いましたが、結構複雑なので、まずは先頭の`3`の部分に注目しましょう。

## parseElement

式の先頭部分、`3`の部分は「要素(Element)」と呼んでいます。要素には`3`のような「数値定数（NumberLiteral）」と、`a`のような「識別子（Identifier）」があります。識別子を使ったコードは後の回で登場します。

~~~ts
	function parseElement():ValueExpression {
        if (parser.nextTokenIs("number")) return parseNumberLiteral();
        if (parser.nextTokenIs("identifier")) return parseIdentifier();
		throw parser.parseError();
	}
~~~
ここの処理では、次に読もうとしているトークンの種類がnumberかidentiferであればそれぞれの処理に移動し、それ以外だったらエラー（構文解析エラー：ParseError）を投げます。

## parseNumberLiteral

ここでは、数値定数のトークンを読み込み、「式」を表すオブジェクトの1つ、`NumberLiteral`オブジェクトを生成します。このオブジェクトの定義は`lang/Expressions.ts`にあります。

~~~ts
function parseNumberLiteral():NumberLiteral {
    const t=parser.readToken("number");
    return new NumberLiteral(parseFloat(t.text));
}
~~~


## parseApplication

さて、parseApplicationを改めてみてみましょう。★Fで、先述の要素（Element）を解析しています。

~~~ts
function parseApplication():ValueExpression {
		let res=parseElement();//★F
        while(true) {
            if (parser.nextTokenIs("lpar")) {//★G
        		parser.readToken("lpar");
        		const args:ValueExpression[]=[parseExpression()];
        		parser.readToken("rpar");
        		res=new Call(res, args);
            } else if (parser.nextTokenIs("dot")) {//★H
                parser.readToken("dot");
        		const ident=parseIdentifier();
        		res=new MemberAccess(res, ident);
            } else break;
        }
		return res;
	}
~~~

その後、次の処理を`while(true) ... `で繰り返していきます。

- ★G：次に読めるのが`(`（lpar）なら、
   - `(`を読み
   - 「式」を読む（「式」は、最初に解説したparseExpressionを再帰呼び出しして解析）、読んだ結果を配列`args`に入れる[^1]
   - `)`（rpar）を読む
   - これまで生成した式と`args`を使って、Callオブジェクトを生成
- ★H：次に読めるのが`.`（dot）なら、
   - `.`を読み
   - 識別子（Idenfifier)を読む
   - これまで生成した式と識別子を使って、MemberAccessオブジェクトを生成
- それ以外のトークンが読めたら、繰り返しを終える

Call、MemberAccessは、NumberLiteralと同様`lang/Expressions.ts`に定義されている、式を表すオブジェクトです。

もう一度、`index.ts`の★Bの出力結果を確認すると、Callや、MemberAccessというオブジェクトが生成されているのがわかります。

~~~
Call {
  left:
   MemberAccess {
     left: Call { left: [MemberAccess], args: [Array] },
     name: Identifier { text: 'add' } },
  args: [ NumberLiteral { value: 1 } ] }
~~~

# 理解度チェック

上の表示では、オブジェクトの階層が深くなると中身が表示できていません。表示を行っているのは、`index.ts`の`run`メソッド内です。

~~~ts
function run(src:string) {
    const t=MyTokenizer(src);
    const tokens=t.tokenize();
    tokens.forEach((token,i)=>console.log(`${i}:[${token.type}] ${token.text}`));
    const p=MyParser(tokens);
    const tree=p.parse();
    console.log(tree); // ←ここ
    //....(後略)
}
~~~

`console.log`の代わりに`console.dir`を使って、オブジェクトの中身をすべて表示してみましょう。

~~~ts
    console.dir(tree, {depth:10});
~~~

次のように、`test/single.txt`の中身を書き換えて、表示がどのように変化するか確認してみましょう。（それぞれ、前に書いた中身を消してから書いてください。複数の式を書くとエラーになります）

- `3`
- `3.add`
- `3.add(2)`
- `3.add(2).add`
- `3.add(2).add(10)`
- `3.add(2).add(10).add(20)`
- `3.add(2.add(10))`

また、これらの表示を下のような図で表現してみましょう。このような図のことを、本連載では「構文木」と呼びます。下図は`3.add(2)`を構文木として表現したものです。

![2021-02-19_22h24_47.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/127248/711e8db1-0e00-2cb9-83e1-d6515aff75b6.png)

[次回](https://qiita.com/hoge1e3/items/5f1ec29732b130d68ee7)は、コードの生成と、それに必要な実行時ライブラリについてみて行きます。

[^1]: この段階では、引数が1つしか使えません。しばらく引数が1つの関数しか出てこないので、必要になったら実装を追加します。