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

第012回_構文解析Sample3

»

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

Sample3 Repetition構文を解析する

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

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

1.Repetitionの処理シーケンス
Repetition構文の役割は、「上限値までの回数分、対象ノードを処理する」ことです。
より細かく説明すると繰り返し処理は、
 子ノードを処理して処理結果を得る
 子ノードの処理結果がOKの場合は、OK数(okCount)を+1する
 子ノードの処理結果がNGの場合は、処理を中断する
となります。

繰り返し処理には下限値があり、これを下回るとエラーとなるので追加処理として、
 OK数が下限値を越えているかどうかを判定する
 下限値より下の場合、NG
 下限値以上の場合、 OK
が必要となります。尚、下限値を設定しない場合は、下限値0となるのでOK数の下限値判定は常にOKになります。
一方、上限値が有る場合、それ以上を処理することがないというだけで、エラーになるわけではありません。

2.上限値がある場合と上限値がない場合のプログラム的な分離
for文・while文の処理は無限ループの場合とそうでない場合を分けた方がすっきりするので、
 1) for文・while文でループの回数に上限がある場合、その数値のカウントを取り、条件式とする
 2) for文・while文でループの回数に上限がない場合、無限ループを書く(常に条件 trueとする)
というように処理を分岐します。

3.ここまでの処理シーケンス
1.上限値がない場合
 1-1.無限ループ
  1-1-1.子ノードを処理して処理結果を得る
  1-1-2.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  1-1-3.子ノードの処理結果がNGの場合は、繰り返し処理を中断する
2.上限がある場合
 2-1.上限値までのforループ(okCountが条件値より下の間)
  2-1-1.子ノードを処理して処理結果を得る
  2-1-2.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  2-1-3.子ノードの処理結果がNGの場合は、繰り返し処理を中断する
3.OKカウントが下限値より少ない場合
 3-1.結果、NG
4.OKカウントが下限値以上の場合
 4-1.結果、OK

4.処理シーケンスの問題点
実は、前述の処理シーケンスには問題点があります。問題点を説明するために例を使って確認します。
例)
 生成規則
  X ::= A E
  A ::= ( B C D )*
 があるとする。
 このとき、EBNFデータツリーは
  X(Sequence)
  ├+A(Repetition 下限0,上限なし)
  | └+無名(Sequence)
  |  ├+B
  |  ├+C
  |  └+D
  |
  └+E
 となる。
 
 さて、このとき入力トークンによる判定を確認しましょう。
 1)入力トークン: B C D
1回目のループでSequenceがOKで返る。2回目へ (処理トークン:B C D)
2回目のループでSequenceがNGで返るのでループ処理を終了する(処理トークン:なし)
okカウント1、かつ下限値0なのでAはOKになる
Xに戻り、Eを判定しようとして、次のトークンが無いためNGになる。

 2)入力トークン: B C D B C D
1回目のループでSequenceがOKで返る。2回目へ (処理トークン:B C D)
2回目のループでSequenceがOKで返る。3回目へ (処理トークン:B C D)
3回目のループでSequenceがNGで返るのでループ処理を終了する(処理トークン:なし)
okカウント2、かつ下限値0なのでAはOKになる
Xに戻り、Eを判定しようとして、次のトークンが無いためNGになる。

 3)入力トークン: B C
1回目のループで構文のDまで到達してNGになり、無名SequenceもNGで返るのでループ処理を終了する(処理トークン:B C)
okカウント0、かつ下限値0なのでAはOKになる
Xに戻り、Eを判定しようとして、次のトークンが無いためNGになる。

3)の内容は先読みが無限にある理想的な解析器の場合、
 無名SequenceはNGで終わった場合、消費した処理トークン B Cを戻す。
 その上で、AはOKで返る。
 最後にXに戻り、Eを判定しようとして次のトークンがBなのでNGになる
となります。

