構文解析その②

EBNF をコードに変換

昨日は、EBNF をそのままコードに変換してみました。作った感じ、以下のようなルールで機械的にコードに変換できそうです（どこかに書いてあったものではないので、間違っているかも）。

表1: メタ記号（再掲）

記号	意味
{ }	カッコ内が 0 回以上の繰り返しと一致
[ ]	カッコ内が 0 回または 1 回一致
a \| b	a または b
()	カッコ内をひとまとまりとする

非終端記号は一つの関数にする

関数内では、生成規則の順に読んでいく

終端記号の場合、普通にトークンを読み込む
非終端記号の場合、対応する非終端記号の関数を呼び出す

{} [] | のときにトークンを先読みし、条件分岐する

{} は while 文へ（先読みしたトークンでループの条件を判断）
[] は if 文へ（先読みしたトークンが条件に）
| は if 文で分岐になるか、{} や [] の条件判断の OR 文になる

このように書いてみると、LL(1) 法で解析できる文法の理解が進みます。おそらく、以下のことに注意しないと思います。

非終端記号の最初の生成規則に、同じ非終端記号が出てこないようにする

左再帰になって無限ループが起きてしまう
生成規則の最初の非終端記号を考えないといけない

{} [] | のときに、一つ先読みしただけで判断できるようにしないといけない

{} や [] の 1 記号目が非終端記号の場合、展開先を考えないといけない

その上で、一意に決まる必要がある

文法全体で考える必要あり（後述）

いずれにしても、非終端記号が出てくるときは、その生成規則もみて判断しないといけません。また、上に書いた「文法全体で考える必要あり」については、例えば

コード1: これは多分ダメ

factor: 	NUMBER | "/" expression "/"
term:		factor { ("*" | "/") factor }
expression:	term { ("+" | "-") term }

としてしまうと、

factor { ("*" | "/") factor }

の後ろの繰り返し部分で、

 ("*" | "/") factor

へ進むべきなのか、それとも factor の

"/" expression "/"

へ進むべきなのかわからなくなります。こういったエラーはうっかり見逃しそうです。つまり、メタ記号の 1 記号目は、全体で注意深くチェックする必要がありそうです。

こう考えると、手でコードを書いていくのはなかなか大変そうですので、やはり何らかのジェネレーターは欲しいところで、すくなくとも、手で書く前には、何らかの既存システムに入れて文法の確認はしたほうが良さそうです。一方で、文法のエラーのチェックやジェネレータの作成は思ったより簡単そうです。

演算子順位法

少々浮気。

2 週間でできる ! スクリプト言語の作り方の方に載っていた、中置記法の二項演算子の構文解析を、演算子の優先度をベースに解析できる方法が乗っていました。この方法を使えば、例えば、演算子を OP として、

コード2: 四則演算

factor: 	NUMBER | "(" expression ")"
expression:	term { OP term }

とだけしておき、普段は LL 法で構文解析し、expression の解析のところだけは演算子順位法を使うということができるようです。演算子はそれなりの数があり、優先順位を EBNF だけで書いていると大変（更にそれを実装するのはしんどい）ですので、とても便利そうです。

本には、アルゴリズムの解説も載っていたのですが、コードを読んだほうが理解が進んだので、とりあえず実装してみることにしました。

using SumireScriptLib.LexicalAnalyzer;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SumireScriptLib.Parser
{
    public class SsParserLLwithOpPrecedence : SsParser
    {

        Dictionary<SsTokenType, SsBinarOperator> operators = new Dictionary<SsTokenType, SsBinarOperator>();


        public SsParserLLwithOpPrecedence(TextReader reader)
            :base(reader)
        {
            //演算子の登録
            operators.Add(SsTokenType.Op_Plus, new SsBinarOperator(SsTokenType.Op_Plus, 20));
            operators.Add(SsTokenType.Op_Minus, new SsBinarOperator(SsTokenType.Op_Minus, 20));
            operators.Add(SsTokenType.Op_Astarisk, new SsBinarOperator(SsTokenType.Op_Astarisk, 30));
            operators.Add(SsTokenType.Op_Slash, new SsBinarOperator(SsTokenType.Op_Slash, 30));

        }

        public override SsASTree Parse()
        {
            SsASTree ret = m_expression();

            if (la.PeekToken(0).TokenType != SsTokenType.EndOfCode)
            {
                throw new SsSyntaxErrorException(
                    string.Format("なんかおかしいはず {0}", la.PeekToken(0)));
            }

            return ret;
        }


        private SsASTree m_factor()
        {
            //前回のまま
            // factor: 	NUMBER | "(" expression ")"

            SsToken first = la.PeekToken(0);

            if (first.TokenType == SsTokenType.Number)
            {
                return new SsASTree(la.GetToken());
            }
            else if (first.TokenType == SsTokenType.Bk_LR)
            {
                SsASTree tree = new SsASTree("factor");

                tree.Add(new SsASTree(la.GetToken()));
                tree.Add(m_expression());

                SsToken close = la.GetToken();
                if (close.TokenType == SsTokenType.Bk_RR)
                {
                    tree.Add(new SsASTree(close));
                }
                return tree;
            }

            throw new SsSyntaxErrorException(string.Format("factor {0}", first));
        }



        private SsASTree m_expression()
        {

            SsASTree tree = m_factor();
            SsBinarOperator next = null;

            while ((next = nextOperator()) != null)
            {
                tree = doShift(tree, next);
            }

            return tree;
        }

        private SsASTree doShift(SsASTree left, SsBinarOperator bop)
        {
            //演算子を読み込み
            SsASTree op = new SsASTree(la.GetToken());
            //右辺を読み込み
            SsASTree right = m_factor();

            SsBinarOperator next = null;
            while ((next = nextOperator()) != null && rightIsExpr(bop, next))
            {
                right = doShift(right, next);
            }
            SsASTree tree = new SsASTree("expression");
            tree.Add(left);
            tree.Add(op);
            tree.Add(right);
            return tree;
        }

        private SsBinarOperator nextOperator()
        {
            SsToken t = la.PeekToken();
            if (operators.ContainsKey(t.TokenType))
            {
                return operators[t.TokenType];
            }
            return null;
        }

        private static bool rightIsExpr(SsBinarOperator bop, SsBinarOperator next)
        {
            if (next.IsLeftAssoc)
            {
                return bop.Precedence < next.Precedence;
            }
            else
            {
                return bop.Precedence <= next.Precedence;
            }
        }
    }

    class SsBinarOperator
    {
        private SsTokenType tokenType;
        private int precedence; //数値大きいほど、優先順位が高い
        private bool isLeftAssoc; // 左結合かどうか

        public SsTokenType TokenType { get { return tokenType; } }
        public int Precedence { get { return precedence; } }
        public bool IsLeftAssoc { get { return isLeftAssoc; } }


        public SsBinarOperator(SsTokenType tt,int prec, bool isLeft = true)
        {
            tokenType = tt;
            precedence = prec;
            isLeftAssoc = isLeft;
        }

        public override string ToString()
        {
            return tokenType.ToString();
        }
    }
}

