【第3回】インタプリタを作ってみよう 2

はじめに

前回までは字句解析と構文解析を実装しました。今回は、残りの構文解析と評価を行う処理を実装し、最後にプログラム全体を実行するCLIを作成します。

デモ

今回もデモ形式で自分が手を動かしながら進めていきます。全てコードを貼ると長くなりますので、コミットを見ながら進めていきましょう。

字句解析

前回の字句解析で、改行（このプログラムにおけるデリミタ）をlexするのを忘れていたので、修正します。単純に改行をスキップせずにEOL(End Of Line)としてトークンを生成するようにしてあげます。

構文解析

前回、構文解析の一部を実装しましたが、残りの構文解析を実装します。

ブロックの構文解析

{ VAR a = 1 } のようなブロックの構文解析を行います。

テストはこんな感じです

it("should parse block statement", () => {
  const input = "{ VAR a = 1 }";
  expect(parse(lex(input))).toEqual({
    type: "Program",
    body: [
      {
        type: "BlockStatement",
        body: [
          {
            type: "VariableDeclaration",
            identifier: "a",
            value: {
              type: "IntegerLiteral",
              value: 1,
            },
          },
        ],
      },
    ],
  });
});

文をパースする処理をBlock内でもProgram内でも使いたいので共通化しています。

ブロックはLBRACEからRBRACEまでの文の集まりなので、parseBlockというStatement[]を返す関数を作りました。

IF文の構文解析

IF文の構文解析を行います。

テストはこんな感じです

describe("should parse if statement", () => {
  it("with if only", () => {
    const input = "IF a < b { a + b }";
    expect(parse(lex(input))).toEqual({
      ...
    });
  });

  it("with if and else", () => {
    const input = "IF a < b { a + b } ELSE { a - b }";
    expect(parse(lex(input))).toEqual({
      ...
    });
  });
});

IF文とIF/ELSE文の構文解析を行います。

IF文の条件式で使う<や>,==,!=などの演算子のパースも実装しています。 parseIfStatementでは、IFの後に条件式、{の後にブロック、ELSEがあればELSEの後にブロックをパースしています。

そして、ELSEがある時とない時でalternateがあるかないかで構文木を仕分けて表現しています。

追加でいくらかテストケースを書いておきます。

評価

さて、これから「評価」という処理を実装していきます。評価は構文解析で作った構文木を辿りながら、実際に計算を行う処理です。これまではただのデータ構造を作っていただけでしたが、ここからが本番です。挙動を確認しながら進めていきましょう。

とりあえずTDDのセットアップをします。

import { evaluate } from "./evaluator";
import { describe, it, expect } from "vitest";
import { parse } from "./parser";
import { lex } from "./lexer";

describe("evaluate", () => {
  it("should evaluate integer literal", () => {
    const input = "1";
    expect(evaluate(parse(lex(input)))).toEqual(1);
  });
});

まずは1という整数リテラルを評価するテストを書きます。このプログラムでは整数リテラルも式という扱いなので、1を評価すると1が返ってくることを期待します。

import { Program } from "./parser";
export const evaluate = (program: Program): number => {
  return 0;
};

まだ何も実装していないので、もちろんテストは失敗します。

スコープ

まずはスコープを実装します。これがないと後に変数の束縛ができません。

Envという型をRecord<string, number>として定義します。これは変数名をキーにして変数に格納された値を取得できるようにするための型です。

type Env = Record<string, number>;

そして、evaluateProgram関数を実装します。

export const evaluateProgram = (program: Program, env: Env): number => {
  return 0;
};

前回作ったAST(Program)と環境(Env)を受け取り、評価を行う関数です。

これをevaluate関数で使います。

export const evaluate = (program: Program): number => {
  const env: Env = {};
  return evaluateProgram(program, env);
};

これで準備OKです。このEnvは後で変数宣言の際に使います。

整数リテラルの評価

次に整数リテラルの評価を実装します。 evaluateProgram関数にはもちろん大域のProgramが渡されますが、ASTの通りProgramは複数の文を持つことができる構造になっています。

const evaluateStatement = (statement: Statement, env: Env): number => {
  switch (statement.type) {
    case "ExpressionStatement":
      return evaluateExpression(statement.expression, env);
    default:
      throw new Error(`Unknown statement: ${statement}`);
  }
};

evaluateStatement関数は文を評価する関数です。今回は式文(整数リテラル)しかないので、ExpressionStatementの場合はevaluateExpression関数を呼び出します。

const evaluateExpression = (expression: Expression, env: Env): number => {
  switch (expression.type) {
    case "IntegerLiteral":
      return expression.value;
    default:
      throw new Error(`Unknown expression: ${expression}`);
  }
};

evaluateExpression関数は式を評価する関数です。

これで整数リテラルの評価ができるようになりました。

ちなみにプログラムが空の場合は0を返すようにしています。

四則演算式の評価

次に四則演算式の評価を実装します。

このようなテストが通ることを期待します。

it("should evaluate addition expression", () => {
  const input = "1 + 2";
  expect(evaluate(parse(lex(input)))).toEqual(3);
});

it("should evaluate complex expression", () => {
  const input = "2 / 4 + 2 * 3 / 4 - 1";
  expect(evaluate(parse(lex(input)))).toEqual(1);
});

Expressionに四則演算処理を書くだけです。+と-, *, /の演算順序はASTがすでにその構造になっているので、それに従ってDFSのように再起的に左辺と右辺の式を評価していきます。

実装は下のコミットを見てください。

変数の評価

次に変数の宣言および使用を実装します。なおこのプログラムには変数の再代入はありません。

このようなテストが通ることを期待します。

it("should evaluate variable declaration", () => {
  const input = "VAR a = 1";
  expect(evaluate(parse(lex(input)))).toEqual(1);
});

it("should evaluate variable assignment and usage", () => {
  const input = `
VAR a = 1
a
`.trim();
  expect(evaluate(parse(lex(input)))).toEqual(1);
});

it("should evaluate variable assignment and use in expression", () => {
  const input = `
VAR a = 1
VAR b = 2
a + b
`.trim();
  expect(evaluate(parse(lex(input)))).toEqual(3);
});

これも実装はめちゃくちゃ簡単で、ASTを走査する途中で宣言式が出てきたら、その変数名をキーにして値を環境Envに格納しておきます。

さらに式中に変数が出てきたら、その変数名をキーにして環境から値を取り出して使います。これだけです。

実はこれだけでスコープの実装ができています。なぜなら、より深いスコープで変数宣言があるときは、そのスコープ内でのみ変数が上書きされるからです。

IF文の評価

最後にIF文の評価を実装します。

it("should evaluate complex if-else statement", () => {
  const input = `
VAR a = 1
VAR b = 2

IF a < b {
a + b
} ELSE {
a - b
}
`.trim();
  expect(evaluate(parse(lex(input)))).toEqual(3);
});
});

