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

はじめに

下向き演算子順位解析は構文解析アルゴリズムの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;
        }
    }
}