Parsowanie w Haskell dla prostego interpretatora

Question

Jestem względnie nowy w Haskell z głównym tłem programowania pochodzącym z języków OO. Próbuję napisać interpreter z parserem dla prostego języka programowania. Do tej pory mam tłumacza w stanie, z którego jestem dość zadowolony, ale walczę trochę z parserem.

Oto fragment kodu, który mam problemy z

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 

język jest nieco bardziej skomplikowane, ale to wystarczy, aby pokazać mój problem.

Tak więc w typie IntExp ICon jest stałą, a IVar jest zmienną, ale teraz jest problem. To na przykład działa skutecznie

runP parseAdd "5 + 5"

co daje (ADD (ikona 5) (ikona 5)), który jest oczekiwany wynik. Problem pojawia się w przypadku korzystania Ivars zamiast ikon np

runP parseAdd „N + M”

To powoduje, że program do błędu się mówiąc, nie było nieoczekiwane „n”, gdzie spodziewano się cyfrą. To prowadzi mnie do przekonania, że ​​parseIntExp nie działa tak jak zamierzałem. Moją intencją było to, że spróbuje przeanalizować ICon, jeśli to zawiedzie, spróbuj sparsować IVar i tak dalej.

Tak więc albo uważam, że problem istnieje w parseIntExp, albo że brakuje mi czegoś w parsevar i parsecton.

Mam nadzieję, że podałem wystarczająco dużo informacji na temat mojego problemu i byłem wystarczająco jasny.

Dzięki za pomoc, jaką możesz mi dać!

Answer 1

Twój problem jest rzeczywiście w parseICon:

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

many syntezatora mecze zero lub więcej wystąpień, więc to kolejny na "m", dopasowując zera cyfr, a następnie prawdopodobnie umiera kiedy read zawiedzie.

---

A gdy jestem przy nim, ponieważ jesteś nowym Haskell, oto niektóre niechciane rada:

• nie wolno używać fałszywych nawiasów. many (digit) powinien być po prostu many digit. Nawiasy tutaj po prostu grupują rzeczy, nie są konieczne do zastosowania funkcji.

• Nie trzeba wykonywać ICon (read x :: Int). Konstruktor danych ICon może zająć tylko Int, więc kompilator może dowiedzieć się, co masz na myśli sam.

• Nie potrzebujesz try wokół pierwszych dwóch opcji w parseIntExp w obecnym stanie - nie ma danych wejściowych, które spowodowałyby, że jeden z nich zużyje jakieś dane wejściowe zanim ulegnie awarii. Natychmiast zawiedzie (co nie jest konieczne try) lub im się to uda po dopasowaniu pojedynczego znaku.

• Zazwyczaj lepiej jest tokenizować przed analizą. Radzenie sobie z białymi znakami w tym samym czasie, co składnia, to ból głowy.

• W Haskell często używa się operatora ($), aby uniknąć nawiasów. Jest to po prostu aplikacja funkcyjna, ale z bardzo niskim priorytetem, tak że można napisać coś takiego jak many1 (char ' ')many1 $ char ' '.

Również robi tego typu rzeczy jest zbędne i niepotrzebne:

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

Kiedy wszystko robisz jest stosowanie regularnych funkcję do wyniku parsera, można po prostu użyć fmap:

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

To dokładnie to samo. Możesz sprawić, by wyglądało jeszcze ładniej, jeśli zaimportujesz moduł Control.Applicative, który daje wersję operatora fmap o nazwie (<$>), a także inny operator (<*>), który pozwala ci na to samo z funkcjami wielu argumentów. Istnieją również operatory (<*) i (*>), które odrzucają odpowiednio prawa lub lewe wartości, które w tym przypadku umożliwiają parsowanie czegoś podczas odrzucania wyniku, na przykład białych znaków i innych.

Oto lekko zmodyfikowana wersja kodu z niektórych z powyższych sugestii stosowanych i kilka innych drobnych stylistycznych poprawek:

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

Jestem również nowe do Haskell, po prostu zastanawiasz się:

będzie parseIntExp kiedykolwiek zmusić go do parseAdd?

Wygląda na to, że ICon lub IVar zawsze będą analizowane przed osiągnięciem "parseAdd".

np. runP parseIntExp "3 + m"

próbowałby parseICon i odnieść sukces, dając

(ikona 3) zamiast (Add (ikona 3) (Ivar m))

Przepraszam, jeśli mam być Głupi tutaj, jestem po prostu niepewny.