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

はじめに

今回はインタプリタづくりを通して、プログラミング言語がどのような仕組みで実装されて、どのように動作するのかを学びます。

インタプリタとは

インタプリタはプログラムを逐次実行するプログラムです。コンパイラとは異なり、コンパイル後のバイナリを生成せずに、プログラムをそのまま実行します。

身近な例としては、PythonやRuby、JavaScriptなどのスクリプト言語があります。これらの言語は、プログラムを実行するためにインタプリタが必要です。

流れ

インタプリタを含むプログラミング言語処理系全般は、一般的に以下のような流れで動作します。

字句解析（Lexical Analysis）
構文解析（Parsing）
評価（Evaluation）

出てくる用語の説明

簡単に先に出てくる用語について説明します。

文法、プログラムの構造に関する用語

演算子: 式で実行する計算の種類を指定する記号やシンボルのこと。たとえば、+、-、*、/ などがあります。
変数: プログラム中で値を保持するための箱のこと。変数には名前がついており、その名前を使って値を取り出すことができます。a = 1 の場合、a が変数で、1 が値です。
値: プログラム中で扱うデータのこと。たとえば、1、2、"Hello, World!" などがあります。
式: 値や演算子を組み合わせて計算するための構造のこと。たとえば、1 + 2、a + b などがあります。
文: IF文やFOR文など、プログラムの流れを制御するための構造のこと。たとえば、IF a < b { a + b } ELSE { a - b } などがあります。
ブロック: {} で囲まれた文の集まりのこと。たとえば、{ a + b } など。

デモ

今回は、簡単な四則演算と変数宣言、IF文をサポートするプログラミング言語を作成します。以下のようなプログラムを実行できるようにします。

VAR a = 1
VAR b = 2
IF a < b {
  a + b
} ELSE {
  a - b
}

一番最後の式の結果が出力されるプログラムです。このプログラムを実行すると、3 が出力されるはずです。

今回は、TypeScriptを使用して実装します。実装リポジトリはこちらです、ぜひ参考にしてください。

字句解析

字句解析は、プログラムをトークン（トークンとは、プログラムの最小単位）に分割する処理です。たとえば、以下のプログラムを字句解析すると、[INT(1), PLUS, INT(2), EOF] のようなトークン列が得られます。

1 + 2

このように、文字を意味のある単位に分割することで、後に行う構文解析を容易にします。

まずは、どんなトークンを定義するかを考えます。今回は、以下のようなトークンを定義します。

値
- 整数値: INT
演算子
- 足し算: PLS
- 引き算: MIN
- 掛け算: MUL
- 割り算: DIV
比較演算子
- 小なり: LT
- 大なり: GT
- 等しい: EQ
- 等しくない: NE
キーワード
- IF: IF
- ELSE: ELSE
- 変数: VAR
その他
- 終端: EOF
- 代入: ASSIGN
- ブロック開始: LBRACE
- ブロック終了: RBRACE
- 識別子: IDENTIFIER

デモで最初に紹介したプログラムを字句解析すると、以下のようなトークン列が得らることを目指します。

[VAR, IDENTIFIER("a"), ASSIGN, INT(1), VAR, IDENTIFIER("b"), ASSIGN, INT(2), IF, IDENTIFIER("a"), LT, IDENTIFIER("b"), LBRACE, IDENTIFIER("a"), PLS, IDENTIFIER("b"), RBRACE, ELSE, LBRACE, IDENTIFIER("a"), MIN, IDENTIFIER("b"), RBRACE, EOF]

なんとか読める形になりましたね。

じゃあこれを元にまずはトークンを定義していきましょう。識別子として使うENUMと、それを使ったトークンの型を定義します。数値や変数宣言などの値を持つトークンにはそれに対応できる value プロパティを持たせます。

export enum TokenType {
  INT = "INT",
  PLS = "PLS",
  MIN = "MIN",
  MUL = "MUL",
  DIV = "DIV",
  LT = "LT",
  GT = "GT",
  EQ = "EQ",
  NE = "NE",
  IF = "IF",
  ELSE = "ELSE",
  VAR = "VAR",
  EOF = "EOF",
  ASSIGN = "ASSIGN",
  LBRACE = "LBRACE",
  RBRACE = "RBRACE",
  IDENTIFIER = "IDENTIFIER",
}

