用 Happy : left-recursion versus right-recursion 解析

Question

Section 2.2 of the Happy user manual建议您使用左递归而不是右递归，因为右递归是“低效的”。基本上他们是说，如果您尝试解析一长串项目，右递归将溢出解析堆栈，而左递归使用常量堆栈。给出的规范示例是

items : item            { $1 : [] }
      | items "," item  { $3 : $1 }

不幸的是，这意味着项目列表倒退了。

现在申请很容易 reverse最后(尽管令人恼火的是，您必须在调用解析器的任何地方执行此操作，而不是在定义它的地方执行一次)。但是，如果项目列表很大，肯定是 reverse也会溢出 Haskell 堆栈吗？不？

基本上，我如何制作它以便我可以解析任意大的文件并仍然以正确的顺序获得结果？

Answer 1

如果您想要的是整个 items成为 reverse d 每次，您都可以定义

items  : items_           {reverse $1}

items_ : item             { $1 : [] }
       | items_ "," item  { $3 : $1 }

reverse不会溢出堆栈。如果您需要说服自己，请尝试评估 length $ reverse [1..10000000]