경수

제가 접하는 많은 것들을 공유하고 싶습니다.

6 minute read

언어 명세

드디어 우리는 간단한 프로그래밍 언어를 만들 수 있는 능력이 갖춰졌다.

처음에도 말했는데, 우리가 만들 언어에는 타입이 없다. 되게 큰 줄기만 한번 설계해보자.

  • 함수 지원
  • 지역변수 지원
  • 전역변수 지원
  • 재귀호출 지원

위 내용을 스택기반의 가상머신을 하나 설계를 하면서 진행하겠다.

가상머신

우리는 고수준의(high-level) 프로그램을 중간코드로 만들고, 중간코드를 실행하는 프로그램을 만들 건데 ~

기본개념은 플랫폼에서 실행하는것이 아니고 가상머신에서 실행가능한 중간코드를 만드는거다.

가상머신을 구현하는 기본핵심 기준 중 하나는 연산자와 피연산자의 형태는 어떻게 처리 할건지다. 우리는 스택머신모델을 사용한다.

스택머신모델에서는 기본적인 산술명령은 스택의 top 에 있는 숫자를 필요한 만큼 꺼내서 연산후 다시 top 에 넣는다.

스택머신모델에서의 연산의 예

A = 3 * (1 + 2) * 3 - 3 + 1

위 연산은 다음과 같은 스택기반의 명령어로 표현가능하다.

          <--------------------top-----------------------------------
push 3    |  3    |       |            |            |               |
push 1    |  3    |   1   |            |            |               | 
push 2    |  3    |   1   |     2      |            |               |   
plus      |  3    |   3   |            |            |               |  
mult      |  9    |       |            |            |               | 
push 3    |  9    |   3   |            |            |               | 
mult      |  27   |       |            |            |               |   
push 3    |  27   |   3   |            |            |               |  
sub       |  24   |       |            |            |               |       
push 1    |  24   |   1   |            |            |               |      
plus      |  25   |       |            |            |               |     
pop A     |       |       |            |            |               |     
---------------------------------------------------------------------

여기서 pop 명령어는 피연산자의 있는 변수에 스택의 top 을 넣는다.

보다시피 push 와 연산자로 피연산자와 연산자의 개념을 표현할 수 있다.

가상머신의 자세한 명세

자 보자. 프로그래밍언어에는 단순 계산에 대한식말고도 반복문, 함수 표현, 메모리접근과 같은 요소도 있다. 이 명령의 체계를 나눠보자면

  • 산술명령
  • 메모리 접근
  • 프로그램 흐름제어
  • 함수호출 및 정의

산술명령은 위의 예로 충분히 개념은 전달되었다고 생각하는데, 메모리 접근하는 방식에 대해 알아보자.

메모리 접근은 다음과 같은 형식으로 접근한다.

  • push segment index : segment index 값을 스택에 push
  • pop segment index : segment index 에 스택의 top 내용을 저장하면서 pop

segment 의 종류는 argument, local, constant 이것으로만 구현하도록 한다. 각각 인자, 지역변수, 상수를 나타낸다.

실전예를 보는 것이 가장 좋다.

/*
someFunction(int arg0) {
int local0;
local0 = arg0 + 3;
}
*/
push argument 0
push constant 3
add
pop local 0

고급프로그램을 저수준의 스택머신으로 표현한 모습이다. 프로그램 흐름제어도 한번 다뤄보자. 몇가지의 흐름제어를 위해 필요한 명령어를 써보자.

eq: 스택의 위치한 두개의 값이 같으면 0이 아닌 값
neq: 스택의 위치한 두개의 값이 다르면 0이 아닌 값
jmp LABEL: LABEL 위치로 무조건 점프
jnz LABEL: LABEL 위치로 스택의 두값이 0이 아니면 점프 (Jmp if value is Not Zero)
jz LABEL: LABEL 위치로 스택의 두값이 0이면 점프 (Jmp if value is Zero): 
label LABEL_NAME: 프로그램 코드의 위치를 나타내는 지시어

배운게 도둑질이라고 intel x86 기반의 어셈을 따라하게 됐다. MASM 의 지시어도 일부 따라한 부분이다.

