代码之家 › 专栏 › 技术社区 › marcosh

递归解析器

megaparsec haskell parsing

4

marcosh · 技术社区 · 6 年前

我需要解析,使用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

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

1 回复 | 直到 6 年前

1

6

sepp2k 6 年前

它不解析任何虚线,因为第一个选项总是成功解析字符串的第一部分。

通过改变备选方案的顺序,可以很容易地解决这个问题。一般来说,每当你有一个选择,总是可以匹配,这个选择必须排在最后。

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

foo ::= alphanum
      | foo "." alphanum

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

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

many 对于 * rule ("seperator" rule)* 更简单地说 sepBy1 . 所以这给了我们:

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