0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Binary_number(Binary number)

【C#】クラスを書くだけで言語を作れる — パーサジェネレータ AstFirst 入門(1) 関数電卓を作る

0
Posted at

はじめに

コンパイラや自作言語を作ってみたい、と思ったことありませんか? 自分専用のプログラミング言語、設定ファイルの DSL、ちょっとしたクエリ言語。でもいざ作ろうとすると、パーサを作るのが一番の壁 って思いませんか?

「字句解析、再帰下降、演算子の優先順位……自分には書けなさそう」って。

正規表現で無理やり parse すると破綻するし、ANTLR は Java 資産を持ち込むしで重い。手書きの再帰下降パーサは柔軟なんですけど、演算子の優先順位が増えるたびに地獄を見ます。

そこで作ったのが AstFirst です。C# のクラスと属性を書くだけで、コンパイル時に Lexer も LALR パーサも全部生成してくれるライブラリです。

この連載のゴールは、AstFirst を使ってゼロから 小さなプログラミング言語 を作れるようになることです。

第1回は、まず 関数電卓 を作って「おっ、動いた」を体験します。sin(0) や sqrt(2) が計算できるやつです。理論は一切出てきません。少しずつ機能を足しながら進めます。

対象は .NET 8 以上 / C# 12 以上。Visual Studio 2022以降 または VS Code + C# Dev Kit で動きます。

AstFirst って何?

一言でいうと 「C# のコードで文法を書くと、Source Generator がコンパイル時にパーサを生成する」 やつです。

得意なこと:

  • 文法が C# のクラスと属性 だけで書ける。独自の DSL ファイルは不要。
  • Lexer / Parser が コンパイル時に 生成される。実行時にコード生成はしない。
  • 演算子の優先順位・結合性が属性1個で解決する。
  • エラー回復付きで、構文エラー後も解析を続ける。
  • 返ってくる AST に意味解析を乗せられる。スコープや型チェックなど。

コンパイル時にメタプログラミングしてパーサを自動生成する、という仕組みです。

セットアップ

1. プロジェクトを用意

dotnet new console -n CalcDemo
cd CalcDemo

2. パッケージを入れる

dotnet add package AstFirst
dotnet add package AstFirst.Runtime

AstFirst が Source Generator 本体で、パッケージを参照するだけでコンパイル時に Lexer / Parser が生成されます。AstFirst.Runtime は実行時に必要な属性や基底クラス（Token や AstNode など）を提供します。Generator パッケージだけだとコンパイル時の参照に含まれないので、こちらも別途入れます。

これで準備完了です。

関数電卓を少しずつ作る

目標は 関数電卓 です。

  • 数値 123 3.14
  • 四則演算 + - * /、優先順位付き
  • 括弧 (1 + 2) * 3
  • 関数呼び出し sin(...) cos(...) sqrt(...) abs(...) など

いきなり全部は書かず、1つずつ足していきます。パーサが式をどう AST（抽象構文木） に組み立てるか、各ステップで図も交えて見ていきましょう。

Step 1: まず数値だけ

Expr.cs を作って、数値リテラル1つだけの文法を書きます。

using AstFirst;

namespace CalcDemo;

// 開始記号。各ノードは自分で自分を評価する
[Grammar]
[Skip(@"\s+")]
public abstract partial class Expr : AstNode
{
    public abstract double Eval();
}

// 数値:  Expr -> 数
public sealed partial class NumExpr : Expr
{
    public double Value { get; private set; }

    [Rule]
    public static void NumToken([Token(@"[0-9]+(\.[0-9]+)?")] Token num) { }

    partial void OnReduce()
        => Value = double.Parse(Num.Text);

    public override double Eval() => Value;
}

読み方を解説します。

  • [Grammar] を付けた Expr が 開始記号 です。ここから文法が始まります。
  • [Skip(@"\s+")] で空白を読み飛ばします。
  • NumExpr : Expr が 「Expr -> 数値」という規則 を表します。親クラスが左辺、自分がその規則の結果です。
  • [Rule] static void NumToken(...) の 引数が右辺 です。[Token(@"[0-9]+(\.[0-9]+)?")] が「数値の正規表現」を表しています。
  • OnReduce はその規則が reduce された瞬間 に呼ばれます。Num は Generator が生成したプロパティで、マッチした Token が入っています。ここから Text を取り出して Value に詰めています。

メソッド名を Num ではなく NumToken にしているのは理由があって、引数 num から自動で Num プロパティが生成されるので、メソッド名と被らないようにずらしています。これ、地味にハまりどころなので後でトラブルシューティングでも触れます。

そして Eval。ここが AstFirst の強みの1つです。生成された AST のノードは ただのデータ木じゃなくて、普通の C# のクラス です。なので、こんなふうに各ノードに Eval メソッドを持たせられます。NumExpr なら自分の値を返すだけ。後でこれが効いてきます。

動かす

Program.cs をこう書きます。result.Ast.Eval() の1行で計算する作りです。

using CalcDemo;

