Как далеко "пробует" задний ход?

Question

Итак... Я испортил запись в формате 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 работает только в "текущем" поплавке. Нет возврата к предыдущим позициям. Это правильно?

И если так... как бы я мог реализовать дальнейшее отслеживание назад?

Answer 1

Как далеко "пытается" вернуться назад?

Парсер try p потребляет столько же входных данных, сколько p если p анализирует успешно, иначе он не потребляет никакого ввода вообще. Так что, если вы посмотрите на это с точки зрения возврата назад, он вернется к точке, в которой вы находились, когда вызывали его.

Моя проблема в том, что, очевидно, попытка работает только в "текущем" поплавке. Нет возврата к предыдущим позициям. Это правильно?

Да, try не "не потреблять" ввод. Все, что он делает, это восстанавливается после сбоя в парсере, который вы ему даете, без использования какого-либо ввода. Он не отменяет эффекты любых парсеров, которые вы применяли ранее, и не влияет на последующие парсеры, которые вы применяете после try p удалось.

И если так... как бы я мог реализовать дальнейшее отслеживание назад?

В основном вы хотите не только знать, pointyFloatP преуспевает на текущем входе, но также и остальная часть вашего lineP будет успешно после успешно pointyFloatP - и если это не так, вы хотите вернуться назад, прежде чем вы подали заявку pointyFloatP, Таким образом, в основном вы хотите парсер для всей оставшейся строки в try, а не только парсер поплавков.

Для достижения этого вы можете сделать floatP возьмем синтаксический анализатор для оставшейся строки в качестве аргумента:

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

Обратите внимание, что этот вид возврата не будет очень эффективным (но я предполагаю, что вы знали, что происходит).

Answer 2

Обновление: включить пользовательский монадический анализатор для более сложных строк.

Использование монады списка для простого анализа

Монада списка делает лучший "анализатор" обратного отслеживания, чем Мегапарсек. Например, для разбора ячеек:

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
>

Использование пользовательской монады на основе монады списка для более сложного анализа

Для более сложного анализа, например, если вы хотите разобрать строку, например:

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)

Обратите внимание на сходство с типом 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 для генерации списка возможных разборов, берет их один за другим в монаде списка для вычисления следующего парсера q использовать (что, как обычно для монадической операции, может зависеть от результата первого разбора), и генерирует список возможных окончательных разборов, которые возвращаются.

Alternative а также MonadPlus примеры довольно просты - они просто снимают пустоту и чередование с монады списка:

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 принимает правильный подход, но предполагает, что вы анализируете символы из String а не произвольные токены из какого-то другого потока (в нашем случае, Stringс из [String]).

Возможно, кто-то еще может указать на готовое решение, которое избавило бы вас от необходимости играть роль вашего собственного типа синтаксического анализатора, экземпляров и примитивов.