이론없이 컴파일러 만들기 꿈파일러 5

자료형 정의

먼저 Token 을 정의한다. str 은 토큰의 내용이고, tokenType 은 분류된 토큰의 종류를 말한다. 그리고 해당 토큰이 몇 번째 라인에서 발견됐는지 알려주는 line 변수. (에러를 표시할 때 유용하게 쓰인다.)

struct Token {
    std::string str;
    TokenType tokenType;
    int line;
    Token(std::string s, TokenType tt, int l = 0) {
        str = s;
        tokenType = tt;
        line = l;
    }
}; 

TokenType 은 다음과 같다. 각종 예약어와 while, for, 지시어등이 담긴다.

enum class TokenType {
    none,
    _var,
    _func,
    integer,
    id,
    assign,
    decassign,
    lbracket,
    rbracket,
    semicolon,
    logical_or,
    logical_and,
    equal,
    not_equal,
    less_than, // <
    less_than_equal, // <=
    greater_than, // >
    greater_than_equal,  // >=
    plus,
    minus,
    mult,
    devide,
    modular,
    lparen,
    rparen,
    comma,
    _if,
    _while,
    _break,
    _continue,
    _return,
    eof
};
struct Token {
    std::string str;
    TokenType tokenType;
    int line;
    Token(std::string s, TokenType tt, int l = 0) {
        str = s;
        tokenType = tt;
        line = l;
    }
}; 
struct BlockInfo {
    std::string sLabel = "SLABEL";
    std::string eLabel = "EkhBEL";
}; 

우리가 작성할 Parser

class KParser {
    public:
        std::vector<std::pair<int, std::string>> m_tree; ///< 
        std::vector<Token> m_tokens; ///< 토큰화된 소스가 담기는 곳
        std::vector<std::vector<std::string>> m_il; ///< 파싱이 진행되면서 중간 생성코드가 여기에 저장된다.
        std::vector<std::string> m_errorMsgs; ///< 파싱이 실패했을 때, 에러메시지가 담긴다.  
        std::map<std::string, int> m_funcToParams; ///< 어떤 함수가 몇 개의 인자가 있는지 
        std::map<std::string, int> m_varToLocal; ///< 어떤 변수가 몇 번째 지역변수인지 저장
        int m_increaseLocals = 0; ///< 함수에서 지역변수가 선언이 될 때 증가함. 새로운 함수 진입시 0 으로 초기화.
        std::map<std::string, int> m_varToArg; ///< 해당 변수가 몇 번째 argument 인지 저장하는 테이블.
        int m_increaseArgs = 0; ///< m_varToArg 보조하기 위한 변수

        int m_parameters = 0;///< m_varToArg 보조하기 위한 변수

