Как сохранить факторные вычисления при разборе строки с Parse c in Haskell?

Question

Я столкнулся с трудностями при попытке расчета факторного вывода с помощью Text.Parse c in Haskell. Давайте посмотрим на некоторый код, который я использую до сих пор:

import Text.Parsec hiding(digit)
import Data.Functor

type CalcParser a = CalcParsec String () a

digit :: CalcParser Char
digit = oneOf ['0'..'9']

number :: CalcParser Double
number = try calcDouble <|> calcInt  

calcInt :: CalcParser Double 
calcInt = read <$> many1 digit

calcDouble :: CalcParser Double 
calcDouble = do
    integ <- many1 digit
    char '.'
    decim <- many1 digit
    pure $ read $ integ <> "." <> decim

numberFact :: CalcParser Integer     
numberFact = read <$> many1 digit

applyMany :: a -> [a -> a] -> a
applyMany x [] = x
applyMany x (h:t) = applyMany (h x) t

div_ :: CalcParser (Double -> Double -> Double)
div_= do
    char '/'
    return (/)

star :: CalcParser (Double -> Double -> Double)
star = do
    char '*'    
    return (*)  

plus :: CalcParser (Double -> Double -> Double)
plus = do
    char '+'    
    return (+)

minus :: CalcParser (Double -> Double -> Double)
minus = do
    char '-'    
    return (-)  

multiplication :: CalcParser Double
multiplication = do
    spaces
    lhv <- atom <|> fact' <|> negation'
    spaces
    t <- many tail
    return $ applyMany lhv t
    where tail =
                do
                    f <- star <|> div_
                    spaces
                    rhv <- atom <|> fact' <|> negation'
                    spaces
                    return (`f` rhv)

atom :: CalcParser Double
atom = number <|> do
    char '('
    res <- addition
    char ')'
    return res

fact' :: CalcParser Double
fact' = do
    spaces
    rhv <- numberFact
    char '!'
    return $ factorial rhv

factorial :: Integer -> Double
factorial n
    | n < 0 = error "No factorial exists for negative inputs" 
    | n == 0 || n == 1 = 1
    | otherwise = acc n 1
    where
    acc 0 a = a
    acc b a = acc (b-1) (fromIntegral b * a) 

negation' :: CalcParser Double
negation' = do
    spaces
    char '~'
    rhv <- atom
    spaces
    return $ negate rhv         

addition :: CalcParser Double
addition = do
    spaces
    lhv <- multiplication <|> fact' <|> negation'
    spaces
    t <- many tail
    return $ applyMany lhv t
    where tail =
                do
                    f <- plus <|> minus 
                    spaces
                    rhv <- multiplication <|> fact' <|> negation'
                    spaces
                    return (`f` rhv)

Это своего рода простой анализатор калькулятора, который обеспечивает сложение / вычитание / факториальную обработку. Я позволю вводить любые связанные с факторами компоненты строкового чанка, чтобы каждый из них состоял из некоторого числа, за которым следует '!' характер (как обычно в большинстве реальных калькуляторов). Однако при запуске теста синтаксического анализатора как:

parseTest addition "3!"

он не может вычислить сам факториал, но возвращает 3.0 (вывод должен быть представлен как число с плавающей запятой, поэтому я использую CalcParser Double в эта программа). Странным фактом является то, что всякий раз, когда я устанавливаю '! до числа:

fact' :: CalcParser Double
fact' = do
    spaces
    char '!'
    rhv <- numberFact
    return $ factorial rhv

результат:

parseTest addition "!3"

соответствует моим ожиданиям, т.е. равен 6.0. После этого я предполагаю, что в первой версии программы есть некоторый недостаток, который не запускает факторные вычисления, когда '! рядом с некоторыми числовыми элементами ввода. Это просто тот случай, когда я ищу какую-либо помощь, чтобы решить здесь. Итак, что не так с правой стороной '!' и как бы вы справились с описанной проблемой?

Answer 1

Общая проблема в том, что Parse c прекращает пробовать альтернативы, когда находит первый, который работает. Если вы напишите:

parseTest (atom <|> fact') "3!"

, это приведет к 3.0. Это потому, что парсер atom успешно анализирует начальную часть строки "3", поэтому Parse c даже не пытается парсер fact'. Оставшаяся строка "!" остается для другого, более позднего парсера, для обработки.

В приведенном выше коде парсера, если вы попытаетесь выполнить синтаксический анализ:

parseTest addition "3!"

синтаксический анализатор addition начинается с попытки парсера multiplication. У синтаксического анализатора multiplication есть строка:

lhv <- atom <|> fact' <|> negation'

, поэтому он начинает работу с парсера atom. Этот синтаксический анализатор работает нормально и возвращает 3.0, поэтому он никогда не утруждает себя попыткой fact' или negation.

Чтобы исправить свой синтаксический анализатор, необходимо убедиться, что вы не успешно проанализировали atom в альтернативе, прежде чем пытаться fact'. Вы можете начать с переключения порядка:

> parseTest (fact' <|> atom) "3!"
6.0

Это нормально работает для разбора "3!" (и дает 6.0), но не получается, если вы попытаетесь разобрать что-то еще:

> parseTest (fact' <|> atom) "3"
parse error at (line 1, column 2):
unexpected end of input
expecting "!"

Это связано с тем, что по соображениям эффективности Parse c автоматически не "возвращается". Если вы попытаетесь что-то проанализировать, и он «потребляет ввод» до того, как потерпит неудачу, он потерпит неудачу полностью, вместо того, чтобы попробовать больше альтернатив. Здесь fact' начинается с вызова numberFact, который успешно «потребляет» "3", а затем пытается char '!', что не удается. Таким образом, fact «завершается неудачно после использования ввода», что приводит к немедленной ошибке разбора.

Вы можете переопределить это поведение, используя функцию try:

> parseTest (try fact' <|> atom) "3"
3.0
> parseTest (try fact' <|> atom) "3!"
6.0

Здесь try fact' применяет синтаксический анализатор fact', но обрабатывает "сбой после использования ввода", как если бы он был "сбой после использования ввода", поэтому можно проверить дополнительные альтернативы.

Если вы применили это изменение к обоим местам в вашем multiplication парсер:

multiplication :: CalcParser Double
multiplication = do
    spaces
    lhv <- try fact' <|> atom <|> negation'
    spaces
    t <- many tail
    return $ applyMany lhv t
    where tail =
                do
                    f <- star <|> div_
                    spaces
                    rhv <- try fact' <|> atom <|> negation'
                    spaces
                    return (`f` rhv)

и внес аналогичные изменения в ваш addition парсер:

addition :: CalcParser Double
addition = do
    spaces
    lhv <- try fact' <|> multiplication <|> negation'
    spaces
    t <- many tail
    return $ applyMany lhv t
    where tail =
                do
                    f <- plus <|> minus
                    spaces
                    rhv <- try fact' <|> multiplication <|> negation'
                    spaces
                    return (`f` rhv)

, тогда он будет работать лучше:

> parseTest addition "3!"
6.0
> parseTest addition "3"
3.0
> parseTest addition "3+2*6!"
1443.0

Это также Хорошая идея добавить анализатор eof в ваш тест, чтобы убедиться, что у вас нет остаточного мусора, который не был проанализирован:

> parseTest addition "3  Hey, I could write anything here"
3.0
> parseTest (addition <* eof) "3  but adding eof will generate an error"
parse error at (line 1, column 4):
unexpected 'b'
expecting space, "*", "/", white space, "+", "-" or end of input