Ich brauche ein paar Tipps für einen kleinen Parser



  • Brauchst Dich nicht zu entschuldigen. Ich müsste ja nicht antworten. Aber ich sehe, dass wir voran kommen.

    Also der Scanner hat einen Zustand. Wenn Du das erste Zeichen liest, dann ist der im Startzustand. Ist das Zeichen ein '(', dann erkennt der Scanner, dass das ein Token sein muss, da es keine sinnvolle Weiterführung geben kann.

    Liest er beispielsweise ein 'i', dann erkennt der Scanner, dass es sich um einen Bezeichner handelt und liest so lange Buchstaben und Zahlen, bis was anderes kommt. Das andere gehört dann möglicherweise zum nächsten Token. Möglicherweise, da ein Whitespace zu keinen Token gehört.

    Ein anderer Fall ist das '+'. Das könnte ein Token sein. Er muss aber in das nächste Zeichen schauen. Ist es ein '=' oder '+', dann gehört das auch noch zum Token. Ist es was anderes, dann war das Token mit dem '+' schon vollständig.



  • achso!
    ich les also ein zeichen, und entscheide dann anhand dieses zeichens, wie es weitergeht!

    das geht aus diesem beispielscanner nicht so gut hervor.

    der beispielscanner/parser macht es so: es wird sozusagen "just-in-time" geparst. also: token lesen, dann sofort parsen.

    wäre es nicht besser, zuerst das script ganz einzulesen und alle tokens in eine liste, und alle bezeichner in einen suchbaum zu speichern?



  • Wenn ich mich nicht grob irre, ist die übliche Praxis durchaus zwei Durchläufe zu machen, jedoch erstmal alle Token nur in einer Liste zu speichern. Token kann dabei Befehl/Schlüsselwort oder eben Bezeichner sein. Ein Token muss auch nicht Text sein, Du kannst durchaus auch eine Node-Klasse machen, von der so was wie "intToken" abgeleitet ist o.ä.

    Die Liste würde ich dann danach parsen, also in einen Baum stecken, wie es eben vernünftig ist.



  • #include <iostream>
    #include <string>
    
    char CurrentChar;
    
    std::string Input;
    std::size_t Pos;
    
    void Init();
    void NextChar();
    bool NextToken();
    
    void Init()
    {
    	Input = "void Func(int a, double b) { Blub(); }";
    	Pos = 0;
    
    	NextChar();
    }
    
    void NextChar()
    {
    	if (Pos > Input.length())
    		CurrentChar = Input[Pos++];
    	else
    		CurrentChar = Input[Pos++];
    }
    
    bool NextToken()
    {
    	while (CurrentChar == ' ' || CurrentChar == '\r' || CurrentChar == '\n' || CurrentChar == '\t')
    		NextChar();
    
    	if (isdigit(CurrentChar))
    	{
    		std::string buf;
    
    		while (isdigit(CurrentChar))
    		{
    			buf += CurrentChar;
    
    			NextChar();
    		}
    
    		std::cout << "Zahl: " << buf << std::endl;
    
    		return true;
    	}
    	else if (isalpha(CurrentChar))
    	{
    		std::string buf;
    
    		while (isalnum(CurrentChar))
    		{
    			buf += CurrentChar;
    
    			NextChar();
    		}
    
    		if (buf == "void" || buf == "int" || buf == "double")
    		{
    			std::cout << "Typ: " << buf << std::endl;
    		}
    		else
    		{
    			std::cout << "Bezeichner: " << buf << std::endl;
    		}
    
    		return true;
    	}
    	else if (CurrentChar == '(')
    	{
    		std::cout << "Zeichen: (" << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else if (CurrentChar == ')')
    	{
    		std::cout << "Zeichen: )" << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else if (CurrentChar == ',')
    	{
    		std::cout << "Zeichen: ," << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else if (CurrentChar == '{')
    	{
    		std::cout << "Zeichen: {" << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else if (CurrentChar == '}')
    	{
    		std::cout << "Zeichen: }" << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else if (CurrentChar == ';')
    	{
    		std::cout << "Zeichen: ;" << std::endl;
    
    		NextChar();
    
    		return true;
    	}
    	else
    	{
    		if (CurrentChar != 0)
    			std::cout << "Unbekanntes Zeichen: " << CurrentChar << std::endl;
    	}
    
    	return false;
    }
    
    int main()
    {
    	// Initialisieren
    	Init();
    
    	// Token lesen
    	while (NextToken())
    		;
    }
    

    Das ist genau das, was der Artikel auch beschreibt. Nur das es im Artikel Objektorientierter gelöst ist.

    Anstatt ein bool kannst du auch ein eigenes Objekt zurückgeben.



  • ja, das ist genauso, wie ich mir das vorgestellt hatte.

    solange kein leerzeichen erreicht wurde, wird alles in einen buffer gelesen.
    dieser buffer wird mit einer liste von tokens ("int", "void" usw.) verglichen.

    wenn kein token erkannt wurde, ist es ein bezeichner.

    danke.



  • niemand. schrieb:

    achso!
    ich les also ein zeichen, und entscheide dann anhand dieses zeichens, wie es weitergeht!

    das geht aus diesem beispielscanner nicht so gut hervor.

    der beispielscanner/parser macht es so: es wird sozusagen "just-in-time" geparst. also: token lesen, dann sofort parsen.

    wäre es nicht besser, zuerst das script ganz einzulesen und alle tokens in eine liste, und alle bezeichner in einen suchbaum zu speichern?

    Du denkst zu konkret. Der Artikel soll zeigen, wie ein Parser prinzipiell funktioniert. Nicht unbedingt, wie er geschrieben werden soll. Er kann so geschrieben werden, aber das passt nicht überall.

    Ich habe zahlreiche Parser geschrieben, die Daten direkt vom Netzwerk parsen. Da holt sich der Scanner nicht die Zeichen von einer Quelle sondern wenn Daten vom Netzwerk kommen, werden sie dem Scanner zugeschoben. Dadurch kann man nicht blockierend lesen. Es wird nur so weit geparst, wie Daten kommen. Da muss dann das Programm ganz anders strukturiert sein. Vom Prinzip funktioniert das aber genauso.

    Parser parsen halt eben nicht einfach nur Programme sondern auch beispielsweise Netzwerkprotokolle oder Konfigurationsdateien.



  • Da die Karperung des Beitrags wie es aussieht vorbei ist, mach ich jetzt wieder weiter.

    Ein kleiner Zwischenstand:

    Ich habe das Ganze jetzt so gelöst, dass der Lexer zusätzlich überprüft ob Befehl und die dazugehörenden Parameter passen. (Überprüfung ob die Art und Anzahl der Parameter stimmt.)
    Somit muss der Parser nur mehr die Werte auf Plausibilität prüfen.
    Weiters kann so der Parser bei groben Fehlern im Skript abbrechen und der zeitaufwendige Parser muss nicht durchlaufen.

    Ich bin mit dem Lexer so gut wie fertig.
    Es fehlen nur ein paar selten bzw. nicht verwendete Befehle.
    Der Rest läuft schon einwandfrei.

    Der Parser mit der Plausibilitätsprüfung wird eine harte Nuss.
    Aber dass ist eine andere Geschichte.


Anmelden zum Antworten