export type Token =
  | { type: TokenType.INT; value: number }
  | { type: TokenType.PLS }
  | { type: TokenType.MIN }
  | { type: TokenType.MUL }
  | { type: TokenType.DIV }
  | { type: TokenType.LT }
  | { type: TokenType.GT }
  | { type: TokenType.EQ }
  | { type: TokenType.NE }
  | { type: TokenType.IF }
  | { type: TokenType.ELSE }
  | { type: TokenType.VAR }
  | { type: TokenType.EOF }
  | { type: TokenType.ASSIGN }
  | { type: TokenType.LBRACE }
  | { type: TokenType.RBRACE }
  | { type: TokenType.IDENTIFIER; value: string };

export function lex(input: string): Token[] {
  return [];
}

ついでに lex 関数を定義しておきましたが、中身はまだ空にしています。

今回は実装しやすさを求めてTest-Driven Development（TDD）を採用します。簡単に言うと、テストを先に書いてから実装を行う手法です。

一番最初に、簡単なテストを書いてみましょう。

import { TokenType, lex } from "./lexer";
import { describe, it, expect } from "vitest";

describe("lexer", () => {
  it("should parse variable declaration", () => {
    const input = "VAR a = 1";
    expect(lex(input)).toEqual([
      { type: TokenType.VAR },
      { type: TokenType.IDENTIFIER, value: "a" },
      { type: TokenType.ASSIGN },
      { type: TokenType.INT, value: 1 },
      { type: TokenType.EOF },
    ]);
  });
});

こうなるべきという期待値を expected に定義して、 lex 関数に input を渡して返ってきた値が expected と一致するかを expect 関数で確認しています。

当然の如く空の配列が返ってくるので、このテストは失敗します。

npm run test

次に、このテストを通すように lex 関数を実装していきます。

まずは、空白文字を無視するようにします。

export function lex(input: string): Token[] {
  const tokens: Token[] = [];
  let pos = 0;

  while (pos < input.length) {
    const char = input[pos];

    if (char === " " || char === "\n" || char === "\t") {
      pos++;
      continue;
    }

    pos++;
  }

  return tokens;
}

基本的に空文字には意味を持たず、空文字以外の文字が出現して初めてトークンが始まると考えられるので、空白文字をスキップするようにしました。（割と一般的な字句解析の手法です）

次に、トークンを切り出す処理を実装します。

export function lex(input: string): Token[] {
  const tokens: Token[] = [];
  let pos = 0;

  while (pos < input.length) {
    const char = input[pos];

    if (char === " ") {
      pos++;
      continue;
    }

    pos++;
  }

  return tokens;
}

じゃあまずは VAR a = 1 という文字列を入力として与えたときに、まずはVARとaのような英文字列をトークンとして切り出す処理、最後にEOFを追加する処理を実装していきます。

    if (char === " ") {
      pos++;
      continue;
    }

+   // 英文字列が来たら、キーワードか識別子のどちらかを判定する
+   if (char.match(/[a-zA-Z]/)) {
+     // 英文字列が続く限り読み進める
+     let value = "";
+     while (pos < input.length && input[pos].match(/[a-zA-Z]/)) {
+       value += input[pos];
+       pos++;
+     }
+     switch (value) {
+       case "VAR":
+         tokens.push({ type: TokenType.VAR });
+         break;
+       default:
+         // キーワードのどれにも一致しない場合は識別子
+         tokens.push({ type: TokenType.IDENTIFIER, value });
+         break;
+     }
+
+     continue;
+   }

    pos++;
  }

  tokens.push({ type: TokenType.EOF });

  return tokens;
}

今回の言語には文字列値がないので、英文字が来たら絶対にキーワードか識別子になります。そのため、英文字が続く限り読み進めて、その後の文字列がキーワードか識別子かを判定しています。

ここまでの実装で、lex("VAR a = 1") が

[
  { type: 'VAR' },
  { type: 'IDENTIFIER', value: 'a' },
  { type: 'EOF' }
]

という結果を返すようになりました。

次に、演算子と数値をトークンとして切り出す処理を実装していきます。

      continue;
    }

+   // 数値が来たら、整数値としてトークンを切り出す
+   if (char.match(/[0-9]/)) {
+     let value = "";
+     while (pos < input.length && input[pos].match(/[0-9]/)) {
+       value += input[pos];
+       pos++;
+     }
+     tokens.push({ type: TokenType.INT, value: parseInt(value, 10) });
+     continue;
+   }

+   // 演算子をトークンとして切り出す
+   switch (char) {
+     case "=":
+       tokens.push({ type: TokenType.ASSIGN });
+       break;
+     default:
+       // それ以外は知らない文字なのでエラー
+       throw new Error(`Unexpected character: ${char}`);
+   }

    pos++;
  }

  tokens.push({ type: TokenType.EOF });

  return tokens;
}