最初に目標に掲げたこのテストが通ることを期待します。

実装は下のコミットを見てください。

比較演算を実装して、trueなら1, falseなら0を返すようにしています。

そして、IF文の条件式を評価して、条件によってconsequentかalternateかを評価します。

これで全てのテストが通るはずです。

CLIの作成

最後にCLIを作成します。

@types/node と typescript をインストールします。

npm install --save-dev typescript @types/node

そしてファイルからソースコードを読んで実行するpythonのようなCLIを作成します。

名前は Let's Make an Interpreter の頭文字をとって lmai とします。

これで最後にビルドしてリンクします。

npm run build
npm link

こうすることでローカルで lmai コマンドが使えるようになります。

lmai <filepath>

では、実際にCLIを使ってみましょう。

test.lmai

VAR a = 1
VAR b = 2

IF a < b {
  a + b
} ELSE {
  a - b
}

lmai test.lmai

これで 3 が返ってくれば成功です。長い間おつかれさまでした。

おわりに

今回は簡単なインタプリタ作りを通して意外と単純な仕組みでプログラミング言語が作れるだということを感じてもらえたらという目的で取り組んでみましたが、いかがでしたでしょうか。

プログラミング言語は非常に複雑なものですが、基本的な構文解析と評価の仕組みを理解することで、プログラミング言語の仕組みが少しでも身近に感じられたらと思います。

また、今回の記事は非常に簡単なインタプリタを作成しましたが、実際のプログラミング言語はもっと複雑で、例えば変数の再代入や参照・コピー、関数の定義や呼び出し、クロージャ、クラスやオブジェクト指向、型システム、例外処理、モジュールシステム、並行処理、Language Serverなどなど、やることは山ほどあります。

ぜひこの作ったインタプリタをベースに、自分だけのプログラミング言語を拡張して作ってみたり、よりパフォーマンスを追求してコンパイル言語で書き直してみたりして色々挑戦してみてください。