COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

Code (Week 3)

module Week3 where

import Data.Char
data Token = IntLit Int 
           | LParen 
           | RParen 
           | TimesSign 
           | PlusSign 
           | Unknown 
           deriving (Show)

data Exp = Plus Exp Exp
         | Times Exp Exp
         | Num Int
         deriving (Show)

lexer :: String -> [Token]
lexer (c:cs) | isSpace c = lexer cs 
             | c == '('  = LParen     : lexer cs 
             | c == ')'  = RParen     : lexer cs 
             | c == '*'  = TimesSign  : lexer cs 
             | c == '+'  = PlusSign   : lexer cs 
             | isDigit c = let 
                (digits,rest) = span isDigit (c:cs)
               in IntLit (read digits) : lexer rest 
             | otherwise = Unknown : lexer cs 
lexer [] = []

parseAtom :: [Token] -> (Exp, [Token])
parseAtom (IntLit i : rest) = (Num i, rest)
parseAtom (LParen : rest) = case parseSExp rest of 
    (a, RParen : rest') -> (a, rest')
    _ -> error "Expected )"
parseAtom (c:cs) = error "Unexpected token"

parsePExp :: [Token] -> (Exp, [Token])
parsePExp tokens = case parseAtom tokens of 
    (a, TimesSign : rest) -> case parsePExp rest of 
        (b, rest') -> (Times a b, rest')
    (a, rest) -> (a, rest)      

parseSExp :: [Token] -> (Exp, [Token])
parseSExp tokens = case parsePExp tokens of 
    (a, PlusSign : rest) -> case parseSExp rest of 
        (b, rest') -> (Plus a b, rest')
    (a, rest) -> (a, rest)      

overall :: String -> Exp 
overall string = case parseSExp (lexer string) of 
    (a, []) -> a  
    (a, leftovers) -> error "Leftover tokens!"

prettyPrinter :: Exp -> String 
prettyPrinter (Num n) = show n 
prettyPrinter (Plus a b) = "(" ++ prettyPrinter a ++ 
                           " + " ++ prettyPrinter b ++ ")"
prettyPrinter (Times a b) = "(" ++ prettyPrinter a ++ 
                            " * " ++ prettyPrinter b ++ ")"

Invocations in GHCi should be relatively straightforward.

2018-11-16 Fri 19:37

Announcements RSS