Действительно ли порядок имеет значение с <|> здесь, в этом парсере?

Question

Утро понедельника Haskell post Синтаксический анализ. Часть 2. Аппликативный анализ говорит об этом с чередованием с regex-applicative:

Обратите внимание, что порядок имеет значение! Если мы сначала поставим целочисленный парсер, у нас будут проблемы! Если мы встретим десятичное число, целочисленный синтаксический анализатор будет жадно преуспевать и проанализирует все до десятичной точки Мы либо потеряем всю информацию после десятичного числа, либо, что еще хуже, произойдет сбой синтаксического анализа.

Обращаясь к этой функции из их Git хранилища :

numberParser :: RE Char Value
numberParser = (ValueNumber . read) <$>
  (negativeParser <|> decimalParser <|> integerParser)
  where
    integerParser = some (psym isNumber)
    decimalParser = combineDecimal <$> many (psym isNumber) <*> sym '.' <*> some (psym isNumber)
    negativeParser = (:) <$> sym '-' <*> (decimalParser <|> integerParser)

    combineDecimal :: String -> Char -> String -> String
    combineDecimal base point decimal = base ++ (point : decimal)

Однако я не могу понять, почему это так. Когда я изменяю decimalParser <|> integerParser на integerParser <|> decimalParser, все равно кажется, что он всегда анализирует правильные вещи (в частности, я сделал это и запустил stack test, и их тесты все еще прошли). Десятичный синтаксический анализатор должен иметь десятичную точку, а целочисленный синтаксический анализатор не может иметь его, поэтому он прекратит там синтаксический анализ, в результате чего десятичная точка приведет к сбою в следующем фрагменте анализа, возвращая нас назад к десятичному парсеру. Кажется, что единственный случай, в котором это не произошло бы, был бы, если бы следующая часть общего синтаксического анализатора после этого могла принять десятичную точку (делая это неоднозначной грамматикой), но вы все равно не "потеряете всю информацию после у десятичной или, что хуже, разбора нет ». Верны ли мои рассуждения, и это ошибка в этой статье, или есть случай, когда я не вижу, где может произойти один из их результатов?

Answer 1

Есть разница, и это важно, но отчасти причина в том, что остальная часть синтаксического анализатора вполне fr agile.

Когда я изменяю decimalParser <|> integerParser на integerParser <|> decimalParser все еще кажется, что он всегда анализирует правильные вещи (в частности, я сделал это и запустил тестирование стека, и все их тесты все еще прошли).

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

Вот тест, который в настоящее время проходит, но не будет, если вы поменяете местами эти парсеры (вставьте его в test/Spec.hs и добавьте его в do блок под main):

badex :: Spec
badex = describe "Bad example" $ do
  it "Should fail" $
    shouldMatch
      exampleLineParser
      "| 3.4 |\n"
      [ ValueNumber 3.4 ]

Если вы поменяете местами парсеры, вы получите в результате ValueNumber 3.0: integerParser (который теперь первый) успешно разбирает 3, но затем остальные входные данные отбрасываются.

Чтобы получить больше контекста, мы должны увидеть, где используется numberParser:

1. numberParser является одной из альтернатив valueParser ...
2. , который используется в exampleLineParser, где за valueParser следует readThroughBar (и я имею в виду соответствующие кусок кода буквально valueParser <* readThroughBar);
3. readThroughBar отбрасывает все символов до следующей вертикальной черты (используя many (psym (\c -> c /= '|' && c /= '\n'))).

Так если valueParser удастся выполнить синтаксический анализ всего 3, то последующее readThroughBar с удовольствием поглотит и откажется от остальных .4 |.

Объяснение из цитируемого вами поста блога является лишь частично правильным:

Обратите внимание, что порядок имеет значение! Если мы сначала поставим целочисленный парсер, у нас будут проблемы! Если мы встретим десятичную дробь, целочисленный синтаксический анализатор будет жадно успешен и проанализирует все до десятичной точки. Мы либо потеряем всю информацию после десятичного числа или, что еще хуже, произойдет сбой синтаксического анализа.

(выделение мое) Вы потеряете информацию только в том случае, если ваш анализатор активно ее отбрасывает , что readThroughBar здесь делает.

Как вы уже предположили, поведение обратного отслеживания RE означает, что некоммутативность <|> действительно имеет значение только для корректности с неоднозначными синтаксисами (она все еще может влиять на производительность в целом), что не было бы проблемой, если бы readThroughBar были менее снисходительными, например, потребляя только пробел до |.

Я думаю, это показывает, что использование psym с (/=) это как минимум кодовый запах, если не чистый антипаттерн. Поиск только ограничителя без ограничения символов в середине затрудняет выявление ошибок, когда предыдущий анализатор не потребляет столько входных данных, сколько должен. Лучшей альтернативой является обеспечение того, чтобы используемые символы не содержали значимой информации, например, требуя, чтобы все они были пробелами.

Answer 2

Проблема заключается в разборе чего-то вроде:

12.34

Если вы сначала попробуете анализатор целых чисел, то он найдет 12, заключите, что он нашел целое число, и затем попытайтесь проанализировать .34 как следующий токен.

[...] десятичная точка, делающая ошибку следующего фрагмента, возвращая нас к десятичному анализатору.

Да, пока ваш анализатор выполняет возврат. Из соображений производительности большинство производственных анализаторов (например, megaparse c) не делают этого, если им специально не сказано (обычно с помощью комбинатора try). Анализатор RE, используемый в сообщении в блоге, вполне может быть исключением, но я не могу найти его интерпретатор для проверки.