C# + Ironyで構文解析を行う (電卓を作ってみます) - 結果だけでなく過程も見てください

皆様新年明けましておめでとうございます。
相変わらずの更新ペースですが、本年もよろしくお願い致します。
挨拶はこの辺にしてさっそく本題。

なぜ構文解析をするのか？

事の発端ですが、うちにはC/C++で書かれたソースコードが山ほどあり、構文解析してヘンな部分を静的解析でもできたら素敵だな～と考えたのが始まりですが、まぁ難易度的に出来る出来ないは置いといて、この字句解析/構文解析という分野、なかなかちゃんと理解できず、曖昧な知識のまま今に至っているので、ちょいとお勉強したいなとも思ったのです。

Ironyとは？

パーサージェネレーターです。
有名なところではyacc/lex、bison/flexがありますね。
これはyacc/lex独自の文法にBNFを食わせて、字句解析/構文解析を行うC言語のプログラムを出力するものです。

今回使うIronyは、BNFの定義をIronyのクラスインスタンスなどを使って、C#のコード上で指定できるものです。
すべてC#のコードで表現できるので、yacc/lexのような独自の文法が不要になります。

C++のboostにも、spiritというC++のコードでBNFを指定し、字句解析/構文解析を行うクラスインスタンスを作成するみたいなライブラリがありました。
さすがC++！クラス/関数テンプレートさえあればなんでもできるんや！魔境へようこそ！って感じですねぇ…。

目標

とりあえず月並みですが、電卓を作ってみたいと思います。概要は以下。

四則演算+べき乗計算
計算の優先順位のためのカッコ対応
マイナス値およびプラス値（-1とか+1とか）
整数のみ
複数の文を定義できる。文ごとに計算され、結果は合算値を表示。
//や/* */のコメント部分や、空白文字は無視

こんな式↓を計算して結果を返すものを作ります。

2 + 3 *(((1 + -2)*(-1)) + 3 ) * ( 2 + 4/2);

準備

当方、Visual Studioのバージョンは2017 Communityです。

C#で適当なプロジェクトを作って（自分はフォームアプリケーションにしました）、
NuGetでIronyのライブラリを取り込んでおく必要があります。やり方は以下。

Visual Studioの[ツール]→[NuGet パッケージ マネージャー]→[ソリューションのNuGetパッケージの管理]を選択、
「Irony」で検索して、「Irony」と「Irony.Interpreter」をインストールします。

BNFのイメージ

詳しくないのであくまでイメージとして記載します。
構文木のトップをProgramとして、複数の文(Statement)を書けるようにします。
文とは計算式の最後にセミコロン(";")をつけたものであり、セミコロン区切りで複数の計算式を定義できるようにします。
式(Expr)は四則演算やカッコなどを含む計算式です。演算子の優先順位を意識する必要があるため、Exprで+, -を解決して、その下にTermを作って*, /を解決して、その下にFactor...とやるのが一般的なようですが、なんか名前がわかりづらいので、ここではExprAddSubやExprMulDivなどの名前にしています。Numberは整数です。

Program ::= Statement*
Statement ::= ExprAddSub ";"
ExprAddSub ::= ExprMulDiv
             |  ExprAddSub "+" ExprAddSub
             |  ExprAddSub "-" ExprAddSub
ExprMulDiv ::= Expr
             |  ExprMulDiv "*" ExprMulDiv
             |  ExprMulDiv "/" ExprMulDiv
             |  ExprMulDiv "**" ExprMulDiv
Expr ::= "(" ExprAddSub ")"
       |  UnOp "(" ExprAddSub ")"
       | UnOp Number
UnOp ::= "+"  | "-"

文法定義部分のC#コード

まずは文法を表現するクラスを定義します。
基本的には上記BNFをまんまコードに落とし込んでいくことになります。

まずはクラスの始まりと、コメントや空白文字、改行などを無視するコード。

using Irony.Interpreter;
using Irony.Parsing;

