String in Tokens zerlegen und Klassifizieren



  • Hallo,

    ich bin gerade dabei einen Tokenizer für mein Programm zu schreiben. Leider bin ich mir nicht sicher ob meine Vorgehensweise dafür wirklich geeignet ist, daher wollte ich mal Meinungen dazu einholen.

    Also ich habe ein Textfeld, welches bei jedem TextChanged Event geparst werden soll. Dazu muss ich den Textfeld String zunächst in Tokens zerlegen. Ich mache das prinzipiell so:

    void TextChanged(void)
    {
        // Aktuelle Textlaenge bestimmen
        unsigned int textLength = GetTextLength();
    
        // Text bestimmen
        const char *text;
        text = new const char[textLength];
        GetTextboxText((LPARAM)text);
    
        // Variablen für Tokens
        std::string word = "";
        std::string prevWord1 = "";
        std::string prevWord2 = "";
        std::string prevWord3 = "";
    
        // Ueber Text iterieren
        for(unsigned int i = 1; i < textLength; i++)
        {
            // Falls gültiger Wort-Char, an aktuelles Wort anhängen
            if(text[i] <= 255 && text[i] > 0 && (isalnum(text[i]) || text[i] == '_'))
            {
                word.append(1, text[i]);
            }
            else
            {
                // Neues Token gefunden!
    
                /*
                Hier sollen die Token weiter verarbeitet werden
                */
    
                // Wörter weiter shiften
                prevWord3.assign(prevWord2);
                prevWord2.assign(prevWord1);
                prevWord1.assign(word);
                word.clear();
            }
        }
    }
    

    Die Frage ist jetzt: Ist das so gut?

    Die Tokens müssen dann halt noch weiter verarbeitet werden, daher habe ich die verschiedenen strings für die vorhergehenden Wörter. Zum Beispiel wenn ich in meinem Textbox Text habe:

    private void MyFunction(void)

    Dann soll MyFunction als Benutzerdefinierte Funktion erkannt werden. Um Rückgabewert und Zugriffsmodifizierer korrekt zu identifizieren brauch ich ja auch die vorhergehenden Token. Ich würde das dann also so machen (in der for Schleife da wo der Kommentar ist):

    if(prevWord2 == "private")
    {
        // Checken ob gültiger Datentyp
        if(IsDataType(prevWord1))
        {
            // Falls ja, den aktuellen Identifier (= MyFunction) speichern
            AddIdentifier(word);
        }
    }
    

    Das funktioniert zwar, da es aber sehr viele Datentypen gibt (und Benutzer auch noch selbst welche definieren können sollen) ist das Ganze momentan nicht sehr performant und auch recht umständlich.

    Wo kann ich hier am effektivsten ansetzen um das Ganze zu verbessern?

    Schöne Grüße,
    hs



  • Erstmal möchte ich kundtun, dass ich nett ausgedrückt von deinem Code angewidert bin 🙄
    Du schaffst ein Memory Leak, benutzt viel C, schreibst umständlich... hach.

    Verkürzen wir erstmal deinen Text-Empfang:

    // Text Buffer mit ausreichend Größe erstellen
        std::string text(GetTextLength()+1, '\0');
        // Text aus Box in Buffer lesen
        GetTextboxText(reinterpret_cast<LPARAM>(text.data()));
        // Terminierungszeichen aus C++ String entfernen
        text.pop_back();
    

    Für das Auftrennen des Strings solltest du eines der folgenden Verfahren verwenden:
    - C++11 Regex Iterator
    - istringstream + getline
    - Boost tokenzier
    Ich persönlich bevorzuge das zweite, da Regex übertrieben ist und die Abhängigkeit von Boost nicht sein muss.
    Die Funde kannst du in einem Vektor speichern.



  • Hi,

    hab hier mal was kleiens gebaut, vielleicht hilfts dir.

    #include <algorithm>
    #include <array>
    #include <initializer_list>
    #include <iostream>
    #include <set>
    #include <string>
    #include <vector>
    using namespace std;
    
    namespace category
    {
    	set<string> accessors = { "private", "protected", "public" };
    	set<string> types     = { "void", "int", "bool" };
    }
    
    template<typename Container>
    void tokenize(const string& s, const char* d, Container& ret)
    {
    	Container output;
    
    	array<bool, 255> delims = { {} };
    	while( *d )
    	{
    		unsigned char code = *d++;
    		delims[code] = true;
    	}
    
    	typedef string::const_iterator iter;
    	iter beg;
    	bool in_token = false;
    	for(auto it=begin(s); it!=end(s); ++it)
    	{
    		if( delims[*it] )
    		{
    			if( in_token )
    			{
    				output.push_back( typename Container::value_type(beg,it) );
    				in_token = false;
    			}
    		}
    		else if( !in_token )
    		{
    			beg = it;
    			in_token = true;
    		}
    	}
    
    	if( in_token )
    		output.push_back( typename Container::value_type(beg,end(s)) );
    	output.swap(ret);
    }
    
    bool is_valid(const string& s, const set<string>& lookup)
    {
    	return binary_search( begin(lookup), end(lookup), s );
    }
    
    int main()
    {
    	const string text = "private void MyFunction(void)";
    	const char* split_by = " (";
    	vector<string> token;
    	tokenize( text, split_by, token );
    
    	if( is_valid(token[0],category::accessors) && is_valid(token[1],category::types) )
    	{
    		cout << "OK";
    	}
    }
    

    Du kannst nun z.B. noch eine kleine Funktion schreiben, die neue Typen zur Lookup-Table hinzufügt, etc.



  • Hallo,

    Youka schrieb:

    Erstmal möchte ich kundtun, dass ich nett ausgedrückt von deinem Code angewidert bin 🙄
    Du schaffst ein Memory Leak, benutzt viel C, schreibst umständlich... hach.

    Das ist nur ein Minimalbeispiel, das wichtige ist eigentlich nur die for-Schleife. Aber Danke für das Feedback.

    Youka schrieb:

    Die Funde kannst du in einem Vektor speichern.

    out schrieb:

    Hi,

    hab hier mal was kleiens gebaut, vielleicht hilfts dir.

    Danke, ich hab da wegen dem Vektor nur eine Frage. Und zwar hab ich das bis jetzt so gemacht, weil ich iteriere ja schon einmal char-weise über den Ganzen Text. Wenn ich jetzt die Tokens in einem Vektor sammel muss ich ja nochmal über den Ganzen Text iterieren (diesmal dann über die Tokens).

    Daher dachte ich es ist effizienter gleich alles in einer einzigen Schleife zu erledigen. Oder ist das irrelevant?

    Auch hab ich mit dem Token-Vektor ein (eventuell sehr einfach zu lösendes) Problem: Und zwar geht bei dem Abspeichern im Vektor die Position des Tokens im Text verloren.

    Das Ganze soll nämlich auch noch kontextsensitiv sein. Dazu ermittel ich beim char-weisen durchlaufen die Position des Carets, eine State-Machine sagt mir in welchem Scope ich gerade bin (namespace, function, struct, etc).

    Wenn ich jetzt über einen Token Vektor iteriere weiß ich ja nicht mehr zwischen welchen Token sich das Caret befindet, da diese Information ja nicht mehr vorhanden ist?

    Schöne Grüße,
    hs



  • Ist jetzt warscheinlich mit Kanonen auf Spatzen geschossen aber ich hatte soetwas ähnliches vor einiger Zeit gefragt http://www.c-plusplus.net/forum/316504 ,allerdings ging es dabei tatsächlich um die Zerlegung von Codestrukturen. Lässt sich aber sicher ummünzen.

    Meine dynamische variante sieht in etwa so aus

    bool Parse(const char* term, SyntaxNode* node)
    			{
    				bool match_failture = false;
    				node->first = term;
    				node->last = term;
    
    				SyntaxNode* tmp = node;
    				while(*term)
    				{
    					if(match_failture)
    						return false;
    
    					for(int i = 0; i < size; i++)
    					{
    						if(tokens[i]->Valid(term, tmp))
    						{
    							if(tmp->next && tmp->next->type == SyntaxType::Ignore)
    							{
    								term = tmp->next->last; //reset node to itselfe as new node
    								tmp->next = 0;
    							}
    							else
    							{
    								tmp = tmp->next; //roll node pointer to next one added by token
    								term = tmp->last; //set term to last char of matching node
    							}
    
    							node->last = term; //position were match failed
    							match_failture = false;
    							break;
    						}
    
    						match_failture = true;
    					}
    				}
    
    				return true;
    			}
    

    dynamisch deswegen weil ich die token anhand eines ebnf pattern zur laufzeit einlade. Es wird ein pointer auf ein SyntaxNode übergeben welches den aktuellen token enthält, sowie einen pointer auf das erste und letzte Zeichen in der Zeichenkette. Die tokens enthalten eine methode

    bool Valid(const char* term, //pointer to current position
               SyntaxNode* root); //the node to write positions to
    

    in der das eigentliche parsing und der anschließende vergleich anhand des teiltyps des token stattfinden. Es kann sich hierbei etwa um einen teilstring handeln der verglichen wird oder ob das aktuelle stück der zeichenkette mit einer zahl beginnt etc. , aber immer nur ein elementarer vergleich auf einmal.
    Du kannst hier z.B. prima mit strspn und strcspn auf deinem text arbeiten.

    In der Awendung brauchst du aber nicht zwangsläufig pointer zu nehmen, es geht auch mit

    SnytaxNode root = SyntaxNode();
    bool match = Parse((const char*)&inputText[0], &root);
    

    Wenn ich dich richtig verstanden habe ist das eher nach dem das was du suchts?



  • Hallo,

    Pria schrieb:

    Ist jetzt warscheinlich mit Kanonen auf Spatzen geschossen aber ich hatte soetwas ähnliches vor einiger Zeit gefragt http://www.c-plusplus.net/forum/316504 ,allerdings ging es dabei tatsächlich um die Zerlegung von Codestrukturen. Lässt sich aber sicher ummünzen.

    ...

    Wenn ich dich richtig verstanden habe ist das eher nach dem das was du suchts?

    naja, bin mir nicht sicher. Also du wolltest bei dem Projekt ja eine dynamische Grammatik, wenn ich den verlinkten Thread richtig verstanden habe. Sowas brauch ich eigentlich nicht, die Grammatik der Sprache steht fest und verändert sich auch nicht. Der dynamische Part bezieht sich lediglich auf das Hinzufügen und Entfernen von Benutzerdefinierten Identifiern (zB. Variablen, Funktionen, etc.). Die Sprach-Syntax an sich muss aber nicht dynamisch sein.

    Also einen AST brauch ich hier eigentlich nicht (soweit ich das einschätzen kann), es geht eigentlich nur um einen Texteditor mit Syntaxhighlighting.

    Die Sache die mir Probleme bereitet ist die: sagen wir ich hab folgenden Code in meinem Texteditor:

    private class MyClass
    {
        void MyFunction(int i)
        {
           | // Das Caret ist an der vertikalen Linie |. Hier soll i als Identifier erkannt werden, außerhalb von MyFunction nicht
        }
    }
    

    Wenn ich das jetzt in Token zerlege, erhalte ich:

    private
    class
    MyClass
    {
    void
    MyFunction
    (
    int
    i
    )
    {
    }
    }

    Da kann ich zwar jetzt drüber iterieren, aber mir fehlt die Information wo sich das Caret befindet.



  • Deswegen hatte ich dir ja extra nur die parser schleife von der textzerlegung gepostet, da werden ja die pointer auf die textindices der einzelnen matches gespeichert, wenn du den AST weglässt und stattdessen sowas anlegst wie

    struct match
    {
       const char* first;
       const char* last;
    };
    

    kannst du mithilfe von first feststellen welche position das war und mit hilfe von last - first erhälst du die länge der zeichenfolge, also im grunde genommen alles was du haben wolltest



  • Pria schrieb:

    struct match
    {
       const char* first;
       const char* last;
    };
    

    Das ist ein Implementierungsdetail.

    Am Anfang schön mit std::string und substr rumbasteln, bis der Parser auch wirklich funktioniert.

    Dann eine eigene Stringklasse schreiben und std::string mit my_string ersetzen - fertig.

    Sich von Performance vom eigentlichen Ziel ablenken zu lassen ist vorerst unklug.



  • Ohne jedes Detail Deiner Requirements zu kennen, hier mal ein ganz simpler Tokenizer (ähnlich zu dem im Chromium Projekt):

    class StringTokenizer {
    public:
      StringTokenizer(const char* string_begin, const char* string_end) :
        m_token_begin(string_begin),
        m_token_end(string_begin),
        m_end(string_end) {}
    
      bool GetNext() {
        static const std::string delims(" ");  // HACK
    
        while (true) {
          m_token_begin = m_token_end;
    
          if (m_token_end == m_end) {
            return false;
          }
    
          m_token_end++;
    
          if (delims.find(*m_token_begin) == std::string::npos) {
            break;
          }
        }
    
        while (m_token_end != m_end && delims.find(*m_token_end) == std::string::npos) {
          m_token_end++;
        }
    
        return true;
      }
    
      std::string Token() const {
        return std::string(m_token_begin, m_token_end);
      }
    
    private:
      const char* m_token_begin;
      const char* m_token_end;
      const char* m_end;
    };
    


  • Tomahawk schrieb:

    Ohne jedes Detail Deiner Requirements zu kennen, hier mal ein ganz simpler Tokenizer (ähnlich zu dem im Chromium Projekt):

    Danke, werd ich auch ausprobieren.

    pimpl schrieb:

    Das ist ein Implementierungsdetail.

    Am Anfang schön mit std::string und substr rumbasteln, bis der Parser auch wirklich funktioniert.

    Dann eine eigene Stringklasse schreiben und std::string mit my_string ersetzen - fertig.

    Sich von Performance vom eigentlichen Ziel ablenken zu lassen ist vorerst unklug.

    Also ich glaube ich hab mich nicht genau ausgedrückt. Der Parser funktioniert schon in seinem jetzigen Zustand. Ich hab eben nur Zweifel daran ob meine Vorgehensweise auch gut ist.

    Die hier geposteten Parser zerlegen den Textbox String in ein String Array welches die verschiedenen Token enthält. Was ich mir halt gedacht habe: Wenn man so vorgeht muss man eben zweimal über den Text iterieren; einmal char-weise über jeden einzelnen Buchstaben und dann nochmal über jedes einzelne Token.

    Der Aufwand dafür wäre dann eben O(n + m) anstatt O(n), wobei n die Anzahl der Buchstaben ist und m die Anzahl der Token. Klar wäre es immer noch linear, aber wenn man sich die m Durchläufe sparen könnte, warum dann machen?

    Nach meinem Verständnis müsste also der von mir gepostete Ansatz schneller sein; allerdings bin ich mir nicht sicher ob dies tatsächlich zutrifft, da man ja nie weiß was so alles im Hintergrund passiert. Zum Beispiel bei dem word.append(1, text[i]) oder bei dem durchshiften der Tokens, ob das vielleicht alles wieder verlangsamt und es sich dadurch nicht lohnt.

    Das ist u.a. meine eigentliche Frage.



  • Was mir auch noch aufgefallen ist:

    Allein diese Zeile in der for-Schleife

    word.clear();
    

    verursacht schon bei relativ wenig Token extreme Performance Probleme; die Auslastung des Prozessors steigt auf volle 25% wenn sehr schnell TextChange Events aufgerufen werden, ohne word.clear() bleibt es irgendwo bei 2-3%.

    Was passiert da im Hintergrund?


Log in to reply