構文解析

次は構文解析器(Parser)を作ります。今回作るのは優先順位無しの構文解析器です。構文解析器いうと堅苦しいのでパーサと呼ぶことにします。以下にパーサのプログラムを示します。

class Parser
  def parse(src)
    @lexer = Lexer.new(src)
    tokens = @lexer.tokens
    exp = tokens.shift.to_i
    while tokens.first == "+" || tokens.first == "-" || tokens.first == "*" || tokens.first == "/"
      op = tokens.shift
      num = tokens.shift.to_i
      exp = [op, exp, num]
    end
    exp
  end
end

パーサクラスにあるのは parse メソッドだけです。parse メソッドではソースプログラムを読み込み、字句解析器 (Lexer) を作成してトークン配列を取得します。トークン配列には数、記号、数、記号、数と入っているので最初に数を読み込み to_i で文字列を数値に変換します。次は記号のはずなので、記号を読み込みます。記号じゃなかったらループを抜けます。でopに記号を読み込み、いままで持っていた式と今読み込んだ記号と数字を１つの２分木として１つにまとめます。 1+2*3 の場合は [+,1,2] が最初できあがります。次にもう一度ループして [*,[+,1,2],3] となって終了します。よくあるプログラミング言語の場合は掛け算を優先的に結合するので [+,1,[*,2,3]] となるのですが、今回は初めてなので優先順位は持たせていません。優先順位をつけたプログラムは次回以降に説明します。