数式を解くプログラムその4 - 構文解析1 - よねＫＥＮのプログラミング研究

id:yone-ken:20090219:p1 の続きです。例によって一般的な説明はwikipedia:構文解析を参照して頂くとして、「数式を解くプログラム」の場合の構文解析を具体的に説明します。そのために以前に定義した文法の抜粋を載せます。

   ::=  ('+' )* |  ('-' )*
         ::=  ('*' )* |  ('/' )*
       ::= '('  ')' | '+'  | '-'  |

上記の定義での部分は、字句解析の処理で単なる数値として既に処理済みです。そのため、文法として意識しなければならないのは、、、の3つの非終端記号です。非終端記号とは文法を構成するルールに名前を付けたもので、そのルールは::=で区切られた右辺に表現されています。実際に数式と文法を比較して解析するには、まず与えられた数式ととを比較します。そして、右辺の形に展開します。右辺の中に非終端記号が出てくる場合は、同様にその非終端記号の右辺の形に展開していきます。それらを繰り返すことで、最終的に非終端記号は消えてなくなり、(,),+,-,*,/,数値といった終端記号に置き換えられたら、構文解析は正常終了です。

コンピュータに行わせる処理はその前に人間が机上で同じことができなければ実装できません。まずは机上で、さまざまな式を文法に照らし合わせてみましょう。

例1

1+2

これを解析すると以下の図1のようになります。この図では、式と構文定義を上から順に照らし合わせて、非終端記号を右辺に展開していきます。

図1 式「1+2」の解析


→               // はではじまる。
→             // はではじまる。
→             // で、今のトークンはNumber(1)のため、である。
                       // 「1」は構文定義に合致した。
→  +    // 次のトークンはOpAddのため、その次はではなくである。
                       // 「+」は構文定義に合致した。
→  +  // はではじまる
→  +  // で、今のトークンはNumber(2)のため、である。
                       // 「2」は構文定義に合致した。
                       // 次のトークンはEofのため、構文解析は終了。

式「1+2」の字句解析では、Number、OpAdd、Number、Eofのトークンの並びが得られます。構文解析の手順は次の通りです。

式はです。
はで始まります。
はで始まります。
は(、+、-のどれかで始まるか、数値です。式の最初のトークンはNumber(1)のため、文法定義の中のが該当します。ここでの解析は終了です。
1つ戻って、の解析を続けます。の解析のうち、始めのの解析は終わっているので、次のトークンとして想定されるのは、*、/のどちらかか、そうでなければは終了です。Numberの次のトークンはOpAddで*、/のどちらでもないので、ここでの解析は終了です。
1つ戻って、の解析を続けます。の解析のうち、始めのの解析は終わっているので、次のトークンは+、-のどちらか、そうでなければの解析は終了です。次のトークンはOpAddのため、さらにその次のトークンはが期待されます。
はでは始まります。
は(、+、-のどれかで始まるか、数値です。次のトークンはNumber(2)のため、文法定義の中のが該当します。ここでの解析は終了です。
次のトークンはEofのため、これで構文解析は完了です。

式が複雑になっても、考え方は同じです。もう1例挙げます。次の例2について、自分でコンピュータになったつもりで解析してみてください。

例2

1+(2-3)*4/5

図2 式「1+(2-3)*4/5」の解析


→
→ 
→ 
→  + 
→  + 
→  + ( 
→  + ( 
→  + ( 
→  + ( 
→  + (  - 
→  + (  - 
→  + (  - 
→  + (  -  )
→  + (  -  ) * 
→  + (  -  ) * 
→  + (  -  ) *  / 
→  + (  -  ) *  /

今回はここまでです。次回も引き続き構文解析についての説明です