컴파일러에서 변수, 조건문 다루기¶

변수를 다루기 위해서는 기계상태에 메모리를 추가하고 메모리 연산을 위한 저급언어 명령을 추가한다.

조건문을 다루기 위해서는 실행코드를 순차적으로만 실행하는 것이 아니라 특정 코드 위치로 이동하여 실행하는 저급언어 명령을 추가한다.

In [1]:

data Expr = Var Name          -- x
          | Val Value         -- n
          | Add Expr Expr     -- e1 + e2
          -- | Sub Expr Expr
          -- | Mul Expr Expr
          -- | Div Expr Expr
          | If Expr Expr Expr -- if e then e1 else e0
          deriving Show

type Name = String -- 변수의 이름은 문자열로 표현
type Value = Int   -- 상수값은 정수

type Stack = [Value]

data Inst = ADD | PUSH Value      -- 스택 명령
          | GOTO Code | JMPZ Code -- 실행코드 명령
          | READ Addr             -- 메모리 명령
          deriving Show
type Code = [Inst]

-- type Env = [ (Name, Value) ] 라는 인터프리터 실행 환경을
-- 두 단계로 아래와 같이 나눈다
type SymTbl = [ (Name, Addr) ]  -- 컴파일 단계에서 사용하는 심볼 테이블
type Memory = [ (Addr, Value) ] -- 기계(가상머신) 실행 단계에서 사용하는 메모리

type Addr = Int -- 주소는 정수로 표현

-- 이제 Kont는 스택만이 아니라 세 요소로 이루어진 기계상태를 변화시키는 함수 타입이다
type Kont = (Stack,Memory,Code) -> (Stack,Memory,Code)

In [2]:

-- 더 이상 실행할 코드가 없는 기계상태로 변화시키는 함수
haltK :: Kont
haltK (s, mem, _) = (s, mem, [])

-- 스택 명령을 실행시키기 위한 기계상태변화 함수들
pushK :: Int -> Kont
pushK n (s, mem, code) = (n:s, mem, code)

addK :: Kont
addK (n2:n1:s, mem, code) = ((n1+n2):s, mem, code)

-- 실행코드 명령을 실행시키기 위한 기계상태변화 함수들
jmpzK :: Code -> Kont
jmpzK code (0:s, mem, _) = (s, mem, code) -- 스택 맨 위 값이 0이면 새로운 code 위치로 점프
jmpzK _    (_:s, mem, c) = (s, mem, c)    -- 스택 맨 위가 0이 아니면 원래 실행하던 코드 c실행

gotoK :: Code -> Kont
gotoK code (s, mem, _) = (s, mem, code)   -- 무조건 새로운 code 위치로 이동

-- 메모리 명령을 실행시키기 위한 기계상태변화 함수
-- (메모리에서 값을 읽어 스택 맨 위에 쌓는다)
readK a (s, mem, code) = case lookup a mem of
                           Nothing -> error (show a ++ " uninitialized memory address")
                           Just v  -> (v:s, mem, code)

In [3]:

compile :: SymTbl -> Expr -> Code
compile tbl (Var x) = case lookup x tbl of
                        Nothing -> error (x ++ " not found")
                        Just a  -> [READ a]
compile tbl (Val n) = [PUSH n]
compile tbl (Add e1 e2) = compile tbl e1 ++ compile tbl e2 ++ [ADD]
compile tbl (If e e1 e0) =
    compile tbl e ++ [JMPZ c0] ++ c1 ++ [GOTO []] ++ c0
    where
      c1 = compile tbl e1
      c0 = compile tbl e0

step :: Inst -> Kont
step (PUSH n) = pushK n
step ADD      = addK
step (GOTO c) = gotoK c
step (JMPZ c) = jmpzK c
step (READ a) = readK a

run :: Kont
run (s, mem, []) = (s, mem, [])
run (s, mem, c:cs) = run (step c (s, mem, cs))

In [4]:

import Data.List (union)

vars (Var x) = [x]
vars (Val _) = []
vars (Add e1 e2) = vars e1 `union` vars e2
vars (If e e1 e0) = vars e `union` vars e1 `union` vars e0

In [12]:

-- 인터프리터에서는 아래 식을 실행하려면 [("x",2),("y",3)]와 같은
-- 실행환경을 만들어 한방에 실행하면 되지만 컴파일러에는 두 단계
e0 = Add (Add (Var "x") (Var "y")) (Val 100)
e0
-- 컴파일할 때는 변수를 메모리 주소에 대응시키는 심볼테이블이 필요
code0 = compile [("x",102),("y",103)] e0
code0
-- 실행할 때는 해당 주소에 적절한 값을 할당한 메모리가 필요
vm0 = ([], [(102,7), (103,3)], code0)
run vm0

Add (Add (Var "x") (Var "y")) (Val 100)

[READ 102,READ 103,ADD,PUSH 100,ADD]

([110],[(102,7),(103,3)],[])

In [6]:

{- b = 2,  x = 12, y = 123 -}

-- if b then (x + 3) else y
e1 = If (Var "b") (Add (Var "x") (Val 3)) (Var "y")
-- (if b then (x + 3) else y) + 1000
e2 = e1 `Add` Val 1000

In [7]:

tbl0 = [("b",101),("x",102),("y",103)]
tbl0

mem0 = [(101,2), (102,12), (103,123)]
mem0

[("b",101),("x",102),("y",103)]

[(101,2),(102,12),(103,123)]

In [8]:

code1 = compile tbl0 e1
code1

code2 = compile tbl0 e2
code2

{-
import GHC.HeapView

putStr =<< ppHeapGraph <$> buildHeapGraph 15 code2 (asBox code2)
-}

[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103]

[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD]

In [9]:

-- 예상대로 e1의 계산 결과 스택 맨 위에 15가 나온다
run ([], mem0, code1)

-- e2의 계산 결과는 1015이어야 하는데 e1과 마찬가지로 15가 되어버린다
run ([], mem0, code2)

([15],[(101,2),(102,12),(103,123)],[])

([15],[(101,2),(102,12),(103,123)],[])

아래는 e2를 컴파일한 code2를 실행한 결과가 왜 원하는 대로 나오지 않는지 좀더 자세히 살펴보기 위해 step 함수를 한단계씩 호출해 가며 각각의 명령 실행 전후의 기계상태 vm0,...,vm6를 알아본 내용이다.

In [10]:

vm0@(s0,   _,c0:cs0) = ([], mem0, code2)
vm0
vm1@(s1,mem1,c1:cs1) = step c0 (s0,mem0,cs0)
vm1
vm2@(s2,mem2,c2:cs2) = step c1 (s1,mem1,cs1)
vm2
vm3@(s3,mem3,c3:cs3) = step c2 (s2,mem2,cs2)
vm3
vm4@(s4,mem4,c4:cs4) = step c3 (s3,mem3,cs3)
vm4
vm5@(s5,mem5,c5:cs5) = step c4 (s4,mem4,cs4)
vm5
vm6 = step c5 (s5,mem5,cs5)
vm6

([],[(101,2),(102,12),(103,123)],[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])

([2],[(101,2),(102,12),(103,123)],[JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])

([],[(101,2),(102,12),(103,123)],[READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])

([12],[(101,2),(102,12),(103,123)],[PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])

([3,12],[(101,2),(102,12),(103,123)],[ADD,GOTO [],READ 103,PUSH 1000,ADD])

([15],[(101,2),(102,12),(103,123)],[GOTO [],READ 103,PUSH 1000,ADD])

([15],[(101,2),(102,12),(103,123)],[])

HW02-compiler2019fall (10점)¶

지금까지 살펴본 compile 함수의 문제점을 해결하여 제대로 된 컴파일러를 정의하려면 다음과 같은 개념으로 접근하면 된다.

지금 내가 주목해서 컴파일하는 부분의 목적 코드를 생성해서 그 다음에 뒤이어 할 일의 코드 앞에다 이어붙이는 코드변환함수를 만드는 것이 컴파일러다.

그러니까 다음과 같은 타입으로 compile 함수를 재작성해야 한다.

type Control = Code -> Code -- 코드변환함수 타입
compile :: SymTbl -> Expr -> Control

(테스트 코드 작성조건 안내 추가예정)

In [ ]:

과제에 도움이 될만한 내용 (아래에 추가예정)

In [ ]: