前置単項演算子と非結合二項演算子も扱える演算子優先順位構文解析器

Wikipedia から直訳した「演算子優先順位構文解析器」は二項演算子で左結合か右結合のものしか扱えないので、 加えて二項演算子の非結合のものと、 前置単項演算子も扱えるように改良しました。 ついでに、 expression から直接 expression への再帰呼び出しをループに変換しました。

演算子の優先順位定義では、 同じ記号で単項演算子だったり二項演算子だったりするものがあるので、 別の演算子として扱うために、スラッシュに 1 か 2 を続けるポストフィックスをつけることで区別します。 さらに、 単項演算子の場合は、 Operator 構造体の assoc に :unary をセットしておきます。 この実装ではポストフィックスと assoc フィールドの両方を正しく記述しないと、 単項演算子として処理できません。

二項演算子で非結合なものは、 assoc を :nonassoc にします。

上向き構文解析との対応関係では、 スタックへのプッシュがシフトに、 ポップが還元になっています。 単項演算子は常にシフトします。 二項演算子はスタックのトップの演算子の優先順位と結合性によりシフトするか還元します。 二項演算子だけの版と同じく、 スタックのトップには前回シフトした演算子が入ります。 ただし、 今回は、 それが単項演算子なのか、 それとも二項演算子なのか区別をしないといけないため、 スラッシュ・ポストフィックスをつけたままでスタックへプッシュします。

2013年3月19日修正: 単項演算子をシフトするとき優先順位を判定するようにしました。

#!/usr/bin/env ruby

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

FUNCTOR = {
  'or/2'  => Operator.new( 1, :left),
  'and/2' => Operator.new( 2, :left),
  'not/1' => Operator.new( 3, :unary),
  '==/2'  => Operator.new(10, :nonassoc),
  '</2'   => Operator.new(10, :nonassoc),
  '+/2'   => Operator.new(20, :left),
  '-/2'   => Operator.new(20, :left),
  '*/2'   => Operator.new(21, :left),
  '//2'   => Operator.new(21, :left),
  '%/2'   => Operator.new(21, :left),
  '-/1'   => Operator.new(22, :unary),
  '**/2'  => Operator.new(23, :left),
  '+/1'   => Operator.new(24, :unary),
  '!/1'   => Operator.new(24, :unary),
}

def expression(input)
  stack = []
  while true
    if FUNCTOR.key?(input.first.to_s + '/1')
      unary = input.shift.to_s + '/1'
      if not stack.empty?
        f = stack.last
        if FUNCTOR[f].precedence > FUNCTOR[unary].precedence
          raise "Syntax error"
        end
      end
      stack.push unary
      next
    end

    expr = primary(input)

    break if not FUNCTOR.key?(input.first.to_s + '/2')
    binary = input.shift.to_s + '/2'
    while not stack.empty?
      f = stack.last
      operator = f.chop.chop!
      break if FUNCTOR[f].precedence < FUNCTOR[binary].precedence
      if FUNCTOR[f].assoc == :unary
        stack.pop
        expr = [operator, expr]
      else
        if FUNCTOR[f].assoc == :nonassoc and FUNCTOR[binary].assoc == :nonassoc
          raise "Syntax error"
        end
        break if FUNCTOR[f].precedence == FUNCTOR[binary].precedence \
              && FUNCTOR[f].assoc != :left
        lhs ,= stack.pop(2)
        expr = [lhs, operator, expr]
      end
    end
    stack.push expr, binary
  end

  while not stack.empty?
    f = stack.pop
    operator = f.chop.chop!
    if FUNCTOR[f].assoc == :unary
      expr = [operator, expr]
    else
      lhs = stack.pop
      expr = [lhs, operator, expr]
    end
  end
  expr
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(['not', '-', 2, '<', 3, '+', 4, '*', 5 , '+', 6, 'and', 10, '==', 10])
#=> [["not", [["-", 2], "<", [[3, "+", [4, "*", 5]], "+", 6]]], "and", [10, "==", 10]]
p expression(['!', '-', 2, '<', 3, '+', 4, '*', 5 , '+', 6, 'and', 10, '==', 10])
#=> [[["!", ["-", 2]], "<", [[3, "+", [4, "*", 5]], "+", 6]], "and", [10, "==", 10]]