Haskell Parsec - парсинг двух списков вещей

Я использую Advent of Code часть 16 в качестве предлога, чтобы научиться использовать Parsec, но я спотыкаюсь о том, как справиться с этим конкретным случаем.

Ввод в следующем формате:

Before: [3, 2, 3, 0]
2 3 1 1
After:  [3, 2, 3, 0]

Before: [1, 0, 2, 1]
7 0 1 1
After:  [1, 1, 2, 1]

...

Before: [0, 0, 2, 1]
6 2 3 1
After:  [0, 6, 2, 1]



5 0 2 3
5 1 3 1
...
5 3 2 2

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

У меня есть рабочие парсеры для каждой из структур - Sample а также MaskedOperationс парсерами sample а также maskedOp соответственно1 - но я не могу понять, как собрать их вместе, чтобы разобрать его в ([Sample], [MaskedOperation]),

Я попробовал следующее:

parseInput :: GenParser Char st ([Sample], [MaskedOperation])
parseInput = do
  samples <- sample `sepBy` (count 2 newline) <* count 3 newline
  operations <- maskedOp `sepBy` newline
  return (samples, operations)

но он терпит неудачу, когда он достигает трех новых строк, ожидая другой образец:

(line 3221, column 1):
unexpected "\n"
expecting "Before:"

Как мне сказать parsec, что я хочу взять как можно больше, затем использовать разделитель (дополнительные символы новой строки), а затем начать читать другие вещи?


1 Прочитайте проблему Адвента Кодекса для контекста; имена не важны.

2 ответа

Решение

Я боюсь, что вы не можете использовать sepBy Вот.

Давайте упростим это до синтаксического анализа "a" как выборок и "b" как новых строк. Вы собираетесь разобрать строки как

a b b a b b b c b c b c b

Так что же думает парсер при обходе такой строки? Давайте пройдем через это:


анализ a или пустая последовательность

[a] b b a b b b c b c b c b

Ох a, Последовательность не пустая, поэтому я буду разбирать many"bb" >> "a" отныне.

a [b b a] b b b c b c b c b

Успех! Давай получим еще или закончим

a b b a [b b] b c b c b c b

Хорошо, я нашел другой bbтак что последовательность продолжается. анализ a

a b b a b b [b] c b c b c b

Wat


Проблема в том, что синтаксический анализатор не выполнит откат без явного запроса на это. Чтобы дать возможность отката парсера вы должны пометить его try комбинатор, иначе он не сможет "отменить" потребляемый ввод.

Пока я не вижу лучшего способа, чем переписать sepBy комбинатор, чтобы он знал, что после синтаксического анализа каждого разделителя может потребоваться вернуть его обратно в буфер при синтаксическом анализе separator >> target терпит неудачу:

sepTry a sep = sepTry1 a sep <|> pure []
sepTry1 a sep = liftA2 (:) a (many (try $ sep *> a))

Обратите внимание, что разбор a должны быть включены в try раздел - это то место, где фактически происходит сбой.

Чтобы визуализировать разницу, давайте посмотрим на тот же сценарий, но с sepTry вместо:


...

a [b b a] b b b c b c b c b

Успех! Давайте попробуем получить еще один, если это возможно

a b b a ![b b] b c b c b c b

Хорошо, я нашел другой bbтак что последовательность продолжается. анализ a

a b b a !b b [b] c b c b c b

Не то, что я ожидал. Вернуть ошибку и переместить курсор на восклицательный знак.

a b b a ![]b b b c b c b c b

Сбой при разборе bba, последовательность разбора закончена. парсить bbb

a b b a [b b b] c b c b c b

Успех!


В вашем случае после каждого Sample этот парсер попытается прочитать 2 новых строки с Sample после них или в случае неудачи 3 перевода строки и продолжения MaskedOperations

Сначала я запустил шаг токенизации, а затем использовал Parser String ([Sample], [Instruction]) вместо Parser Char ([Sample], [Instruction]), Наличие списка, уже разбитого на лексемы, значительно упростило игнорирование пробелов и других несоответствующих знаков препинания.

solve = parse . tokenize 
  where tokenize = concatMap words . lines . filter (not . (`elem` ",:[]"))
        parse = (,) <$> many sample <*> many instr
        sample = -- ...
        instr = -- ...

Обратного отслеживания не требуется, поскольку образцы и инструкции отличаются только от их первого токена.

Другие вопросы по тегам