Shunting-yard algorithm

1961年に Dijkstra が提案したアルゴリズム。
一本のスタックを利用して、中置記法で記述された式を後置記法に書き換えることで構文解析を行う。

アルゴリズムの概観

Shunting-yard algorithm では、トークンは
入力 -> スタック -> 出力
の順に移動する。
この "入力 -> スタック" の移動と "スタック -> 出力" の移動のどちらを行うかを演算子の優先度を用いて判断する。
基本的にはこれだけ。

例えば 1 * 2 + 3 のような例では、

入力	スタック	出力	備考
1 * 2 + 3 $	$		初期状態
* 2 + 3 $	1 $		1 > $ なので "入力 -> スタック"
* 2 + 3 $	$	1	* < `1` なので "スタック -> 出力"
2 + 3 $	* $	1	* > $ なので "入力 -> スタック"
+ 3 $	2 * $	1	2 > * なので "入力 -> スタック"
+ 3 $	* $	1 2	+ < `2` なので "スタック -> 出力"
+ 3 $	$	1 2 *	+ < `*` なので "スタック -> 出力"
3 $	+ $	1 2 *	+ > $ なので "入力 -> スタック"
$	3 + $	1 2 *	3 > + なので "入力 -> スタック"
$	+ $	1 2 * 3	$ < `3` なので "スタック -> 出力"
$	$	1 2 * 3 +	$ < `+` なので "スタック -> 出力"

のように解析が行われる。
$ は入力およびスタックの終端を表す。

また、1 + 2 * 3 のような例では、

入力	スタック	出力	備考
1 + 2 * 3 $	$		初期状態
+ 2 * 3 $	1 $		1 > $ なので "入力 -> スタック"
+ 2 * 3 $	$	1	+ < `1` なので "スタック -> 出力"
2 * 3 $	+ $	1	+ > $ なので "入力 -> スタック"
* 3 $	2 + $	1	2 > + なので "入力 -> スタック"
* 3 $	+ $	1 2	* < `2` なので "スタック -> 出力"
3 $	* + $	1 2	* > + なので "入力 -> スタック"
$	3 * + $	1 2	3 > * なので "入力 -> スタック"
$	* + $	1 2 3	$ < `3` なので "スタック -> 出力"
$	+ $	1 2 3 *	$ < `*` なので "スタック -> 出力"
$	$	1 2 3 * +	$ < `+` なので "スタック -> 出力"

のように解析が行われる。

アルゴリズム詳説

上記で説明したアルゴリズムは Dijkstra が提案した Shunting-yard algorithm だが、
現在ではこれをもう少し改良したものが一般的に用いられている。
改良版の Shunting-yard algorithm は、同じ演算子でも入力側とスタック側で異なる優先度が割り当てられる。
こうすることで、演算子の結合性や括弧のような演算子を表現することが可能となる。

以下の表は優先度割り当ての一例である。

	Num	Id	+	*	=	(	)	$
入力 (Pin)	9	9	4	6	3	8	1	0
スタック (pst)	9	9	5	7	2	1		0

