数式のパース：バッカス・ナウア記法(BNF)

前回操車場アルゴリズムで数式をパースしましたが、符号がうまくパースできませんでした。
符号を使えないのは不便なのでなんとかしたいと思います。

hollyhockberry.hatenablog.com

BNF

文法の定義といえば、BNF、つまり「バッカス・ナウア記法」ですね。バンダイナムコフェスではないですよ？（アイカツ！おじさんギャグ）

ja.wikipedia.org

四則演算のBNFを調べるとこんな感じの拡張BNF表記が例示されていることが多いです。

expr ::= <term> { "+" | "-", <term> }
term ::= <factor> { "*" | "/", <factor> }
factor ::= "(" <expr> ")" | <number>
number ::= 数値

この定義を利用して構文木を作ると加減より乗除が優先度高く処理されるの本当美しいですね。すごい。

さて、正攻法だとここに四則演算に加えて優先度の違うべき乗にも対応しなくてはならないのですが複雑になりそうです。
なんとなく手に負えそうもないので前回判定できなかった単項演算子の区別だけ解決を目指します。

まずはややこしいので2項演算子をまとめちゃいます。

expr ::= <term> { "+" | "-" | "*" | "/" | "%" | "**", <term> }
term ::= "(" <expr> ")" | <number>
number ::= 数値

単項演算子はの前にくっつくので、ダサいですが term2 を導入して定義します。

expr ::= <term> { "+" | "-" | "*" | "/" | "%" | "**", <term> }
term ::= <term2> | "+" | "-" | "~", <term2> 
term2 ::= "(" <expr> ")" | <number>
number ::= 数値

の部分は数字か変数か関数になるように置き換えます。名前が変かもだけどそこは気にせず・

expr ::= <term> { "+" | "-" | "*" | "/" | "%" | "**", <term> }
term ::= <term2> | "+" | "-" | "~", <term2> 
term2 ::= "(" <expr> ")" | <factor>
factor ::= <literal> [ "(", [ <arglist> ] ")" ]
arglist ::= <expr> { ",", <expr> }
literal ::= 数値とか変数とか

やりたいことはできたはずなのでコードを書いてみます。

void Parse(IEnumerable<string> tokens) {
    var token_queue = new Queue<string>(tokens);

    expr();
    Console.WriteLine();

    string? pop() => token_queue?.Dequeue();
    string? top() => token_queue?.Count > 0 ? token_queue.First() : null;

    void expr() {
        term();
        string[] operators = new string[] { "+", "-", "*", "/", "%", "**" };
        while (operators.Contains(top())) {
            Console.Write($"{pop()} ");
            term();
        }
    }

    void term() {
        string[] operators = new string[] { "+", "-", "~" };
        if (operators.Contains(top())) {
            // こいつ単項演算子なので括弧で表示する！
            Console.Write($"[{pop()}] ");
            term2();
        } else {
            term2();
        }
    }

    void term2() {
        if (top() == "(") {
            Console.Write($"{pop()} ");
            expr();
            Console.Write($"{pop()} ");
        } else {
            factor();
        }
    }

    void factor() {
        literal();
        if (top() == "(") {
            Console.Write($"{pop()} ");
            while (top() != ")") {
                arglist();
            }
            Console.Write($"{pop()} ");
        }
    }

    void arglist() {
        expr();
        while (top() == ",") {
            Console.Write($"{pop()} ");
            expr();
        }
    }

    void literal() {
        Console.Write($"{pop()} ");
    }
}

符号がついた数式をパースさせてみます。

var formula = "3 + 4 * +2 / -( 1 - 5 ) ** 2 ** 3";
Console.WriteLine($"INPUT: {formula}");
var tokens = Split(formula);
Parse(tokens);

// 結果
// INPUT: 3 + 4 * +2 / -( 1 - 5 ) ** 2 ** 3
// 3 + 4 * [+] 2 / [-] ( 1 - 5 ) ** 2 ** 3

期待通り符号のトークンが括弧で表示されていますね、よかった！

完成

先程の関数でコンソールに出力していたトークンをリストにしてreturnし、Analyze()に渡せばパーサの完成です。その際は演算子の振る舞いを定義したDictionaryも変更するのも忘れずに、ですね。

   :
   { "[~]", (1, (a) => ~(int)a.First()) },
   { "[+]", (1, (a) => a.First()) },
   { "[-]", (1, (a) => -a.First()) },
   :

BNFは学生の時に苦手意識を持っていたので手を出したくなかったんですが、なんとかやりたいことができてよかったです。
実際は難しいところから目をそらして通り抜けたので苦手なままですし、正しい実装かはわかりませんがひとまず完成としてしまいます。

実装時もよくわかんなくなって諦めのツイートしてますね。気持ちわかる。

なんだか合ってるのかよくわからんけどテストケースが全て通るので問題ないと言うことにしてしまう
— イナバ (@hollyhockberry) 2022年9月20日

例によって、これまでの実装にテストコード含めたソースを公開しています。（VS2022 for macのプロジェクトです)

github.com

イナバちゃんログ

数式のパース：バッカス・ナウア記法(BNF)

BNF

完成

参考