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

# はじめに

下向き演算子順位解析は構文解析アルゴリズムの1つです。
ご存知の方も多いと思いますが、[ビューティフルコード](http://www.amazon.co.jp/dp/4873113636)という本で、その存在を知りました。
この解析法の要になる部分のコードは、ビューティフルコード9章の**式**の節で紹介される関数`expression`です。その関数はとても小さく単純で、まさしくビューティフルコードなのですが、なかなかその仕組が理解できませんでした。
ここではその関数`expression`の仕組みを理解するために、Javaによる実装で、本文中のコードを二項演算子の構文木を作るだけにそぎ落とし、簡単にしました。そして仕組みを考えてみたいと思います。
9章の原文は[こちら](http://javascript.crockford.com/tdop/tdop.html)で読むことができます。

# 構文解析で解決する問題

構文解析の役割の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を比較して、大きい方の演算子に要素を結合する。
* 同じだったら、左の演算子に要素を結合する。

# プログラム

順位の付け方をふまえて、プログラムを見ていきたいと思います。
[元の実装](https://github.com/douglascrockford/TDOP/blob/master/parse.js)を、二項演算子の解析のみに特化して、Javaで実装したものです。

## 構成

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

```java
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`へ自身の参照をついでに設定します。

```java
    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}`の書式でさらに文字列にします。

```java
    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`のサブクラスを見ていきます。

```java
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は解析後に、構文木で端にくる要素なので、解析結果が自身になります。

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

## Infixクラス

Infixは`+`、`-`、`*`、`/`のような左結合の演算子を表します。
式の途中にしか来ないので、`led`メソッドのみ実装します。

### `led`メソッド

構文木の左右を構築します。
構文木の左側が`first`に、右側が`second`になります。
左側は既に解析された結果として、引数で渡されます。
右側はこれから解析する結果として、`expression`メソッドを呼び出して受取ります。
この呼び出しで、この`led`メソッドを持つ演算子が、結合力比較の**先**にくる演算子になります。
`expression`メソッド呼び出しでは、自身の結合力を引数にします。
`expression`メソッド内ではそれが、右結合力になります。

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


## InfixRクラス

InfixRは`=`、`+=`、`-=`のような右結合の演算子を表します。
こちらも式の途中にしか来ないので、`led`メソッドのみ実装します。

### `led`メソッド

Infixクラスとほぼ同様ですが、`expression`メソッドを呼び出しの結合力に違いがあります。
右結合の演算子の右結合力になるので、結合力から１を引いて渡しています。

```java
    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`に入り、標準出力へ構文木を表示します。

```java
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に戻る
}
```

# ソース

最後にまとめてソースを記載します。
ありがとうございました。

```java
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;
        }
    }
}
```