演算子優先順位構文解析器

富豪的 CLOSURE 計算結果使い捨て型シフト還元解析おもちゃ」は、プログラミング言語用の構文解析器で使うのには向いていません。どちらかというと、左再帰があるテキスト処理やデータ処理の構文解析器に使えないものかと考えています。

ところで、プログラミング言語で上向き構文解析したい箇所と言えば、左再帰になっている二項演算子式の生成規則がまっさきに思い浮かびます。他は下向き構文解析向けの部分が大半です。それならば、下向き用の定番、再帰下降型解析器の中に上向き構文解析器を組み込めると何かと便利でしょう。そのような用途に、演算子優先順位構文解析器 (Operator-precedence parser) がうってつけです。yacc/bison のように優先順位と左結号か右結合かを指定するだけで望みのままに二項演算子を利用できる解析器を、再帰下降型構文解析器へシームレスに組み込むことができるようになります。

一見すると、再帰下降型構文解析器そっくりですが、この解析器はれっきとした上向き解析器です。シフトするか還元するかの判定はトークン先読みで注目している演算子の結合性と優先順位から判定します。この判定条件に上向き構文解析器の歴史的な古典、Dijkstra の操車場アルゴリズムと同じものを使います。還元するときはすべての二項演算子式が同じ長さの生成規則であることを利用します。

Wikipedia には擬似コードがあるだけなので、動くものを Ruby で記述してみました。括弧付きの中置記法の数式をトークンにばらして配列にしたものをパラメータに渡すと、構文解析して結果を返します。

2013年3月18日。前置単項演算子と非結合二項演算子も扱えるように改良したもの

#!/usr/bin/env ruby

Operator = Struct.new(:precedence, :assoc)

BINOP = {
  '+' => Operator.new(1, :left),
  '-' => Operator.new(1, :left),
  '*' => Operator.new(2, :left),
  '/' => Operator.new(2, :left),
  '%' => Operator.new(2, :left),
  '**' => Operator.new(3, :right),
}

def expression(input)
  lhs = primary(input)
  expr_op_expr(input, lhs, 0)
end

def expr_op_expr(input, lhs, min_precedence)
  while BINOP.key?(input.first) \
        && BINOP[input.first].precedence >= min_precedence
    op = input.shift
    rhs = primary(input)
    while true
      lookahead = input.first
      break if not BINOP.key?(lookahead)
      break if BINOP[lookahead].precedence < BINOP[op].precedence
      break if BINOP[lookahead].precedence == BINOP[op].precedence \
            && BINOP[lookahead].assoc == :left
      rhs = expr_op_expr(input, rhs, BINOP[lookahead].precedence)
    end
    lhs = [lhs, op, rhs]
  end
  lhs
end

def primary(input)
  case input.first
  when Numeric
    return input.shift
  when '('
    input.shift
    v = expression(input)
    input.first == ')' or raise "Syntax error"
    input.shift
    return v
  else
    raise "Syntax error"
  end
end

p expression([2, '+', 3, '+', 4, '**', 5, '%', 6, '+', 7])
#=> [[[2, "+", 3], "+", [[4, "**", 5], "%", 6]], "+", 7]