Basheyev 8 авг 2021 в 18:25

Разработка стековой виртуальной машины и компилятора под неё (итог)

16 мин

10K

Технотекст 2021

Для завершения реализации компилятора потребовалось около месяца времени (вечерами), чтобы на практике познакомиться с такими темами как BNF (Backus Naur Form), Abstract Syntax Tree (AST), Symbol Table, способами генерации кода, разработки самого компилятора (front-end, back-end), а также модификации виртуальной машины CVM. Ранее с этими темами был не знаком, но благодаря комментаторам погрузился. Хоть затрагиваемых тем много, постараюсь рассказать очень лаконично. Но обо всём по порядку. Если вы не читали предыдущих частей, вот ссылки:

Разработка стековой виртуальной машины и компилятора под неё (часть I)

Разработка стековой виртуальной машины и компилятора под неё (часть II)

Разработка стековой виртуальной машины и компилятора под неё (часть III)

1. Описание грамматики Си подобного языка

Действительно, как отметили комментаторы, начинать писать компилятор не выписав формальные грамматики (BNF/EBNF) - прям очень плохая идея. Тупик гарантирован. Потому сначала описал грамматику своего упрощенного Си подобного языка.

Вкратце: он будет уметь функции, один тип данных - int, без глобальных переменных, структур данных и классов, указателей и ссылок (строк и массивов, соответственно), но уметь рекурсию. Такие ограничения связаны с тем, чтобы разобраться в базовых механизмах компиляции, так как дальнейшее расширение его возможностей хоть и не тривиально, но более менее понятно. Итак, грамматика языка следующая (EBNF):

<module>      ::= {<function>}*
<type>        ::= 'int'
<function>    ::= <type> <identifier> '(' <argument> {, <argument>}* ')' <block>
<argument>    ::= <type> <identifier>
<statement>   ::= <block> | <declaration> | <assign> | <if-else> | <while> | <jump> | <call>
<declaration> ::= <type> <identifier> {','<identifier>}* ';'
<block>       ::= '{' {<statement>}* '}'
<call>        ::= <identifier> '(' {<expression>} {, expression}* ')'
<if-else>     ::= 'if' '(' <condition> ')' <statement> { 'else' <statement> }
<while>       ::= 'while' '(' <condition> ')' <statement>
<jump>        ::= 'return' <expression> ';' | 'break' ';'
<assign>      ::= <identifier> = <expression> ';'
<logical>     ::= <comparison> {( && | '||') <comparison>}
<comparison>  ::= <expression> {( == | != | > | >= | < | <= ) <expression>}
<expression>  ::= <term> {(+|-) <term>}
<term>        ::= <bitwise> {(*|/) <bitwise>}
<bitwise>     ::= <factor> {( & | '|' | ^ | << | >> ) <factor>}
<factor>      ::= ({~|!|-|+} <number>) | <identifer> | <call>

По ходу изучения вопроса, заметил, что ещё более наглядно и удобно при разработке компилятора помогает вот такая графическая нотация (название нотации не знаю):

Сначала мы разделим входящий исходный код на последовательность лексем (tokens), о чем было рассказано ранее в предыдущей части II (вот тут). Затем, используя описанные выше грамматики из последовательности лексем построим абстрактное синтаксическое дерево (AST) и таблицу символов, чтобы упростить генерацию кода.

2. Абстрактное синтаксическое дерево (AST)

Если вкратце, то Abstract Syntax Tree (AST) - это ориентированное дерево, в котором внутренние вершины являются операторами, а листья — с соответствующими операндами. Это то, во что надо "перевести" последовательность лексем, чтобы дальнейшая генерация кода не представляло сложности. Для примера, Abstract Syntax Tree может выглядеть так, как на приведенной ниже схеме:

Чтобы сформировать такое дерево, мне потребовался класс, который описывал бы структуру данных - узел синтаксического дерева, с указателем на родителя и дочерние элементы, типом узла и соответствующими методами:

//------------------------------------------------------------------------
// Abstract Syntax Tree Node
//------------------------------------------------------------------------

