homeSoftwaredesign Softwaredesign: Beispiel: Mini-Interpretierer für eine Programmiersprache Prof. Dr. Uwe Schmidt FH Wedel

Beispiel: Mini-Interpretierer für eine Programmiersprache


weiter

Eine Mini-Programmiersprache mit Interpretierer und Beispielprogramm

   1module ProgLang
   2where
   3
   4import Data.Maybe
   5
   6import           Data.Map(Map)
   7import qualified Data.Map as M
   8
   9-- ------------------------------------------------------------
  10--
  11-- the abstract syntax (syntactic domains)
  12
  13data Stmt       = Assign        Ident Expr
  14                | If            Expr Stmt Stmt
  15                | While         Expr Stmt
  16                | StmtList      [Stmt]
  17                  deriving (Show)
  18
  19data Expr       = Const         Value
  20                | Var           Ident
  21                | BinExpr       Op Expr Expr
  22                  deriving (Show)
  23
  24data Op         = Plus
  25                | Minus
  26                | Mult
  27                | Div
  28                | Equal
  29                | NotEqual
  30                | GreaterThan
  31                | GreaterOrEq
  32                  deriving (Eq, Show)
  33
  34type Value      = Int
  35type Ident      = String
  36
  37-- ------------------------------------------------------------
  38--
  39-- semantic domains
  40
  41type State      = Map Ident Value
  42
  43-- ------------------------------------------------------------
  44--
  45-- the statement interpreter
  46
  47interprete      :: Stmt -> State -> State
  48
  49interprete (Assign v e) s
  50    = M.insertWith (\ x y -> x) v val s
  51      where
  52      val = eval e s
  53
  54interprete (If condExpr thenPart elsePart) s
  55    | cond /= 0 = interprete thenPart s
  56    | otherwise = interprete elsePart s
  57    where
  58    cond = eval condExpr s
  59
  60interprete st@(While condExpr body) s
  61    | cond /= 0 = let
  62                  s1 = interprete body s
  63                  in
  64                  interprete st s1
  65    | otherwise = s
  66    where
  67    cond = eval condExpr s
  68
  69interprete (StmtList sl) s
  70    = foldl (flip interprete) s sl
  71
  72-- ------------------------------------------------------------
  73--
  74-- the expression evaluator
  75
  76eval            :: Expr -> State -> Value
  77eval (Const val) s
  78    = val
  79
  80eval (Var v) s
  81    = fromJust . M.lookup v $ s
  82
  83eval (BinExpr op e1 e2) s
  84    = (fromJust . lookup op $ fctMap) val1 val2
  85      where
  86      val1 = eval e1 s
  87      val2 = eval e2 s
  88      fctMap = [ (Plus,         (+)     )
  89               , (Minus,        (-)     )
  90               , (Mult,         (*)     )
  91               , (Div,          div     )
  92               , (Equal,        pred (==))
  93               , (NotEqual,     pred (/=))
  94               , (GreaterThan,  pred (> ))
  95               , (GreaterOrEq,  pred (>=))
  96               ]
  97      pred rel x y
  98          = fromEnum (x `rel` y)
  99
 100-- ------------------------------------------------------------
 101--
 102-- greatest common divisor
 103
 104idx = "x"
 105idy = "y"
 106
 107
 108prog1   :: Stmt
 109prog1
 110    = While
 111      ( BinExpr NotEqual x y )
 112      ( If
 113        ( BinExpr GreaterThan x y )
 114        ( Assign idx (BinExpr Minus x y) )
 115        ( Assign idy (BinExpr Minus y x) )
 116      )
 117    where
 118    x  = Var idx
 119    y  = Var idy
 120
 121state0  :: State
 122state0
 123    = M.fromList [(idx, 18), (idy, 10)]
 124
 125
 126state1 = interprete prog1 state0
 127
weiter

weiter

Ein Testlauf

ghc -e state1 ProgLang
weiter

weiter

Quellen

Download

Letzte Änderung: 24.06.2013
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel