前記事で解説したプログラムは，

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を渡して作成します．

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）」があります。識別子を使ったコードは後の回で登場します。

	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にあります。

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

parseApplication

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

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に入れる¹
- )（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メソッド内です。

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を使って、オブジェクトの中身をすべて表示してみましょう。

    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)を構文木として表現したものです。

次回は、コードの生成と、それに必要な実行時ライブラリについてみて行きます。

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