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

左右递归分析器

megaparsec haskell parsing

marcosh · 技术社区 · 6 年前

我需要用megaparsc分析数据结构,比如

data Foo =
    Simple String
    Dotted Foo String
    Paren String Foo

我想分析它的字符串

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

例如a字符串 "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 但我没能弄好

1 回复 | 直到 6 年前

Jon Purdy 6 年前

要在此中考虑左递归:

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或1 Maybe ~ optional 和 * ~零或更多~ [] ~ 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

推荐文章

batman · 如何用特定模式grep特定行及其子网行?

2 年前

user19251203 · ReactJs:Uncaught TypeError:无法读取未定义的属性(读取“0”)

2 年前

Jensen Holm · 在非常大的字符串中查找链接时遇到问题

2 年前

MBF · PHP导入/解析XML文件内容保存到数据库

2 年前

John Bustos · Javascript——基于字典/对象中的键解析字符串

2 年前

user10717742 · 用java编写的自定义文件解析器需要改进

2 年前

Taj Harris · JSONArray文本必须以“[”开头,位于1[字符2第1行]:需要帮助解析Json

2 年前

Muhsin Muhammed · 向文件中的行添加引号和逗号

2 年前

Felkru · 添加字符串会在Javascript中返回空字符串

3 年前

Mustard Tiger · 熊猫解析文本列

3 年前