enum class TreeNodeType {
    UNKNOWN = 0, MODULE, CONSTANT, TYPE, SYMBOL, UNARY_OP, BINARY_OP, CALL,
    FUNCTION, BLOCK, ASSIGNMENT, IF_ELSE, WHILE, RETURN, BREAK
};

constexpr char* const TREE_NODE_TYPE_MNEMONIC[] = {
    "UNKNOWN", "MODULE", "CONSTANT", "TYPE", "SYMBOL", "UNARY_OP", "BINARY_OP", "CALL",
    "FUNCTION", "BLOCK", "ASSIGNMENT", "IF_ELSE", "WHILE", "RETURN", "BREAK"
};

class TreeNode {
    public:
        TreeNode(Token token, TreeNodeType type, SymbolTable* scope);
        ~TreeNode();
        TreeNode* addChild(TreeNode* node);
        bool removeChild(TreeNode* node);
        void removeAll();
        TreeNodeType getType();
        Token getToken();
        TreeNode* getParent();
        TreeNode* getChild(size_t index);
        size_t getChildCount();
        size_t getDepth();
        void print();
        inline void setSymbolTable(SymbolTable* scope) { symbols = scope; }
        inline SymbolTable* getSymbolTable() { return symbols; }
    private:
        Token token;
        SymbolTable* symbols = NULL;
        vector<TreeNode*> childs;
        TreeNode* parent;
        TreeNodeType type;
        void print(int tab);
};

Исходный код: https://github.com/Basheyev/CVM/blob/master/src/compiler/TreeNode.cpp

3. Таблица символов (Symbol Tree)

Наряду, с синтаксическим деревом потребуется структура данных, называемая Таблицей символов. Таблица символов (Symbol Table) - это древовидная структура данных в которой содержится объявленные функции, переменные, аргументы, их типы, адреса, а также области видимости. Она позволяет выявлять обращение к не объявленным идентификаторам, дублирующиеся объявления, контролировать область видимости в выражениях и многое другое. Лучше понять как она устроена можно на приведенном ниже примере.

Допустим, у нас есть вот такой исходный код:

void pro_one()
{
   int one_1;
   int one_2;
   {                 \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
   }                 /
   int one_5; 
   {                 \   
      int one_6;      |_  inner scope 2
      int one_7;      |
   }                 /
}

void pro_two()
{
   int two_1;
   int two_2;
   {                 \
      int two_3;      |_  inner scope 3
      int two_4;      |
   }                 /
   int two_5;
}

По этому исходному коду должно быть сформировано следующее дерево Таблиц символов, чтобы мы легко могли определять область видимости символов:

Чтобы реализовать дерево таблиц, опишем структуру данных SymbolTable и методы работы с ней. Например, добавлять символы указывая тип, искать символы как в самой таблице, так и в её родительских узлах вплоть до корня. Вот описание:

//------------------------------------------------------------------------
// Symbol table
//------------------------------------------------------------------------
enum class SymbolType {
    UNKNOWN, CONSTANT, FUNCTION, ARGUMENT, VARIABLE
};

constexpr char* const  SYMBOL_TYPE_MNEMONIC[] = {
    "UNKNOWN", "CONSTANT", "FUNCTION", "ARGUMENT", "VARIABLE"
};

class Symbol {
    public:
        string name = "";
        SymbolType type = SymbolType::UNKNOWN;
        WORD localIndex = -1;
        WORD address = -1;
        WORD argCount = 0;
};

class SymbolTable {
    public:
        SymbolTable(string name = "GLOBAL");
        ~SymbolTable();
        bool addChild(SymbolTable* child);
        void removeChild(SymbolTable* child);
        SymbolTable* getChildAt(size_t index);
        size_t getChildCount();
        inline const char* getName() { return name.c_str(); };
        void clearSymbols();
        size_t getSymbolsCount();
        bool addSymbol(Token& token, SymbolType type);
        Symbol* lookupSymbol(Token& token);
        Symbol* lookupSymbol(char* name, SymbolType type);
        Symbol* getSymbolAt(size_t index);
        void printSymbols();
    private:
        string name;
        vector<Symbol> symbols;
        vector<SymbolTable*> childs;
        SymbolTable* parent;
        int getNextIndex(SymbolType type);
        void printRecursive(int depth);
};

