## 不要なノードの除去

[ノードのmerge](13.ノードのmerge.md)を行うと無駄なノードが残ってしまう。
`$ACCEPT`から辿れないノードは必要ないので除去する。

```
ノードN :
    stmt : . expr
    expr : . left '+' right # 次の記号がleftならノードXに遷移
    expr : . left '-' right # 次の記号がleftならノードYに遷移

↓ leftの遷移先をマージ

ノードN :
    stmt : . expr
    expr : . left '+' right # 次の記号がleftならノードMに遷移
    expr : . left '-' right

この時マージ前のノードX、ノードYには到達できなくなってしまう。
```

不要なノードの除去は次の疑似コードで表す。
`$ACCEPT`から辿れるノードにマークを付け、マークの付いていないノードは除去する。
要は[マーク・アンド・スイープによるガベージコレクション](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%AF%E3%83%BB%E3%82%A2%E3%83%B3%E3%83%89%E3%83%BB%E3%82%B9%E3%82%A4%E3%83%BC%E3%83%97)である。

```
mark関数(node)
    nodeをマーク
    foreach (x in nodeの遷移先)
        mark関数(x)

mark関数($ACCEPTのノード)

foreach (node in ノード集合)
    if (nodeがマークされていなければ)
        ノード集合からnodeを除去
```

ここまででLR(0)のノード集合が完成する。