これで、lex("VAR a = 1") が

[
  { type: 'VAR' },
  { type: 'IDENTIFIER', value: 'a' },
  { type: 'ASSIGN' },
  { type: 'INT', value: 1 },
  { type: 'EOF' }
]

という結果を返すようになり、変数宣言が正しく字句解析されるようになりました。

では残りのトークンもテストから順に実装していきます。これは長くなるので、実際のコードはリポジトリを参照してください。

注意点としてASSIGNとEQの区別が必要です。=は代入演算子として使われ、==は比較演算子として使われます。そのため、=が来たら、その次の文字が=であればEQ、そうでなければASSIGNとしてトークンを切り出すようにします。

これで、字句解析が完了しました。次に、構文解析を行います。

構文解析

構文解析は、字句解析で得られたトークン列を解析して、プログラムの構造を表すデータ構造（抽象構文木）を生成する処理です。

抽象構文木は、プログラムの構造を木構造で表現したものです。たとえば、以下のプログラムを抽象構文木に変換すると、以下のような構造になります。

VAR a = 1
VAR b = 2
IF a < b {
  a + b
} ELSE {
  a - b
}

{
    type: "Program",
    body: [
        {
            type: "VariableDeclaration",
            identifier: "a",
            value: {
                type: "IntegerLiteral",
                value: 1
            }
        },
        {
            type: "VariableDeclaration",
            identifier: "b",
            value: {
                type: "IntegerLiteral",
                value: 2
            }
        },
        {
            type: "IfStatement",
            condition: {
                type: "LessThanExpression",
                left: {
                    type: "Identifier",
                    value: "a"
                },
                right: {
                    type: "Identifier",
                    value: "b"
                }
            },
            consequent: {
                type: "BlockStatement",
                body: [
                    {
                        type: "AdditionExpression",
                        left: {
                            type: "Identifier",
                            value: "a"
                        },
                        right: {
                            type: "Identifier",
                            value: "b"
                        }
                    }
                ]
            },
            alternate: {
                type: "BlockStatement",
                body: [
                    {
                        type: "SubtractionExpression",
                        left: {
                            type: "Identifier",
                            value: "a"
                        },
                        right: {
                            type: "Identifier",
                            value: "b"
                        }
                    }
                ]
            }
        }
    ]
}

Statement は文を表し、Expression は式を表します。BlockStatement はブロックを表し、Identifier は識別子を表します。IntegerLiteral は整数リテラルを表し、AdditionExpression は加算式を表します。

このような抽象構文木を生成することで、プログラムの構造を再帰的に処理することができます。

まずは、どんな構文木を定義するかを考えます。今回は、以下のような構文木を定義します。

プログラム: Program
- 変数宣言: VariableDeclaration
- 整数リテラル: IntegerLiteral
- 識別子: Identifier
- 加算式: AdditionExpression
- 減算式: SubtractionExpression
- 乗算式: MultiplicationExpression
- 除算式: DivisionExpression
- 小なり式: LessThanExpression
- 大なり式: GreaterThanExpression
- 等しい式: EqualExpression
- 等しくない式: NotEqualExpression
- IF文: IfStatement
- ブロック: BlockStatement

それぞれの構文木を表す型を定義します。

export type Program = {
  type: "Program";
  body: Statement[];
};

export type Statement =
  | VariableDeclaration
  | ExpressionStatement
  | IfStatement
  | BlockStatement;

export type Expression =
    | IntegerLiteral
    | Identifier
    | AdditionExpression
    | SubtractionExpression
    | MultiplicationExpression
    | DivisionExpression
    | LessThanExpression
    | GreaterThanExpression
    | EqualExpression
    | NotEqualExpression;

export type VariableDeclaration = {
    type: "VariableDeclaration";
    identifier: string;
    value: Expression;
};

export type IntegerLiteral = {
    type: "IntegerLiteral";
    value: number;
};

export type Identifier = {
    type: "Identifier";
    value: string;
};

type BinaryExpression<T extends string> = {
    type: T;
    left: Expression;
    right: Expression;
};

