ゼロから始める MoonBit インタプリタの実装（2）

プログラミング言語の字句解析、構文解析、解釈実行に関する以下の概念があります。

Token（トークン）：トークンはプログラミング言語の基本単位であり、構文の中の一つの意味要素を表します。例えば、算術式の中で、プラス (+)、マイナス (-)、数字 (123) はすべてトークンとなります。各トークンにはタイプ（例：Plus、Minus、NumberLiteral）と、ソースコード内でこれらのトークンを識別するためのパターン（正規表現で定義）があります。
Lexer（字句解析器）：Lexer はソースコードの文字列を一連のトークンに変換するツールです。これは言語の基本構成要素（トークン）を識別する役割を担います。Lexer は不要な文字（空白など）をスキップし、有用なトークンを生成して後続の構文解析器に渡します。
CST（Concrete Syntax Tree、具体構文木）：CST はソースコードの具体的な構文構造を表すデータ構造です。すべての構文要素とその関係を含んでいます。CST はパーサーがソースコードの構造を理解するのを可能にし、構文の完全なビューを提供し、後続の処理（意味解析やコード生成など）を容易にします。
AST（Abstract Syntax Tree、抽象構文木） はプログラムの構造を表す木構造のデータ構造であり、コンパイラやインタプリタで広く使用されています。CST（具体構文木）とは異なり、AST はプログラムの論理構造にのみ焦点を当て、構文の具体的な詳細（空白、括弧など）は無視します。
Parser（構文解析器）：Parser はトークンの列を処理し、ST を生成するコンポーネントです。これは言語の構文規則に基づいて、トークンの組み合わせが期待される構造に合致しているかを判断します。
Visitor（ビジターパターン）：ビジターパターンは、オブジェクト構造を変更することなく操作を行うことを可能にするデザインパターンです。この文脈では、CST を遍歴し、対応する操作（式の値を計算するなど）を実行するために使用されます。

AST と CST の比較#

CST:

コードの具体的な構造を表し、すべての構文の詳細を含みます。
括弧、セミコロン、空白など、すべての構文要素を含みます。

AST:

より簡潔なビューを提供し、構文の意味部分にのみ焦点を当てます。
不要な詳細（余分な空白や区切り文字など）を省略します。

以下のような単純な式があると仮定します：

1 + 2 * 3;

その AST は次のように表現されるかもしれません：

この木の中で：
根ノードは + 演算子です。左の子ノードはオペランド 1 です。
右の子ノードは * 演算子で、その左の子ノードはオペランド 2、右の子ノードはオペランド 3 です。

AST はプログラムの構造を表現し操作するための効率的な方法を提供し、ソースコードの構文情報を抽象化します。AST を使用することで、コンパイラやインタプリタはコードの分析、最適化、生成をより容易に行うことができ、コード処理の効率と柔軟性を向上させます。

コード#

シンプルな加減算パーサーから始め、段階的にシンプルな加算パーサーを実装し、その後さらに多くの構文を追加していきます。

Addition Parser

まず、Chevrotainをインストールする必要があります。
ほとんどの人は pnpm を使用しています。

pnpm install chevrotain

私は個人的に bun を使用するのが好きです。

bun i chevrotain

bun add v1.1.20 (ae194892)
installed [email protected]
[271.00ms] done

インストールが完了したら、index.tsファイルを作成します。

インポート#

import {
  createToken,
  Lexer,
  CstParser,
  tokenMatcher,
  CstNode,
} from "chevrotain";

Chevrotain の関連メソッドとクラスをインポートし、字句解析器と構文解析器を作成します。

トークンの作成#

// AdditionOperator: 加算演算子を表すトークンを作成しますが、Lexer.NAを使用して、このトークンが直接マッチしないことを示します（これはカテゴリです）。
const AdditionOperator = createToken({
  name: "AdditionOperator",
  pattern: Lexer.NA,
});
// Plus と Minus: それぞれ加号（+）と減号（-）を表すトークンを作成します。これらはすべてAdditionOperatorのサブクラスです。
const Plus = createToken({
  name: "Plus",
  pattern: /\+/,
  categories: AdditionOperator,
});
const Minus = createToken({
  name: "Minus",
  pattern: /-/,
  categories: AdditionOperator,
});
// NumberLiteral: 数字を表すトークンを作成します。正規表現 /[1-9]\d*/ は1から9で始まる整数（つまり0で始まらない）にマッチします。
const NumberLiteral = createToken({
  name: "NumberLiteral",
  pattern: /[1-9]\d*/,
});
// WhiteSpace: 空白を表すトークンを作成します。Lexer.SKIPPEDを使用して、字句解析中にスキップされることを示します（つまりトークンを生成しません）。
const WhiteSpace = createToken({
  name: "WhiteSpace",
  pattern: /\s+/,
  group: Lexer.SKIPPED,
});

字句解析器の設定#

const allTokens = [WhiteSpace, Plus, Minus, NumberLiteral, AdditionOperator];
// 定義したすべてのトークンを配列allTokensに入れ、新しい字句解析器CalculatorLexerを作成します。
const CalculatorLexer = new Lexer(allTokens);

構文解析器の作成#

class CalculatorPure extends CstParser {
  constructor() {
    super(allTokens);

    const $ = this;
    // expression ルール: このルールは式に対応し、加算式を含みます。後でさらに多くの式を追加します：例えば乗算。
    $.RULE("expression", () => {
      $.SUBRULE($.additionExpression);
    });

    // additionExpression ルール: このルールは加算式の構造を定義し、まず左オペランド（lhs）としてNumberLiteralを消費し、その後0個以上の加算演算子と右オペランド（rhs）を消費します。
    $.RULE("additionExpression", () => {
      $.CONSUME(NumberLiteral, { LABEL: "lhs" });
      $.MANY(() => {
        $.CONSUME(AdditionOperator);
        $.CONSUME2(NumberLiteral, { LABEL: "rhs" });
      });
    });

    this.performSelfAnalysis();
  }
}

パーサーインスタンスの作成#

const parser = new CalculatorPure();
const BaseCstVisitor = parser.getBaseCstVisitorConstructor();

class CalculatorInterpreter extends BaseCstVisitor {
  constructor() {
    super();
    this.validateVisitor();
  }

  expression(ctx) {
    return this.visit(ctx.additionExpression);
  }
  // additionExpression メソッド: 加算式のロジックを処理します。まず左オペランドの値を取得し、右オペランドを遍歴し、演算子に基づいて加算または減算を行います。
  additionExpression(ctx) {
    let result = Number.parseInt(ctx.lhs[0].image, 10);

    if (ctx.rhs) {
      ctx.rhs.forEach((rhsOperand, idx) => {
        let rhsValue = Number.parseInt(rhsOperand.image, 10);
        let operator = ctx.AdditionOperator[idx];

        if (tokenMatcher(operator, Plus)) {
          result += rhsValue;
        } else {
          result -= rhsValue;
        }
      });
    }

    return result;
  }
}

このコードはシンプルな加算と減算の計算機を定義し、式を解析して結果を計算します。これは Chevrotain の機能を使用してトークンを作成し、構文規則を構築し、インタプリタのロジックを実装しています。

実行#

function eval(input: string) {
  const lexResult = CalculatorLexer.tokenize(input);
  parser.input = lexResult.tokens;
  const cst = parser.row();
  return new CalculatorInterpreter().visit(cst);
}

console.log(eval("1 + 2 + 3")); // 6
console.log(eval("1 + 2 - 3")); // 0

この記事ではシンプルな加算パーサーを実装しました。今後、さらに多くの構文規則を追加していきます。

プロジェクトのアドレス： https://github.com/oboard/moonrepl