Исходный код: https://github.com/Basheyev/CVM/blob/master/src/compiler/SymbolTable.cpp

4. Parser - строитель AST и таблиц символов

Теперь, имея на руках формально описанные грамматики языка, структуры данных для хранения абстрактного синтаксического дерева (AST) и дерева таблиц символов (Symbol Table), можно реализовать Parser, который на вход будет получать исходный код, а на выходе давать построенное синтаксическое дерево и таблицы символов. Примечание: в данном конкретном случае, Lexer и Parser - два в одном.

//------------------------------------------------------------------------
// Syntax Parser (Abstract Syntax Tree Builder)
//------------------------------------------------------------------------
class SourceParser {
    public:
        SourceParser(const char* sourceCode);
        ~SourceParser();
        inline size_t getTokenCount() { return tokens.size(); }
        Token& getToken(size_t index) { return tokens[index]; }
        SymbolTable& getSymbolTable() { return rootSymbolTable; }
        TreeNode* getSyntaxTree() { return root; }
    private:
        vector<Token> tokens;
        TreeNode* root = NULL;
        SymbolTable rootSymbolTable;
        size_t currentToken = 0;
        int blockCounter = 0;

        void parseToTokens(const char* sourceCode);
        bool isBlank(char value) { return strchr(BLANKS, value) != NULL; };
        bool isDelimeter(char value) { return strchr(DELIMETERS, value) != NULL; };
        bool pushToken(char* text, int length, int row, int col);
        TokenType getTokenType(char* text, int length);
        TokenType validateNumber(char* text, int length);
        TokenType validateIdentifier(char* text, int length);
        TokenType validateString(char* text, int length);

        void buildSyntaxTree();
        TreeNode* parseModule(SymbolTable* scope);
        TreeNode* parseDeclaration(SymbolTable* scope);
        TreeNode* parseFunction(SymbolTable* scope);
        TreeNode* parseArgument(SymbolTable* scope);
        TreeNode* parseBlock(SymbolTable* scope, bool isFunction, bool whileBlock);
        TreeNode* parseStatement(SymbolTable* scope, bool whileBlock);
        TreeNode* parseCall(SymbolTable* scope);
        TreeNode* parseIfElse(SymbolTable* scope, bool whileBlock);
        TreeNode* parseWhile(SymbolTable* scope);
        TreeNode* parseAssignment(SymbolTable* scope);
        TreeNode* parseLogical(SymbolTable* scope);
        TreeNode* parseComparison(SymbolTable* scope);
        TreeNode* parseExpression(SymbolTable* scope);
        TreeNode* parseTerm(SymbolTable* scope);
        TreeNode* parseBitwise(SymbolTable* scope);
        TreeNode* parseFactor(SymbolTable* scope);

        inline bool next() { currentToken++; return currentToken < getTokenCount(); }
        inline Token getToken() { return getToken(currentToken); }
        inline Token getNextToken() { return getToken(currentToken + 1); }
        inline bool isTokenType(TokenType type) { return getToken().type == type; }

        inline bool isComparison(TokenType type) { return type >= TokenType::EQUAL && type <= TokenType::LS_EQUAL; }
        inline bool isLogical(TokenType type) { return type >= TokenType::LOGIC_AND && type <= TokenType::LOGIC_OR; }
        inline bool isBitwise(TokenType type) { return type >= TokenType::AND && type <= TokenType::SHR; }
        inline bool isDataType(TokenType type) { return type == TokenType::INT; }
        inline void checkToken(TokenType type, const char* msg) { if (!isTokenType(type)) raiseError(msg); }
        inline void raiseError(Token& tkn, const char* msg) { throw ParserException{ tkn, msg }; }
        inline void raiseError(const char* msg) { throw ParserException{ getToken(), msg }; }
};

Исходный код: https://github.com/Basheyev/CVM/blob/master/src/compiler/SourceParser.cpp

Теперь можно переходить к кульминации - генерации кода.

4. Генерация кода

