はじめに
下向き演算子順位解析は構文解析アルゴリズムの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を結び付けるかということです。
順を追っていきましょう。
まず演算子同士の比較で解析するので、演算子に挟まれていないaやcのために、仮想の演算子(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として定義しました。
まず役割を実装したクラス、ContextとTokenがあります。
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は式の要素を表します。先の例のa、b、cや+、-、+=、-=です。
また解析も行います。
解析前の式はこのTokenの配列で表します。
解析後の構文木は、Token自身とフィールド変数のfirstとSecondで表します。
Tokenは後ほど、変数や演算子用にサブクラスへ特化します。
initメソッド
Tokenはinitメソッドで、値と結合力を決めてから使います。
nudメソッド
式の先頭にこられる要素を解析します。a、b、cのような変数などです。この記事では扱っていませんが、-1の-のような前置演算子や、計算の優先順位付けの括弧の開始(などもこれに当たります。
ledメソッド
逆に式の先頭にこられない要素を解析します。ledメソッドを持つ要素自身より前にある要素の解析結果は、引数leftで受取ります。自身より後にある要素の解析は、ledメソッドの中でします。
expressionメソッド
nudメソッドやledメソッドを組合せて、解析を実現します。
結合力比較の先にくる要素が、このメソッドを呼び出します。先の要素の結合力比較が強い場合、whileの外に出る場合は、このメソッドの返り値として、先の要素に解析結果が返されます。先の要素に解析結果が結合されるわけです。
結合力比較の後にくる要素が強い場合、whileの中にいる場合は、後の要素に、続けて解析結果が引き取られていきます。
treeメソッド
解析結果の確認用に、構文木を文字列にします。自身が端なら、自身の値のみの文字列にします。firstやsecondがあれば、{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はa、b、cのような変数を表すします。
式の先頭にしか来ないので、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メソッドを呼び出しの結合力に違いがあります。
右結合の演算子の右結合力になるので、結合力から１を引いて渡しています。
static class InfixR extends Token {
@Override
public Token led(Token left) {
first = left;
second = expression(lbp - 1);
return this;
}
}
mainメソッド
以上のクラスを使って、解析を実施します。
tokenｓは式を表します。値と結合力を指定して、式の要素の並びで、変数か演算子のTokenを作り、それを配列にしています。見た目は冗長ですが、やっていることは単純です。
次にContextを作り、tokensで初期化します。
初期化するとContext.tokenがtokensの先頭になり、そのexpressionをrbp: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;
}
}
}