        ...

Parser 구현부

int KParser::_root(int begin,  BlockInfo& bi) {
    int i = begin;
    int t = 0;

    while (i < m_tokens.size()) {
        t = _external(i, bi);
        i = t;
        if (t < 0) {
            break;
        }
        i = t;
    }
    return i; 
}
int KParser::_external(int begin,  BlockInfo& bi) { 
    int i = begin;
    int t = 0;

    if (m_tokens[i].tokenType == TokenType::eof) {
        i++;
        return i;
    }

    t = _func(i, bi); 
    if (t >= 0) {
        m_errorMsgs.clear();
        return t;
    }

    t = _var(i, bi); 
    if (t >= 0) {
        return t;
    }
    addErrorString(i, "함수 선언이나 변수 선언이 와야 합니다.");
    return -1;
}
int KParser::_func(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0; 
    if (m_tokens[i].tokenType != TokenType::_func) {
        return -1;
    }
    i++; 
    if (m_tokens[i].tokenType != TokenType::id) {
        addErrorString(i, "func 뒤에는 식별자가 와야합니다.");
        return -1;
    } 
    std::string funcName = m_tokens[i].str;
    m_codes.clear();
    addCode("func", funcName, "");
    i++; 
    m_parameters = 0; 
    t = _parameters(i, bi);
    if (t < 0) {
        addErrorString(i, "함수인자 정의가 잘못 됐습니다.");
        return -1;
    }
    m_funcToParams[funcName] = m_parameters;
    i = t;

    m_locals = 0;
    m_increaseLocals = 0;
    t = _block(i, bi);
    if (t < 0) {
        addErrorString(i, "함수몸체 정의가 잘못 됐습니다.");
        return -1;
    }
    i = t;
    m_codes[0][2] = std::to_string(m_locals); 
    for(auto& i: m_codes) {
        if(m_varToArg.find(i[1]) != m_varToArg.end()) {
            i[2] = std::to_string(m_varToArg[i[1]]);
            i[1] = "argument";
        }
        if(m_varToLocal.find(i[1]) != m_varToLocal.end()) {
            i[2] = std::to_string(m_varToLocal[i[1]]);
            i[1] = "local";
        }
    }

    m_il.insert(m_il.end(), m_codes.begin(), m_codes.end());
    return i;
}
int KParser::_parameters(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;
    if (m_tokens[i].tokenType != TokenType::lparen) {
        addErrorString(i, "( 가 빠졌습니다.");
        return -1;
    }
    i++;

    if (m_tokens[i].tokenType == TokenType::rparen) {
        i++;
        return i;
    }
    // 이 까지 왔으면 매개변수가 하나이상 있는 것이다.
    int idIndex = i;
    if (m_tokens[idIndex].tokenType != TokenType::id) {
        addErrorString(idIndex, "함수 인자에는 식별자가 와야합니다.");
        return -1;
    }
    i++;
    m_varToArg[m_tokens[idIndex].str] = m_parameters;
    m_parameters++;

    while (1) {
        int tryI = i;
        std::string rightValue = m_tokens[tryI].str;
        TokenType tokenValue = m_tokens[tryI].tokenType;
        if(tokenValue != TokenType::comma) {
            break;
        }
        tryI++;
        if (m_tokens[tryI].tokenType != TokenType::id) {
            addErrorString(tryI, ", 뒤에 식별자를 기대했습니다.");
            return -1; 
        }
        m_varToArg[m_tokens[tryI].str] = m_parameters;
        m_parameters++;
        tryI++;
        i = tryI;
    } 
    if (m_tokens[i].tokenType != TokenType::rparen) {
        addErrorString(i, ", 뒤에 식별자를 기대했습니다.");
        return -1;
    }
    i++;
    return i;
}
int KParser::_block(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    if(m_tokens[i].tokenType != TokenType::lbracket) {
        return -1;
    }
    i++;
    while(1) {
        if(m_tokens[i].tokenType == TokenType::rbracket) {
            i++;
            break;
        }
        t = _statement(i, bi);
        if (t < 0) {
            char buf[256];
            sprintf(buf, "line[%d]: 문장이 아닙니다.\n", m_tokens[i].line);
            m_errorMsgs.push_back(buf);
            return -1;
        }
        i = t; 
    }
    return i; 
}
int KParser::_var(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;

    if (m_tokens[i].tokenType != TokenType::_var) {
        return -1;
    }
    i++;

    if (m_tokens[i].tokenType != TokenType::id) {
        char buf[256];
        sprintf(buf, "line[%d]: 식별자가 빠졌습니다.\n", m_tokens[i].line);
        m_errorMsgs.push_back(buf);
        return -1;
    }
    i++;

    if (m_tokens[i].tokenType != TokenType::semicolon) {
        char buf[256];
        sprintf(buf, "line[%d]: ; 가 빠졌습니다.\n", m_tokens[i].line);
        m_errorMsgs.push_back(buf);
        return -1;
    }
    i++;
    return i;
}
int KParser::_statement(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;
    if((t = _if(i, bi)) >= 0) {
        i = t;
    } else if((t = _while(i, bi)) >= 0) {
        i = t;
    }else if((t = _assign(i, bi)) >= 0) {
        i = t;
    } else if((t = _decassign(i, bi)) >= 0) {
        i = t;
    } else if((t = _block(i, bi)) >= 0) {
        i = t;
    } else if((t = _break(i, bi)) >= 0) {
        i = t;
    } else if((t = _continue(i, bi)) >= 0) {
        i = t;
    }else if((t = _simple_expr(i, bi)) >= 0) {
        i = t;
    } else if((t = _return(i, bi)) >= 0) {
        i = t;
    } else {
        return -1;
    }
    return i;
}

int KParser::_call(int begin,  BlockInfo bi) {
    // some();
    // some(a);
    // some(a,b,c);
    int i = begin;
    int t = 0;

    // 인자가 없는 경우 
    if (m_tokens[i].tokenType == TokenType::id && 
        m_tokens[i + 1].tokenType == TokenType::lparen && 
        m_tokens[i + 2].tokenType == TokenType::rparen
        ) {
        addCode("call", m_tokens[i].str,  std::to_string( m_funcToParams[m_tokens[i].str]));
        return i + 3;
    }

    // 인자가 하나이상 있는 경우
    if (m_tokens[i].tokenType == TokenType::id && 
        m_tokens[i + 1].tokenType == TokenType::lparen) {
        i = i + 2;
        // 이 까지 왔으면 매개변수가 하나이상 있는 것이다.
        t = _expr(i, bi);
        if (t < 0) {
            addErrorString(i, "함수 인자에는 표현식이 와야합니다.");
            return -1;
        }
        i = t;

        while (1) {
            int tryI = i;
            std::string rightValue = m_tokens[tryI].str;
            TokenType tokenValue = m_tokens[tryI].tokenType;
            if(tokenValue != TokenType::comma) {
                break;
            }
            tryI++;
            t = _expr(tryI, bi);
            if (t < 0) {
                addErrorString(i, ", 뒤에 표현식을 기대했습니다.");
                return -1; 
            }
            tryI = t;
            i = tryI;
        } 
        if (m_tokens[i].tokenType != TokenType::rparen) {
            addErrorString(i, "_call: ) 가 빠졌습니다.");
            return -1;
        }
        i++;
        addCode("call", m_tokens[begin].str,  std::to_string( m_funcToParams[m_tokens[begin].str]));
        return i;
    }

    return -1; 
}

int KParser::_return(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;

    if (m_tokens[i].tokenType != TokenType::_return) {
        return -1;
    }
    i++;

    if ((t = _expr(i, bi)) < 0) {
        addErrorString(i, "표현식이 와야합니다.");
        return -1;
    } 
    i = t;
    if (m_tokens[i].tokenType != TokenType::semicolon) {
        addErrorString(i, "; 이 와야합니다.");
        return -1;
    }
    i++;
    addCode("return", "", "");
    return i;
}

int KParser::_expr(int begin,  BlockInfo bi) {
    return _adv_expr(begin, bi);
}

int KParser::_simple_expr(int begin,  BlockInfo bi) {
    // <expr>;
    int i = begin;
    int t = 0;
    if ((t = _expr(i, bi)) < 0) {
        return -1;
    }
    i = t;
    if (m_tokens[i].tokenType != TokenType::semicolon) {
        addErrorString(i, "; 이 와야합니다.");
        return -1;
    }
    i++;
    // 대입문이 없으므로 빈 스택을 pop 해준다.
    addCode("pop", "", ""); 
    return i;
}
int KParser::_adv_expr(int begin,  BlockInfo bi) {
    return _or_expr(begin, bi);
}

int KParser::_or_expr(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    std::string leftValue = m_tokens[i].str;
    t = _and_expr(i, bi);
    if (t < 0) {
        return -1;
    }
    i = t;
    while (1) {
        int tryI = i;
        std::string rightValue = m_tokens[tryI].str;
        TokenType tokenValue = m_tokens[tryI].tokenType;
        if(tokenValue != TokenType::logical_or) {
            break;
        }
        tryI++;
        t = _and_expr(tryI, bi);
        if (t < 0) {
            break;
        }
        addCode("or", "", "");
        i = t; 
    } 
    return i;
}

int KParser::_and_expr(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    std::string leftValue = m_tokens[i].str;
    t = _cmp_expr(i, bi);
    if (t < 0) {
        return -1;
    }
    i = t;
    while (1) {
        int tryI = i;
        std::string rightValue = m_tokens[tryI].str;
        TokenType tokenValue = m_tokens[tryI].tokenType;
        if(tokenValue != TokenType::logical_and) {
            break;
        }
        tryI++;
        t = _cmp_expr(tryI, bi);
        if (t < 0) {
            break;
        }
        // bi.addCode(leftValue);
        // bi.addCode(rightValue);
        addCode("and", "", "");
        i = t; 
    } 
    return i;
}

int KParser::_cmp_expr(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    std::string leftValue = m_tokens[i].str;
    t = _add_expr(i, bi);
    if (t < 0) {
        return -1;
    }
    i = t;

    do {
        int tryI = i;
        auto tokenValue = m_tokens[tryI].tokenType;
        if(tokenValue != TokenType::equal 
           && tokenValue != TokenType::not_equal
           && tokenValue != TokenType::less_than
           && tokenValue != TokenType::less_than_equal
           && tokenValue != TokenType::greater_than
           && tokenValue != TokenType::greater_than_equal
           ) {
            break;
        }
        tryI++;
        std::string rightValue = m_tokens[tryI].str;
        t = _add_expr(tryI, bi);
        if (t < 0) {
            break;
        }
        // bi.addCode(leftValue);
        // bi.addCode(rightValue);
        if(tokenValue == TokenType::equal) {
            addCode("eq", "", "");
        } else if(tokenValue == TokenType::not_equal) {
            addCode("neq", "", "");
        }else if(tokenValue == TokenType::less_than) {
            printf("lt!!\n");
            addCode("lt", "", "");
        }else if(tokenValue == TokenType::less_than_equal) {
            printf("lte!!\n");
            addCode("lte", "", "");
        }else if(tokenValue == TokenType::greater_than) {
            addCode("gt", "", "");
        }else if(tokenValue == TokenType::greater_than_equal) {
            addCode("gte", "", "");
        } 
        i = t; 
    } while(0);
    return i;
}
int KParser::_add_expr(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    std::string leftValue = m_tokens[i].str;
    t = _mul_expr(i, bi);
    if (t < 0) {
        return -1;
    }
    i = t;
    while (1) {
        int tryI = i;
        auto tokenValue = m_tokens[tryI].tokenType;
        if(tokenValue != TokenType::plus && tokenValue != TokenType::minus) {
            break;
        }
        tryI++;
        std::string rightValue = m_tokens[tryI].str;
        t = _mul_expr(tryI, bi);
        if (t < 0) {
            break;
        }
        if(tokenValue == TokenType::plus) {
            addCode("add", "", "");
        } else if(tokenValue == TokenType::minus) {
            addCode("sub", "", "");
        }
        i = t; 
    } 
    return i;
}
int KParser::_mul_expr(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    std::string leftValue = m_tokens[i].str;
    t = _sign_expr(i, bi);
    if (t < 0) {
        return -1;
    }
    i = t;
    while (1) {
        int tryI = i;
        auto tokenValue = m_tokens[tryI].tokenType;
        t = _mul_op(tryI, bi);
        if(t < 0) {
            break;
        }
        tryI++;
        std::string rightValue = m_tokens[tryI].str;
        t = _sign_expr(tryI, bi);
        if (t < 0) {
            break;
        }
        if(tokenValue == TokenType::mult) {
            addCode("mult", "", "");
        } else if(tokenValue == TokenType::devide) {
            addCode("div", "", "");
        } else if(tokenValue == TokenType::modular) {
            addCode("mod", "", "");
        }

        i = t; 
    } 
    return i;
}

int KParser::_mul_op(int begin,  BlockInfo bi) {
    int i = begin;
    if (m_tokens[i].tokenType != TokenType::mult && m_tokens[i].tokenType != TokenType::devide && 
        m_tokens[i].tokenType != TokenType::modular) {
        return -1;
    }
    i++;
    return i;
}
int KParser::_sign_expr(int begin,  BlockInfo bi) {
    int i = begin;
    bool isMinus = false;
    if(m_tokens[i].tokenType == TokenType::minus) {
        isMinus = true;
        i++;
    } 
    int t = _factor_expr(i, bi);
    if(t < 0) {
        return -1;
    }
    if (isMinus) {
        addCode("neg", "", "");
    }
    return t;
}

int KParser::_factor_expr(int begin,  BlockInfo bi) {
    int i = begin;
    TokenType tokenType = m_tokens[i].tokenType;
    int t = 0;

    if((t = _call(i, bi)) >= 0) {
        i = t;
    } else if(tokenType == TokenType::id) {
        addCode("push", m_tokens[i].str, "");
        i++;
    } else if(tokenType == TokenType::integer) {
        addCode("push", "constant", m_tokens[i].str);
        i++;
    } else if(tokenType == TokenType::lparen) {
        int tryI = i;
        tryI++;
        int t = _expr(tryI, bi);
        if(t < 0) {
            addErrorString(i, "표현식의 오류.");
            return -1;
        }
        if(m_tokens[t].tokenType != TokenType::rparen) {
            addErrorString(i, "닫는 괄호가 빠졌습니다.\n");
            return -1; 
        }
        t++;
        i = t;
    } 
    else {
        return -1;
    } 
    return i;
}


int KParser::_if(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;
    if( m_tokens[i].tokenType != TokenType::_if ) {
        return -1;
    }
    i++;

    if((t = _expr(i, bi)) < 0) {
        return -1;
    } else {
        i = t;
    } 
    std::string eLabel = "LABEL" + std::to_string(m_labelNumber++);

    addCode("jz", eLabel, "");
    if((t = _block(i, bi)) < 0) {
        return -1;
    } else {
        i = t;
    }
    addCode("label", eLabel, "");
    return i;
}

int KParser::_while(int begin,  BlockInfo bi) {
    int i = begin;
    int t = 0;

    if( m_tokens[i].tokenType != TokenType::_while ) {
        return -1;
    }
    i++; 
    std::string sLabel = "LABEL" + std::to_string(m_labelNumber++);
    std::string eLabel = "LABEL" + std::to_string(m_labelNumber++);
    bi.sLabel = sLabel;
    bi.eLabel = eLabel;
    addCode("label", sLabel, "");
    if((t = _expr(i, bi)) < 0) {
        return -1;
    } else {
        i = t;
    } 
    addCode("jz", eLabel, "");


    if((t = _block(i, bi)) < 0) {
        return -1;
    } else {
        i = t;
    }
    addCode("jmp", sLabel, "");
    addCode("label", eLabel, "");
    return i;
}
int KParser::_break(int begin,  BlockInfo bi) {
    int i = begin;
    int t;

    if (m_tokens[i].tokenType != TokenType::_break) {
        return -1;
    } 
    i++;
    if (m_tokens[i].tokenType != TokenType::semicolon) {
        return -1;
    }
    i++;
    addCode("jmp", bi.eLabel, "");
    return i;
}

int KParser::_continue(int begin,  BlockInfo bi) {
    int i = begin;
    int t;

    if (m_tokens[i].tokenType != TokenType::_continue) {
        return -1;
    } 
    i++;
    if (m_tokens[i].tokenType != TokenType::semicolon) {
        return -1;
    }
    i++;
    addCode("jmp", bi.sLabel, "");
    return i;
}

int KParser::_assign(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    int idIndex = i;
    if (m_tokens[i].tokenType != TokenType::id) {
        return -1;
    } 
    i++; 
    if (m_tokens[i].tokenType != TokenType::assign) {
        return -1;
    } 
    i++; 

    int exprIndex = i;
    t = _expr(i, bi);
    if (t < 0) {
        char buf[256];
        sprintf(buf, "line[%d]: 표현식의 오류\n", m_tokens[i].line); 
        m_errorMsgs.push_back(buf);
        return -1;
    } 
    i = t;

    if (m_tokens[i].tokenType != TokenType::semicolon) {
        char buf[256];
        sprintf(buf, "line[%d]: ; 가 빠졌습니다.\n", m_tokens[i].line); 
        m_errorMsgs.push_back(buf);
        return -1;
    }
    i++;
    addCode("pop", m_tokens[idIndex].str, "");
    return i;
} 

int KParser::_decassign(int begin,  BlockInfo bi) {
    int i = begin;
    int t;
    int idIndex = i;
    if (m_tokens[i].tokenType != TokenType::id) {
        return -1;
    } 
    i++; 
    if (m_tokens[i].tokenType != TokenType::decassign) {
        return -1;
    } 
    i++; 

    int exprIndex = i;
    t = _expr(i, bi);
    if (t < 0) {
        char buf[256];
        sprintf(buf, "line[%d]: decassign 표현식의 오류\n", m_tokens[i].line); 
        m_errorMsgs.push_back(buf);
        return -1;
    } 
    i = t;

    if (m_tokens[i].tokenType != TokenType::semicolon) {
        char buf[256];
        sprintf(buf, "line[%d]: _decassign ; 가 빠졌습니다.\n", m_tokens[i].line); 
        m_errorMsgs.push_back(buf);
        return -1;
    }
    i++;
    m_locals++;
    addCode("pop", m_tokens[idIndex].str, "");
    m_varToLocal[m_tokens[idIndex].str] = m_increaseLocals++;
    printf("%s => %d\n",  m_tokens[idIndex].str.c_str(), m_increaseLocals);
    return i;
}

굉장히 길다. 길기만 길지 어려운 부분은 없다. 앞서 정의한 EBNF 를 그대로 코드로 옮겨논 것에 불과하다. 이 옮기는 과정에서 버그는 나올 수 있고, 내가 작성한 코드 역시 버그가 있을 수 있다. 앞장에서 정의한 EBNF 과 이 코드와 비교하면서 읽어보기를 권한다.

지역변수, 함수인자의 심볼 제거

우리는 가상머신을 정의할 때 segment index 식으로 표기하기로 했다. 즉 가상머신코드로 변환이 될 때 지역변수이름, 함수인자이름 대신에 index 형태로 나타나야한다는 것을 뜻한다. 어떻게 숫자를 부여하며 구현했는지 설명한다.

여기서 가상머신과 결합하는 부분의 포인트만 짚고 넘어간다. _decassign 함수 부분은 지역변수를 선언하는 부분이다. decassign 함수의 m_varToLocal[m_tokens[idIndex].str] = m_increaseLocals++; 를 보면 함수에서 쓰인 지역변수가 몇 번째 지역변수인지 탐색된 순서부터 숫자가 부여된다. 함수 해석이 다 끝날 때 _func 함수의 끝에 보면

for(auto& i: m_codes) {
    if(m_varToArg.find(i[1]) != m_varToArg.end()) {
        i[2] = std::to_string(m_varToArg[i[1]]);
        i[1] = "argument";
    }
    if(m_varToLocal.find(i[1]) != m_varToLocal.end()) {
        i[2] = std::to_string(m_varToLocal[i[1]]);
        i[1] = "local";
    }
}

여기서 push variable_name 와 같은 형식이 push local 0 와 같은 형식으로 바뀌게 된다. 이는 변수 선언할 때 m_varToLocal 로 인해 매겨진 순서에 의해 변환이 된다. local 뿐 아니라 arg 도 마찬가지로 심볼릭에서 인자의 숫자로 변환된다.

함수의 인자의 개수 구하기

가상머신코드를 정의할 때 caller 쪽에서 부르는 함수가 인자가 몇 갠지 알아야 한다고 했다. _func 함수 밑에 parameter 해석하는 부분이 끝난 후 m_funcToParams 테이블에 어떤 함수이름이 몇 개의 인자를 가지는지 m_parameters 로 조사한 후, 테이블에 값을 넣는다.

m_funcToParams[funcName] = m_parameters;

그리고 _call 부분에서 함수이름을 이용하여 바이트코드를 완성시킨다.

가상머신 구현

이상 앞에서 다룬 부분은 구문분석 단계에서 스택기반의 코드를 생성하는 것이 목표였다. 이제 생성된 스택기반의 코드를 실행하는 실행기를 만들어야 한다.

class Vm {
    public:
        static const int STACK_FRAME_SIZE = 3;
        std::vector<std::vector<std::string>> m_program; 
        std::vector<int> m_stack; 
        std::map<std::string, int> m_labelToEip;
        std::map<std::string, int> m_funcToEip;
        int m_eip = 0;
        int m_argPointer = 0;
        int m_localPointer = 0;
        int m_stackPointer = 0;