Теперь, имея построенное AST и таблицу символов, мы можем начать генерировать код, последовательно обходя AST. По ходу генерации кода функций, мы также будем заполняем глобальную таблицу символов указывая фактические адреса функций, чтобы при вызовах могли их найти и указывать:

class CodeGenerator {
    public:
        CodeGenerator();
        ~CodeGenerator();
        bool generateCode(ExecutableImage* img, TreeNode* rootNode);
        void emitModule(ExecutableImage* img, TreeNode* rootNode);
        void emitFunction(ExecutableImage* img, TreeNode* node);
        void emitStatement(ExecutableImage* img, TreeNode* body);
        void emitBlock(ExecutableImage* img, TreeNode* body);
        void emitDeclaration(ExecutableImage* img, TreeNode* node);
        void emitCall(ExecutableImage* img, TreeNode* node);
        void emitIfElse(ExecutableImage* img, TreeNode* node);
        void emitWhile(ExecutableImage* img, TreeNode* node);
        void emitReturn(ExecutableImage* img, TreeNode* node);
        void emitBreak(ExecutableImage* img, TreeNode* node);
        void emitAssignment(ExecutableImage* img, TreeNode* assignment);
        void emitExpression(ExecutableImage* img, TreeNode* expression);
        void emitSymbol(ExecutableImage* img, TreeNode* node);
        WORD emitOpcode(ExecutableImage* img, Token& token);
    private:
        inline void raiseError(char* msg) { throw CodeGeneratorException{msg }; }
};

Вот несколько отрывков исходников по генерации кода блока, IF-ELSE и операторов:


void CodeGenerator::emitBlock(ExecutableImage* img, TreeNode* body) {
    size_t count = body->getChildCount();
    TreeNode* statement;
    for (int j = 0; j < count; j++) {
        statement = body->getChild(j);
        emitStatement(img, statement);
    }
}

void CodeGenerator::emitStatement(ExecutableImage* img, TreeNode* statement) {
    switch (statement->getType()) {
    case TreeNodeType::TYPE:       break; // skip because already emitted
    case TreeNodeType::ASSIGNMENT: emitAssignment(img, statement); break;
    case TreeNodeType::IF_ELSE:    emitIfElse(img, statement); break;
    case TreeNodeType::WHILE:      emitWhile(img, statement); break;
    case TreeNodeType::CALL:       emitCall(img, statement); break;
    case TreeNodeType::BLOCK:      emitBlock(img, statement); break;
    case TreeNodeType::RETURN:     emitReturn(img, statement); break;
    case TreeNodeType::BREAK:      emitBreak(img, statement); break;
    default: raiseError("Unknown structure in syntax tree.");
    }
}


void CodeGenerator::emitIfElse(ExecutableImage* img, TreeNode* node) {
    TreeNode* condition = node->getChild(0);
    TreeNode* thenBlock = node->getChild(1);
    TreeNode* elseBlock = node->getChild(2);
    ExecutableImage conditionCode, thenCode, elseCode;
    WORD offset;
    
    emitExpression(&conditionCode, condition);          // generate condition code
    emitStatement(&thenCode, thenBlock);                // generate then block code
    if (elseBlock) {                                    // if there is else block
        emitStatement(&elseCode, elseBlock);            // generate else block code
    }

    // IF: emit conditional jump code
    offset = thenCode.getSize() + 1;                    // calculate next address after then block 
    if (elseBlock) offset += JUMP_OFFSET;               // if there is an else block add JMP offset
    img->emit(conditionCode);
    img->emit(OP_IFZERO, offset);                      

    // THEN: emit then block code
    img->emit(thenCode);
    if (elseBlock) {                                    // if there is an else block
        offset = elseCode.getSize() + 1;                // calculate next address after else block
        img->emit(OP_JMP, offset);                      // emit unconditional jump over else block
    }

    // ELSE: emit else block code
    if (elseBlock) img->emit(elseCode);

}

...

