Разбор в Haskell для простого переводчика

Question

Я относительно новичок в Haskell с основами программирования, основанными на языках OO. Я пытаюсь написать интерпретатор с парсером для простого языка программирования. Пока у меня есть переводчик в состоянии, которым я достаточно доволен, но немного борюсь с синтаксическим анализатором.

Вот фрагмент кода, с которым у меня возникают проблемы

data IntExp
 = IVar Var
 | ICon Int
 | Add IntExp IntExp
 deriving (Read, Show)

whitespace = many1 (char ' ')

parseICon :: Parser IntExp
parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

parseIVar :: Parser IntExp
parseIVar = 
  do x <- many (letter)
     prime <- string "'" <|> string ""
     return (IVar (x ++ prime))

parseIntExp :: Parser IntExp
parseIntExp =
  do x <- try(parseICon)<|>try(parseIVar)<|>parseAdd
     return x

parseAdd :: Parser IntExp
parseAdd =
  do x <- parseIntExp   
     whitespace
     string "+"
     whitespace
     y <- parseIntExp
     return (Add x y)

runP :: Show a => Parser a -> String -> IO ()
runP p input
  = case parse p "" input of
      Left err ->
        do putStr "parse error at "
           print err
      Right x -> print x

Язык немного сложнее, но этого достаточно, чтобы показать мою проблему.

Таким образом, в типе IntExp ICon является константой, а IVar - переменной, но теперь о проблеме. Это, например, работает успешно

runP parseAdd "5 + 5"

, который дает (Добавить (ICon 5) (ICon 5)), что является ожидаемым результатом. Проблема возникает при использовании IVars, а не ICons, например

runP parseAdd "n + m"

Это приводит к тому, что программа выдает ошибку, говоря, что было неожиданное «n», где ожидалась цифра. Это приводит меня к мысли, что parseIntExp не работает так, как я планировал. Мое намерение состояло в том, что он попытается проанализировать ICon, если это не удастся, то попытаться проанализировать IVar и так далее.

Так что я думаю, что проблема существует в parseIntExp, или я что-то упускаю в parseIVar и parseICon.

Надеюсь, я дал достаточно информации о своей проблеме, и я достаточно ясно.

Спасибо за любую помощь, которую вы можете оказать мне!

Answer 1

Ваша проблема на самом деле в parseICon:

parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

Комбинатор many соответствует нулю или большему количеству вхождений, поэтому он успешно выполняется на "m" путем сопоставления нулевых цифр,затем, вероятно, умирает, когда read терпит неудачу.

---

И пока я в этом, поскольку вы новичок в Haskell, вот несколько незапрошенных советов:

• Не используйте ложные скобки.many (digit) должно быть просто many digit.Скобки здесь просто группируют вещи, они не нужны для применения функций.

• Вам не нужно делать ICon (read x :: Int).Конструктор данных ICon может принимать только Int, поэтому компилятор сам может понять, что вы имели в виду.

• Вам не нужно try вокруг первогодве опции в parseIntExp в том виде, в каком они есть - нет входных данных, которые бы приводили к тому, что один из них потреблял бы некоторый ввод перед сбоем.Они либо сразу потерпят неудачу (для этого не нужно try), либо преуспеют после сопоставления с одним символом.

• Обычно лучше сначала разбить токены перед парсингом.Работа с пробелами одновременно с синтаксисом является головной болью.

• Обычно в Haskell используется оператор ($), чтобы избежать скобок.Это просто функциональное приложение, но с очень низким приоритетом, так что можно написать что-то вроде many1 (char ' ') many1 $ char ' '.

Кроме того, выполнение такого рода вещей является излишним и ненужным:

parseICon :: Parser IntExp
parseICon =
  do x <- many digit
     return (ICon (read x))

Когда все, что вы делаете - это применяете обычную функцию к результату парсера, вы можете просто использовать fmap:

parseICon :: Parser IntExp
parseICon = fmap (ICon . read) (many digit)

Это одно и то же,Вы можете сделать вещи еще лучше, если импортируете модуль Control.Applicative, который дает вам версию оператора fmap, называемую (<$>), а также другой оператор (<*>), который позволяет вам делать то же самое с функциями:несколько аргументов.Также есть операторы (<*) и (*>), которые отбрасывают правое или левое значения соответственно, что в данном случае позволяет анализировать что-то при отбрасывании результата, например, пробел и т. Д.

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

whitespace = many1 $ char ' '

parseICon :: Parser IntExp
parseICon = ICon . read <$> many1 digit

parseIVar :: Parser IntExp
parseIVar = IVar <$> parseVarName

parseVarName :: Parser String
parseVarName = (++) <$> many1 letter <*> parsePrime

parsePrime :: Parser String
parsePrime = option "" $ string "'"

parseIntExp :: Parser IntExp
parseIntExp = parseICon <|> parseIVar <|> parseAdd

parsePlusWithSpaces :: Parser ()
parsePlusWithSpaces = whitespace *> string "+" *> whitespace *> pure ()

parseAdd :: Parser IntExp
parseAdd = Add <$> parseIntExp <* parsePlusWithSpaces <*> parseIntExp

Answer 2

Я также новичок в Haskell, просто интересно:

будет ли parseIntExp когда-либо делать это для parseAdd?

Кажется, что ICon или IVar всегда будут анализироваться до достижения parseAdd.

например, runP parseIntExp "3 + m"

попытается выполнить parseICon и выполнится успешно, выдав

(ICon 3) вместо (Добавить (ICon 3) (IVar m))

Извините, если я здесь тупой, я просто не уверен.