上記に加えて、前回のコードの SsASTree クラスの Calc 内の、expression での計算も、掛け算・割り算もやるように修正しました。

こちらに、前回同様、

((6 + 8) * 7 + 8 - 7) / 9 / 3

を入れると以下のような感じになります。なんとなく、良さそうです。

expression[1]
    expression[1]
        expression[3]
            term[3]
                factor[3]
                    Bk_LR[1:0-1,1] (
                    expression[1]
                        expression[3]
                            expression[3]
                                expression[1]
                                    term[3]
                                        factor[3]
                                            Bk_LR[1:1-1,2] (
                                            expression[1]
                                                expression[3]
                                                    term[1]
                                                        Number[1:2-1,3] 6 (Integer)
                                                    Op_Plus[1:4-1,5] +
                                                    term[1]
                                                        Number[1:6-1,7] 8 (Integer)
                                            Bk_RR[1:7-1,8] )
                                        Op_Astarisk[1:9-1,10] *
                                        Number[1:11-1,12] 7 (Integer)
                                Op_Plus[1:13-1,14] +
                                term[1]
                                    Number[1:15-1,16] 8 (Integer)
                            Op_Minus[1:17-1,18] -
                            term[1]
                                Number[1:19-1,20] 7 (Integer)
                    Bk_RR[1:20-1,21] )
                Op_Slash[1:22-1,23] /
                Number[1:24-1,25] 9 (Integer)
            Op_Slash[1:26-1,27] /
            Number[1:28-1,29] 3 (Integer)

Result = 3.666667

6 + 8 * 7 + 8 - 7 / 9 / 3 + 18

を入れると、

expression[1]
    expression[3]
        expression[3]
            expression[3]
                expression[3]
                    term[1]
                        Number[1:0-1,1] 6 (Integer)
                    Op_Plus[1:2-1,3] +
                    expression[1]
                        term[3]
                            Number[1:4-1,5] 8 (Integer)
                            Op_Astarisk[1:6-1,7] *
                            Number[1:8-1,9] 7 (Integer)
                Op_Plus[1:10-1,11] +
                term[1]
                    Number[1:12-1,13] 8 (Integer)
            Op_Minus[1:14-1,15] -
            expression[1]
                expression[3]
                    term[3]
                        Number[1:16-1,17] 7 (Integer)
                        Op_Slash[1:18-1,19] /
                        Number[1:20-1,21] 9 (Integer)
                    Op_Slash[1:22-1,23] /
                    Number[1:24-1,25] 3 (Integer)
        Op_Plus[1:26-1,27] +
        term[1]
            Number[1:28-1,30] 18 (Integer)

Result = 87.74074

となります。Google に計算式を入れたところ、同じ結果が返ってきましたので、多分あってます。

まとめ

EBNF →コード変換について考えました。そして、ちょっと浮気して、演算子優先順位法を試してみました。演算子は比較演算を考えるとなかなかの量がありますので、演算子優先順位法はほぼ必須なように思います。

次は、EBNF （風の表記）のパーサを作り、それを使って、EBNF からコードを生成するようなプログラムを作ってみようと思います。EBNF を書きながら EBNF のデバッグをして、出力のデバッグをして…といった作業を考えると、JavaScript で書き直そうかと思います（C# だとテスト入力用のエディタやデバッグ表示の表現を作るのが大変だったためです）。

構文解析その②

EBNF をコードに変換

演算子順位法

まとめ

目次

アウトライン