WORD CodeGenerator::emitOpcode(ExecutableImage* img, Token& token) {
    switch (token.type) {
    case TokenType::PLUS:      img->emit(OP_ADD);     break;
    case TokenType::MINUS:     img->emit(OP_SUB);     break;
    case TokenType::MULTIPLY:  img->emit(OP_MUL);     break;
    case TokenType::DIVIDE:    img->emit(OP_DIV);     break;
    case TokenType::EQUAL:     img->emit(OP_EQUAL);   break;
    case TokenType::NOT_EQUAL: img->emit(OP_NEQUAL);  break;
    case TokenType::GREATER:   img->emit(OP_GREATER); break;
    case TokenType::GR_EQUAL:  img->emit(OP_GREQUAL); break;
    case TokenType::LESS:      img->emit(OP_LESS);    break;
    case TokenType::LS_EQUAL:  img->emit(OP_LSEQUAL); break;
    case TokenType::LOGIC_AND: img->emit(OP_LAND);    break;
    case TokenType::LOGIC_OR:  img->emit(OP_LOR);     break;
    case TokenType::LOGIC_NOT: img->emit(OP_LNOT);    break;
    case TokenType::NOT:       img->emit(OP_NOT);     break;
    case TokenType::AND:       img->emit(OP_AND);     break;
    case TokenType::OR:        img->emit(OP_OR);      break;
    case TokenType::XOR:       img->emit(OP_XOR);     break;
    case TokenType::SHL:       img->emit(OP_SHL);     break;
    case TokenType::SHR:       img->emit(OP_SHR);     break;
    default:
        cout << "UNKNOWN OPERATION: ";
        cout.write(token.text, token.length);
        cout << endl;
        break;
    }
    return 0;
}

Наряду с пользовательскими функциями в исходном коде скрипта, для ввода и вывода целых чисел в консоли, добавил в компилятор "системные" функции iput (integer put) и iget (integer get). А именно при генерации кода они автоматически добавляются в глобальную таблицу символов и при генерации автоматически заменяются на системный вызов виртуальной машины syscall.

Исходный код: https://github.com/Basheyev/CVM/blob/master/src/compiler/CodeGenerator.cpp

5. Испытание компилятора: факториал

Вычисление факториала на C подобном языке (скрипт factorial.cvm). В коде есть лишние конструкции для проверки их работы (if-else, break):

int fact(int n) {
   int x;
   if (n) {
      x = n * fact(n-1);
      return x;
   } else {
      x = 10;
      return 1;
   }
   return 0;
}


int main() {
    int n, i;
    i = 1;
    while (i<=100) {
        if (i<12) {
            n = fact(i);
            iput(n);
            i = i + 1;
        } else break;
    }
	return n;
}

В результате работы парсера построено следующее дерево:

-----------------------------------------------------
Parsed abstract syntax tree
-----------------------------------------------------
''(MODULE) GLOBAL
|-'fact'(FUNCTION) GLOBAL
| |-'int'(TYPE) GLOBAL
| |-''(SYMBOL) fact
| | |-'int'(TYPE) fact
| | | |-'n'(SYMBOL) fact
| |-'BLOCK'(BLOCK) fact
| | |-'int'(TYPE) fact
| | | |-'x'(SYMBOL) fact
| | |-'if'(IF_ELSE) fact
| | | |-'n'(SYMBOL) fact
| | | |-'BLOCK'(BLOCK) block0
| | | | |-'='(ASSIGNMENT) block0
| | | | | |-'x'(SYMBOL) block0
| | | | | |-'*'(BINARY_OP) block0
| | | | | | |-'n'(SYMBOL) block0
| | | | | | |-'fact'(CALL) block0
| | | | | | | |-'-'(BINARY_OP) block0
| | | | | | | | |-'n'(SYMBOL) block0
| | | | | | | | |-'1'(CONSTANT) block0
| | | | |-'return'(RETURN) block0
| | | | | |-'x'(SYMBOL) block0
| | | |-'BLOCK'(BLOCK) block1
| | | | |-'='(ASSIGNMENT) block1
| | | | | |-'x'(SYMBOL) block1
| | | | | |-'10'(CONSTANT) block1
| | | | |-'return'(RETURN) block1
| | | | | |-'1'(CONSTANT) block1
| | |-'return'(RETURN) fact
| | | |-'0'(CONSTANT) fact
|-'main'(FUNCTION) GLOBAL
| |-'int'(TYPE) GLOBAL
| |-''(SYMBOL) main
| |-'BLOCK'(BLOCK) main
| | |-'int'(TYPE) main
| | | |-'n'(SYMBOL) main
| | | |-'i'(SYMBOL) main
| | |-'='(ASSIGNMENT) main
| | | |-'i'(SYMBOL) main
| | | |-'1'(CONSTANT) main
| | |-'while'(WHILE) main
| | | |-'<='(BINARY_OP) main
| | | | |-'i'(SYMBOL) main
| | | | |-'100'(CONSTANT) main
| | | |-'BLOCK'(BLOCK) block2
| | | | |-'if'(IF_ELSE) block2
| | | | | |-'<'(BINARY_OP) block2
| | | | | | |-'i'(SYMBOL) block2
| | | | | | |-'12'(CONSTANT) block2
| | | | | |-'BLOCK'(BLOCK) block3
| | | | | | |-'='(ASSIGNMENT) block3
| | | | | | | |-'n'(SYMBOL) block3
| | | | | | | |-'fact'(CALL) block3
| | | | | | | | |-'i'(SYMBOL) block3
| | | | | | |-'iput'(CALL) block3
| | | | | | | |-'n'(SYMBOL) block3
| | | | | | |-'='(ASSIGNMENT) block3
| | | | | | | |-'i'(SYMBOL) block3
| | | | | | | |-'+'(BINARY_OP) block3
| | | | | | | | |-'i'(SYMBOL) block3
| | | | | | | | |-'1'(CONSTANT) block3
| | | | | |-'break'(BREAK) block2
| | |-'return'(RETURN) main
| | | |-'n'(SYMBOL) main

Следующие таблицы символов:

-----------------------------------------------------
Symbol table
-----------------------------------------------------
GLOBAL:
iput    FUNCTION at [0] args=1
iget    FUNCTION at [0] args=1
fact    FUNCTION at [4] args=1
main    FUNCTION at [38] args=0
        fact:
        n       ARGUMENT #0
        x       VARIABLE #0
                block0:
                block1:
        main:
        n       VARIABLE #0
        i       VARIABLE #1
                block2:
                        block3:

И сгенерирован код для виртуальной машины:

-----------------------------------------------------
Virtual machine executable image disassembly
-----------------------------------------------------
[     0]    call    [38], 0
[     3]    ---- halt ----
[     4]    iconst  0
[     6]    iarg    #0
[     8]    ifzero  [+19]
[    10]    iarg    #0
[    12]    iarg    #0
[    14]    iconst  1
[    16]    isub
[    17]    call    [4], 1
[    20]    imul
[    21]    istore  #0
[    23]    iload   #0
[    25]    ret
[    26]    jmp     [+8]
[    28]    iconst  10
[    30]    istore  #0
[    32]    iconst  1
[    34]    ret
[    35]    iconst  0
[    37]    ret
[    38]    iconst  0
[    40]    iconst  0
[    42]    iconst  1
[    44]    istore  #1
[    46]    iload   #1
[    48]    iconst  100
[    50]    lsequal
[    51]    ifzero  [+32]
[    53]    iload   #1
[    55]    iconst  12
[    57]    less
[    58]    ifzero  [+21]
[    60]    iload   #1
[    62]    call    [4], 1
[    65]    istore  #0
[    67]    iload   #0
[    69]    syscall 0x21
[    71]    iload   #1
[    73]    iconst  1
[    75]    iadd
[    76]    istore  #1
[    78]    jmp     [+3]
[    80]    jmp     [+3]
[    82]    jmp     [-37]
[    84]    iload   #0
[    86]    ret

Результат исполнения скрипта выдаёт:

-----------------------------------------------------
Virtual machine runtime
-----------------------------------------------------
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
VM: IP=4 FP=16383 LP=16382 SP=16382 STACK=[39916800] -> TOP
Execution time: 0.0037108s

6. Испытание компилятора: простые числа

Компиляция скрипта вычисления простых чисел (primenumber.cvm):

int isPrime(int n) {
   int i,a,b;
   i = 2;
   while (i < n) {
      a = n / i;
      b = a * i;
      if (b == n) return 0;
      i = i + 1;
   }
   return 1;
}