먼저 if 문의 스택머신표현을 보자.

ifStatement() {
    a := 5;
    if a == 5 {
        a = a + 1;
    }
}
push constant 5
pop local 0                  // a := 5
push local 0
push constant 5
eq                           // a == 5
jz LABEL555
push local 0
push constant 1 
add
pop local 0                  // a = a + 1
label LABEL555

소스의 의미는 의미가 없지만 if 문을 잘 표현하고 있다. 다음으로 while 문의 표현을 보자. if 와 다른점은 블록끝} 에서 무조건 점프가 들어갔다. 조금만 생각해보면 if 문과 while 문의 한끗차이~

someFunction() {
    a := 5;
    sum := 0;
    while a != 0 {
        sum = sum + a;
    }
}

push constant 5
pop local 0                  // a := 5
push constant 0 
pop local 1                  // sum := 0
label LABEL222 <---------------------------------------------
push local 0                                                |
push constant 0                                             | 
neq                          // a != 0                      |
jz LABEL111     ---------------                             |    
push local 1                  |                             |    
push local 0                  |                             |    
add                           | // sum + a                  |
pop local 0                   | // sum = sum + a            |   
jmp LABEL222    --------------|------------------------------
                              |
label LABEL111  <--------------

본의 아니게 아스키아트

해당 while 문은 영원히 탈출하지 못하는 while 문이지만 while 문이 어떻게 스택머신으로 나타내는지 표현하기에 충분하니 넘어가도록 하자~

다음으로 함수표현을 살펴보자. 되게 중요하게 설계해야 하는 부분이다. 이 부분을 어떻게 하느냐에 따라 언어가 재귀호출을 지원하는지 스코프를 지원하는지 여부가 갈린다.

function functionName nLocals: functionName 은 nLocals 개의 지역변수를 가짐.
call functionName nArgs: nArgs 개의 인자를 받은 함수 호출
return: 함수호출이 일어난 부분의 다음 부분으로 점프

문제를 간단하게 하기 위해 한가지 가정을 하자. 모든 함수는 리턴을 해야 한다.

함수라는 것을 만들기 위해서 어떤것이 필요할까? 일단 먼저 해야할 생각은 함수가 콜됐을 때, 함수는 자기자신이 돌아가야 할 위치를 알 수가 없다. 부르는 쪽에서 돌아갈 주소를 결정해야 한다. 합리적으로 보인다. 함수콜이 끝났을 때에는 돌아간 곳에서는 함수호출하기 위해 준비했던 직전의 스택상태로 돌아가야 한다.

  • 함수를 부르는 쪽, 즉 caller 쪽에서 돌아갈 위치를 정해줘야 한다.
  • 함수콜이 끝났을 때에 직전의 스택상태로 돌아가야 한다.

인자의 위치를 다루기 위한, 지역변수의 위치를 다루기 위한 가상머신 내부의 변수가 필요하다. 보통 cpu 모델에서 이를 담당하는 놈은 register 라고 부른다. 먹은 밥이 인텔 어셈이기 때문에 이 역시 그 컨셉을 최대한 비슷하게 한다. 궁금하신 분들은 EBP 로 검색해보시라.

우리는 EBP 대신에 ArgPointer, LocalPointer 라는 가상머신의 변수(레지스터)를 생각한다. N 번째 인자 argN 과 N 번째 지역변수 localN 에 대해 argN 과 localN 은 각각 stack[ArgPointer + N], stack[LocalPointer + N] 으로 접근할 수 있다. 예를 들어 설명하면,

3 개의 변수를 더해서 리턴하는 함수가 있다고 가정하자 func sum(a, b, c) { return a + b + c;}

a := sum(1, 2, 3) 이 실행이 되었을 때(a 는 첫번 째 지역변수로 가정), CPU 상태와 STACK 의 상태를 그려보면

[     CPU         ]
EIP     |   COMMAND
102     |   push 1
103     |   push 2 
104     |   push 3 
105     |   call sum 3 // 인자가 3개
106     |   pop local 0

[    STACK        ]
SP      |   VALUE
4004    |   1        
4005    |   2    
4006    |   3    
4007    |  106 // 돌아갈 주소
4008    |  PrevLocalPointer   
4009    |  PrevArgPointer

