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

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

0 голосов
/ 23 января 2019

Я использую Advent of Code part 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 Прочтите проблему Advent of Code для контекста; имена не важны.

Ответы [ 2 ]

0 голосов
/ 24 января 2019

Сначала я запустил шаг токенизации, а затем 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 = -- ...

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

0 голосов
/ 24 января 2019

Боюсь, что вы не можете использовать 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

ваты

Проблема в том, что синтаксический анализатор не откатится, если явно не попросить сделать это . Чтобы дать возможность отката парсера, вы должны пометить его комбинатором 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 новых строки и будет продолжать MaskedOperation s

...