int main() { 
    int j;
    j = 2;
    while (j < 100) {
       if (isPrime(j)) iput(j);
       j = j + 1;
    }

    return 0;
}

строит следующее дерево:

-----------------------------------------------------
Parsed abstract syntax tree
-----------------------------------------------------
''(MODULE) GLOBAL
|-'isPrime'(FUNCTION) GLOBAL
| |-'int'(TYPE) GLOBAL
| |-''(SYMBOL) isPrime
| | |-'int'(TYPE) isPrime
| | | |-'n'(SYMBOL) isPrime
| |-'BLOCK'(BLOCK) isPrime
| | |-'int'(TYPE) isPrime
| | | |-'i'(SYMBOL) isPrime
| | | |-'a'(SYMBOL) isPrime
| | | |-'b'(SYMBOL) isPrime
| | |-'='(ASSIGNMENT) isPrime
| | | |-'i'(SYMBOL) isPrime
| | | |-'2'(CONSTANT) isPrime
| | |-'while'(WHILE) isPrime
| | | |-'<'(BINARY_OP) isPrime
| | | | |-'i'(SYMBOL) isPrime
| | | | |-'n'(SYMBOL) isPrime
| | | |-'BLOCK'(BLOCK) block0
| | | | |-'='(ASSIGNMENT) block0
| | | | | |-'a'(SYMBOL) block0
| | | | | |-'/'(BINARY_OP) block0
| | | | | | |-'n'(SYMBOL) block0
| | | | | | |-'i'(SYMBOL) block0
| | | | |-'='(ASSIGNMENT) block0
| | | | | |-'b'(SYMBOL) block0
| | | | | |-'*'(BINARY_OP) block0
| | | | | | |-'a'(SYMBOL) block0
| | | | | | |-'i'(SYMBOL) block0
| | | | |-'if'(IF_ELSE) block0
| | | | | |-'=='(BINARY_OP) block0
| | | | | | |-'b'(SYMBOL) block0
| | | | | | |-'n'(SYMBOL) block0
| | | | | |-'return'(RETURN) block0
| | | | | | |-'0'(CONSTANT) block0
| | | | |-'='(ASSIGNMENT) block0
| | | | | |-'i'(SYMBOL) block0
| | | | | |-'+'(BINARY_OP) block0
| | | | | | |-'i'(SYMBOL) block0
| | | | | | |-'1'(CONSTANT) block0
| | |-'return'(RETURN) isPrime
| | | |-'1'(CONSTANT) isPrime
|-'main'(FUNCTION) GLOBAL
| |-'int'(TYPE) GLOBAL
| |-''(SYMBOL) main
| |-'BLOCK'(BLOCK) main
| | |-'int'(TYPE) main
| | | |-'j'(SYMBOL) main
| | |-'='(ASSIGNMENT) main
| | | |-'j'(SYMBOL) main
| | | |-'2'(CONSTANT) main
| | |-'while'(WHILE) main
| | | |-'<'(BINARY_OP) main
| | | | |-'j'(SYMBOL) main
| | | | |-'100'(CONSTANT) main
| | | |-'BLOCK'(BLOCK) block1
| | | | |-'if'(IF_ELSE) block1
| | | | | |-'isPrime'(CALL) block1
| | | | | | |-'j'(SYMBOL) block1
| | | | | |-'iput'(CALL) block1
| | | | | | |-'j'(SYMBOL) block1
| | | | |-'='(ASSIGNMENT) block1
| | | | | |-'j'(SYMBOL) block1
| | | | | |-'+'(BINARY_OP) block1
| | | | | | |-'j'(SYMBOL) block1
| | | | | | |-'1'(CONSTANT) block1
| | |-'return'(RETURN) main
| | | |-'0'(CONSTANT) main

и таблицу символов:

-----------------------------------------------------
Symbol table
-----------------------------------------------------
GLOBAL:
iput    FUNCTION at [0] args=1
iget    FUNCTION at [0] args=1
isPrime FUNCTION at [4] args=1
main    FUNCTION at [57] args=0
        isPrime:
        n       ARGUMENT #0
        i       VARIABLE #0
        a       VARIABLE #1
        b       VARIABLE #2
                block0:
        main:
        j       VARIABLE #0
                block1:

