1

我有一个解析器列表，例如[string "a",string "ab"]“重叠”。我既不能改变解析器本身也不能改变它们的顺序。

使用这些解析器，我想解析一个令牌序列，每个令牌都与其中一个解析器完全匹配，例如"aaaab", "ab", "abab"但不是"abb"

如果没有解析器，我只会实现部门优先搜索，但我想用解析器解决这个问题。

我得到了这么远：

import Control.Applicative
import Text.Trifecta

parsers = [string "a",string "ab"]

parseString (many (choice parsers) <* eof) mempty "aab"

这失败了，因为它会解析"a"两次，而不是回溯，因为choice不这样做。此外，string "a"两次都成功了，因此可能无法再检索消耗的输入。如何实现一个可以回溯并生成解析结果列表的解析器，例如Success ["a","ab"]？

如果我要求输入将标记分开，我仍然无法使其工作：

这有效：

parseString (try (string "a" <* eof) <|> (string "ab" <*eof)) mempty "ab"

但这不会：

parseString (try (foldl1 (<|>) $ map (\x -> x <* eof) parsers)) mempty "ab"
4

1 回答 1

1

级别执行得try太高。您应该在各个解析器上执行它。例如：

parseString (foldl1 (<|>) $ map (\x -> try (x <* eof)) parsers) mempty "ab"

在您写的原始解析器中：

parseString ((try (string "a" <* eof)) <|> (string "ab" <*eof)) mempty "ab"

请注意， 的左操作数<|>包含try (string "a" <* eof)在内try。

而在你与 一起表演的那一场中foldl1，你写道：

parseString (try ((string "a" <* eof) <|> (string "ab" <*eof))) mempty "ab"

所以这里是try左操作数的 not 部分。结果，如果第一个解析器失败，“光标”将不会返回到它决定尝试第一个操作数的点。

我们可以通过以下方式改进上述内容asum :: (Foldable t, Alternative f) -> t (f a) -> f a：

import Data.Foldable(asum)

parseString (asum (map (\x -> try (x <* eof)) parsers)) mempty "ab"
于 2019-10-11T12:54:09.440 回答