while (true)
{
    Console.Write("> ");
    var input = Console.ReadLine();
    if (string.IsNullOrWhiteSpace(input)) break;

    var result = ExprParser.Parse(input);

    if (result.HasErrors)
    {
        Console.WriteLine("  構文エラーです");
        continue;
    }

    Console.WriteLine($"  = {((Expr)result.Ast!).Eval()}");
}

result.Ast は object で返ってくるので、Expr にキャストしています。! は null 警告の免除です（エラーがなければ Ast は null じゃないので）。

> 42
  = 42
> 3.14
  = 3.14

数値がパースできて、評価できました。ExprParser はビルド時に自動生成されているので、自分で書く必要はありません。

42 という入力が、こんな AST になります。

ノード1つのシンプルな木です。ここから少しずつ育てていきます。

Step 2: 足し算を足す

Expr.cs に AddExpr を追加します。

// 足し算:  Expr -> Expr + Expr
[Precedence(1)]
public sealed partial class AddExpr : Expr
{
    [Rule]
    public static void Add(Expr left, [Token(@"\+")] Token op, Expr right) { }

    partial void OnReduce()
        => Span = SourceSpan.Merge(Left.Span, Right.Span);

    public override double Eval() => Left.Eval() + Right.Eval();
}

Add(Expr left, Token op, Expr right) の引数をそのまま読むと Expr + Expr になっています。ここでも 引数が右辺 です。left と right は Expr なので、子ノードとしてパーサが詰めてくれます。

注目は Eval です。

public override double Eval() => Left.Eval() + Right.Eval();

Left と Right は Expr 型なので、それぞれの Eval がポリモーフィズムで呼ばれます。Left が NumExpr なら NumExpr.Eval、AddExpr なら AddExpr.Eval。

これが AstFirst の強みです。 各ノードが自分の評価方法を知っているので、ルートの Eval() だけで木全体を再帰的に計算できます。プログラム側に巨大な switch も Visitor パターンもいりません。ノードを足したくなったら、そのノードのクラスに Eval を実装するだけです。

> 1 + 2
  = 3
> 1 + 2 + 3
  = 6

足し算が動きました。[Precedence(1)] は今は演算子が1つしかないので意味がないですが、次の Step で効いてきます。

1 + 2 の AST はこうなります。+ の左右に NumExpr ぶら下がった木です。

1 + 2 + 3 なら、左結合なので (1 + 2) + 3 と解釈されて、AddExpr の左にさらに AddExpr ぶら下がる2段の木になります。

Step 3: 四則演算と、優先順位

引き算を掛け算割り算を足します。まず、さっきの AddExpr にもう1つ [Rule] を足して Sub も扱えるようにします。

// 加減:  Expr -> Expr + Expr | Expr - Expr
[Precedence(1)]
public sealed partial class AddExpr : Expr
{
    [Rule]
    public static void Add(Expr left, [Token(@"\+")] Token op, Expr right) { }

    [Rule]
    public static void Sub(Expr left, [Token(@"-")] Token op, Expr right) { }

    partial void OnReduce()
        => Span = SourceSpan.Merge(Left.Span, Right.Span);

    public override double Eval() => RuleName switch
    {
        "Add" => Left.Eval() + Right.Eval(),
        "Sub" => Left.Eval() - Right.Eval(),
        _ => throw new InvalidOperationException(),
    };
}

1つのクラスに [Rule] を複数書けます。 AddExpr は「Expr -> Expr + Expr」と「Expr -> Expr - Expr」の2規則をまとめて持っています。乗除も別クラスで作ります。

// 乗除:  Expr -> Expr * Expr | Expr / Expr
[Precedence(2)]
public sealed partial class MulExpr : Expr
{
    [Rule]
    public static void Mul(Expr left, [Token(@"\*")] Token op, Expr right) { }

    [Rule]
    public static void Div(Expr left, [Token(@"/")] Token op, Expr right) { }

    partial void OnReduce()
        => Span = SourceSpan.Merge(Left.Span, Right.Span);

    public override double Eval() => RuleName switch
    {
        "Mul" => Left.Eval() * Right.Eval(),
        "Div" => Left.Eval() / Right.Eval(),
        _ => throw new InvalidOperationException(),
    };
}

複数規則があるとき、どの規則で reduce されたか は RuleName プロパティで分かります。Eval の中で RuleName が "Add" か "Sub" かを見て、+ か - かを判定しています。

そして [Precedence]。AddExpr は1、MulExpr は2。数字が大きいほど先に計算 されます。

> 1 + 2 * 3
  = 7
> 10 - 2 - 3
  = 5
> 8 / 2 / 2
  = 2

1 + 2 * 3 が 7 なのは * が先。10 - 2 - 3 が 5 なのは左結合で (10 - 2) - 3 と解釈されるからです。

1 + 2 * 3 の AST がこちら。* が先に結合するので、MulExpr が下にまとまっています。

