4

Happy 用户手册第 2.2 节建议您使用左递归而不是右递归，因为右递归“效率低下”。基本上他们是说，如果您尝试解析一长串项目，右递归将溢出解析堆栈，而左递归使用常量堆栈。给出的典型例子是

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

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

现在它很容易reverse在最后应用（尽管您必须在调用解析器的任何地方都这样做，而不是在定义它的地方一次）。但是，如果项目列表很大，肯定reverse也会溢出 Haskell 堆栈吗？不？

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

4

1 回答 1

4

如果你想要的只是每次items都是d 的整数，你可以定义reverse

items  : items_           {reverse $1}

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

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

于 2015-11-01T18:02:27.570 回答