DIY Interpreter-Bytecodes


    Programmiersprachen für virtuelle Maschinen haben sich in den letzten Jahrzehnten sehr verbreitet. Seit der Vorstellung der Java Virtual Machine in der zweiten Hälfte der 90er Jahre ist viel Zeit vergangen, und man kann mit Sicherheit sagen, dass Bytecode-Interpreter nicht die Zukunft, sondern die Gegenwart sind.


    Meines Erachtens ist diese Technik jedoch nahezu universell, und ein Verständnis der Grundprinzipien der Dolmetscherentwicklung wird nicht nur dem Schöpfer des nächsten Bewerbers für den Titel "Sprache des Jahres" gemäß TIOBE , sondern jedem Programmierer im Allgemeinen von Nutzen sein .


    Kurz gesagt, wenn Sie wissen möchten, wie sich Zahlen zu unseren bevorzugten Programmiersprachen addieren, worüber sich die Entwickler von virtuellen Maschinen immer noch streiten und wie schmerzlos Strings und reguläre Ausdrücke zusammenpassen, geben Sie bitte die Beschreibung unter "Katze" an.


    Teil Eins, einführender (aktueller)
    Teil Zwei, Optimierung von
    Teil Drei, angewendet


    Vorgeschichte


    Eines der selbstgeschriebenen Systeme der Business Intelligence-Abteilung unseres Unternehmens verfügt über eine Schnittstelle in Form einer einfachen Abfragesprache. In der ersten Version des Systems wurde diese Sprache ohne Übersetzung direkt aus der Eingabezeichenfolge mit der Abfrage interpretiert. Die zweite Version des Parsers arbeitet mit Byte-Zwischencode, der es ermöglicht, die Abfragesprache von ihrer Ausführung zu trennen und den Code erheblich zu vereinfachen.


    Während der Arbeit an der zweiten Version des Systems hatte ich einen Urlaub, in dem ich mich täglich für ein oder zwei Stunden von Familienangelegenheiten ablenkte, um Materialien über die Architektur und Leistung von Bytecode-Interpreter zu studieren. Ich beschloss, die resultierenden Notizen und Beispiele für Dolmetscher den Lesern von Habr in Form einer Artikelserie zur Verfügung zu stellen.


    Die erste zeigt fünf kleine (bis zu hundert Zeilen einfachen C-Codes) virtueller Maschinen (ok), von denen jede einen bestimmten Aspekt der Entwicklung solcher Interpreter aufdeckt.


    Wo gibt es Bytecodes in Programmiersprachen


    Virtuelle Maschinen, eine Vielzahl von virtuellen Instruktionssätzen in den letzten Jahrzehnten, viele wurden erfunden. Wikipedia behauptet, dass die ersten Programmiersprachen bereits in den 60er Jahren des letzten Jahrhunderts in verschiedenen vereinfachten Zwischendarstellungen zusammengefasst wurden. Einige dieser ersten Bytecodes wurden in Maschinencodes umgewandelt und von realen Prozessoren ausgeführt, andere wurden von virtuellen Prozessoren im laufenden Betrieb interpretiert.


    Die Beliebtheit von virtuellen Befehlssätzen als Zwischencodedarstellung wird aus drei Gründen erklärt:


    1. Programme in Form von Bytecodes werden einfach auf neue Plattformen übertragen.
    2. Bytecode-Interpreter arbeiten schneller als Syntaxbauminterpreter.
    3. In nur wenigen Stunden können Sie eine einfache virtuelle Maschine entwickeln.

    Machen wir einige einfachste virtuelle C-Maschinen und verwenden Sie diese Beispiele, um die wichtigsten technischen Aspekte der Implementierung von virtuellen Maschinen hervorzuheben.


    Vollständige Beispielcodes sind auf GitHub veröffentlicht . Beispiele können mit jedem relativ frischen GCC gesammelt werden:


    gcc interpreter-basic-switch.c -o interpreter
    ./interpreter

    Alle Beispiele haben die gleiche Struktur: Zuerst kommt der Code der virtuellen Maschine selbst, danach - die Hauptfunktion mit Assertions, die die Funktionsweise des Codes überprüfen. Ich habe versucht, die Opcodes und die Standorte der Schlüsselinterpreter klar zu kommentieren. Ich hoffe, dass der Artikel auch für Menschen klar ist, die nicht täglich in C schreiben.


    Der weltweit einfachste Bytecode-Interpreter.


    Wie ich schon sagte, ist der einfachste Dolmetscher sehr einfach zu machen. Kommentare - direkt nach der Auflistung, aber beginnen wir direkt mit dem Code:


    struct {uint8_t *ip;
        uint64_t accumulator;
    } vm;
    typedefenum {
        /* increment the register */
        OP_INC,
        /* decrement the register */
        OP_DEC,
        /* stop execution */
        OP_DONE
    } opcode;
    typedefenum interpret_result {
        SUCCESS,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    voidvm_reset(void){
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    interpret_result vm_interpret(uint8_t *bytecode){
        vm_reset();
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_INC: {
                vm.accumulator++;
                break;
            }
            case OP_DEC: {
                vm.accumulator--;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
        return SUCCESS;
    }
    

    Es gibt weniger als einhundert Zeilen, aber alle charakteristischen Merkmale einer virtuellen Maschine werden dargestellt. Das Fahrzeug hat ein einzelnes Register ( vm.accumulator), drei Operationen (Registerinkrement, Registerabnahme und Beendigung der Programmausführung) und einen Zeiger auf den aktuellen Befehl ( vm.ip).


    Jede Operation (d. H. Operationscode oder Opcode ) wird in einem Byte codiert, und das Dispatching wird mit dem switchin der Funktion üblichen Bereich ausgeführt vm_interpret. Verzweigungen switchenthalten die Logik der Operationen, dh ändern den Status des Registers oder schließen die Ausführung des Programms ab.


    Die Operationen werden vm_interpretals ein Array von Bytes - Bytecode ( Bytecode ) - an die Funktion übergeben und werden nacheinander ausgeführt, bis die Operation zum Herunterfahren der virtuellen Maschine ( OP_DONE) im Bytecode auftritt .


    Ein Schlüsselaspekt einer virtuellen Maschine ist die Semantik, dh eine Reihe von Operationen, die auf dieser Maschine möglich sind. In diesem Fall gibt es nur zwei Operationen, und sie ändern den Wert eines einzelnen Registers.


    Einige Forscher ( Virtual Machine Abstraction and Optimization Techniques , 2009) schlagen vor, virtuelle Maschinen in High-Level- und Low-Level- Maschinen einzuteilen , je nach Nähe der Semantik der virtuellen Maschine zur Semantik der physischen Maschine, auf der der Bytecode ausgeführt wird.


    Im Extremfall kann der Bytecode von virtuellen Maschinen auf niedriger Ebene den Maschinencode einer physischen Maschine mit simuliertem RAM, einem vollständigen Satz von Registern, Anweisungen zum Arbeiten mit dem Stapel usw. vollständig wiederholen. Die virtuelle Maschine von Bochs zum Beispiel wiederholt den Befehlssatz der x86-Architektur.


    Und umgekehrt: Die Operationen hochrangiger virtueller Maschinen spiegeln die Semantik der in Bytecode kompilierten spezialisierten Programmiersprache genau wider. So funktionieren beispielsweise SQLite, Gawk und zahlreiche Versionen von Prolog.


    Die mittlere Position wird von Dolmetschern von Programmiersprachen für allgemeine Zwecke besetzt, die Elemente sowohl hoher als auch niedriger Ebene aufweisen. Die populärste Java Virtual Machine bietet sowohl einfache Anweisungen zum Arbeiten mit einem Stack als auch integrierte Unterstützung für objektorientierte Programmierung mit automatischer Speicherzuordnung.


    Es ist wahrscheinlicher, dass der obige Code das primitivste virtuelle System auf niedriger Ebene ist: Jeder virtuelle Befehl ist ein Wrapper für einen oder zwei physische Befehle, und das virtuelle Register entspricht vollständig einem Register des "Eisen" -Prozessors.


    Argumente von Anweisungen in Bytecode


    Wir können sagen, dass der einzige Fall in unserem Beispiel für eine virtuelle Maschine sowohl das Argument als auch der Rückgabewert aller ausgeführten Anweisungen ist. Es kann jedoch erforderlich sein, Argumente an Anweisungen zu übergeben. Eine Möglichkeit ist, sie direkt in den Bytecode zu setzen.


    Wir erweitern das Beispiel durch Einfügen von Anweisungen (OP_ADDI, OP_SUBI), die ein Argument in Form eines Bytes annehmen, das unmittelbar auf den Opcode folgt:


    struct {uint8_t *ip;
        uint64_t accumulator;
    } vm;
    typedefenum {
        /* increment the register */
        OP_INC,
        /* decrement the register */
        OP_DEC,
        /* add the immediate argument to the register */
        OP_ADDI,
        /* subtract the immediate argument from the register */
        OP_SUBI,
        /* stop execution */
        OP_DONE
    } opcode;
    typedefenum interpret_result {
        SUCCESS,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    voidvm_reset(void){
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    interpret_result vm_interpret(uint8_t *bytecode){
        vm_reset();
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_INC: {
                vm.accumulator++;
                break;
            }
            case OP_DEC: {
                vm.accumulator--;
                break;
            }
            case OP_ADDI: {
                /* get the argument */uint8_t arg = *vm.ip++;
                vm.accumulator += arg;
                break;
            }
            case OP_SUBI: {
                /* get the argument */uint8_t arg = *vm.ip++;
                vm.accumulator -= arg;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
        return SUCCESS;
    }
    

    Neue Anweisungen (siehe Funktion vm_interpret) lesen ihr Argument aus Bytecode und fügen es dem Register hinzu / subtrahieren es aus dem Register.


    Ein solches Argument wird als unmittelbares Argument (das unmittelbare Argument ) bezeichnet, da es sich direkt im Array der Opcodes befindet. Die Haupteinschränkung in unserer Implementierung besteht darin, dass das Argument ein einzelnes Byte ist und nur 256 Werte annehmen kann.


    In unserer virtuellen Maschine spielt der Bereich der möglichen Werte der Befehlsargumente keine große Rolle. Wenn die virtuelle Maschine jedoch als Interpreter einer realen Sprache verwendet wird, ist es sinnvoll, den Bytecode zu komplizieren, indem eine vom Opcode-Array getrennte Konstantentabelle und Anweisungen mit einem direkten Argument hinzugefügt wird, das der Adresse des vorliegenden Arguments in der Konstantentabelle entspricht.


    Stapelmaschine


    Anweisungen in unserer einfachen virtuellen Maschine arbeiten immer mit einem Register und können keine Daten auf irgendeine Art und Weise übertragen. Darüber hinaus kann das Argument der Anweisung nur unmittelbar sein, die Additions- oder Multiplikationsoperation erfordert jedoch zwei Argumente.


    Einfach ausgedrückt, wir haben keine Möglichkeit, komplexe Ausdrücke zu bewerten. Um dieses Problem zu lösen, benötigen Sie eine Stack-Maschine, dh eine virtuelle Maschine mit einem integrierten Stack:


    #define STACK_MAX 256struct {uint8_t *ip;
        /* Fixed-size stack */uint64_tstack[STACK_MAX];
        uint64_t *stack_top;
        /* A single register containing the result */uint64_t result;
    } vm;
    typedefenum {
        /* push the immediate argument onto the stack */
        OP_PUSHI,
        /* pop 2 values from the stack, add and push the result onto the stack */
        OP_ADD,
        /* pop 2 values from the stack, subtract and push the result onto the stack */
        OP_SUB,
        /* pop 2 values from the stack, divide and push the result onto the stack */
        OP_DIV,
        /* pop 2 values from the stack, multiply and push the result onto the stack */
        OP_MUL,
        /* pop the top of the stack and set it as execution result */
        OP_POP_RES,
        /* stop execution */
        OP_DONE,
    } opcode;
    typedefenum interpret_result {
        SUCCESS,
        ERROR_DIVISION_BY_ZERO,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    voidvm_reset(void){
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
        vm.stack_top = vm.stack;
    }
    voidvm_stack_push(uint64_t value){
        *vm.stack_top = value;
        vm.stack_top++;
    }
    uint64_t vm_stack_pop(void)
    {
        vm.stack_top--;
        return *vm.stack_top;
    }
    interpret_result vm_interpret(uint8_t *bytecode){
        vm_reset();
        puts("Start interpreting");
        vm.ip = bytecode;
        for (;;) {
            uint8_t instruction = *vm.ip++;
            switch (instruction) {
            case OP_PUSHI: {
                /* get the argument, push it onto stack */uint8_t arg = *vm.ip++;
                vm_stack_push(arg);
                break;
            }
            case OP_ADD: {
                /* Pop 2 values, add 'em, push the result back to the stack */uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left + arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_SUB: {
                /* Pop 2 values, subtract 'em, push the result back to the stack */uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left - arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_DIV: {
                /* Pop 2 values, divide 'em, push the result back to the stack */uint64_t arg_right = vm_stack_pop();
                /* Don't forget to handle the div by zero error */if (arg_right == 0)
                    return ERROR_DIVISION_BY_ZERO;
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left / arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_MUL: {
                /* Pop 2 values, multiply 'em, push the result back to the stack */uint64_t arg_right = vm_stack_pop();
                uint64_t arg_left = vm_stack_pop();
                uint64_t res = arg_left * arg_right;
                vm_stack_push(res);
                break;
            }
            case OP_POP_RES: {
                /* Pop the top of the stack, set it as a result value */uint64_t res = vm_stack_pop();
                vm.result = res;
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
        return SUCCESS;
    }
    

    In diesem Beispiel gibt es bereits mehr Operationen, und fast alle arbeiten nur mit dem Stack. OP_PUSHI legt sein unmittelbares Argument auf den Stack. Die Anweisungen OP_ADD, OP_SUB, OP_DIV, OP_MUL extrahieren ein Wertepaar aus dem Stack, berechnen das Ergebnis und schieben es zurück auf den Stack. OP_POP_RES entfernt den Wert aus dem Stack und platziert ihn im Ergebnisregister, das für die Ergebnisse der virtuellen Maschine bestimmt ist.


    Für den Divisionsbetrieb (OP_DIV) wird der Fehler der Division durch Null eingefangen, wodurch der Betrieb der virtuellen Maschine gestoppt wird.


    Die Fähigkeiten einer solchen Maschine sind viel breiter als die vorherige mit einem einzigen Register und ermöglichen beispielsweise die Berechnung komplexer arithmetischer Ausdrücke. Ein weiterer (und wichtiger!) Vorteil ist die einfache Kompilierung von Programmiersprachen in eine Bytecode-Stapelmaschine.


    Maschine registrieren


    Aufgrund ihrer Einfachheit werden virtuelle Maschinen im Stapelformat von Entwicklern von Programmiersprachen am häufigsten verwendet. Dieselbe JVM- und Python-VMs verwenden sie.


    Solche Maschinen haben jedoch Nachteile: Sie müssen spezielle Anweisungen für die Arbeit mit dem Stapel hinzufügen. Beim Berechnen von Ausdrücken durchlaufen alle Argumente wiederholt eine einzige Datenstruktur. Viele unnötige Anweisungen erscheinen im Stapelcode.


    Inzwischen erfordert die Implementierung jeder zusätzlichen Anweisung die Kosten für die Planung, d. H. Das Dekodieren des Operationscodes und den Übergang zu dem Befehlskörper.


    Eine Alternative zu Stack-Maschinen sind registergestützte virtuelle Maschinen. Sie haben einen komplizierteren Bytecode: Jeder Befehl codiert eindeutig die Anzahl der Registerargumente und die Anzahl der Registerergebnisse. Dementsprechend wird anstelle eines Stapels ein erweiterter Satz von Registern als Repository für Zwischenwerte verwendet.


    #define REGISTER_NUM 16struct {uint16_t *ip;
        /* Register array */uint64_t reg[REGISTER_NUM];
        /* A single register containing the result */uint64_t result;
    } vm;
    typedefenum {
        /* Load an immediate value into r0  */
        OP_LOADI,
        /* Add values in r0,r1 registers and put them into r2 */
        OP_ADD,
        /* Subtract values in r0,r1 registers and put them into r2 */
        OP_SUB,
        /* Divide values in r0,r1 registers and put them into r2 */
        OP_DIV,
        /* Multiply values in r0,r1 registers and put them into r2 */
        OP_MUL,
        /* Move a value from r0 register into the result register */
        OP_MOV_RES,
        /* stop execution */
        OP_DONE,
    } opcode;
    typedefenum interpret_result {
        SUCCESS,
        ERROR_DIVISION_BY_ZERO,
        ERROR_UNKNOWN_OPCODE,
    } interpret_result;
    voidvm_reset(void){
        puts("Reset vm state");
        vm = (typeof(vm)) { NULL };
    }
    voiddecode(uint16_t instruction,
                uint8_t *op,
                uint8_t *reg0, uint8_t *reg1, uint8_t *reg2,
                uint8_t *imm){
        *op = (instruction & 0xF000) >> 12;
        *reg0 = (instruction & 0x0F00) >> 8;
        *reg1 = (instruction & 0x00F0) >> 4;
        *reg2 = (instruction & 0x000F);
        *imm = (instruction & 0x00FF);
    }
    interpret_result vm_interpret(uint16_t *bytecode){
        vm_reset();
        puts("Start interpreting");
        vm.ip = bytecode;
        uint8_t op, r0, r1, r2, immediate;
        for (;;) {
            /* fetch the instruction */uint16_t instruction = *vm.ip++;
            /* decode it */
            decode(instruction, &op, &r0, &r1, &r2, &immediate);
            /* dispatch */switch (op) {
            case OP_LOADI: {
                vm.reg[r0] = immediate;
                break;
            }
            case OP_ADD: {
                vm.reg[r2] = vm.reg[r0] + vm.reg[r1];
                break;
            }
            case OP_SUB: {
                vm.reg[r2] = vm.reg[r0] - vm.reg[r1];
                break;
            }
            case OP_DIV: {
                /* Don't forget to handle the div by zero error */if (vm.reg[r1] == 0)
                    return ERROR_DIVISION_BY_ZERO;
                vm.reg[r2] = vm.reg[r0] / vm.reg[r1];
                break;
            }
            case OP_MUL: {
                vm.reg[r2] = vm.reg[r0] * vm.reg[r1];
                break;
            }
            case OP_MOV_RES: {
                vm.result = vm.reg[r0];
                break;
            }
            case OP_DONE: {
                return SUCCESS;
            }
            default:
                return ERROR_UNKNOWN_OPCODE;
            }
        }
        return SUCCESS;
    }
    

    Das Beispiel zeigt eine Registermaschine mit 16 Registern. Die Anweisungen dauern jeweils 16 Bit und sind auf drei Arten codiert:


    1. 4 Bits pro Opcode + 4 Bits pro Registernamen + 8 Bits pro Argument.
    2. 4 Bits für den Operationscode + drei mal 4 Bits für die Namen der Register.
    3. 4 Bits pro Opcode + 4 Bits für einen einzelnen Registernamen + 8 nicht verwendete Bits.

    Unsere kleine virtuelle Maschine hat nur sehr wenige Operationen, daher reichen vier Bits (oder 16 mögliche Operationen) pro Opcode. Die Operation bestimmt genau, was die verbleibenden Bits der Anweisung darstellen.


    Die erste Art der Codierung (4 + 4 + 8) wird benötigt, um Daten mit der Operation OP_LOADI in die Register zu laden. Der zweite Typ (4 + 4 + 4 + 4) wird für arithmetische Operationen verwendet, die wissen müssen, wo einige Argumente verwendet werden sollen und wo das Ergebnis der Berechnung hinzugefügt werden muss. Und schließlich wird die letzte Ansicht (4 + 4 + 8 unnötige Bits) für Anweisungen mit einem einzelnen Register als Argument verwendet. In unserem Fall ist dies OP_MOV_RES.


    Für das Kodieren und Dekodieren von Anweisungen decodewird nun eine spezielle Logik (Funktion ) benötigt . Auf der anderen Seite wird die Logik der Anweisungen aufgrund der expliziten Angabe der Position der Argumente einfacher - Operationen mit dem Stapel verschwinden.


    Die Hauptmerkmale sind: Es gibt weniger Anweisungen im Bytecode der Registermaschinen, separate Anweisungen sind breiter, das Kompilieren in einen solchen Bytecode ist komplizierter - der Compiler muss entscheiden, wie die verfügbaren Register verwendet werden.


    Es ist zu beachten, dass virtuelle Maschinen für Register normalerweise einen Stapel haben, in dem beispielsweise Funktionsargumente platziert werden. Register werden verwendet, um einzelne Ausdrücke auszuwerten. Auch wenn kein expliziter Stack vorhanden ist, wird ein Array zum Erstellen des Stacks verwendet, der die gleiche Rolle wie der Arbeitsspeicher in physischen Maschinen spielt.


    Maschinen stapeln und registrieren, Vergleich


    Es gibt eine interessante Studie ( Showdown für virtuelle Maschinen: Stack vs. Register , 2008), die alle nachfolgenden Entwicklungen auf dem Gebiet der virtuellen Maschinen für Programmiersprachen maßgeblich beeinflusste. Seine Autoren schlugen eine Methode für die Live-Übersetzung vom Stapelcode der Standard-JVM zum Registercode vor und verglichen die Leistung.


    Die Methode ist nicht trivial: Der Code wird zuerst übersetzt und dann auf ziemlich komplizierte Weise optimiert. Der nachfolgende Leistungsvergleich desselben Programms zeigte jedoch, dass die zusätzlichen Prozessorzyklen, die für das Dekodieren von Befehlen aufgewendet werden, durch eine Verringerung der Gesamtzahl der Befehle vollständig kompensiert werden. Kurz gesagt, die Registermaschine erwies sich als effizienter als die Stapelmaschine.


    Wie bereits erwähnt, hat diese Effizienz einen sehr spürbaren Preis: Der Compiler muss die Register selbst zuordnen, und außerdem ist ein fortgeschrittener Optimierer wünschenswert.


    Die Debatte darüber, welche Architektur besser ist, ist noch nicht vorbei. Wenn wir über Java-Compiler sprechen, wurde der Dalvik-VM-Bytecode registriert, der bis vor kurzem auf jedem Android-Gerät funktionierte. Die Titel-JVM behielt jedoch den Stack-Befehlssatz bei. Die virtuelle Lua-Maschine verwendet die Registermaschine, die Python-VM ist jedoch immer noch ein Stapel. Usw.


    Bytecode in Interpretern regulärer Ausdrücke


    Lassen Sie uns zum Ablenken von virtuellen Maschinen auf niedriger Ebene einen spezialisierten Interpreter betrachten, der Zeichenfolgen auf Übereinstimmung mit regulären Ausdrücken überprüft:


    typedefenum {
        /* match a single char to an immediate argument from the string and advance ip and cp, or
         * abort*/
        OP_CHAR,
        /* jump to and match either left expression or the right one, abort if nothing matches*/
        OP_OR,
        /* do an absolute jump to an offset in the immediate argument */
        OP_JUMP,
        /* stop execution and report a successful match */
        OP_MATCH,
    } opcode;
    typedefenum match_result {
        MATCH_OK,
        MATCH_FAIL,
        MATCH_ERROR,
    } match_result;
    match_result vm_match_recur(uint8_t *bytecode, uint8_t *ip, char *sp){
        for (;;) {
            uint8_t instruction = *ip++;
            switch (instruction) {
            case OP_CHAR:{
                char cur_c = *sp;
                char arg_c = (char)*ip ;
                /* no match? FAILed to match */if (arg_c != cur_c)
                    return MATCH_FAIL;
                /* advance both current instruction and character pointers */
                ip++;
                sp++;
                continue;
            }
            case OP_JUMP:{
                /* read the offset and jump to the instruction */uint8_t offset = *ip;
                ip = bytecode + offset;
                continue;
            }
            case OP_OR:{
                /* get both branch offsets */uint8_t left_offset = *ip++;
                uint8_t right_offset = *ip;
                /* check if following the first offset get a match */uint8_t *left_ip = bytecode + left_offset;
                if (vm_match_recur(bytecode, left_ip, sp) == MATCH_OK)
                    return MATCH_OK;
                /* no match? Check the second branch */
                ip = bytecode + right_offset;
                continue;
            }
            case OP_MATCH:{
                /* success */return MATCH_OK;
            }
            }
            return MATCH_ERROR;
        }
    }
    match_result vm_match(uint8_t *bytecode, char *str){
        printf("Start matching a string: %s\n", str);
        return vm_match_recur(bytecode, bytecode, str);
    }
    

    Die Hauptanweisung ist OP_CHAR. Es nimmt sein unmittelbares Argument und vergleicht es mit dem aktuellen Zeichen in der Zeichenfolge ( char *sp). Bei Übereinstimmung der erwarteten und aktuellen Zeichen in der Zeile erfolgt der Übergang zur nächsten Anweisung und zum nächsten Zeichen.


    Die Maschine versteht auch die Übergangsoperation (OP_JUMP), die ein einziges unmittelbares Argument benötigt. Argument bedeutet absoluter Offset im Bytecode, ab dem die Berechnung fortgesetzt werden soll.


    Die letzte wichtige Operation ist OP_OR. Es werden zwei Offsets benötigt, wobei versucht wird, den Code zuerst auf den ersten Code anzuwenden und im Fehlerfall den zweiten Code. Dies geschieht mit Hilfe eines rekursiven Aufrufs, d. H. Der Befehl führt eine Durchforstung aller möglichen Varianten eines regulären Ausdrucks in die Baumtiefe durch.


    Überraschenderweise reichen vier Opcodes und siebzig Codezeilen aus, um reguläre Ausdrücke der Form "abc", "a? Bc", "(ab | bc) d", "a * bc" auszudrücken. In dieser virtuellen Maschine gibt es nicht einmal einen expliziten Zustand, da alles, was benötigt wird - Zeiger auf den Beginn des Befehlsstroms, die aktuelle Anweisung und das aktuelle Symbol - von den Argumenten der rekursiven Funktion übergeben wird.


    Wenn Sie an den Details der Arbeit der regulären Ausdrücke interessiert sind, können Sie sich zunächst mit der Artikelserie von Russ Cox ( Google Co2 , Autor Russ Cox ), dem Autor der regulären Ausdrücke von Google RE2, vertraut machen .


    Ergebnisse


    Lassen Sie uns zusammenfassen.


    Für allgemeine Programmiersprachen werden in der Regel zwei Architekturen verwendet: Stack und Register.


    In einem Stack-Modell ist der Stack die Hauptdatenstruktur und der Weg, Argumente zwischen Anweisungen zu übertragen. Im Registermodell wird ein Satz von Registern zum Auswerten von Ausdrücken verwendet, ein expliziter oder impliziter Stack wird jedoch weiterhin zum Speichern von Funktionsargumenten verwendet.


    Das Vorhandensein eines expliziten Stacks und einer Reihe von Registern bringt solche Maschinen näher an die unteren und sogar an die physischen. Die Fülle von Low-Level-Befehlen in einem solchen Bytecode bedeutet, dass eine beträchtliche Menge an physischen Prozessorressourcen für das Decodieren und Abgeben virtueller Befehle aufgewendet wird.


    Andererseits spielen Anweisungen auf hoher Ebene eine wichtige Rolle in beliebten virtuellen Maschinen. In Java zum Beispiel sind dies Anweisungen für polymorphe Funktionsaufrufe, die Zuordnung von Objekten und die Garbage Collection.


    Rein übergeordnete virtuelle Maschinen - zum Beispiel Bytecode-Interpreter von Sprachen mit fortgeschrittener Semantik, die weit von Eisen entfernt sind - werden die meiste Zeit nicht in der Steuerung oder im Decoder, sondern in den Befehlsorganen verbracht und sind daher relativ effektiv.


    Praktische Empfehlungen:


    1. Wenn Sie einen Bytecode ausführen müssen, und dies in einer angemessenen Zeit tun, versuchen Sie, mit Anweisungen zu arbeiten, die Ihrer Aufgabe am nächsten kommen. Je höher das semantische Niveau, desto besser. Dies reduziert die Kosten für die Planung und vereinfacht die Codegenerierung.
    2. Wenn größere Flexibilität und heterogene Semantik erforderlich waren, sollten Sie zumindest versuchen, den gemeinsamen Nenner im Byte-Code so zu isolieren, dass die resultierenden Anweisungen einen bedingten Durchschnitt bilden.
    3. Wenn in Zukunft möglicherweise Ausdrücke berechnet werden müssen, erstellen Sie eine Stapelmaschine. Dies verringert die Kopfschmerzen beim Kompilieren von Bytecode.
    4. Wenn keine Ausdrücke vorgesehen sind, erstellen Sie eine triviale Registermaschine, die die Kosten des Stacks vermeidet und die Anweisungen selbst vereinfacht.

    In den folgenden Artikeln werde ich die praktischen Implementierungen von virtuellen Maschinen in gängigen Programmiersprachen analysieren und erläutern, warum die Business Intelligence-Abteilung Badoo einen Bytecode benötigt.


    Jetzt auch beliebt: