我需要解析,使用Megaparsec这样的数据结构
data Foo
= Simple String
| Dotted Foo String
我可以用点分隔的字母数字字符串。
例如,abc
应该被解析为Simple "abc"
和abc.def
到Dotted (Simple "abc") "def"
。
我的解析器此刻就像
fooParser :: Parser Foo
fooParser
= Simple <$> alphaNum
<|> do
foo <- fooParser
constant "."
end <- alphaNum
pure $ Dotted foo end
这适用于Simple
,但它不解析任何Dotted
,因为第一个选项总是成功解析字符串的第一部分。
哪个是修复我的解析器的最佳选择?
它不解析任何Dotted,因为第一个选项总是成功解析字符串的第一部分。
通过改变替代方案的顺序,可以很容易地解决这个问题。一般来说,只要你有一个总能匹配的替代方案,那个替代方案必须是最后的。
然而,这只会引导您进入下一个问题:您的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