нежадное повторение с Parsec

Я пытаюсь разделить свой ввод на те части, которые соответствуют определенному шаблону, а остальные, скажем,

data Data = A Int | B Char | C String
parseDatas :: Parsec [Token] () a [Data]

Я уже написал два более-менее сложных парсера

parseA :: Parsec [Token] () Data
parseB :: Parsec [Token] () Data

которые соответствуют вещам, которые я ищу. Теперь очевидное решение

parseDatas = many (parseA <|> parseB <|> parseC)

где парсер для промежуточных частей будет выглядеть так:

makeC :: [Token] -> Data
makeC = C . concatMap show -- or something like this
parseC :: Parsec [Token] () Data
parseC = makeC <$> many anyToken

Мех, это выдает среду выполнения [ERROR] Text.ParserCombinators.Parsec.Prim.many: combinator 'many' is applied to a parser that accepts an empty string. - хорошо, это легко исправить:

parseC = makeC <$> many1 anyToken

Но теперь parseC потребляет весь ввод (который начинается с чего-то, что я не ищу), игнорируя любые шаблоны, которые должны дать A или B!

Если бы мои шаблоны были регулярными выражениями1, я бы сейчас заменил оператор + на нежадный оператор +?. Как сделать то же самое для комбинатора парсера many1?

1: который я не могу использовать, так как работаю с токенами, а не с символами

Решение, которое я нашел, было

parseC = makeC <$> many1 (notFollowedBy (parseA <|> parseB) >> anyToken)

но это выглядит, ммм, неоптимально. Это не совсем универсально. Должно быть что-то лучше.

Я также просмотрел Parsec, как найти совпадения в строке, где предлагалось определить рекурсивный синтаксический анализатор, но это выглядит как проблема, если я не хочу отбрасывать промежуточные токены и вместо этого собирать их в список.


haskell parsec non-greedy
person Bergi    schedule 04.08.2016    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете позволить parseC потреблять ровно один токен за раз:

parseDatas = many $ parseA <|> parseB <|> (C . show <$> anyToken)

а затем, если хотите, сгруппируйте соседние C в один, чтобы сохранить семантику:

groupCs (C c) (C c':xs) = C (c ++ c') : xs
groupCs x xs = x : xs
parseDatas = foldr groupCs [] <$> many (parseA <|> parseB <|> (C . show <$> anyToken))

Если вы хотите применить некоторую операцию make :: [Token] -> String к последовательным C:

data Data c = A Int | B Char | C c deriving Functor

groupCs :: [Data a] -> [Data [a]] -> [Data [a]]
groupCs (C c) (C cs:xs) = C (c:cs) : xs
groupCs (C c) xs = C [c] : xs
groupCs x xs = x : xs

parseDatas = (map.fmap) make . foldr groupCs [] <$> many (parseA <|> parseB <|> (C <$> anyToken))
person Gurkenglas    schedule 04.08.2016
comment
Хм, моя проблема в том, что я должен использовать makeC, который принимает список токенов. makeC . return <$> anyToken будет работать, но выглядит уродливо и так же неэффективно, как и мое текущее решение. - person Bergi; 04.08.2016
comment
@Bergi, вот как освободить место для применения make. Далее таким образом лежала библиотека lens. - person Gurkenglas; 04.08.2016
comment
@Bergi Почему вы считаете, что makeC . return <$> anyToken неэффективен? Это, конечно, не будет таким неэффективным, как произвольный просмотр, как в вашем вопросе. - person Daniel Wagner; 04.08.2016
comment
Не знаю, думаю, надо проверить. Производительность в Haskell немного непредсказуема. Просто единственная функция для преобразования токенов, предоставляемая библиотекой, которую я использую, принимает этот список токенов, поэтому я подумал, что ее следует вызывать с большим количеством токенов. Это точный тип [Token] -> Data.Text, если это поможет. - person Bergi; 04.08.2016
comment
Спасибо за функторный подход, думаю, я смогу это сделать. - person Bergi; 04.08.2016

arrow_upward
1
arrow_downward

Комбинатор парсеров sepCap из < href="https://hackage.haskell.org/package/replace-megaparsec/" rel="nofollow noreferrer">replace-megaparsec может разбить строку на те части, которые соответствуют определенному шаблону, а остальные .

Попробуй это:

sepCap (parseA <|> parseB)

Или, если parseA и parseB являются синтаксическими анализаторами для разных типов вещей, то, возможно, используйте eitherP например:

sepCap (eitherP parseA parseB)
person James Brock    schedule 30.08.2019