这是this question的演变。
我需要用megaparsec解析数据结构
data Foo =
Simple String
Dotted Foo String
Paren String Foo
我想解析它的字符串
foo ::= alphanum
| foo "." alphanum
| alphanum "(" foo ")"
例如,字符串"a(b.c).d"
应该被解析为Dotted (Paren "a" (Dotted (Simple "b") "c")) "d"
。
我遇到的问题是,这是左右递归的同时。
我为第一个和第三个案例编写解析器没有问题:
parser :: Parser Foo
parser
= try (do
prefix <- alphanum
constant "("
content <- parser
constant ")"
pure $ Paren prefix content
)
<|> Simple alphanum
但是我无法将第二种情况下的解析器放在一起。我试图用sepBy1
或makeExprParser
接近它,但我无法做到正确
将此递归分解为:
foo ::= alphanum
| foo "." alphanum
| alphanum "(" foo ")"
你可以从重写它开始:
foo ::= alphanum ("(" foo ")")?
| foo "." alphanum
然后你可以使用替换的标准技巧来分解左递归:
x ::= x y | z
附:
x ::= z x'
x' ::= y x' | ∅
换一种说法:
x ::= z y*
随着x
= foo
,y
= "." alphanum
和z
= alphanum ("(" foo ")")?
,变为:
foo ::= alphanum ("(" foo ")")? ("." alphanum)*
然后我相信你的解析器可以是这样的,因为?
~0或者一个~Maybe
~optional
和*
~0或更多~[]
~many
:
parser = do
prefix <- Simple <$> alphanum
maybeParens <- optional (constant "(" *> parser <* constant ")")
suffixes <- many (constant "." *> alphanum)
let
prefix' = case maybeParens of
Just content -> Paren prefix content
Nothing -> prefix
pure $ foldl' Dotted prefix' suffixes