export type AdditionExpression = BinaryExpression<"AdditionExpression">;
export type SubtractionExpression = BinaryExpression<"SubtractionExpression">;
export type MultiplicationExpression = BinaryExpression<"MultiplicationExpression">;
export type DivisionExpression = BinaryExpression<"DivisionExpression">;
export type LessThanExpression = BinaryExpression<"LessThanExpression">;
export type GreaterThanExpression = BinaryExpression<"GreaterThanExpression">;
export type EqualExpression = BinaryExpression<"EqualExpression">;
export type NotEqualExpression = BinaryExpression<"NotEqualExpression">;

export type ExpressionStatement = {
    type: "ExpressionStatement";
    expression: Expression;
};

export type IfStatement = {
    type: "IfStatement";
    condition: Expression;
    consequent: BlockStatement;
    alternate?: BlockStatement;
};

export type BlockStatement = {
    type: "BlockStatement";
    body: Statement[];
};

export function parse(tokens: Token[]): Program {
    return {
        type: "Program",
        body: [],
    };
}

これで、構文木を表す型を定義しました。次に、字句解析で得られたトークン列を構文解析して、抽象構文木を生成する処理を実装します。

こちらもTDDで進めていきます。まずは、簡単なテストを書いてみましょう。

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

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

lexで得られたトークン列をparse関数に渡して、抽象構文木が期待通りに生成されるかを確認しています。

もちろん、このテストは失敗します。

npm run test

次に、このテストを通すように parse 関数を実装していきます。

今回は、再帰下降構文解析(Recursive Descent Parsing)を使用して構文解析を行います。再帰下降構文解析は、トップダウン型の構文解析手法で、プログラムの構文規則を再帰的に処理することで、抽象構文木を生成します。DFSのような感じです。

まずは、テストに書いた通り、変数宣言をパースする処理のみを実装してみましょう。

まずは、parse 関数を実装していきます。

export function parse(tokens: Token[]): Program {
  const program: Program = {
    type: "Program",
    body: [],
  };

  while (tokens.length > 0) {
    const token = tokens.at(0);

    if (!token) {
      break;
    }

    switch (token.type) {
      case TokenType.VAR:
        tokens.shift();
        program.body.push(parseVariableDeclaration(tokens));
        break;
      case TokenType.EOF:
        tokens.shift();
        break;
      default:
        throw new Error(`Unexpected token: ${token.type}`);
    }
  }

  return program;
}

この parse 関数は、トークン列を受け取り、プログラム全体を表す Program 型のオブジェクトを生成します。トークンを順に処理し、VAR トークンが見つかった場合は parseVariableDeclaration 関数を呼び出して変数宣言を解析します。

次にexpectToken 関数を実装します。

function expectToken<T extends TokenType>(
  token: Token | undefined,
  type: T
): Extract<Token, { type: T }> {
  if (!token) {
    throw new Error(`Unexpected end of input. Expected ${type}`);
  }

  if (token.type !== type) {
    throw new Error(`Unexpected token: ${token.type}. Expected ${type}`);
  }

  return token as Extract<Token, { type: T }>;
}

この関数は、指定されたトークンが期待される型であることを確認します。もしトークンが期待される型でない場合はエラーを投げます。

次に、parseVariableDeclaration 関数を実装します。

function parseVariableDeclaration(tokens: Token[]): VariableDeclaration {
  const identifier = expectToken(tokens.shift(), TokenType.IDENTIFIER);
  expectToken(tokens.shift(), TokenType.ASSIGN);
  const value = parseValue(tokens);

  return {
    type: "VariableDeclaration",
    identifier: identifier.value,
    value,
  };
}

この関数は、変数宣言を解析して VariableDeclaration 型のオブジェクトを生成します。まず、識別子トークンを取得し、次に代入演算子トークンを確認します。その後、parseValue 関数を呼び出して値を解析します。

次に、parseValue 関数を実装します。

function parseValue(tokens: Token[]): Expression {
  const token = tokens.shift();

  if (!token) {
    throw new Error("Unexpected end of input");
  }

  switch (token.type) {
    case TokenType.INT:
      return { type: "IntegerLiteral", value: token.value };
    case TokenType.IDENTIFIER:
      return { type: "Identifier", value: token.value };
    default:
      throw new Error(`Unexpected token: ${token.type}`);
  }
}

この関数は、トークンを解析して Expression 型のオブジェクトを生成します。整数リテラルや識別子を解析し、それぞれに対応するオブジェクトを返します。

これで、parse("VAR a = 1") が

{
  type: 'Program',
  body: [
    {
      type: 'VariableDeclaration',
      identifier: 'a',
      value: {
        type: 'IntegerLiteral',
        value: 1
      }
    }
  ]
}