不要なノードの除去 🔗

ノードのmergeを行うと無駄なノードが残ってしまう。
$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から辿れるノードにマークを付け、マークの付いていないノードは除去する。
要はマーク・アンド・スイープによるガベージコレクションである。

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

mark関数($ACCEPTのノード)

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

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