この木の形こそが「優先順位」の正体です。木の下にあるほど先に評価されるので、下の MulExpr が先に計算されて 2 * 3 = 6、そのあと 1 + 6 = 7 となります。

Step 4: 括弧

Expr.cs に ParenExpr を追加します。

// 括弧:  Expr -> ( Expr )
public sealed partial class ParenExpr : Expr
{
    [Rule]
    public static void Paren([Token(@"\(")] Token lp, Expr inner, [Token(@"\)")] Token rp) { }

    partial void OnReduce()
        => Span = SourceSpan.Merge(Lp.Span, Rp.Span);

    public override double Eval() => Inner.Eval();
}

Paren(Token lp, Expr inner, Token rp) の引数が ( Expr )。Eval は中身をそのまま評価するだけです。

> (1 + 2) * 3
  = 9
> 2 * (3 + 4)
  = 14

括弧で計算順序を変えられるようになりました。

(1 + 2) * 3 の AST です。さっきと違って、MulExpr の下に ParenExpr が来て、その中に AddExpr があります。

括弧のおかげで AddExpr が木の下に入り、先に 1 + 2 = 3、次に 3 * 3 = 9 と計算されます。Step 3 の木と見比べると、優先順位を括弧がひっくり返した様子がよく分かります。

Step 5: 関数呼び出し

最後です。Expr.cs に CallExpr を追加します。

// 関数呼び出し:  Expr -> 関数名 ( Expr )
public sealed partial class CallExpr : Expr
{
    public string Name { get; private set; } = "";

    [Rule]
    public static void Call([Token(@"[A-Za-z_]\w*")] Token nameTok,
                            [Token(@"\(")] Token lp,
                            Expr arg,
                            [Token(@"\)")] Token rp) { }

    partial void OnReduce()
        => Name = NameTok.Text;

    public override double Eval() => Name switch
    {
        "sin"  => Math.Sin(Arg.Eval()),
        "cos"  => Math.Cos(Arg.Eval()),
        "tan"  => Math.Tan(Arg.Eval()),
        "sqrt" => Math.Sqrt(Arg.Eval()),
        "abs"  => Math.Abs(Arg.Eval()),
        _ => throw new InvalidOperationException($"未知の関数: {Name}"),
    };
}

引数を読むと 関数名 ( Expr )。関数名は [Token(@"[A-Za-z_]\w*")] で識別子です。

1つだけ小技があります。関数名の引数を name ではなく nameTok にしています。これは Name プロパティを自分で定義したので、Generator が生成するプロパティと 名前が被らないようにずらした ものです。nameTok にすると NameTok が生成されるので、OnReduce で Name = NameTok.Text と詰めます。Eval では Name で関数名を見て Math の関数に振り分けています。

> sqrt(2)
  = 1.4142135623730951
> sin(0) + cos(0)
  = 1
> abs(3 - 10)
  = 7

sin(0) + cos(0) の AST です。AddExpr の左右に CallExpr がぶら下がり、それぞれが NumExpr を引数に持ちます。

評価はボトムアップ。sin(0) = 0、cos(0) = 1、それらを足して 1。木の下から順に Eval が再帰的に回って、ルートの Eval() で 1 が出てきます。

関数電卓のでき上がりです。 クラス5つ、Program.cs は Eval() の1行のまま、ここまで来ました。

トラブルシューティング

ビルドは通るのに ExprParser が見つからない

→ IDE を再起動してみてください。Source Generator はビルド時にコードを生成するので、エディタが生成コードを認識するまで少しラグがあります。

partial を付け忘れる

→ クラスは 必ず partial を付けてください。Generator が Left / Arg / Num などのプロパティを別ファイルで生成するためです。

Rule メソッド名が、引数からできるプロパティと被る

→ [Rule] メソッドの名前を変えてください。例えば引数 num からは Num プロパティが自動生成されるので、メソッド名も Num にすると被ってコンパイルエラーになります。この記事では NumToken にしています。Add / Sub / Mul / Div も、引数と被らない名前にするのが安全です。

自分で定義したプロパティと Generator が被る

→ [Rule] メソッドの引数名を変えれば OK です。CallExpr の nameTok のように、引数名をずらして被らないようにします。

おわりに

第1回はここまで。

やったこと:

  • AstFirst のパッケージを入れた
  • 数値 → 足し算 → 四則演算 → 括弧 → 関数と、少しずつクラスを足して関数電卓を作った
  • 演算子の優先順位を [Precedence] 1個で解決した
  • 各ノードに Eval を持たせて、Eval() の1行で計算した
  • 各ステップで AST の形を Mermaid で確認した
  • 実際に動かして sin(0) + cos(0) = 1 を確認した

「え、これだけでパーサできるの?」と思ってもらえたら嬉しいです。

第2回は 変数と文 を足します。let x = 1 + 2; とか print x; みたいな、それっぽいプログラミング言語 に進化させます。

AstFirst は GitHub で公開しています。Star いただけると励みになります。
https://github.com/actbit/AstFirst

それでは、第2回で。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?