        ...

vm.h 정의 부분이다. 4장에서 jump label 을 다루는 변수는 m_labelToEip 다. 이 변수는 label 에서 eip 로의 테이블이다. 마찬가지로 m_funcToEip 역시 어떤 함수가 몇 번째 코드에 있는지 나타낸다.

어떻게 테이블을 채우나?

main.cpp:
    kparser.parse();
    Vm vm;
    for(auto i: kparser.m_il) {
        vm.addCommand(i);
    }

vm.h:
    void addCommand(std::vector<std::string> k) {
        if (k[0] == "func") {
            m_funcToEip[k[1]] = m_program.size();
        } else if(k[0] == "label") {
            m_labelToEip[k[1]] = m_program.size();
        }
        m_program.push_back(k);
    }

명령어가 들어오면 현재 m_program.size() 가 하나씩 증가하는데 레이블과 관련된 func, label 키워드가 들어오면 labelToEip 테이블에 값을 넣는다. 추후 call 이나 jump 명령어가 들어오면 이 테이블을 참조하여 eip 를 얻는다.

명령어의 실행

        int step() {
            if (m_program[m_eip].size() && m_eip <= m_program.size() - 1) {
                auto cmd = m_program[m_eip][0]; 
                if (cmd == "neq") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t1 != t2);
                    m_eip++;
                } else if (cmd == "eq") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t1 == t2);
                    m_eip++;
                } 
                else if (cmd == "lt") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 < t1);
                    m_eip++;
                }else if (cmd == "lte") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 <= t1);
                    m_eip++;
                }else if (cmd == "gt") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 > t1);
                    m_eip++;
                }else if (cmd == "gte") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 >= t1);
                    m_eip++;
                } 
                else if (cmd == "add") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t1 + t2);
                    m_eip++;
                } else if (cmd == "sub") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 - t1);
                    m_eip++;
                } else if (cmd == "mult") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 * t1);
                    m_eip++;
                } else if (cmd == "div") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 / t1);
                    m_eip++;
                } else if (cmd == "mod") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 % t1);
                    m_eip++;
                } else if (cmd == "neg") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    m_stack.push_back(-t1);
                    m_eip++;
                } else if (cmd == "and") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 && t1);
                    m_eip++;
                } else if (cmd == "or") {
                    int t1 = getStackTop();
                    m_stack.pop_back();
                    int t2 = getStackTop();
                    m_stack.pop_back(); 
                    m_stack.push_back(t2 || t1);
                    m_eip++;
                }

                else if (cmd == "push") {
                    if (m_program[m_eip].size() < 3) {
                        return -1;
                    } 
                    auto next = m_program[m_eip][1];
                    if (next == "local") {
                        auto pos = std::stoi(m_program[m_eip][2]);
                        m_stack.push_back(m_stack[m_localPointer + pos]);
                    } else if (next == "argument") {
                        auto pos = std::stoi(m_program[m_eip][2]);
                        m_stack.push_back(m_stack[m_argPointer + pos]);
                    } else if (next == "constant") {
                        auto pos = std::stoi(m_program[m_eip][2]);
                        m_stack.push_back(pos);
                    } else {
                        return -1;
                    }
                    m_eip++;
                } else if (cmd == "pop") {
                    if (m_program[m_eip].size() < 3) {
                        m_stack.pop_back();
                    } else {
                        auto next = m_program[m_eip][1];
                        if (next == "local") {
                            auto pos = std::stoi(m_program[m_eip][2]);
                            m_stack[m_localPointer + pos] = getStackTop();
                            m_stack.pop_back();
                        } else if (next == "argument") {
                            auto pos = std::stoi(m_program[m_eip][2]);
                            m_stack[m_argPointer + pos] = getStackTop();
                            m_stack.pop_back();
                        } else if (next == "constant") {
                            // not op
                        } else if (next == "") {
                            m_stack.pop_back(); 
                        } else {
                            return -1;
                        }
                    }
                    m_eip++;
                } 
                else if (cmd == "label") {
                    m_eip++;
                } else if (cmd == "jmp") {
                    auto next = m_program[m_eip][1];
                    m_eip = m_labelToEip[next]; // [next] = m_eip + 1;
                } else if (cmd == "jz") {
                    auto next = m_program[m_eip][1];
                    if (getStackTop() == 0) {
                        m_eip = m_labelToEip[next];
                    } else {
                        m_eip++;
                    }
                    m_stack.pop_back(); 
                } else if (cmd == "jnz") {
                    auto next = m_program[m_eip][1];
                    if (getStackTop() != 0) {
                        m_eip = m_labelToEip[next];
                    } else {
                        m_eip++;
                    }
                    m_stack.pop_back(); 
                } 
                else if (cmd == "call") {
                    // call fn 2
                    if (m_program[m_eip].size() < 3) {
                        std::cout << "<3\n";
                        return -1;
                    }
                    auto fn = m_program[m_eip][1];
                    if(fn == "print") {
                        int t = *m_stack.rbegin();
                        // m_stack.pop_back(); 
                        std::cout << t << "\n"; //  << "built-in-function\n";
                        m_eip++;
                    } else {
                        int argNumber = std::stoi(m_program[m_eip][2]);
                        int oldLocalPointer = m_localPointer;
                        int oldArgPointer = m_argPointer;
                        m_argPointer = m_stack.size() - argNumber;
                        m_stack.push_back(m_eip + 1);
                        m_stack.push_back(oldLocalPointer);
                        m_stack.push_back(oldArgPointer);
                        m_localPointer = m_stack.size();
                        m_eip = m_funcToEip[fn]; 
                    }
                } else if (cmd == "func") {
                    // call fn 2
                    if (m_program[m_eip].size() < 3) {
                        return -1;
                    }
                    auto fn = m_program[m_eip][1];
                    int locals = std::stoi(m_program[m_eip][2]);
                    for(int i=0; i<locals; i++) {
                        m_stack.push_back(0); // 지역변수를 전부 0 으로 초기화 함.
                    }
                    m_eip++;
                } else if (cmd == "return") {
                    int frame = m_localPointer;
                    int ret = m_stack[frame - STACK_FRAME_SIZE]; // 돌아갈 주소
                    m_stack[m_argPointer] = getStackTop();
                    int pops = m_argPointer + 1; // 해당 함수에서 단 하나의 숫자가 남을 때 까지 팝하기 위해서
                    m_argPointer = m_stack[frame - 1];
                    m_localPointer = m_stack[frame - 2];
                    while (m_stack.size() > pops) {
                        m_stack.pop_back();
                    }
                    m_eip = ret; 
                } else if (cmd == "exit") {
                    return -1;
                } 
                return 0;
            } 
            return -1;
        } 

step 함수의 구현부의 일부는 이전장에서 다뤘었다.

push, pop, return, func, call, jnz, jz 부분을 중심으로 테이블 변수가 어떻게 쓰이는지 스택 프레임을 어떻게 구성하는지 주의깊게 보면 좋겠다.

전체 Source

https://github.com/hsnks100/dreampiler

전체 소스는 위 github 에서 배포한다. 테스트코드는 main.cpp 에 하드코딩으로 넣어놨다. 파일로 빼는 것이 좋겠지만, 상용적으로 쓰이는 것이 아닌 학습의 목적이 있기 때문에 따로 테스트코드를 파일로 처리하진 않았다.