Получаем такой сгенерированный код виртуальной машины:

-----------------------------------------------------
Virtual machine executable image disassembly
-----------------------------------------------------
[     0]    call    [57], 0
[     3]    ---- halt ----
[     4]    iconst  0
[     6]    iconst  0
[     8]    iconst  0
[    10]    iconst  2
[    12]    istore  #0
[    14]    iload   #0
[    16]    iarg    #0
[    18]    less
[    19]    ifzero  [+34]
[    21]    iarg    #0
[    23]    iload   #0
[    25]    idiv
[    26]    istore  #1
[    28]    iload   #1
[    30]    iload   #0
[    32]    imul
[    33]    istore  #2
[    35]    iload   #2
[    37]    iarg    #0
[    39]    equal
[    40]    ifzero  [+4]
[    42]    iconst  0
[    44]    ret
[    45]    iload   #0
[    47]    iconst  1
[    49]    iadd
[    50]    istore  #0
[    52]    jmp     [-39]
[    54]    iconst  1
[    56]    ret
[    57]    iconst  0
[    59]    iconst  2
[    61]    istore  #0
[    63]    iload   #0
[    65]    iconst  100
[    67]    less
[    68]    ifzero  [+21]
[    70]    iload   #0
[    72]    call    [4], 1
[    75]    ifzero  [+5]
[    77]    iload   #0
[    79]    syscall 0x21
[    81]    iload   #0
[    83]    iconst  1
[    85]    iadd
[    86]    istore  #0
[    88]    jmp     [-26]
[    90]    iconst  0
[    92]    ret

и результат исполнения (верный):

-----------------------------------------------------
Virtual machine runtime
-----------------------------------------------------
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
VM: IP=4 FP=16383 LP=16382 SP=16382 STACK=[0] -> TOP
Execution time: 0.0047877s

7. В заключение

Подытоживая серию статей о разработке виртуальной машины и компилятора C подобного языка, хотелось бы отметить, что проект получился насыщенным по применению алгоритмов, структур данных и нетривиальных инженерных решений.

Например, оказалось, что в виртуальной машине достаточно всего одной инструкции условного перехода IFZERO [относительный адрес], так как структуры IF-ELSE, WHILE в условиях применяют булеву логику и условные прыжки надо осуществлять, только если на вершине стека лежит 0 (ноль - false). Остальные команды условных переходов оказались не нужны (раньше было аж 6 штук).

Чего только стоили конвенции по вызовам: как передавать аргументы, кто очищает стек. Как аллоцировать локальные переменные на стеке, если их объявление разбросано по телу функции. И много других подобных задач.

Еще одним интересным примером является компиляция ключевого слова "break", которое должно генерировать код "выпрыгивающий" из цикла по относительному адресу, который на момент генерации команды JMP еще не известен, так как генерация следующих выражений продолжается. Решил обычной подстановкой - помечаем место прыжка особым MAGIC WORD и в тот момент, когда размер блока кода WHILE известен, подставляем JMP с конкретным относительным адресом.

Очень интересный хобби-проект! Испытываю воодушевление, что получилось его реализовать и восстановить некоторые навыки программирования C/C++. Спасибо большое комментаторам, вы выступили менторами и направили в нужном направлении!

Хоть вся эта деятельность и является хобби, а днём я предприниматель, опять хочется вечером взяться за новую интересную и не тривиальную задачу по системному программированию. Всё таки в глубине души это моё...

Ура!

Исходный код проекта

Теги:

Хабы:

Разработка стековой виртуальной машины и компилятора под неё (итог)

1. Описание грамматики Си подобного языка

2. Абстрактное синтаксическое дерево (AST)

3. Таблица символов (Symbol Tree)

4. Parser - строитель AST и таблиц символов

4. Генерация кода

5. Испытание компилятора: факториал

6. Испытание компилятора: простые числа

7. В заключение

Публикации

Истории

Работа

Ближайшие события