C# - 力技で四則演算式をLL(1)構文解析する

yaccとかCompilerProviderクラスとかを使わずに、四則演算式を解析するプログラムを作成してみた。
字句解析器を分離してないので無駄にハマった・・。

参考サイト

今回の四則演算のBNF風メモ

E  -> T E2
E2 -> "+" T E2 | "-" T E2 | empty
T  -> F T2
T2 -> "*" F T2 | "/" F T2 | empty
F  -> "(" E ")" |  number

サンプルコード

上のBNFに沿って文字列を解析して、演算します。
エラーとかオーバーフローは放置です。

using System;
using System.IO;
using System.Text;


class TestLL
{
    MemoryStream ms;
    
    TestLL()
    {
    }

    bool Parse(string expr)
    {
        ms = new MemoryStream(Encoding.UTF8.GetBytes(expr));
        int x=0;
        if (Expr_E(ref x)){
            Console.WriteLine(x);
            return true;
        }
        return false;
    }

    bool Expr_E(ref int y)
    {
        int x1=0;
        string ope="";
        int x2=0;
        if ( Expr_T(ref x1) ) {
            y = x1;
            if ( Expr_E2(ref ope, ref x2) ) {
                if (ope=="+"){y+=x2;}
                else if(ope=="-"){y-=x2;}
                return true;
            }
        }
        throw new Exception("Expr error");
    }

    bool Expr_E2(ref string yOpe, ref int y)
    {
        int x1=0;
        string ope="";
        int x2=0;
        if ( TokenCheck("+") ) {
            yOpe = "+";
            if ( Expr_T(ref x1) ) {
                y = x1;
                if ( Expr_E2(ref ope, ref x2) ) {
                    if (ope=="+"){y+=x2;}
                    else if(ope=="-"){y-=x2;}
                    return true;
                }
            }
        }
        else if ( TokenCheck("-") ) {
            yOpe = "-";
            if ( Expr_T(ref x1) ) {
                y = x1;
                if ( Expr_E2(ref ope, ref x2) ) {
                    if (ope=="+"){y+=x2;}
                    else if(ope=="-"){y-=x2;}
                    // else{y=y;}
                    return true;
                }
            }
        }
        else{
            return true;
        }
        throw new Exception("Expr error");
    }

    bool Expr_T(ref int y)
    {
        int x1=0;
        string ope="";
        int x2=0;
        if ( Expr_F(ref x1) ) {
            y = x1;
            if ( Expr_T2(ref ope, ref x2) ) {
                if (ope=="*"){y*=x2;}
                else if(ope=="/"){y/=x2;}
                return true;
            }
        }
        throw new Exception("Expr error");
    }

    bool Expr_T2(ref string yOpe, ref int y)
    {
        int x1=0;
        string ope="";
        int x2=0;
        if ( TokenCheck("*") ) {
            yOpe = "*";
            if ( Expr_F(ref x1) ) {
                y=x1;
                if ( Expr_T2(ref ope, ref x2) ) {
                    if (ope=="*"){y*=x2;}
                    else if(ope=="/"){y/=x2;}
                    return true;
                }
            }
        }
        else if ( TokenCheck("/") ) {
            yOpe = "/";
            if ( Expr_F(ref x1) ) {
                y=x1;
                if ( Expr_T2(ref ope, ref x2) ) {
                    if (ope=="*"){y*=x2;}
                    else if(ope=="/"){y/=x2;}
                    return true;
                }
            }
        }
        else{
            return true;
        }
        throw new Exception("Expr error");
    }

    bool Expr_F(ref int y)
    {
        if ( TokenCheck("(") ) {
            if ( Expr_E(ref y) ) {
                if ( TokenCheck(")")) {
                    return true;
                }
            }
        }
        else if ( TokenIntCheck(ref y) ) {
            return true;
        }
        ms.Position = pos;
        throw new Exception("Expr error");
    }

    // ---------------------------------------------

    bool TerminalCheck()
    {
        int b = ms.ReadByte();
        if ( b < 0 ) {
            return true;
        }
        else {
            ms.Position--;
            return false;
        }
    }
    bool TokenIntCheck(ref int x)
    {
        long pos = ms.Position;
        int i = 0;
        int b;
        x = 0;
        //Console.WriteLine("CheckNum");
        while ( ( b = ms.ReadByte() ) >= 0 ) {
            if ('0'<=b&&b<='9') {
                x *= 10;
                x += b-'0';
                i++;
            }
            else if ('a'<=b&&b<='z') {
                ms.Position = pos;
                return false;
            }
            else if ('A'<=b&&b<='Z') {
                ms.Position = pos;
                return false;
            }
            else {
                break;
            }
        }
        if (i==0){
            ms.Position = pos;
            return false;
        }
        if (b>=0) {
            ms.Position--;
        }
        Console.WriteLine("Num");
        return true;
    }

    bool TokenCheck(string s)
    {
        byte[] t = Encoding.UTF8.GetBytes(s);
        //Console.WriteLine("CheckToken('"+s+"')");
        long pos = ms.Position;
        int i = 0;
        int b;
        while ( i<t.Length ) {
            b = ms.ReadByte();
            if (b==t[i]) {
                i++;
            }
            else {
                ms.Position = pos;
                return false;
            }
        }
        Console.WriteLine("Token('"+s+"')");
        return true;
    }

    [STAThread]
    static void Main(string[] args)
    {
        string exprStr = "1+2+3";
        if (args.Length>=1) {
            exprStr = String.Join("",args);
        }
        Console.WriteLine("Input: "+exprStr);

        var t = new TestLL();
        t.Parse(exprStr);
    }
}

実行結果

Input: 1+2+3
6

Input: 1+2*3
7

Input: 1+2*(3-1)
5

Input: 7/2
3

※除算は整数除算なので、7/2は3.5にはならず、3になります。