Lexer mit optimaler "Reichweite"?



  • Hallo,

    angenommen ich habe einen Lexer der mir einen Text in einen Vektor aus Tokens zerlegt. Meine Frage ist jetzt, wie macht man es am besten so, dass man nach Veränderungen des Textes eine möglichst kleine Anzahl an Zeichen neu lexen muss? (Vorraussetzung ist das nur die "üblichen" Veränderungen eines normalen Texteditors benutzt werden).

    Also wenn ich den Text habe:

    int i = 5;
    

    würde mein Lexer das zum Beispiel so zerteilen:

    Type          Length
    --------------------
    Identifier    3
    Identifier    1
    Operator=     1
    Number        1
    Operator;     1
    EOF           0
    

    Soweit so gut. Ich speichere nur die Länge der Tokens (nicht deren Position), weil sich durch eine Änderung am Anfang des Textes ja alle nachfolgenden Positionen verändern (und somit invalidiert) werden würden.

    Wenn jetzt jemand was mitten in dem Text einfügt, zum Beispiel so:

    int my_i = 5;
    

    Hier wurde jetzt der Text "my_" mitten im Text eingefügt, es muss also eigentlich nur ein Token neu gelext werden. Die neue Tokenliste sähe dann so aus:

    Type          Length
    --------------------
    Identifier    3
    Identifier    4 // Einzige Veränderung
    Operator=     1
    Number        1
    Operator;     1
    EOF           0
    

    Für "normale" Token funktioniert das auch alles problemlos. Mein Problem sind allerdings Token, die sich über (beliebig) viele Zeilen erstrecken können, zum Beispiel Block-Kommentare. Wenn der Text also so aussieht:

    int i = */ 5;
    

    und jemand vor dem Istgleich-Zeichen den Text "/*" einfügt, dann reicht es nicht mehr die editierten Token neu zu lexen, da auch nachfolgende Token durch den Einfügevorgang betroffen sein können:

    int i /*= */ 5;
    

    Das Istgleich-Zeichen ist hier vom Editiervorgang überhaupt nicht betroffen, trotzdem muss es aus der Tokenliste verschwinden.

    Deswegen jetzt meine Frage, wie kann man sowas am besten handeln? Ich will nicht bei jeder kleinen Veränderung den gesamten Text neu lexen, sondern nach Möglichkeit immer nur das was wirklich notwendig ist um die Tokenliste korrekt zu aktualisieren.

    Wie könnte man hier effizient vorgehen?



  • happystudent schrieb:

    Deswegen jetzt meine Frage, wie kann man sowas am besten handeln? Ich will nicht bei jeder kleinen Veränderung den gesamten Text neu lexen, sondern nach Möglichkeit immer nur das was wirklich notwendig ist um die Tokenliste korrekt zu aktualisieren.

    Dann mach das doch (?). Ich habe wohl das Problem nicht verstanden. Wofür soll das ganze denn verwendet werden?



  • TyRoXx schrieb:

    Wofür soll das ganze denn verwendet werden?

    Intellisense.

    TyRoXx schrieb:

    Dann mach das doch (?). Ich habe wohl das Problem nicht verstanden.

    Das Problem ist, dass ich nicht weiß wann ich aufhören kann mit lexen. Anfangen muss man ja logischerweise dort, wo die Text-Modifikation anfängt. Allerdings kann man nicht einfach auch dort wieder aufhören wo diese aufhört, eben wegen den beschriebenen mehrzeiligen Token.

    Ein Beispiel ist eben das gezeigte Istgleich-Zeichen: Dort muss ja über den Editierten Bereich hinaus gelext werden. Allerdings eben auch nicht bis zum Ende, die "5" und der ";" können ja wieder verwendet werden.



  • Du musst von der geänderten Stelle an solange neu lexen, wie sich Tokens ändern. Der Kommentar schluckt den Operator. Irgendwann endet der Kommentar und der Rest müsste ja noch stimmen.



  • TyRoXx schrieb:

    Du musst von der geänderten Stelle an solange neu lexen, wie sich Tokens ändern. Der Kommentar schluckt den Operator. Irgendwann endet der Kommentar und der Rest müsste ja noch stimmen.

    Moment, wie soll ich das überprüfen?

    Die Text-Modifikation kann ja auch ein CTRL-V (also ein paste) sein, welches am Ende zufällig das gleiche Token besitzt wie nach dem Kommentar? Also etwa so:

    Vorher:

    int i = /*1 + 2 + 3 +*/ 4;
    

    Nachher:

    int i = /*irgendein kommentar*/ 4 + 4;
    

    Hier würde ich jetzt über den Kommentar lexen, und danach sehen dass das Gleiche Token (nämlich die "4") kommt und aufhören. Allerdings kommt da ja noch ein "+" und eine "4".



  • Du musst natürlich berücksichtigen, wie viele Zeichen geändert worden sind.



  • TyRoXx schrieb:

    Du musst natürlich berücksichtigen, wie viele Zeichen geändert worden sind.

    Aber das wird auch nicht immer funktionieren, oder verstehe ich was falsch?

    Mal ein ausführlicheres Beispiel.

    Vorher:

    int i = 0;
    /* int j = 1; */
    int k = 2;
    

    Nacher:

    int i = 0;
    /**/ int j = 1; */
    int k = 2;
    

    Geändert wurden zwei Zeichen (es wurde ein "*/" eingefügt). Also weiß ich dass schonmal mindestens 2 Zeichen neu gelext werden müssen ab dem Start meiner Editier-Position. Jetzt ist der Kommentar fertig gelext, also schaue ich nach welches das nächste Token ist. Und dieses ist eben identisch mit dem nächsten Token in meiner Tokenliste (beide "int", also vom Typ IDENTIFIER).

    Was jetzt? Damit würde ich ja die Zeichen j = 1; */ nicht berücksichtigen. Wie kann ich wissen dass ich an dieser Stelle noch weiter lexen muss und erst beim (insgesamt) dritten "int" aufhören kann?



  • Du musst das Token finden, in welchem das Einfügen stattfindet. Dieses Token möge t heißen. Von min(t.begin, insertion.begin) bis max(t.end, insertion.end) musst du neu scannen. Die Tokens, die dabei entstehen, ersetzen das t . Du musst dann noch den Sonderfall behandeln, dass das letzte neue Token seine Bedeutung durch weitere Eingabezeichen ändern könnte. Das kann zum Beispiel bei einem unvollendeten Kommentar, einem Identifier oder einer Zahl der Fall sein. Du solltest deinen Scanner so schreiben, dass er zurückgibt, ob das letzte Token definitiv abgeschlossen ist oder nicht. Ersteres ist einfach, weil da nichts weiter zu tun ist. Wenn es möglicherweise nicht abschlossen ist, musst du deinen Scanner fragen, wie viele der nächsten Zeichen man noch anhängen kann. Dabei musst du natürlich Tokens kürzen und bei Länge null entfernen, wenn deren Zeichen verschluckt werden.

    Original:
    /* int j = 1; */ int k = 2;
    
    Eingefügte Zeichen:
    /**/ int j = 1; */ int k = 2;
      ^^
    
    min(t.begin, insertion.begin) bis max(t.end, insertion.end):
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^^^^^
    
    Scannen... (altes Token weg, neue dort einfügen)
    /**/ int j = 1; */ int k = 2;
    ^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^^^^
    
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^^^^^
    
    Die Bedeutung von / kann sich zu /= oder // ändern, also weiter:
    /**/ int j = 1; */ int k = 2;
    ^^^^^^^^^^^^^^^^^^^^^^
    
    Nö, hat sich nicht geändert. Fertig.
    


  • Wow, danke schonmal für die ausführliche Erklärung, das bringt mich auf jeden Fall weiter (auch wenn das ganz schön tricky wird) 👍

    Wenn man den Lexer so baut dass er in einem Token gestartet werden und loslaufen kann, müsste es sogar reichen von insertion.begin bis max(t.end, insertion.end) zu laufen, wobei t dann das letzte Token ist in dem die Editierung passiert ist (wenn die Editierung sich über mehrere Token erstreckt).

    Ein Problem habe ich allerdings noch:

    Angenommen ich schreibe (z.B eine Doku) in einem sehr langen Block-Kommentar. Dann muss mit dieser Methode jedesmal komplett der gesamte Kommentar gelext werden (also im Worst-Case wieder das ganze Dokument), auch wenn sich eigentlich so gut wie nix ändert.

    Könnte man das noch irgendwie umgehen?



  • happystudent schrieb:

    Angenommen ich schreibe (z.B eine Doku) in einem sehr langen Block-Kommentar. Dann muss mit dieser Methode jedesmal komplett der gesamte Kommentar gelext werden (also im Worst-Case wieder das ganze Dokument), auch wenn sich eigentlich so gut wie nix ändert.

    Du kannst den Fall natürlich vor dem vollständigen Scannen abfangen. Wenn sich durch das Einfügen die Bedeutung des Tokens nicht ändert, musst du nichts weiter machen.

    Original:
    /* abc*def */
    
    Eingefügt:
    /* abc*/def */
           ^
    
    Relevantes Stück:
    /* abc*/def */
          ^^^
          ^^ <- Kommentarende ändert sich
    
    if (is_multi_line_comment(t))
    {
    	auto relevant_slice = make_iterator_range(
    		full_source.begin() + std::max(1, insertion.begin) - 1,
    		full_source.begin() + insertion.end + std::min(1, full_source.size() - insertion.end)
    	);
    	if (!contains(relevant_slice, "*/"))
    	{
    		//Kommentar bleibt Kommentar
    		return;
    	}
            //Rest des alten Kommentars neu scannen..
    }
    


  • Ok... gut, ich glaub damit dürften alle Fälle abgedeckt sein.

    Danke auf jeden Fall für die Hilfe, werd mich dann mal dran machen und versuchen das umzusetzen. 🙂


Log in to reply