はじめに

コンパイラや自作言語を作ってみたい、と思ったことありませんか? 自分専用のプログラミング言語、設定ファイルの 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回で。