parsing - 避免 Clojure 中递归导致的堆栈溢出

Question

我是 Clojure 的新手，无法弄清楚如何在某些情况下避免堆栈溢出。在尝试使用解析器组合库将解析项目移植到 Clojure 时出现了这样一种情况，我发现它被称为 kern .
Kern 定义了一个“many-till”解析器的递归实现:source
这适用于小输入:

(def input-text "The blue {cat} and the red {dog} became best friends with the white {wolf} END {not included}")

(def  between-brackets "parser that grabs all text between brackets"
  (between (sym* \{) (sym* \}) (<+> (many (none-of* "}")))))

(def parse-enclosed-words "parser that attempts to grab text between brackets, 
skips a character when it can't, and halts when it hits the string END"
  (many-till (<|> between-brackets (skip any-char)) (token* "END")))

(filter #(some? %) (value parse-enclosed-words input-text)) ;; => ("cat" "dog" "wolf")

不幸的是，随着输入字符串的增长，解析器会遇到堆栈溢出:

(def file-input-text (slurp (io/resource "[input-text-20x-repeated.txt][2]") ))
(filter #(some? %) (value parse-enclosed-words file-input-text)) ;; => Unhandled java.lang.StackOverflowError

从我在线阅读的情况来看，这可能是由于该函数使用了消耗堆栈的递归。我尝试了一些使用“recur”关键字重写函数的尝试，但由于递归调用不在尾部位置，这似乎不起作用。
如何修改 many-till 以避免堆栈溢出？

Answer 1

我不认为你可以用库提供的抽象来做到这一点。这是many-till很自然的定义，并且在 Parsec 中可以正常工作，Kern 显然受到该库的启发。但是 Clojure 没有 Haskell 的惰性求值和自动蹦床，所以嵌套的 lambdas many-till构建不可避免地消耗无限堆栈。您将需要一个更像它的实现 many 的实现。 ，它从函数中手动构建解析器。我会在下面包含它的来源，但我不拥有它，所以我认为我没有授权给 Stack Overflow 一个 CC BY-SA 4.0 许可证，as posting it would do .相反，这里是指向 its source 的链接.