2008/03/30

偷轉

承接〈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 啊,怎麼會發生這種事勒?原來當我看到 ExprExpr' 展開成 TermExpr' 的時候,生成 syntax tree 的函式會把 Term 的 syntax tree 塞到 Expr' 的 partial syntax tree 左側,就如同對 parse tree 做 left-rotation!轉兩次之後,加法(和乘法)就又變回 left-associative 了 XD。

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

--
挺有趣的 XD。

Labels:

<< 回到主頁