gpt4 book ai didi

parsing - 递归解析器

转载 作者:行者123 更新时间:2023-12-05 00:47:14 26 4
gpt4 key购买 nike

我需要使用 Megaparsec 来解析这样的数据结构

data Foo
= Simple String
| Dotted Foo String

我可以用点分隔字母数字字符串。

例如 abc 应该解析为 Simple "abc"abc.defDotted (Simple "abc") “def”

我现在的解析器是这样的

fooParser :: Parser Foo
fooParser
= Simple <$> alphaNum
<|> do
foo <- fooParser
constant "."
end <- alphaNum
pure $ Dotted foo end

这对 Simple 工作正常,但它不解析任何 Dotted,因为第一个选项总是成功解析字符串的第一部分。

哪个是修复我的解析器的最佳选择?

最佳答案

it does not parse any Dotted, because the first option always succeeds parsing the first piece of the string.

通过更改备选方案的顺序可以很容易地解决这个问题。通常,只要您有始终匹配的备选方案,该备选方案就必须排在最后。

然而,这只会导致您遇到下一个问题:您的 Dotted 解析器是左递归的,parsec 不支持它,这意味着一旦它实际到达,它将导致无限递归。

通常,当我们想使用左递归语法和不处理左递归的解析算法时,我们用重复替换递归,然后对结果列表执行左折叠。所以给定原始语法:

foo ::= alphanum
| foo "." alphanum

我们可以像这样使用重复来重写它:

foo ::= alphanum ("." alphanum)*

现在,对 Parsec 的最直接翻译将使用 many 作为 *,然后左折叠结果列表。但是,我们可能会注意到模式 rule ("seperator"rule)* 可以更简单地与 sepBy1 匹配。所以这给了我们:

fooParser =
do
first : rest <- sepBy1 alphanum $ constant "."
return $ foldl Dotted (Simple first) rest

关于parsing - 递归解析器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52198620/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com