用 Happy 解析：左递归与右递归

Question

Section 2.2 of the Happy user manual建议你使用左递归而不是右递归，因为右递归是"inefficient"。基本上他们是说，如果您尝试解析一长串项目，右递归将溢出解析堆栈，而左递归使用常量堆栈。给出的典型例子是

items : item            {  : [] }
      | items "," item  {  :  }

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

现在很容易在最后应用 reverse（虽然令人恼火的是你必须在调用解析器的任何地方执行此操作，而不是一次在调用解析器的地方执行此操作已定义)。但是，如果项目列表很大，那么 reverse 肯定也会溢出 Haskell 堆栈吗？没有？

基本上，我该怎么做才能解析任意大的文件并仍然以正确的顺序得到结果？

Answer 1

如果你只想让整个items每次都是reversed，你可以定义

items  : items_           {reverse }

items_ : item             {  : [] }
       | items_ "," item  {  :  }

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

Parsing with Happy: left-recursion versus right-recursion