本コラムの第3回で書いたように今回検討する解析器はLL (1)です。
LL (1)解析とは
LL (1)の解析方法について説明します。
LLとは "input from Left to right, performing Leftmost derivation"(左から右に入力があり、左端のトークンから構文を導出する)解析法です。構文を導出するとは、"適応する構文を決定する"と考えると良いと思いますが、詳しくは文脈自由文法のWikiの説明などを参考にしてください。また、括弧で囲まれた部分は先読みトークン数を示しており、1の場合は次のトークンを先読みして構文を決定することを意味します。
ということで、LL (1)は、1トークン分先読みしてある構文αにマッチした場合に、そのまま構文αの残りにマッチしなければならず、構文αの残りとマッチしなければその時点で構文解析エラーとなります。

検討を3)に戻すと、LL (1)解析が可能な構文では、消費したトークンB Cを戻す処理は必要ありません。
※もし、B Cを戻さなければいけなければ、それはLL (3以上)の構文であるということになります。「XMLの構文はLL (1)である」のでこのような実装は不要です。

では3)をLL (1)で解析した場合にその処理がどうなるかというと、
ループの中の処理の先頭で現在の処理トークン数を記憶する(処理数0)
子ノード(無名Sequence)の処理を順次行う(B,Cのトークンは構文とのマッチがOKになり、処理トークン数が2になる)
構文のDまで到達してNGになり、無名SequenceもNGで返る
無名SequenceがNGで返ったのでAのループ処理から抜ける
ここでAの戻り値は子ノード内での処理数が1以上になっているのでNGを返す(処理数の差が1以上ならLL (1)は構文決定しており構文エラーと判断できる)
AがNGを返すのでXはNGを返す。
となります。

 4)入力トークン: B C D B C E
これも3)と同じように、ここまでに検討した処理シーケンスでは上手くいきません。内容は3)と同じなのでLL (1)の動作結果のみ記載しておきます。

1回目のループでSequenceがOKで返る。2回目へ (処理トークン: B C D)
2回目のループでSequenceがNGで返るのでループ処理を終了する(処理トークン: B C)
Aの戻り値はSequenceが消費トークン1以上の処理をしているのでNGを返す。
Xは途中でNGとなっているので、NGを返す。

5.修正版の処理シーケンスの検討
3),4)がLL (1)で正しく処理できるように修正します。処理の修正方法は3つの方法があると思います。

●修正方法1 子ノードの消費したトークン数を数える方法
この方法は、子ノードを処理する前に現在のトークン位置(count)を記憶して、子ノードを処理した後かつ子ノードの結果がNGだった場合に、その時点でのトークン位置(count2)を確認して、
countとcount2が同じならば結果はOK
countとcount2が同じでないなら結果はNG
とします。つまり子ノードがNGの場合はcount==count2の条件結果をループ処理の結果とします。 ただし、下限値判定もあるので組み合わせによるRepetitionの最終結果は次のようになります。
下限値判定処理ループの結果 最終結果
NGOKNG
NGNGNG
OKOKOK
OKNGNG

修正した処理は次のようになります。
1.上限値がない場合
 1-1.無限ループ
  1-1-1.countを取得する
  1-1-2.子ノードを処理する
  1-1-3.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  1-1-4.子ノードの処理結果がNGの場合
   1-1-4-1.count2を取得する
   1-1-4-2.count==count2をokFlagに保存する
   1-1-4-3.繰り返し処理を中断する

2.上限がある場合
 2-1.上限値までのforループ
  2-1-1.countを取得する
  2-1-2.子ノードを処理する
  2-1-3.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  2-1-4.子ノードの処理結果がNGの場合は
   2-1-4-1.count2を取得する
   2-1-4-2.count==count2をokFlagに保存する
   2-1-4-3.繰り返し処理を中断する

3.OKカウントが下限値より少ない場合
 3-1.結果、NG
4.OKカウントが下限値以上の場合
 4-1.結果、okFlagとする

