第018回_構文の実装_EbnfDocumentNode

» 2017/05/22

前回までで面倒な検討が必要な構文を除いた構文の検討が完了しました。
そこで今回からSampleで紹介した内容を拡張して本格的な実装に入りたいと思います。
最初に取り扱うのはEBNFデータツリーの作成です。

EBNFデータツリーによる構文の単純な実装

SampleのAnalyzeSyntax#mainメソッドの中で作成してきたEBNFデータツリーを別クラスに委譲します。

全体から見たEBNFデータツリーの位置は次のように構文解析器の一部となります。
18クラス構成図.jpg

18-1.ソフトウェア構成図
例として
　document ::= prolog element Misc*
を実装してみます。


public final class EbnfDocumentNode extends EbnfSequenceNode
{
    public EbnfDocumentNode()
    {
        //document ::= prolog element Misc*
    
        EbnfPrologNode prolog = new EbnfPrologNode();

        EbnfElementNode element = new EbnfElementNode();

        EbnfAsterRepetitionNode aster = new EbnfAsterRepetitionNode();
        {
            EbnfMiscNode misc = new EbnfMiscNode();

            aster.addChild(misc);
        }

        m_children.add(prolog);
        m_children.add(element);
        m_children.add(aster);
    }

    public void accept(EbnfVisitor v)
    {
        v.visit(this);
    }
}

EbnfDocumentNodeが表現していることは、
　　構文documentは連接を持つため、EbnfSequenceNodeを継承する
　　定義する子要素をコンストラクタで構築する
　　Visitorパターンを受け入れるためにacceptメソッドを持つ
というところです。

実装の問題点と対処の検討

Documentは自己参照や循環参照のない構文ですから、上記実装で問題はありません。
一方で、構文に自己参照や循環参照がある場合はコンストラクタにも自己参照や循環参照が発生して無限ループとなり、コンストラクタの初期化が完了しません。
LL法による構文解析では、構文は左再帰を持たない限り、自己参照や循環参照を持つことを許しますから、上記のような初期化の無限ループは実装で対処しなければいけません。

補足：自己参照と直接左再帰
　自己参照とは、
　　例:　<HOGE> ::= <FUGA> <HOGE>
　というように定義中に定義対象自体(例でいえば<HOGE>)が出てくる構文を意味します。
　また、直接左再帰とは、
　　例:　<HOGE> ::= <HOGE>　<FUGA>
　のように、右辺の最左端に左辺と同じ非終端が現れて無限ループに陥る構文を意味します。

補足：循環参照と間接左再帰
　循環参照とは、
　　例:　choice ::= SYMBOL ('(') S? cp ( S? SYMBOL ('|') S? cp )+ S? SYMBOL (')')
　　cp ::= (Name | choice | seq) (SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
のようにお互いが参照しあっている構文を意味します。
　また、間接左再帰とは、
　　例:　 <HOGE> ::= (<FUGA> <HOGE>) | <MOGA>
　　　　　<FUGA> ::= <HOGE> <MOGA>
　で <HOGE> から <FUGA> <HOGE> を導出して、さらに <HOGE> <MOGA> <HOGE>　のような導出が可能な場合に
　右辺の最左端に左辺と同じ非終端が現れて無限ループに陥る構文を意味します。

左再帰は除去しなければいけませんが、そうでない自己参照や循環参照を許すようにコンストラクタの実装を変更します。
変更は次のようにします。
　変更1.コンストラクタの処理をinit()メソッドへ移す
　変更2.初期化フラグ(m_initialized)を用意し、未初期化時のみ構文の構築処理を実施する

自己参照・循環参照を対処した実装

修正した実装は次のようになります。


public final class EbnfDocumentNode extends EbnfSequenceNode
{
    private boolean m_initialized;

    public EbnfDocumentNode()
    {
        m_initialized = false;
    }

    public void init()
    {
        if (m_initialized)
        {
            //何もしない
        }
        else
        {
            m_initialized = true;

            //以下、構文構築処理
            EbnfPrologNode prolog = new EbnfPrologNode();
            prolog.init();//初期化の追加

            EbnfElementNode element = new EbnfElementNode();
            element.init();//初期化の追加

            EbnfAsterRepetitionNode aster = new EbnfAsterRepetitionNode();
            {
                EbnfMiscNode misc = new EbnfMiscNode();
                misc.init();//初期化の追加

                aster.addChild(misc);
            }

            m_children.add(prolog);
            m_children.add(element);
            m_children.add(aster);
        }
    }

    public void accept(EbnfVisitor v)
    {
        v.visit(this);
    }
}

上記実装において、一つの懸念は初期化忘れです。
初期化忘れを防止する方法はいくつもあるのですが、EbnfDocumentNodeのインスタンスが実行中にただ1つで良いことを考慮するとシングルトンパターンを用いて対処できます。

初期化忘れを対処した実装


public final class EbnfDocumentNode extends EbnfSequenceNode
{
    private static final EbnfDocumentNode m_instance = new EbnfDocumentNode();
    private boolean m_initialized;

    private EbnfDocumentNode()
    {
        m_initialized = false;
    }

    public static EbnfDocumentNode getInstance()
    {
        m_instance.init();
        return m_instance;
    }

    private void init()//privateメソッドに変更
    {
        if (m_initialized)
        {
            //何もしない
        }
        else
        {
            m_initialized = true;

            //以下、構文構築処理
            //他の非終端記号もシングルトン化する
            EbnfPrologNode prolog = EbnfPrologNode.getInstance();

            //他の非終端記号もシングルトン化する
            EbnfElementNode element = EbnfElementNode.getInstance();

            EbnfAsterRepetitionNode aster = new EbnfAsterRepetitionNode();
            {
                //他の非終端記号もシングルトン化する
                EbnfMiscNode misc = EbnfMiscNode.getInstance();

                aster.addChild(misc);
            }

            m_children.add(prolog);
            m_children.add(element);
            m_children.add(aster);
        }
    }

    public void accept(EbnfVisitor v)
    {
        v.visit(this);
    }
}

終端記号の構文は、自己参照や循環参照がないので初期化フラグによる回避は不要です。
(内容は単純な実装に準拠します)

次回コラムではVisitorからトークンリストの生成機能(役割)を分離します。

0/1相転移炉 2017/05/22 10:00:00 Comment(0)

次の投稿へ

前の投稿へ