[Language("MyNumbersGrammar")]
class NumbersGrammar : InterpretedLanguageGrammar
{
    public NumbersGrammar() : base(true)
    {
        // 一行コメント(//)や、複数行コメント(/* ... */)、その他文法上無視するものの指定
        var singleLineComment = new CommentTerminal("SingleLineComment", "//", "\r", "\n", "\u2085", "\u2028", "\u2029");
        var delimitedComment = new CommentTerminal("DelimitedComment", "/*", "*/");
        NonGrammarTerminals.Add(singleLineComment);
        NonGrammarTerminals.Add(delimitedComment);

続いて、終端文字です。
今回は整数と、それ以外のこまごまとして演算子や記号を定義します。

        // 1. Terminals
        NumberLiteral Number = new NumberLiteral("number");
        KeyTerm AddOperator = ToTerm("+");
        KeyTerm SubOperator = ToTerm("-");
        KeyTerm MulOperator = ToTerm("*");
        KeyTerm DivOperator = ToTerm("/");
        KeyTerm PowOperator = ToTerm("**");
        KeyTerm LeftParen = ToTerm("(");
        KeyTerm RightParen = ToTerm(")");
        KeyTerm EndOfSentence = ToTerm(";");

肝の部分の非終端記号です。
上記BNFの非終端記号を1つずつ定義していきます。
NonTerminalの第一引数は構文木を解析したときに、要素を見分けるための文字列です。適当で良いです。
第二引数には、構文木(Abstract Syntax Tree, 以下AST)を解析したあと、それをどう評価するか、ノードごとに評価するコードを持つクラスを指定します。
これらのクラスは後述します。

        // 2. Non-Terminals
        var Program = new NonTerminal("Program", typeof(NumbersGrammarProgramNode));

        var Statement = new NonTerminal("Statement", typeof(NumbersGrammarStatementNode));

        var ExprAddSub = new NonTerminal("ExprAddSub", typeof(NumbersGrammarExprNode));
        var ExprMulDiv = new NonTerminal("ExprMulDiv", typeof(NumbersGrammarExprNode));
        var Expr = new NonTerminal("Expr", typeof(NumbersGrammarExprNode));
        var ParenExpr = new NonTerminal("ParenExpr", typeof(NumbersGrammarParenExprNode));

        var UnExpr = new NonTerminal("UnExpr", typeof(NumbersGrammarUnExprNode));
        var UnOp = new NonTerminal("UnOp", typeof(NumbersGrammarUnOpNode) );

BNFのルールを書いていきます。

        // 3. BNF
        Program.Rule = MakeStarRule(Program, Statement);

        Statement.Rule = ExprAddSub + EndOfSentence;

        ExprAddSub.Rule = ExprMulDiv
                | ExprAddSub + AddOperator + ExprAddSub
                | ExprAddSub + SubOperator + ExprAddSub
                ;

        ExprMulDiv.Rule = Expr
                | ExprMulDiv + MulOperator + ExprMulDiv
                | ExprMulDiv + DivOperator + ExprMulDiv
                | ExprMulDiv + PowOperator + ExprMulDiv
                ;

        Expr.Rule = ParenExpr
               | UnExpr   
               | Number;  

        ParenExpr.Rule = LeftParen + ExprAddSub + RightParen;

        UnExpr.Rule = UnOp + ParenExpr | UnOp + Number;

        UnOp.Rule = ToTerm("+") | "-";

最後に、このルールのトップをthis.Rootに指定し、
演算子の優先順位をRegisterOperators関数で指定します(※)
あとはASTを作成するフラグもONにします。

(※)補足。RegisterOperatorsでの演算子の優先順位がうまく動かないので、BNFとしては"*", "/"が"+", "-"よりも先に評価されるような文法にしています。

        this.Root = Program;

        RegisterOperators(1, "+", "-");
        RegisterOperators(2, "*", "**", "/");

        LanguageFlags = LanguageFlags.CreateAst;
    }
}

これで入力された文字列を読み取り、構文木を作成することができます。

ASTを評価する部分のC#のコード

非終端記号毎に、AstNodeのサブクラスを作成します。
重要な点として、これらのクラスは必ずアクセス修飾子をpublicにする必要があります。

今回はInit関数、DoEvaluate関数をオーバーライドしています。
Init関数でノード情報を取得し、DoEvaluate関数で評価した結果（今回は主に整数）を取得します。

トップレベルの非終端記号Programに対応するクラスです。
Programは複数のStatementを所持できるので、AstNodeのリストで管理しています。

public class NumbersGrammarProgramNode : AstNode
{
    // プログラム全体は複数の数字を結果として持つ

    public List<AstNode> numList = new List<AstNode>();

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();
        foreach ( var node in nodes )
        {
            this.numList.Add(AddChild("numList", node));
        }
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        // すべての文を評価した結果得られた整数値の合計を返す
        int result = 0;
        foreach ( var num in this.numList )
        {
            result += (int)num.Evaluate(thread);
        }

        thread.CurrentNode = Parent;

        return result;
    }
}

次にStatementですが、これは式の最後にセミコロンをつけたものなので、
式のAstNodeだけを所持するようにします。

public class NumbersGrammarStatementNode : AstNode
{
    public AstNode exprNode = null;

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();
        this.exprNode = AddChild("exprNode", nodes[0]);  // 数字のみ取り出す。nodes[1]の";"は無視。
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        // 単一式を評価して、整数を取得する
        int number = (int)exprNode.Evaluate(thread);

        thread.CurrentNode = Parent;

        return number;
    }
}

式Exprを評価します。
式は構文によって、値が1つだったり、3つだったりするので、
取得した要素分だけ配列サイズを確保して、ノード情報を所持するようにします。

public class NumbersGrammarExprNode : AstNode
{
    public AstNode[] numberNodes = null;

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();

        this.numberNodes = new AstNode[nodes.Count];

