グラフ簡約 - mrsekut-p

グラフ簡約

graph reduction

どのへんがグラフなのか

グラフ簡約は必要呼びをするときなどに使用される

これは、既に簡約した同じ式を再度利用する方法

このとき、構文木を簡約する際に、構文木は木ではなくgraphになる

例えば((2+2) + (2+2)) + (3+3)という式を簡約するときに、

最左最外簡約では普通に木構造で簡約していく

https://gyazo.com/4decdf92ea8fd0e5be276f6fdb5dbf27

一度使ったツリーを再利用する構造になるので、木ではなくグラフになる

https://gyazo.com/c87ee635aac5843e7fb1f9a86b0e0780

これだけ見ると、でっていうって感じだなmrsekut.icon

どのようにして実装されている？

参考