●修正方法2 Sequenceで1個以上トークンを消費してNGになった場合は例外を投げる方法
この方法は、Sequenceの子ノード処理においてokCountが0でなくかつ結果がNGの場合、例外(SyntaxErrorException)を投げる方法です。
例外をRuntimeExceptionの継承クラスにする場合は問題ないですがRuntimeExceptionの継承クラスにしない場合は各メソッドにthrows句が必要になります。
この修正方法はどこで例外を捕捉するのかを決定するために「エラー処理に関する検討をする」のが大変です。簡単に考えるならばrootノード部分で捕捉すれば最低限、問題はないでしょう。

●修正方法3 Sequenceで1個以上トークンを消費してNGになった場合は戻り値フィールドに異常値を設定する方法
この方法は、Repetitionで処理しないという点で修正方法2と同じですが、
例外を投げずに、戻り値を拡張します。 拡張の方法は、Visitorのフィールド:boolean m_result値(OKとNGの2値判定)を変更して、
OK, NG, SyntaxErrorを示す3値判定に変更します。
Visitorのフィールド意味説明
m_reuslt.isOk();OK構文にマッチした
m_result.isNg();NG構文の最初の終端/非終端記号がマッチしなかった
m_result.isError();Error構文の最初の終端/非終端記号がマッチしたのに、残りの部分のどこかでNGになった

修正した処理は次のようになります。
1.上限値がない場合
 1-1.無限ループ
  1-1-1.子ノードを処理する
  1-1-2.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  1-1-3.子ノードの処理結果がNG/Errorの場合
   1-1-3-1.繰り返し処理を中断する

2.上限がある場合
 2-1.上限値までのforループ
  2-1-1.子ノードを処理する
  2-1-2.子ノードの処理結果がOKの場合は、OKカウント(okCount)を+1する
  2-1-3.子ノードの処理結果がNGの場合は
   2-1-3-1.繰り返し処理を中断する

3.OKカウントが下限値より少ない場合
 3-1.結果、NG
4.OKカウントが下限値以上の場合
 4-1.Repetitionとしての戻り値を得る
  4-1-1.処理結果がOK/NGの場合は戻り値をOKとする  (VisitorResultの中)
  4-1-2.処理結果がErrorの場合は戻り値をErrorとする(VisitorResultの中)

修正方法の比較
修正方法修正内容修正箇所
1Visitorの管理するフィールド値として処理するRepetition
2例外として処理するSequence、Repetition
3Visitorの管理するフィールド値として処理するSequence、Repetition、全ての戻り値

ここで考える必要があるのは修正方法2,3に求められる内容です。修正方法2,3が求めるのは構文解析エラーとなったときにどのような処理をするべきかです。
というわけで、パーサの構文解析エラー時の処理について少しお話します。

パーサの構文解析エラー処理
XMLファイルにしてもソースコードにしても、人間の作成したファイルに含まれるエラーの数は1つとは限りません。このことは、仮にソースコードのコンパイル時に先頭のたった1つのエラーしか発見できないとすれば1回のソースコード作成時にN回のコンパイル作業が必要になることを示しています。現実のコンパイラの機能は1回のコンパイルによって1つ以上のエラーを発見することから、先の仮定は構文解析の機能として正しくなく、構文解析器は先頭のエラーを発見しても処理を中断せずに最大数のエラーを発見するべきです。

結論
パーサの構文解析エラー時は処理を完全に終了することなく、残りのファイルに潜むエラーも報告すべきです。これは最終的な話であって、VisitorパターンとEBNFデータツリーを使って構文解析の正常系が表現できるかのSampleにはふさわしくありません。よって、今回はとりあえず、修正方法1を使って実装します。

サンプルの例示

ようやくとなりますが、サンプルを紹介します。
構文は、
 EBNFデータツリー:
  seq(Sequence)  
   ├+WORD 
   ├+EqSeq(Sequence)    
   | ├+rep1(Repetition(0,1) )
   | |  +S      
   | ├+Symbol('=')  
   | └+rep2(Repetition(0,1) )
   |    +S      
   └+LITERAL   
とし、これに対し、
 入力トークンリスト:WORD ('version') S SYMBOL ('=') LITERAL ('1.1')
を解析する処理を考えてみます。

