偷轉

承接〈Parser Combinators in Haskell〉，Wikipedia 上的 left recursion 條目下有個 pitfall 子項，裡面用的 example grammar 正好就是我用的，一模一樣。它說經過 left-recursion elimination 之後，加法的 association 就從 left-associative 變成 right-associative，parse tree 會向右傾。

我就很納悶了：我造出來的 abstract syntax tree（ExprTree）都是 left-associative 啊，怎麼會發生這種事勒？原來當我看到 Expr 或 Expr' 展開成 Term 和 Expr' 的時候，生成 syntax tree 的函式會把 Term 的 syntax tree 塞到 Expr' 的 partial syntax tree 左側，就如同對 parse tree 做 left-rotation！轉兩次之後，加法（和乘法）就又變回 left-associative 了 XD。

從這例子也可以清楚看出 parse tree 和 abstract syntax tree 是不一樣的東西。

--
挺有趣的 XD。