本家「@IT」にはない内容をエンジニアライフで技術紹介するコラム。広く議論する場になることを目指します。

第013回_構文解析Sample4

»

今回は、Sample4としてAlternative構文を解析できるようにします。

Sample4 Alternative構文を解析する

EBNFの生成規則の内、選択を表現するためにEBNFデータツリーのAlternative構文を解析します。

処理シーケンスを検討してからソースコードを紹介する流れで説明します。

1.Alternativeの処理シーケンス
Alternative構文の確認する内容は、
 N個の子ノードを順にチェックし、
 NGが返ってきたら次の子ノードへ
 OKが返ってきたところで中断する
ことです。

より詳細な処理シーケンスは次のようになります。
1.子ノード数分のループ
 1-1.子ノードを処理する
 1-2.結果がOKの場合
  1-2-1.処理を中断する
 1-3.結果がNGの場合
  1-3-1.次の子ノードへ

尚、戻り値については、全てがNGならAlternativeの戻り値もNGになります。いずれかの子ノードでOKならAlternativeの戻り値もOKになります。両方の状況を考えるとAlternativeの戻り値を別途設定する必要はありません。

2.処理シーケンスの問題点
Repetitionと同じように子ノードの少なくとも先頭1トークンがOKでそれより後ろのトークンがNGの場合は戻り値がNGでもAlternativeのループは中断し、Alternativeの戻り値もNGになります。よって、子ノード処理のループの中断条件は戻り値ではなく、
 処理OKの場合:処理を中断する(トークンの処理数は1以上になる)
 処理がNGの場合:
  子ノードの処理数が1つでもある場合: 処理を中断する
  子ノードの処理数が0の場合    : 次の子ノードへ
となり、整理すると、
 子ノードの処理数が1つでもある場合: (結果がOKでもNGでも)処理を中断する
 子ノードの処理数が0の場合    : 次の子ノードへ
となります。

修正した処理シーケンスは次のようになります。
 1.子ノード数分のループ
  1-1.子ノードを処理する
  1-2.処理トークン数が0の場合
   1-2-1.次の子ノードへ
  1-3.処理トークン数が0でない(1つ以上ある)場合
   1-3-1.処理を中断する

サンプルの例示

シーケンスの検討が終わったので実装に入ります。
今回のサンプルは、EBNFデータツリーを
  seq(Sequence)
   ├+WORD ('standalone')
   ├+EqSeq(Sequence)
   | ├+rep1(Repetition(0,1) )
   | |  +S
   | ├+Symbol ('=')
   | └+rep2(Repetition(0,1) )
   |    +S
   └+alter(Alternative)
     ├+LITERAL ('yes')
     └+LITERAL ('no')
と定義して、入力トークンリストが
 WORD ('standalone') S SYMBOL ('=') S LITERAL ('yes')
のときtrueとなること、また、LITERAL ('no')としてもOKになること、
LITERAL ('yes')でもLITERAL ('no')でもないときfalseになることを確認します。
#以下にLITERAL ('yes')の場合だけを例示します。

AnalyzeSyntax

public class AnalyzeSyntax
{
    public static void main(String args[])
    {
         Sample4Visitor v = new Sample4Visitor();

         //EBNFデータツリーを構築する
         EbnfSequenceNode seq = new EbnfSequenceNode();
         {
             EbnfLimitedWordNode standalone
                         = new EbnfLimitedWordNode("standalone");

             EbnfSequenceNode eqSeq = new EbnfSequenceNode();
             {
                 EbnfRepetitionNode rep1 = new EbnfRepetitionNode(0,1);
                 {
                     EbnfWhiteSpaceNode s = new EbnfWhiteSpaceNode();
                     rep1.setChild(s);
                 }

                 EbnfSymbolNode           eq = new EbnfSymbolNode("=");
             
                 EbnfRepetitionNode rep2 = new EbnfRepetitionNode(0,1);
                 {
                     EbnfWhiteSpaceNode s = new EbnfWhiteSpaceNode();
                     rep2.setChild(s);
                 }
                 
                 eqSeq.addChild(rep1);
                 eqSeq.addChild(eq);
                 eqSeq.addChild(rep2);
             }
             
             EbnfAltanativeNode alter = new EbnfAlternative();
             {
                 EbnfLimitedLiteralNode  yes
                       = new EbnfLimitedLiteralNode("yes");
                 EbnfLimitedLiteralNode  no
                       = new EbnfLimitedLiteralNode("no");
                 
                 alter.addChild(yes);
                 alter.addChild(no);
             }

             seq.addChild(standalone);
             seq.addChild(eqSeq);
             seq.addChild(alter);
         }

         seq.accept(v);

         System.out.println(v.getResult());
    }
}