+ の優先度は入力側では 4, スタック側では 5 となっている。
これは、 先に読んだ + の方が先に結合すること、つまり左結合であることを表している。
逆に、= の優先度は入力側では 3, スタック側では 2 となっている。
これは、先に読んだ = よりも後から読む = が先に結合すること、つまり右結合であることを表す。
( はかなり特殊で、入力側では優先度が 8 と非常に高いのに対して、スタック側では優先度は 1 と非常に低くなっている。
こうすることで括弧が優先度をリセットするのを表現している。
スタック側の ( の優先度と入力側の ) の優先度が等しくなっているが、
これはこれらの演算子がペアであることを表している。
(Num や Id も同じ値を用いているが、これらは連続して現れないためであり大した意味はない。
異なる値でも良いし、+∞などにしても良い。)

実際にこの優先度割り当てを使って解析をしてみよう。
少し複雑だが a = b = 1 + 2 * (3 * 4 + 5) + 6 を考える。

入力	スタック	出力	備考
a = b = 1 + 2 * (3 * 4 + 5) + 6 $	$		初期状態
= b = 1 + 2 * (3 * 4 + 5) + 6 $	a $		pin(a) : 9 > pst($) : 0
= b = 1 + 2 * (3 * 4 + 5) + 6 $	$	a	pin(=) : 3 < pst(a) : 9
b = 1 + 2 * (3 * 4 + 5) + 6 $	= $	a	pin(=) : 3 > pst($) : 0
= 1 + 2 * (3 * 4 + 5) + 6 $	b = $	a	pin(b) : 9 > pst(=) : 2
= 1 + 2 * (3 * 4 + 5) + 6 $	= $	a b	pin(=) : 3 < pst(b) : 9
1 + 2 * (3 * 4 + 5) + 6 $	= = $	a b	pin(=) : 3 > pst(=) : 2
+ 2 * (3 * 4 + 5) + 6 $	1 = = $	a b	pin(1) : 9 > pst(=) : 2
+ 2 * (3 * 4 + 5) + 6 $	= = $	a b 1	pin(+) : 4 < pst(1) : 9
2 * (3 * 4 + 5) + 6 $	+ = = $	a b 1	pin(+) : 4 > pst(=) : 2
* (3 * 4 + 5) + 6 $	2 + = = $	a b 1	pin(2) : 9 > pst(+) : 5
* (3 * 4 + 5) + 6 $	+ = = $	a b 1 2	pin(*) : 6 < pst(2) : 9
(3 * 4 + 5) + 6 $	* + = = $	a b 1 2	pin(*) : 6 > pst(+) : 5
3 * 4 + 5) + 6 $	( * + = = $	a b 1 2	pin(() : 8 > pst(*) : 7
* 4 + 5) + 6 $	3 ( * + = = $	a b 1 2	pin(3) : 9 > pst(() : 1
* 4 + 5) + 6 $	( * + = = $	a b 1 2 3	pin(*) : 6 < pst(3) : 9
4 + 5) + 6 $	* ( * + = = $	a b 1 2 3	pin(*) : 6 > pst(() : 1
+ 5) + 6 $	4 * ( * + = = $	a b 1 2 3	pin(4) : 9 > pst(*) : 7
+ 5) + 6 $	* ( * + = = $	a b 1 2 3 4	pin(+) : 4 < pst(4) : 9
+ 5) + 6 $	( * + = = $	a b 1 2 3 4 *	pin(+) : 4 < pst(*) : 7
5) + 6 $	+ ( * + = = $	a b 1 2 3 4 *	pin(+) : 4 > pst(() : 1
) + 6 $	5 + ( * + = = $	a b 1 2 3 4 *	pin(5) : 9 > pst(+) : 5
) + 6 $	+ ( * + = = $	a b 1 2 3 4 * 5	pin()) : 1 < pst(5) : 9
) + 6 $	( * + = = $	a b 1 2 3 4 * 5 +	pin()) : 1 < pst(+) : 5
+ 6 $	* + = = $	a b 1 2 3 4 * 5 + ()	pin()) : 1 = pst(() : 1
+ 6 $	+ = = $	a b 1 2 3 4 * 5 + () *	pin(+) : 4 < pst(*) : 7
+ 6 $	= = $	a b 1 2 3 4 * 5 + () * +	pin(+) : 4 < pst(+) : 5
6 $	+ = = $	a b 1 2 3 4 * 5 + () * +	pin(+) : 4 > pst(=) : 2
$	6 + = = $	a b 1 2 3 4 * 5 + () * +	pin(6) : 9 > pst(+) : 5
$	+ = = $	a b 1 2 3 4 * 5 + () * + 6	pin($) : 0 < pst(6) : 9
$	= = $	a b 1 2 3 4 * 5 + () * + 6 +	pin($) : 0 < pst(+) : 5
$	= $	a b 1 2 3 4 * 5 + () * + 6 + =	pin($) : 0 < pst(=) : 2
$	$	a b 1 2 3 4 * 5 + () * + 6 + = =	pin($) : 0 < pst(=) : 2

この式はこのように解析される。
+ が左結合で解釈されたのに対して、 = が右結合で解釈されたのがわかるだろうか。

擬似コード

Shunting-yard algorithm の擬似コードは以下のようになる。
あくまで擬似コードなので、入力終端及びスタックの末尾を表す $ の処理などは省略している。
(ここではpeek関数が適当に処理するものとしている)

  def shunting_yard (input, p_in, p_st) {
    var stack := empty
    while (input.non_empty || stack.non_empty) {
      if (p_in(input.peek) > p_st(stack.peek)) {
        stack.push(input.read)
      }
      else if (p_in(input.peek) < p_st(stack.peek)) {
        output(stack.pop)
      }
      else {
        output(compose(stack.pop, input.read))
      }
    }
  }

こう書いても良いだろう。

  def shunting_yard (input, p_in, p_st) {
    val stack := empty
    for (token in input) {
      read_token(token, stack, p_in, p_st)
    }
  }

  def read_token (token, stack, p_in, p_st) {
    if (p_in(token) > p_st(stack.peek)) {
      stack.push(token)
    }
    else if (p_in(token) < p_st(stack.peek)) {
      output(stack.pop)
      read_token(token, stack, p_in, p_st)
    }
    else {
      output(compose(stack.pop, token))
    }
  }

計算量

全てのトークンに関して "入力 -> スタック" の移動と "スタック -> 出力" の移動が行われたとき解析が終了するので、
計算量はトークン数 N に対して 2N となる。
つまり、計算量のオーダーは O(N) である。

あとがき

前に作った ビジュアル構文解析 の解説があると良いかなと思って作ったが、予想以上に大変だった。気が向いたら他のアルゴリズムも作ります。