        for (int i = 0; i < nodes.Count; ++i)
        {
            this.numberNodes[i] = AddChild("numberNode", nodes[i]);
        }
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        int number = 0;
        if (this.numberNodes.Length == 1)
        {
            // 要素1つの場合
            number = (int)this.numberNodes[0].Evaluate(thread);
        }
        else
        {
            // 要素3つの場合(と仮定)

            int nLeft = (int)this.numberNodes[0].Evaluate(thread);
            int nRight = (int)this.numberNodes[2].Evaluate(thread);

            // 演算子はこれ以上評価できないので、取得した文字列を直接参照する。
            string strBinOp = this.numberNodes[1].Term.Name;
            if (strBinOp.Equals("+"))
            {
                number = nLeft + nRight;
            }
            else if (strBinOp.Equals("-"))
            {
                number = nLeft - nRight;
            }
            else if (strBinOp.Equals("*"))
            {
                number = nLeft * nRight;
            }
            else if (strBinOp.Equals("/"))
            {
                number = nLeft / nRight;
            }
            else
            {
                // **(べき乗)と仮定する。
                number = (int)Math.Pow(nLeft, nRight);
            }

        }

        thread.CurrentNode = Parent;

        return number;
    }
}

続いてカッコ付の式を評価するクラス。

public class NumbersGrammarParenExprNode : AstNode
{
    public AstNode middleExprNode = null;

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();

        this.middleExprNode = AddChild("middleExprNode", nodes[1]);   // 両端の(と)は無視して、間だけを評価する
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        int result = (int)this.middleExprNode.Evaluate(thread);

        thread.CurrentNode = Parent;

        return result;
    }
}

次に、負値（とオマケで明示的な正の値）を式として評価するクラス。

public class NumbersGrammarUnExprNode : AstNode
{
    public AstNode unOpNode = null;
    public AstNode termNode = null;

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();

        this.unOpNode = AddChild("unOpNode", nodes[0]);
        this.termNode = AddChild("termNode", nodes[1]);
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        // "-"なら-1を掛けて負の値にする。それ以外は+とする。
        int result = (int)this.termNode.Evaluate(thread) * (((string)this.unOpNode.Evaluate(thread)).Equals("-") ? -1 : +1);

        thread.CurrentNode = Parent;

        return result;
    }
}

負値および正の値の前につける"-"または"+"を評価するクラス。

public class NumbersGrammarUnOpNode : AstNode
{
    public AstNode unOpNode = null;

    public override void Init(AstContext context, ParseTreeNode treeNode)
    {
        base.Init(context, treeNode);

        ParseTreeNodeList nodes = treeNode.GetMappedChildNodes();

        this.unOpNode = AddChild("unOpNode", nodes[0]);
    }

    protected override object DoEvaluate(ScriptThread thread)
    {
        thread.CurrentNode = this;

        string result = (string)this.unOpNode.Term.ToString();

        thread.CurrentNode = Parent;

        return result;
    }
}

電卓を使用してみる！

最後に、上記コードで作成した電卓に値を渡し、結果を取得するコードをご紹介します。
Main関数に書いたり、フォームアプリケーションでボタンが押されたときのコールバック関数に書くと良いでしょう。

また自分は入力データをtbExprというテキストボックスから取得し、
tbResultというテキストボックスに結果を出力しています。

var grammar  = new NumbersGrammar();
var language = new LanguageData(grammar);

try
{
    var app = new ScriptApp(language);
    int result = (int)app.Evaluate(this.tbExpr.Text);

    this.tbResult.Text = result.ToString();
}
catch (ScriptException ex)
{
    Console.Error.WriteLine("{0} {1}", ex.Location, ex.Message);
}

電卓に渡す値の例

機能を一通り使った式

2 + 3 *(((1 + -2)*(-1)) + 3 ) * ( 2 + 4/2);

結果

複数の文を渡す

セミコロンで区切れば、複数の式を渡すこともできます。

2 + 3 *(((1 + -2)*(-1)) + 3 ) * ( 2 + 4/2);
((2 + -2 )/3 + 5) * 2 + 1;

結果

以下のように、コメントは無視されます。

2 + 3 *(((1 + -2)*(-1)) + 3 ) * ( 2 + 4/2);
((2 + -2 )/3 + 5) * 2 + 1;
// 100 * 5
/*
300 * 5;
400 * 5;
*/
+5;

結果

途中から解説が面倒になってコードを張り付けるだけみたいな感じになってしまいました。
解説も非常に適当で、間違ってそうなところがちらほらと・・・。
後日修正するかもしれません。修正するんじゃないかな？さぼったらごめんなさい。

参考サイト

Irony - Language Implementation Kit - Wikibooks, open books for an open world

Ironyを使ってみようその1 - Qiita

Irony の簡単な使い方の説明 - カーテンを開けよう - Windows アプリ開発関連まとめサイト

Ironyをいじってみた - ものがたり

c# - Expression precedence in Irony parser - Stack Overflow