Edited at

下向き演算子順位解析の本質に近づく

More than 3 years have passed since last update.


はじめに

下向き演算子順位解析は構文解析アルゴリズムの1つです。

ご存知の方も多いと思いますが、ビューティフルコードという本で、その存在を知りました。

この解析法の要になる部分のコードは、ビューティフルコード9章のの節で紹介される関数expressionです。その関数はとても小さく単純で、まさしくビューティフルコードなのですが、なかなかその仕組が理解できませんでした。

ここではその関数expressionの仕組みを理解するために、Javaによる実装で、本文中のコードを二項演算子の構文木を作るだけにそぎ落とし、簡単にしました。そして仕組みを考えてみたいと思います。

9章の原文はこちらで読むことができます。


構文解析で解決する問題

構文解析の役割の1つに、式の順位付けがあります。

例えば式a + b * cで順位を括弧付けすると、a + (b * c)となります。

この順位付けを、下向き演算子順位解析がどう解決するかを見ていきます。


順位の付け方


結合力

下向き演算子順位解析は、計算の順位をつけるのに、演算子それぞれに結合力(Binding Powers)という値を割り当ます。

その結合力の大小で、順位付けをしていきます。

次のように、結合力を決めます。

演算子
結合力

*, /
70

+, -
60

=, +=, -=
10

(start), (end)
0


訂正しました。検討が足りずすみません。


注意、以下の説明は、結合の対象になっていない要素も括弧付している点が、間違っているので、訂正する予定です。




a + b * cの場合

先ほどの式a + b * cについて考えてみます。

下向き演算子順位解析は式の順位付けの問題を、要素の左右にある演算子のどちらが、要素を結び付けるかの問題と捉えます。

式の例では+*のどちらがbを結び付けるかということです。

順を追っていきましょう。

まず演算子同士の比較で解析するので、演算子に挟まれていないacのために、仮想の演算子(start)(end)を追加します。

どちらも結合力が0なので、結合の順序に影響を与えません。

(start) a + b * c (end)

これでaの両方に演算子があるので、比較ができます。

a(start)+のどちらに結び付くかを比較します。

その範囲を[ ]で囲みます。

[(start) a +] b * c (end)

次に演算子に結合力を書き添えます。

[(start)@rbp:0 a +@lbp:60] b * c (end)

rbpはRight Binding Powerの略で、演算子が右側の要素に働く結合力、右結合力です。

lbpはLeft Binding Powerの略で、rbpの左右逆、左結合力を意味します。

rbp、lbpに続く数字が、それぞれ結合力です。

(start)が右側のaを結び付ける力(rbp)が0

+が左側のaを結び付ける力(lbp)が60

という意味になります。

そのため+の力が強く、そちらがaを結び付けます。

結びついた方を#で繋ぎます。

a+#で結び付きました。