EbnfAlternativeNode

public class EbnfAlternativeNode implements EbnfNodeAcceptor
{
    protected ArrayList<EbnfNodeAcceptor> m_children;

    public EbnfAlternativeNode()
    {
        m_children = new ArrayList<EbnfNodeAccepter>();
    }

    public void addChild(EbnfNodeAcceptor child)
    {
        m_children.add(child);
    }

    public ArrayList<EbnfNodeAcceptor> getChildren()
    {
        return m_children;
    }

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

Sample4Visitor

public class Sample4Visitor extends EbnfVisitor
{
    private boolean m_result;
    private int              m_index;
    private ArrayList<Token> m_list;

    public Sample4Visitor()
    {
        m_result = true;
        
        m_index = 0;
        //字句解析で取得したトークン列の構成
        //WORD('standalone') S SYMBOL('=') S Literal(yes)
        m_list = new ArrayList<Token>();
        WordToken       token1 = new WordToken("standalone", 0, 10);
        WhiteSpaceToken token2 = new WhiteSpaceToken(10,1);
        SymbolToken     token3 = new SymbolToken("=", 11, 1);
        WhiteSpaceToken token4 = new WhiteSpaceToken(12,1);
        LiteralToken    token5 = new LiteralToken("yes", 13, 3);
        m_list.add(token1);
        m_list.add(token2);
        m_list.add(token3);
        m_list.add(token4);
        m_list.add(token5);
    }

    public void visit(EbnfAlternativeNode n)
    {
        ArrayList<EbnfNodeAcceptor> children = n.getChildren();

        //処理前のトークン位置を保存する
        int count = m_index;

        for(EbnfNodeAcceptor child :children)
        {
            child.accept(this);

            //処理後のトークン位置を保存する
            int count2 = m_index;

            //処理トークンがない場合
            if (count == count2)
            {
                //次の子ノードへ
            }
            //処理トークンがある場合
            else
            {
                break;
            }
        }
    }

    public boolean getResult(){割愛}
    public void visit(EbnfLimitedWordNode n){割愛}
    public void visit(EbnfLimitedLiteralNode n){割愛}
    public void visit(EbnfSymbolNode n){割愛}
    public void visit(EbnfSequenceNode n){割愛}
    public void visit(EbnfWhiteSpaceNode n){割愛}
    public void visit(EbnfRepetitionNode n){割愛}
}

Sample紹介の終りに

Sample1~Sample4を通してEBNFデータツリーとVisitorによる
 ・終端
 ・連接
 ・繰り返し
 ・選択
を使った構文解析の実装例を紹介できました。

ただし、第10回_新説Visitorパターンで述べたVisitorパターンを使うことによるメリットは今後の意味解析や抽象構文木の生成で発揮することになりますから、今はその良さがわかり難いかもしれません。
それ以外のメリットとして、後述する条件付字句解析のための切り替えポイントを平易に実装できるという点があります。

  例:
   public void visit(EbnfCDataNode n)
   {
    CDataの条件の開始制御
    //この区間でトークンの取り出しをするときは、
    //CData用の条件付字句解析を呼び出す
    CDataの条件の終了制御
   }

XML構文は読みやすさを重視してLL (1)にはなっていませんので次回から数回にわたってXML構文のLL (1)化を行います。
Comment(0)

コメント

コメントを投稿する