最近RPrecという演算子の優先順位に基づいて構文解析を行うRubyのライブラリを実装しました。 その中で、演算子の優先順位と結合順位についての理解が深まりました。

演算子の優先順位 (precedence) というのは、1 + 2 * 3が1 + (2 * 3)と解釈されて「*は+よりもつよく結合する」というように言われるものです。 この優先順位はJavaScriptであればこの辺りに、Rubyであればこの辺りにまとまっています。

そして、演算子の結合規則 (associativity) というのは、左結合とか右結合とか言われるものです。 1 + 2 + 3は(1 + 2) + 3と解釈されるので+は左結合であったり、a = b = 1がa = (b = 1)と解釈されるので=は右結合というようなものです。

今回は、この演算子の結合規則のバリエーションについて考察したことについて、まとめたいと思います。

想定読者: 構文解析やプログラミング言語の構文に興味があり、これらについて多少の知識があることを想定しています。

RPrec

RPrecはRubyで書かれた演算子の優先順位に基づく構文解析の実装です。 演算子の優先順位をRubyのDSLで記述して、レキサーを用意することで構文解析が行えます。

README.mdから取ってきた例ですが、次のコードは四則演算を含む簡単な式の構文を定義して、パースしています。

grammar = RPrec::DSL.build do
  prec :main => :add_sub
 
  prec :add_sub => :mul_div do
    left_assoc '+' do |left, op_tok, right|
      [:add, left, right]
    end
    left_assoc '-' do |left, op_tok, right|
      [:sub, left, right]
    end
  end
 
  prec :mul_div => :unary do
    left_assoc '*' do |left, op_tok, right|
      [:mul, left, right]
    end
    left_assoc '/' do |left, op_tok, right|
      [:div, left, right]
    end
  end
 
  prec :unary => :atom do
    prefix '+' do |op_tok, expr|
      [:plus, expr]
    end
    prefix '-' do |op_tok, expr|
      [:minus, expr]
    end
  end
 
  prec :atom do
    closed 'INT' do |int_tok|
      [:nat, int_tok.value]
    end
    closed '(', :add_sub, ')' do |lpar_tok, expr, rpar_tok|
      [:paren, expr]
    end
  end
end
 
lexer = RPrec::RegexpLexer.new(
  skip: /\s+/,
  pattern: %r{
    (?<digits>\d+)|
    (?<op>[-+*/()])
  }x
) do |match|
  if (value = match[:digits])
    ['INT', value.to_i]
  elsif (op = match[:op])
    op
  else
    raise ScriptError, 'Unreachable'
  end
end
 
grammar.parse(lexer.lex('1 + 2 * 3'))
# => [:add, [:int, 1], [:mul, [:int, 2], [:int, 3]]]

RPrecを実装するにあたって、演算子の優先順位を使った構文解析について調査・考察しました。 とくに結合規則のバリエーションについての理解が深まったため、この記事ではそれについて説明したいと思います。

演算子の優先順位を使った構文解析については、次の論文を参考にしました。

Danielsson, Nils Anders, and Ulf Norell. "Parsing mixfix operators." Implementation and Application of Functional Languages: 20th International Symposium, IFL 2008, Hatfield, UK, September 10-12, 2008 Revised Selected Papers 20. Springer Berlin Heidelberg, 2011.

こちらも面白い論文ですので、興味があったらぜひ目を通してみてください。

結合規則のバリエーション

最初に演算子の種類や優先順位、結合規則について確認します。 そして、優先順位と結合規則の関係から結合規則のバリエーションを考えていきます。

演算子の種類・優先順位・結合規則

まずはじめに、演算子の種類 (fixity) について確認します。 演算子は+や*などの二項 (中置) 演算子の他に、!のような前置演算子や配列の参照の[]のような後置演算子が存在します。 これらの関係を表で整理します。

また、これらの種類の他に整数などのリテラルや括弧で囲まれた式のような、演算子を含まない閉じた (closed) 式も構文には含まれます。

演算子には種類とは別に優先順位 (precedence) が存在します。 これは、複数の演算子が一つの式に並んでいるときに、どのように結合するかを決めるための順位です。 例えば、*は+よりも優先順位が高い演算子です。 そのため、1 * 2 + 3は(1 * 2) + 3のように解釈されます。 しかし、優先順位が同じ演算子が並んでいる場合、例えば1 + 2 + 3のような場合はどのように解釈されるのでしょうか？

このような、同じ優先順位の演算子が並んでいる場合の結合方法を決めるための規則が、結合規則 (associativity) です。 二項演算子の結合規則には主に、左結合 (left associative) と右結合 (right associative)が存在します。

