3

所以......我搞砸了 CSV 格式的录音：

23,95489,0,20,9888

由于语言设置，浮点数用逗号作为分隔符写入......在逗号分隔值文件中......

问题是该文件对每个浮点数都没有很好的格式。有些根本没有意义，点后面的数字数量也各不相同。

我的想法是构建一个MegaParsec解析器，它会尝试读取所有可能的浮点格式，继续前进，如果发现错误则回溯。

例如上面的例子：

  1. 阅读 23,95489 -> 好
  2. 阅读 0,20 -> 好（到目前为止）
  3. 读取 9888 -> 错误（因为列的值太高（检查guard））
  4. （回溯到 2。）读取 0 -> 再次良好
  5. 阅读 20,9888 -> 好
  6. 完毕

我已将其实现为（此处为伪代码）：

floatP = try pointyFloatP <|> unpointyFloatP

lineP = (,,) <$> floatP <* comma <*> floatP <* comma <*> floatP <* comma

我的问题是，显然try只有在“当前”浮动中有效。没有回溯到以前的位置。这个对吗？

如果是这样……我将如何实施进一步的回溯？

4

2 回答 2

3

“尝试”回溯多远？

解析器try p消耗的输入与解析成功时一样多p，p否则它根本不消耗任何输入。因此，如果您从回溯的角度来看，它会回溯到您调用它时所在的位置。

我的问题是，显然尝试只适用于“当前”浮动。没有回溯到以前的位置。这个对吗？

是的，try不会“取消使用”输入。它所做的只是从您提供给它的解析器中的故障中恢复，而无需消耗任何输入。它不会撤消您之前应用的任何解析器的效果，也不会影响您try p成功后应用的后续解析器。

如果是这样……我将如何实施进一步的回溯？

基本上你想要的不仅是知道pointyFloatP当前输入是否成功，而且你的其余部分在lineP成功后是否会成功pointyFloatP——如果你不想回溯到应用之前pointyFloatP。所以基本上你想要解析器中的整个剩余行try，而不仅仅是浮点解析器。

为了实现这一点，您可以floatP将剩余行的解析器作为这样的参数：

floatP restP = try (pointyFloatP <*> restP) <|> unpointyFloatP <*> restP

请注意，这种回溯不会非常有效（但我假设您知道这样做）。

于 2018-07-23T17:30:52.860 回答
2

更新：为更复杂的行包含一个自定义单子解析器。

使用 List Monad 进行简单解析

list monad 是比 Megaparsec 更好的回溯“解析器”。例如，要解析单元格：

row :: [String]
row = ["23", "95489", "0", "20", "9888"]

精确到满足特定界限（例如，小于 30）的三列值，您可以生成所有可能的解析：