[(start)@rbp:0 a#+@lbp:60] b * c (end)

比較範囲を右にずらし、同様に結合力を添え、力関係によって#で繋ぎます。

60<70で、b*が結び付きました。

(start) a#[+@rbp:60 b#*@lbp:70] c (end)

同様にずらし、70>0で、*cが結び付きました。

(start) a#+ b#[*@rbp:70#c (end)@lbp:0]

ここで*の両側が結び付いたので、それは1つの要素とみなせます。

そこで括弧( )で囲みます。

(start) a#+ (b#*#c) (end)

囲んだ要素は1つみなし、その両側の演算子でまた比較を行います。

60>0で、+と囲んだ要素が結び付きました。

(start) a#[+@rbp:60#(b#*#c) (end)@lbp:0]

+も両側が結び付いたので、それは1つの要素とみなします。

最後は(start)(end)の比較になり、結合力はどちらも0です。

結合力が同じ場合は、左に結合します。

[(start)@rbp:0#(a#+#(b#*#c)) (end)@lbp:0]

(start)の右側をみると、#で結び付けて作った括弧が、順位の通りなりました。

順位付けができました。

(start)#(a#+#(b#*#c)) (end)

さらに色々な場合を見ていきましょう。


d + e - fの場合

手間を省くために、最初の(start)+の比較は(start)の結合力がいつも0なので端折って、d+に結びついた状態から始めます。

そして+-の比較から始めます。

+-は結合力が同じなので、eは左に結合します。

(start) d#[+@rbp:60#e -@lbp:60] f (end)

(d#+#e)を要素とみなし、(start)-の比較で、-に結合します。

[(start)@rbp:0 (d#+#e)#-@lbp:60] f (end)

-(end)の比較で、f-に結合します。

(start) (d#+#e)#[-@rbp:60#f (end)@lbp:0]

最後の(start)(end)の比較は、以前と同じなので端折って、(start)の右をみると、順位付けできました。

(start)#((d#+#e)#-#f) (end)


g += h -= iの場合

この式は、右結合の演算子の連続になっていて、多くのプログラミング言語で、このような順位で解析されます。

g += (h -= i)

しかし今までの規則でいくと、+=-=の結合力は同じなので、左の+=演算子に結合されてしまい、間違った解析結果になってしまいます。

そこで、このように右へくる演算子が優先の場合は、結合力から1を引いてrbpとします。

9<10でh-=と結合します。

(start) g#[+=@rbp:9 h#-=@lbp:10] i (end)

(-=)(end)の比較で、i-=に結合します。

-=の両方に結合できたので、1つの要素になります。

(start) g#+= h#[-=@rbp:9#i (end)@lbp0]

(+=)(end)の比較で、(h#-=#i)+=に結合します。

(start) g#[+=@rbp:9#(h#-=#i) (end)@lbp0]

最後の(start)(end)の比較は端折り、順位付けできました。

(start)#(g#+=#(h#-=#i)) (end)

右結合の演算子も解析できたわけです。


以上のまとめ


  • 演算子に順位を決める結合力を指定する。

  • 演算子が右結合の場合、rbpは結合力から1引く。

  • rbpとlbpを比較して、大きい方の演算子に要素を結合する。

  • 同じだったら、左の演算子に要素を結合する。


プログラム

順位の付け方をふまえて、プログラムを見ていきたいと思います。

元の実装を、二項演算子の解析のみに特化して、Javaで実装したものです。


構成

プログラムは簡単のために、役割を実装したクラスを、全てTDOPEssentialクラスの下に、static classとして定義しました。

まず役割を実装したクラス、ContextTokenがあります。

public class TDOPEssential {

static class Context {
// 省略
}

static class Token {
// 省略
}

}


Contextクラス

Contextは解析途中の状況を表し、解析対象の式を持ちます。また全てのTokenで状況を共有するために使われます。


initメソッド

解析対象の式を受取り、フィールド変数Token[] tokensへ保持します。

1度advanceメソッドを呼び出し、フィールド変数Token[] tokensの先頭を、注目しているTokenにします。


advanceメソッド

注目するTokenを次に進め、フィールド変数public Token tokenに、現状で注目しているTokenを入れます。

もしフィールド変数Token[] tokensの要素を超えて次に進んだ場合は、式の終端を表すToken(end)を注目するTokenにします。

Tokenは解析のときにこのContextを使うので、注目したTokenのフィールド変数public Context ctxへ自身の参照をついでに設定します。

    static class Context {

int token_nr;
Token[] tokens;
public Token token;

public Context init(Token[] tokens) {
this.tokens = tokens;
this.token_nr = 0;
advance();
return this;
}

public void advance() {
if (token_nr < tokens.length) {
token = tokens[token_nr];
token.ctx = this;
token_nr += 1;
} else if (token_nr == tokens.length) {
token = new Token().init("(end)", 0);
token.ctx = this;
}
}
}


Tokenクラス

Tokenは式の要素を表します。先の例のabc+-+=-=です。

また解析も行います。

解析前の式はこのTokenの配列で表します。

解析後の構文木は、Token自身とフィールド変数のfirstSecondで表します。

Tokenは後ほど、変数や演算子用にサブクラスへ特化します。


initメソッド

Tokeninitメソッドで、値と結合力を決めてから使います。


nudメソッド

式の先頭にこられる要素を解析します。abcのような変数などです。この記事では扱っていませんが、-1-のような前置演算子や、計算の優先順位付けの括弧の開始(などもこれに当たります。


ledメソッド

逆に式の先頭にこられない要素を解析します。ledメソッドを持つ要素自身より前にある要素の解析結果は、引数leftで受取ります。自身より後にある要素の解析は、ledメソッドの中でします。


expressionメソッド

nudメソッドやledメソッドを組合せて、解析を実現します。

結合力比較のにくる要素が、このメソッドを呼び出します。の要素の結合力比較が強い場合、whileの外に出る場合は、このメソッドの返り値として、の要素に解析結果が返されます。の要素に解析結果が結合されるわけです。

結合力比較のにくる要素が強い場合、whileの中にいる場合は、の要素に、続けて解析結果が引き取られていきます。


treeメソッド

解析結果の確認用に、構文木を文字列にします。自身が端なら、自身の値のみの文字列にします。firstsecondがあれば、{first, second}の書式でさらに文字列にします。

    static class Token {

public Context ctx;
public String value;
public int lbp;
public Token first;
public Token second;

public Token init(String value, int lbp) {
this.value = value;
this.lbp = lbp;
return this;
}

public Token nud() {
throw new RuntimeException("Missing operator.");
}

public Token led(Token left) {
throw new RuntimeException("Undefined.");
}

public Token expression(int rbp) {
Token left, tn, tl;

tn = ctx.token;
ctx.advance();
left = tn.nud();
while (rbp < ctx.token.lbp) {
tl = ctx.token;
ctx.advance();
left = tl.led(left);
}
return left;
}

public String tree() {
return value
+ (first != null ? "{" + first.tree() : "")
+ (second != null ? ", " + second.tree() : "")
+ (first != null ? "}" : "")
;
}
}


Tokenのサブクラス

続いてTokenのサブクラスを見ていきます。

public class TDOPEssential {

static class Variable extends Token {
// 省略
}

static class Infix extends Token {
// 省略
}

static class InfixR extends Token {
// 省略
}
}


Variableクラス

Variableはabcのような変数を表すします。

式の先頭にしか来ないので、nudメソッドのみ実装します。


nudメソッド

自身を返します。

Variableは解析後に、構文木で端にくる要素なので、解析結果が自身になります。

    static class Variable extends Token {

@Override
public Token nud() {
return this;
}
}


Infixクラス

Infixは+-*/のような左結合の演算子を表します。

式の途中にしか来ないので、ledメソッドのみ実装します。


ledメソッド

構文木の左右を構築します。

構文木の左側がfirstに、右側がsecondになります。

左側は既に解析された結果として、引数で渡されます。

右側はこれから解析する結果として、expressionメソッドを呼び出して受取ります。

この呼び出しで、このledメソッドを持つ演算子が、結合力比較のにくる演算子になります。

expressionメソッド呼び出しでは、自身の結合力を引数にします。

expressionメソッド内ではそれが、右結合力になります。

    static class Infix extends Token {

@Override
public Token led(Token left) {
first = left;
second = expression(lbp);
return this;
}
}


InfixRクラス

InfixRは=+=-=のような右結合の演算子を表します。

こちらも式の途中にしか来ないので、ledメソッドのみ実装します。


ledメソッド

Infixクラスとほぼ同様ですが、expressionメソッドを呼び出しの結合力に違いがあります。

右結合の演算子の右結合力になるので、結合力から1を引いて渡しています。

    static class InfixR extends Token {

@Override
public Token led(Token left) {
first = left;
second = expression(lbp - 1);
return this;
}
}


mainメソッド

以上のクラスを使って、解析を実施します。

tokensは式を表します。値と結合力を指定して、式の要素の並びで、変数か演算子のTokenを作り、それを配列にしています。見た目は冗長ですが、やっていることは単純です。

次にContextを作り、tokensで初期化します。

初期化するとContext.tokentokensの先頭になり、そのexpressionrbp:0で呼び出して解析を始めます。

解析結果がparsedに入り、標準出力へ構文木を表示します。

public class TDOPEssential {

public static void main(String[] args) {
Token[] tokens;
Token parsed;

// a + b * c

tokens = new Token[] {
new Variable().init("a", 0),
new Infix().init("+", 60),
new Variable().init("b", 0),
new Infix().init("*", 70),
new Variable().init("c", 0)
};
parsed = new Context()
.init(tokens)
.token.expression(0)
;
System.out.println(parsed.tree());
}
}


expressionメソッドをrbp:0で呼び出すことについて

その意味は、順位の付け方で導入した、仮想の(start)演算子の右結合力を与えていることになります。

解析の最後は(start)(end)の比較になるので、それまでの解析結果がまとまったものが、左優先で(start)に結合されます。

(start)に結合されるということは、rbp:0で呼び出したexpressionメソッドの戻り値になるということです。

それは式の解析結果そのものです。


トレース

解析処理は単純な式の解析でも、関数の呼び出し階層が深くなりがちです。

呼び出し階層が深い処理は、処理の把握がしずらいものです。

mainメソッドでのexpressionメソッド呼び出しから、実行をトレースして、解析の感じに触れてみます。


a + b * cの場合


Level: 0

mainメソッドでのexpressionメソッド呼び出し直後を、Level: 0としました。

以降、expressionメソッドかledメソッドが呼び出されれば、単純にLevel(階層)を下がっていきます。(数値としては増えますが)

簡単のため、変数の宣言などは端折ってます。

:の横に、その変数の具体的な値を添えました。状況によって多少矛盾した記述になると思いますが、ご容赦下さい。

下のLevel呼び出しを->と書いています。

expression(rbp: 0) {

tn: a = ctx.token
ctx.advance(): ctx.token: +
left: a = tn.nud()
while(rbp: 0 < ctx.token: +.lbp: 60) {
tl: + = ctx.token
ctx.advance(): ctx.token: b
left = tl: +.led(left: a) -> Level: 1
}
return left
}


Level: 1

+の左がaで決まります。

this: +

led(left: a) {
first = left: a
second = expressiont(lbp: 60) -> Level: 2
return this
}


Level: 2

+より*が結合力が強いので、*bを結合しようとします。

expression(rbp: 60) {

tn: b = ctx.token
ctx.advance(): ctx.token: *
left: b = tn.nud()
while(rbp: 60 < ctx.token: *.lbp: 70) {
tl: * = ctx.token
ctx.advance(): ctx.token: c
left = tl: *.led(left: b) -> Level: 3
}
return left
}


Level: 3

*の左がbで決まります。

this: *

led(left: b) {
first = left: b
second = expressiont(lbp: 70) -> Level: 4
return this
}


Level: 4

注目しているToken(end)に達します。

(end)の結合力は0なので、(end)は何も結合しません。

つまりledメソッドが呼び出されず、階層を上がっていきます。

上のLevelへの戻りを=>と書いています。

expression(rbp: 70) {

tn: c = ctx.token
ctx.advance(): ctx.token: (end)
left: c = tn.nud()
while(rbp: 70 < ctx.token:(end) .lbp:0) {
tl = ctx.token
ctx.advance()
left = tl.led(left)
}
return left: c => Level 3
}


Level: 3

下のLevelからの戻りを<=と書いています。

*の右がcで決まり、*の式が解析されました。

this: *

led(left: b) {
first = left: b
second: c = expressiont(lbp: 70) -> Level: 4 <=
return this: *{b, c} => Level: 2
}


Level: 2

tl.led(left)からの戻りです。

(end)の結合力が0なので階層を戻ります。

expression(rbp: 60) {

tn: b = ctx.token
ctx.advance(): ctx.token: *
left: b = tn.nud()
while(rbp: 60 < ctx.token:(end) .lbp:0) {
tl = ctx.token
ctx.advance()
left: *{b, c} = tl: *.led(left: b) -> Level: 3 <=
}
return left: *{b, c} => Level: 1
}


Level: 1

+の右が*で決まり、+の式が解析されました。

this: +

led(left: a) {
first = left: a
second: *{b, c} = expressiont(lbp: 60) -> Level: 2 <=
return this: +{a, *{b, c}} => Level: 0
}


Level: 0

開始のrbp:0と、(end)のlbp:0が比較される結果となり、見かけ上は、開始のrbp:0と結合して終わります。

最後のledメソッドの呼び出し結果が、解析結果となり、解析ができました。

expression(rbp: 0) {

tn: a = ctx.token
ctx.advance(): ctx.token: +
left: a = tn.nud()
while(rbp: 0 < ctx.token: (end) .lbp: 0) {
tl = ctx.token
ctx.advance()
left = tl.led(left)
left: +{a, *{b, c}} = tl: +.led(left: a) -> Level: 1 <=
}
return left:+{a, *{b, c}} => mainに戻る
}


d + e - fの場合


Level: 0

expression(rbp: 0) {

tn: d = ctx.token
ctx.advance(): ctx.token: +
left: d = tn.nud()
while(rbp: 0 < ctx.token: +.lbp: 60) {
tl: + = ctx.token
ctx.advance(): ctx.token: e
left = tl: +.led(left: d) -> Level: 1
}
return left
}


Level: 1

this: +

led(left: d) {
first = left: d
second = expression(lbp: 60) -> Level: 2
return this
}


Level: 2

rbpとlbpが同じなので、左結合で扱われ、Token eは先の演算子+に結合される。

Token eはこのexpressionメソッドの、呼び出し元の演算子に結合される。

expression(rbp: 60) {

tn: e = ctx.token
ctx.advance(): ctx.token: -
left: e = tn.nud()
while(rbp: 60 < ctx.token: -.lbp: 60) {
tl = ctx.token
ctx.advance()
left = tl.led(left)
}
return left: e => Level: 1
}


Level: 1

this: +

led(left: d) {
first = left: d
second: e = expression(lbp: 60) -> Level: 2 <=
return this: +{d, e} => Level: 0
}


Level: 0

expression(rbp: 0) {

tn = ctx.token
ctx.advance()
left = tn.nud()
while(rbp: 0 < ctx.token: +.lbp: 60) {
tl: + = ctx.token
ctx.advance(): ctx.token: e
left: +{d, e} = tl: +.led(left: d) -> Level: 1 <=
}
// 繰り返し2回め
while(rbp: 0 < ctx.token: -.lbp: 60) {
tl: - = ctx.token
ctx.advance(): ctx.token: f
left = tl -.led(left: +{d, e}) -> Level: 1-2
}
return left
}


Level: 1-2

this: -

led(left: +{d, e}) {
first = left: +{d, e}
second = expression(lbp: 60) -> Level: 2-2
return this
}


Level: 2-2

expression(rbp: 60) {

tn: f = ctx.token
ctx.advance(): ctx.token: (end)
left: f = tn.nud()
while(rbp: 60 < ctx.token: (end).lbp: 0) {
tl = ctx.token
ctx.advance()
left = tl.led(left)
}
return left: f => Level: 1-2
}


Level: 1-2

this: -

led(left: +{d, e}) {
first = left: +{d, e}:
second: f = expression(lbp: 60) -> Level: 2-2 <=
return this:-{+{d, e}, f} => Level: 0
}


Level: 0

expression(rbp: 0) {

tn = ctx.token
ctx.advance()
left = tn.nud()
// 繰り返し2回め
while(rbp: 0 < ctx.token: (end).lbp: 0) {
tl = ctx.token
ctx.advance()
left:-{+{d, e}, f} = tl: -.led(left: +{d, e}) -> Level: 1-2 <=
}
return left:-{+{d, e}, f} => mainに戻る
}


g += h -= iの場合


Level: 0

expression(rbp: 0) {

tn: g = ctx.token
ctx.advance(): ctx.token: +=
left: g = tn.nud()
while(rbp: 0 < ctx.token: +=.lbp: 10) {
tl: += = ctx.token
ctx.advance(): ctx.token: h
left = tl: +=.led(left: g) -> Level: 1
}
return left
}


Level: 1

+=は右結合なので、lbpは1を引きます。

this: +=

led(left: g) {
first = left: g
second = expression(lbp: 10 - 1) -> Level: 2
return this
}


Level: 2

expression(rbp: 9) {

tn: h = ctx.token
ctx.advance(): ctx.token: -=
left: h = tn.nud()
while(rbp: 9 < ctx.token: -=.lbp: 10) {
tl: -= = ctx.token
ctx.advance(): ctx.token: i
left = tl: -=.led(left: h) -> Level: 3
}
return left
}


Level: 3

this: -=

led(left: h) {
first = left: h
second = expression(lbp: 10 - 1) -> Level: 4
return this
}


Level: 4

expression(rbp: 9) {

tn: i = ctx.token
ctx.advance(): ctx.token: (end)
left: i = tn.nud()
while(rbp: 9 < ctx.token: (end).lbp: 0) {
tl = ctx.token
ctx.advance()
left = tl.led(left)
}
return left: i => Level: 3
}


Level: 3

this: -=

led(left: h) {
first = left: h
second: i = expression(lbp: 10 - 1) -> Level: 4 <=
return this: -={h, i} => Level: 2
}


Level: 2

expression(rbp: 9) {

tn: h = ctx.token
ctx.advance(): ctx.token: -=
left: h = tn.nud()
while(rbp: 9 < ctx.token: (end).lbp: 0) {
tl = ctx.token
ctx.advance()
left: -={h, i} = tl: -=.led(left: h) -> Level: 3 <=
}
return left: -={h, i} => Level: 1
}


Level: 1

this: +=

led(left: g) {
first = left: g
second: -={h, i} = expression(lbp: 10 - 1) -> Level: 2 <=
return this: +={g, -={h, i}} => Level: 0
}


Level: 0

expression(rbp: 0) {

tn: g = ctx.token
ctx.advance(): ctx.token: +=
left: g = tn.nud()
while(rbp: 9 < ctx.token: (end).lbp: 0) {
tl = ctx.token
ctx.advance()
left: +={g, -={h, i}} = tl: +=.led(left: g) -> Level: 1 <=
}
return left: +={g, -={h, i}} => mainに戻る
}


ソース

最後にまとめてソースを記載します。

ありがとうございました。

public class TDOPEssential {

public static void main(String[] args) {
Token[] tokens;
Token parsed;

// a + b * c

tokens = new Token[] {
new Variable().init("a", 0),
new Infix().init("+", 60),
new Variable().init("b", 0),
new Infix().init("*", 70),
new Variable().init("c", 0)
};
parsed = new Context()
.init(tokens)
.token.expression(0)
;
System.out.println(parsed.tree());

// d + e - F

tokens = new Token[] {
new Variable().init("d", 0),
new Infix().init("+", 60),
new Variable().init("e", 0),
new Infix().init("-", 60),
new Variable().init("f", 0)
};
parsed = new Context()
.init(tokens)
.token.expression(0)
;
System.out.println(parsed.tree());

// g += h -= i

tokens = new Token[] {
new Variable().init("g", 0),
new InfixR().init("+=", 10),
new Variable().init("h", 0),
new InfixR().init("-=", 10),
new Variable().init("i", 0)
};
parsed = new Context()
.init(tokens)
.token.expression(0)
;

System.out.println(parsed.tree());
}

static class Context {

int token_nr;
Token[] tokens;
public Token token;

public Context init(Token[] tokens) {
this.tokens = tokens;
this.token_nr = 0;
advance();
return this;
}

public void advance() {
if (token_nr < tokens.length) {
token = tokens[token_nr];
token.ctx = this;
token_nr += 1;
} else if (token_nr == tokens.length) {
token = new Token().init("(end)", 0);
token.ctx = this;
}
}
}

static class Token {

public Context ctx;
public String value;
public int lbp;
public Token first;
public Token second;

public Token init(String value, int lbp) {
this.value = value;
this.lbp = lbp;
return this;
}

public Token nud() {
throw new RuntimeException("Missing operator.");
}

public Token led(Token left) {
throw new RuntimeException("Undefined.");
}

public Token expression(int rbp) {
Token left, tn, tl;

tn = ctx.token;
ctx.advance();
left = tn.nud();
while (rbp < ctx.token.lbp) {
tl = ctx.token;
ctx.advance();
left = tl.led(left);
}
return left;
}

public String tree() {
return value
+ (first != null ? "{" + first.tree() : "")
+ (second != null ? ", " + second.tree() : "")
+ (first != null ? "}" : "")
;
}
}

static class Variable extends Token {
@Override
public Token nud() {
return this;
}
}

static class Infix extends Token {
@Override
public Token led(Token left) {
first = left;
second = expression(lbp);
return this;
}
}

static class InfixR extends Token {
@Override
public Token led(Token left) {
first = left;
second = expression(lbp - 1);
return this;
}
}
}