Softwaredesign: Beispiel: Mini-Interpretierer für eine Programmiersprache
| Softwaredesign: Beispiel: Mini-Interpretierer für eine Programmiersprache |
|
|
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
|
|
| Letzte Änderung: 24.06.2013 | © Prof. Dr. Uwe Schmidt |