[   REGISTER     ]
LocalPointer = 4010
ArgPointer = 4004

차근차근 설명해보겠다. 먼저 우리의 가상머신은 push 1, push 2, push3 을 수행하면 STACK 의 상태는 4004 부터 4006 까지 1, 2, 3 의 숫자가 들어간다. 이 때 call sum 3 이 실행되면 가상머신은 함수호출을 하기 위한 몇 가지 준비를 한다.

먼저 ArgPointer = 함수에 인자를 넣는 push 가 시작된 위치 (4004)

  • 들어갈 주소
  • 이전 지역변수 포인터
  • 이전 함수 인자 포인터

를 차례대로 스택에 넣는다. 그리고 LocalPointer 를 SP 로 세팅한다. 그 값은 이 예에서는 4010 이 된다. 이 위치 부터 지역변수 개수만큼 스택을 키운다.

가상머신은 return 을 만나면 LocalPointer, ArgPointer 를 복구하고 SP 가 4005 가 될 때 까지 STACK 을 pop 한다.

가상머신 실제 코드

int frame = m_localPointer;
int ret = m_stack[frame - STACK_FRAME_SIZE]; // return address, STACK_FRAME_SIZE: const 3
m_stack[m_argPointer] = getStackTop(); // setting return value
int pops = m_argPointer + 1; // to pop data for m_stack.size() > pops 
m_argPointer = m_stack[frame - 1]; // restore
m_localPointer = m_stack[frame - 2]; // restore
while (m_stack.size() > pops) {
    m_stack.pop_back();
}
m_eip = ret;  // setting return address

다시 쓰는 EBNF

우리가 다룰 가상머신에 대해서는 충분히 설명이 되었다. 이제 상세 EBNF 를 정의하고 이를 구현해야 한다.

EBNF 에 앞서서 전체적인 언어의 구조는 다음과 같다. 프로그램의 시작은 함수 정의로 시작한다. 함수안에서 여러가지 if, while, assign 과 같은 statement 가 이어진다.

external {
    func {
        statement {
            if | while | assign | simple_expr | assign | return | break ...
        }
    }
}

한번 호흡 가다듬고 우리가 만들 언어의 전체 EBNF 를 정리하여 써보면

EBNF 에서는 {}, [], (a|b) 표현이 있다. 각각 0번이상 반복, 생략가능, a or b 양자택일.

<ROOT> ::= {<function>}
<function> ::= "func" <id> <parameters> <block>
<parameters> ::= "(" ")" | "(" <id> {"," <id>}  ")" 
<block> ::= "{" {<statement>} "}"
<statement> ::= <if> | <while> | "break" ";" | "continue" ";" | <assign> | <decassign> | <block> | <simple_expr> | <return>
<if> ::= "if" <expr> <block>
<while> ::= "while" <expr> <block>
<assign> ::= <id> "=" <expr> ";"
<decassign> ::= <id> ":=" <expr> ";"
<simple_expr> ::= <expr> ";"
<return> ::= "return" <expr> ";"
--------------------------------
<expr> ::= <or_expr> {"&&" <or_expr>} <------------------------------------------------------
<or_expr> ::= <and_expr> {"||" <and_expr>}                                                  |
<and_expr> ::= <add_expr> {("==" | "!=" | "<" | ">" | "<=" | ">=") <add_expr>}              |
<add_expr> ::= <mul_expr> {("+" | "-") <mul_expr>}                                          |
<mul_expr> ::= <sign_expr> {("*" | "/") <sign_expr>}                                        |
<sign_expr> ::= ["-"] <factor_expr>                                                         |
<factor_expr> ::= <call> | <id> | <number> | "(" <expr> ")"                     -------------
<call> ::= <id> "(" ")" | <id> "(" <expr> {"," <expr> } ")"

우리는 산업역군의 프로그래머니까 고상한 이론은 집어치우고 빨리 구현체를 보고 싶을 것이다. 말로는 누가 못 짜나.

다음 장에서는 이렇게 정의한 가상머신과 EBNF 에 대해 파서구현에 대해 다뤄보겠다. 분량조절 실패

Updated:

You May Also Enjoy