oboard

oboard

https://oboard.eu.org/
github
email
tg_channel
medium
twitter
bilibili
steam_profiles
follow
ホームアーカイブPortfolios

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

#MoonBit#MoonRepl87
AI 翻訳
この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示
AI が生成した要約
この文書では、プログラミング言語の構文解析に関する基本的な概念が説明されています。主な用語には以下が含まれます： - **Token（トークン）**: プログラミング言語の基本単位で、文法の意味要素を表します。 - **Lexer（字句解析器）**: ソースコードをトークンの系列に変換するツールです。 - **CST（具体構文木）**: ソースコードの具体的な構文構造を表すデータ構造です。 - **AST（抽象構文木）**: プログラムの論理構造を表す木構造で、具体的な文法の詳細を無視します。 - **Parser（構文解析器）**: トークンの系列を処理し、構文木を生成します。 - **Visitor（ビジターパターン）**: CSTを遍歴し、操作を実行するためのデザインパターンです。 ASTとCSTの比較では、CSTが具体的な構造を示すのに対し、ASTはより簡潔な視点を提供し、不要な詳細を省略します。例として、式「1 + 2 * 3」のASTが示されています。 さらに、Chevrotainを使用して加減算のパーサーを実装する方法が説明されており、トークンの作成、字句解析器と構文解析器の設定、計算ロジックの実装が含まれています。最終的に、簡単な加算器が完成し、実行例が示されています。

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

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

AST と CST の比較#

CST:

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

AST:

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

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

1 + 2 * 3;

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

     +
    / \
   1   *
      / \
     2   3

この木の中で：
根ノードは + 演算子です。左の子ノードはオペランド 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

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。