左結合は同じ優先順位の演算子が並んだときに、左側か結合していく結合規則です。 例えば+はそのような演算子で1 + 2 + 3は(1 + 2) + 3のように解釈されます。 左結合は一番ポピュラーな結合規則で、+や*などの多くの演算子がこの結合規則になっています。

右結合は同じ優先順位の演算子が並んだときに、右側から結合していく結合規則です。 変数の代入に使う=はそのような演算子で、a = b = 1はa = (b = 1)のように解釈されます。 左結合と比べると右結合の演算子は多くありませんが、累乗を表す ** 演算子や、三項演算子... ? ... : ...は右結合として扱われることが多いです¹。

右結合の式と左結合の式は、たとえ両方が同じ優先順位だったとしても並べられないものとします。

二項演算子の優先順位と結合規則

演算子の前後に入ることのできる式の優先順位と、結合規則の関係について考えてみます。

まず、左結合の演算子について考えます。 左結合の演算子の前 (左側) の式には同じ優先順位までの演算子の式が入ることができます。 そして、後 (右側) の式には必ずそれよりも高い優先順位の演算子の式が入らなければいけません。

右結合の演算子の場合、演算子の前 (右側) の式はより高い優先順位の演算子の式でなければならず、後 (右側) の式には同じ優先順位までの演算子の式が入ります。

この関係を表にして整理してみましょう。 ここで、↑はより高い優先順位の演算子でなければいけないことを、=は同じ優先順位までの演算子の式が入ることを表します。

こうして見ると、さらに次の2つの結合規則のバリエーションが考えられます。

1. 両側が=になっている結合規則
2. 両側が↑になっている結合規則

しかし「両側が=になっている結合規則」はどこで結合すればいいのか分からずナンセンスです。

一方「両側が↑になっている結合規則」は、少なくとも意味を考えることはできるものになっています。 このような結合規則では、両側に同じ結合順位の演算子の式が入ってはいけないため、その演算子を複数並べてはいけないことを表せます。

実は、このような結合規則は非結合 (non-associative) と呼ばれるものです。 例えば、等価性をチェックする==演算子などは、言語によっては非結合の演算子として扱われることがあります。 1 == 2 == 3は(1 == 2) == 3と1 == (2 == 3)のどちらで解釈されてもあまり嬉しくないため、構文のレベルでこれを弾いてしまうことには価値があります。

単項演算子の優先順位

単項演算子 (前置演算子と後置演算子) についても、同様に優先順位との関係を考えてみます。

前置演算子は、その後の式には同じ優先順位までの演算子の式が入ることになります。 例えば+ + 1は+ (+ 1)のように解釈されます。 この結合の仕方は右結合と同様のため、同じ優先順位の右結合の演算子と並べることができます。

同様に、後置演算子は、その前の式に同じ優先順位までの演算子の式が入ります。 例えばfoo[1][2]は(foo[1])[2]のように解釈されます。 こちらの結合の仕方は左結合と同様のため、同じ優先順位の左結合の演算子と並べることができます。

ここで重要なことは、前置演算子も後置演算子も同じ優先順位までの式が入る (前の表で =) ことになっていることです。 つまり、↑が入るようなバリエーションも考えることができます。

この↑が入るバリエーションを、非結合前置演算子 (non-associative prefix) と非結合後置演算子 (non-associative postfix) と呼ぶことにします。 これらの非結合版の前置演算子や後置演算子はあまり言及されることがありませんが、一部便利なことがあります。 例えば制御構文のreturnを前置演算子として考えたとすると、return return 1はreturn (return 1)として解釈されてもあまり意味がないため、構文で弾けると便利でしょう。

結合規則のバリエーション

最後に、結合規則のバリエーションを表にまとめておきます。

RPrecでは、これらの結合規則・種類を実装しています。

あとがき

結合規則は「左右」なのに演算子の種類は「前置・後置」と、言葉遣いがブレていることは、結合規則と優先順位、さらに演算子の種類との考察をするのを難しているような気がします。

せっかくなので、RPrecを開発した理由についてメモしておきます。

RubyのパーサーのPrismは、式のパースに演算子の優先順位に基づく構文解析を利用しています。 しかし、最適化のために実装がやや独特な形になっており、単項演算子と二項演算子が絡む場合のパースが上手くいかないように見えました。 その辺りの問題を解決するために、これまでどうしているのかを調べるために実装したのが、RPrecになります。

RPrec自体は実験的なものですが、RBSの型定義なども用意してあり、使えるものになっているはずです。 これからも気が向いたときにアップデートしていくつもりなので、どうかよろしくお願いします。

それでは、最後まで目を通していただきありがとうございました。