ポイントとしては、
 SYMBOL ('=')の前のSがあってOKになって
 SYMBOL ('=')の後ろのSがなくてOKになる
箇所を確認してください。

analyzeSyntax

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

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

             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);
             }
             
             EbnfLimitedLiteralNode  num
                     = new EbnfLimitedLiteralNode("1.1");

             seq.addChild(version);
             seq.addChild(eqSeq);
             seq.addChild(num);
         }

         seq.accept(v);

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

EbnfWhiteSpaceNode

public class EbnfWhiteSpaceNode implements EbnfNodeAcceptor
{
    private static final EbnfWhiteSpaceNode m_instance
                = new EbnfWhiteSpaceNode();

    protected EbnfWhiteSpaceNode()
    {
    }

    public static EbnfWhiteSpaceNode getInstance()
    {
        return m_instance;
    }

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

EbnfRepetitionNode

public class EbnfRepetitionNode implements EbnfNodeAcceptor
{
    public static final int ASTER = -1;

    protected EbnfNodeAcceptor m_child;
    private int m_lowerbound;
    private int m_upperbound;

    public EbnfRepetitionNode(int lower, int upper)
    {
        m_child = null;
        m_lowerbound = lower;
        m_upperbound = upper;
    }

    public void setChild(EbnfNodeAcceptor child)
    {
        m_child = child;
    }

    public EbnfNodeAcceptor getChild()
    {
        return m_child;
    }

    public int getUpper()
    {
        return m_upperbound;
    }

    public int getLower()
    {
        return m_lowerbound;
    }

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

Sample3Visitor

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

    public Sample3Visitor()
    {
        m_result = true;
        
        m_index = 0;
        
        //字句解析で取得したトークン列の構成
        m_list = new ArrayList<Token>();
        WordToken       token1 = new WordToken("version", 0, 7);
        WhiteSpaceToken token2 = new WhiteSpaceToken(7,1);
        SymbolToken     token3 = new SymbolToken("=", 8, 1);
        LiteralToken    token4 = new LiteralToken("1.1", 9, 3);
        m_list.add(token1);
        m_list.add(token2);
        m_list.add(token3);
        m_list.add(token4);
    }

    public void visit(EbnfWhiteSpaceNode n)
    {
        Token token = m_list.get(m_index);
        
        if(token instanceof WhiteSpaceToken)
        {
            m_index++;
            m_result = true;
        }
        else
        {
            m_result = false;
        }
    }

    public void visit(EbnfRepetitionNode n)
    {
        int upper = n.getUpper();
        int lower = n.getLower();
        EbnfNodeAcceptor node = n.getChild();
        int size = children.size();
        int okCount=0;

        boolean okFlag = true;
        
        //上限値がない場合
        if (upper == EbnfRepetitionNode.ASTER)
        {
            //無限ループ処理
            while(true)
            {
                int count = m_index;
                
                //子ノード評価を行う
                node.accept(this);

                //評価結果がOKの場合
                if (m_result)
                {
                    //OKカウントを+1する
                    okCount++;
                }
                //評価結果がNGの場合
                else
                {
                    int count2 = m_index;
                    okFlag = (count == count2);
                    
                    //ループ処理を中断する
                    break;
                }
            }
        }
        //上限値がある場合
        else
        {
            //処理ループ(0~上限値まで)
            for (int i=0; i<upper; i++)
            {
                int count = m_index;

                //子ノード評価を行う
                node.accept(this);

                //評価結果がOKの場合
                if (m_result)
                {
                    //OKカウントを+1する
                    okCount++;
                }
                //評価結果がNGの場合
                else
                {
                    int count2 = m_index;
                    okFlag = (count == count2);
                    
                    //ループ処理を中断する
                    break;
                }
            }
        }

        //OKカウントが下限値より少ない場合
        if(okCount<lower)
        {
            //評価NG
            m_result = false;
        }
        //OKカウントが下限値より多い場合
        else
        {
            //評価OK
            m_result = okFlag;
        }
    }

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

コメント

コメントを投稿する