{-# OPTIONS_GHC -Wall #-}

import Control.Monad
import Control.Applicative

rowResults :: [String] -> [[Double]]
rowResults = cols 3
  where cols :: Int -> [String] -> [[Double]]

        cols 0 [] = pure []   -- good, finished on time
        cols 0 _  = empty     -- bad, didn't use all the data

        -- otherwise, parse exactly @n@ columns from cells @xs@
        cols n xs = do
          -- form @d@ from one or two cells
          (d, ys) <- num1 xs <|> num2 xs
          -- only accept @d < 30@
          guard $ d < 30
          ds <- cols (n-1) ys
          return $ d : ds

        -- read number from a single cell
        num1 (x:xs) | ok1 x = pure (read x, xs)
        num1 _ = empty

        -- read number from two cells
        num2 (x:y:zs) | ok1 x && ok2 y = pure (read (x ++ "." ++ y), zs)
        num2 _ = empty

        -- first cell: "0" is okay, but otherwise can't start with "0"
        ok1 "0" = True
        ok1 (c:_) | c /= '0' = True
        ok1 _ = False

        -- second cell: can't end with "0" (or *be* "0")
        ok2 xs = last xs /= '0'

上面的基于列表的解析器试图通过假设如果“xxx，yyy”是一个数字，“xxx”不会以零开头（除非它只是“0”），而“yyy”不会以零开头以零结尾（或者，就此而言，是单个“0”）。如果这不正确，只需ok1根据需要进行修改ok2。

应用于row，这给出了一个明确的解析：

> rowResults row
[[23.95489,0.0,20.9888]]

应用于模棱两可的行，它给出所有解析：

> rowResults ["0", "12", "5", "0", "8601"]
[[0.0,12.5,0.8601],[0.0,12.5,0.8601],[0.12,5.0,0.8601]]

无论如何，我建议使用标准 CSV 解析器将您的文件解析为一个String单元格矩阵，如下所示：

dat :: [[String]]
dat = [ ["23", "95489", "0", "20", "9888"]
      , ["0", "12", "5", "0", "8601"]
      , ["23", "2611", "2", "233", "14", "422"]
      ]

然后rowResults在上面使用获取不明确的行数：

> map fst . filter ((>1) . snd) . zip [1..] . map (length . rowResults) $ dat
[2]
>

或无法解析：

> map fst . filter ((==0) . snd) . zip [1..] . map (length . rowResults) $ dat
[]
>

假设没有不可解析的行，您可以重新生成一个可能的固定文件，即使某些行不明确，但只需为每一行获取第一个成功解析：

> putStr $ unlines . map (intercalate "," . map show . head . rowResults) $ dat
23.95489,0.0,20.9888
0.0,12.5,0.8601
23.2611,2.233,14.422
>

使用基于 List Monad 的自定义 Monad 进行更复杂的解析

对于更复杂的解析，例如，如果您想解析如下行：

type Stream = [String]
row0 :: Stream
row0 = ["Apple", "15", "1", "5016", "2", "5", "3", "1801", "11/13/2018", "X101"]

使用字符串和数字的混合，编写一个基于列表单子的单子解析器实际上并不难，它生成所有可能的解析。

关键思想是将解析器定义为一个函数，它接受一个流并生成一个可能的解析列表，每个可能的解析都表示为从流的开头成功解析的对象的元组，并与流的其余部分配对。包装在一个新类型中，我们的并行解析器看起来像：

newtype PParser a = PParser (Stream -> [(a, Stream)]) deriving (Functor)

请注意与 from 类型的相似性，ReadS从Text.ParserCombinators.ReadP技术上讲，它也是“所有可能的解析”解析器（尽管您通常只期望从reads调用返回一个明确的解析）：

type ReadS a = String -> [(a, String)]

无论如何，我们可以像这样定义一个Monad实例PParser：

instance Applicative PParser where
  pure x = PParser (\s -> [(x, s)])
  (<*>) = ap
instance Monad PParser where
  PParser p >>= f = PParser $ \s1 -> do  -- in list monad
    (x, s2) <- p s1
    let PParser q = f x
    (y, s3) <- q s2
    return (y, s3)

这里没有什么太棘手的地方： pure x返回一个可能的解析，即x具有未更改的流的结果s，同时p >>= f应用第一个解析器p生成可能解析的列表，在列表 monad 中逐个获取它们以计算下一个q要使用的解析器 (与通常的一元操作一样，它可以取决于第一次解析的结果），并生成一个可能返回的最终解析列表。

Alternativeand实例非常简单——它们只是从MonadPluslist monad 中消除空虚和交替：

instance Alternative PParser where
  empty = PParser (const empty)
  PParser p <|> PParser q = PParser $ \s -> p s <|> q s
instance MonadPlus PParser where

要运行我们的解析器，我们有：

parse :: PParser a -> Stream -> [a]
parse (PParser p) s = map fst (p s)

现在我们可以引入原语：

-- read a token as-is
token :: PParser String
token = PParser $ \s -> case s of
  (x:xs) -> pure (x, xs)
  _ -> empty

-- require an end of stream
eof :: PParser ()
eof = PParser $ \s -> case s of
  [] -> pure ((), s)
  _ -> empty

和组合器：

-- combinator to convert a String to any readable type
convert :: (Read a) => PParser String -> PParser a
convert (PParser p) = PParser $ \s1 -> do
  (x, s2) <- p s1     -- for each possible String
  (y, "") <- reads x  -- get each possible full read
                      -- (normally only one)
  return (y, s2)

以及 CSV 行中各种“术语”的解析器：

-- read a string from a single cell
str :: PParser String
str = token

-- read an integer (any size) from a single cell
int :: PParser Int
int = convert (mfilter ok1 token)

-- read a double from one or two cells
dbl :: PParser Double
dbl = dbl1 <|> dbl2
  where dbl1 = convert (mfilter ok1 token)
        dbl2 = convert $ do
          t1 <- mfilter ok1 token
          t2 <- mfilter ok2 token
          return $ t1 ++ "." ++ t2

-- read a double that's < 30
dbl30 :: PParser Double
dbl30 = do
  x <- dbl
  guard $ x < 30
  return x

-- rules for first cell of numbers:
-- "0" is okay, but otherwise can't start with "0"
ok1 :: String -> Bool
ok1 "0" = True
ok1 (c:_) | c /= '0' = True
ok1 _ = False

-- rules for second cell of numbers:
-- can't be "0" or end in "0"
ok2 :: String -> Bool
ok2 xs = last xs /= '0'

然后，对于特定的行模式，我们可以编写一个行解析器，就像我们通常使用一元解析器一样：

-- a row
data Row = Row String Int Double Double Double
               Int String String deriving (Show)
rowResults :: PParser Row
rowResults = Row <$> str <*> int <*> dbl30 <*> dbl30 <*> dbl30
                 <*> int <*> str <*> str <* eof

并获得所有可能的解析：

> parse rowResults row0
[Row "Apple" 15 1.5016 2.0 5.3 1801 "11/13/2018" "X101"
,Row "Apple" 15 1.5016 2.5 3.0 1801 "11/13/2018" "X101"]
>

完整的程序是：

{-# LANGUAGE DeriveFunctor #-}
{-# OPTIONS_GHC -Wall #-}

import Control.Monad
import Control.Applicative

type Stream = [String]

newtype PParser a = PParser (Stream -> [(a, Stream)]) deriving (Functor)
instance Applicative PParser where
  pure x = PParser (\s -> [(x, s)])
  (<*>) = ap
instance Monad PParser where
  PParser p >>= f = PParser $ \s1 -> do  -- in list monad
    (x, s2) <- p s1
    let PParser q = f x
    (y, s3) <- q s2
    return (y, s3)
instance Alternative PParser where
  empty = PParser (const empty)
  PParser p <|> PParser q = PParser $ \s -> p s <|> q s
instance MonadPlus PParser where

parse :: PParser a -> Stream -> [a]
parse (PParser p) s = map fst (p s)

-- read a token as-is
token :: PParser String
token = PParser $ \s -> case s of
  (x:xs) -> pure (x, xs)
  _ -> empty

-- require an end of stream
eof :: PParser ()
eof = PParser $ \s -> case s of
  [] -> pure ((), s)
  _ -> empty

-- combinator to convert a String to any readable type
convert :: (Read a) => PParser String -> PParser a
convert (PParser p) = PParser $ \s1 -> do
  (x, s2) <- p s1     -- for each possible String
  (y, "") <- reads x  -- get each possible full read
                      -- (normally only one)
  return (y, s2)

-- read a string from a single cell
str :: PParser String
str = token

-- read an integer (any size) from a single cell
int :: PParser Int
int = convert (mfilter ok1 token)

-- read a double from one or two cells
dbl :: PParser Double
dbl = dbl1 <|> dbl2
  where dbl1 = convert (mfilter ok1 token)
        dbl2 = convert $ do
          t1 <- mfilter ok1 token
          t2 <- mfilter ok2 token
          return $ t1 ++ "." ++ t2

-- read a double that's < 30
dbl30 :: PParser Double
dbl30 = do
  x <- dbl
  guard $ x < 30
  return x

-- rules for first cell of numbers:
-- "0" is okay, but otherwise can't start with "0"
ok1 :: String -> Bool
ok1 "0" = True
ok1 (c:_) | c /= '0' = True
ok1 _ = False

-- rules for second cell of numbers:
-- can't be "0" or end in "0"
ok2 :: String -> Bool
ok2 xs = last xs /= '0'

-- a row
data Row = Row String Int Double Double Double
               Int String String deriving (Show)
rowResults :: PParser Row
rowResults = Row <$> str <*> int <*> dbl30 <*> dbl30 <*> dbl30
                 <*> int <*> str <*> str <* eof

row0 :: Stream
row0 = ["Apple", "15", "1", "5016", "2", "5", "3", "1801", "11/13/2018", "X101"]

main = print $ parse rowResults row0

现成的解决方案

我有点惊讶我找不到提供这种“所有可能的解析”解析器的现有解析器库。中的内容Text.ParserCombinators.ReadP采用了正确的方法，但它假定您正在解析来自 a 的字符，String而不是来自其他流（在我们的例子中String是来自 a 的 s [String]）的任意标记。

也许其他人可以指出一个现成的解决方案，使您不必扮演自己的解析器类型、实例和原语。

于 2018-07-23T23:47:49.757 回答