Ich brauche ein paar Tipps für einen kleinen Parser

Ich bin zwar nicht der Threadersteller, aber wollte ihn insofern in Schutz nehmen und darauf hinweisen, dass der Artikel zwar ausschließlich C++ ist, aber auch Beispielcodes (als Download) in C, C++ und C# zu finden sind.

tntnet

Muss er vor mir geschützt werden? Ich bin doch eigentlich ein ganz harmloser. Ich versuche sogar hier im Forum freiwillig zu helfen und niemanden was anzutun. Aber gut - ich habe die Beispiele tatsächlich nicht gesehen. Also gute Ergänzung.

niemand. 0

also jetzt hab ich mich hier registriert.

mein problem ist folgendes:
wie ich jetzt schon mehrmals sagte, im beispielparser sind die tokens nur ein zeichen, deswegen kann man sie einfach aus dem inputbuffer heraus mit case oder if vergleichen.

wenn ich jetzt aber mehrzeichige tokens habe, dann geht das nicht.

meine frage ist: wie mache ich das dann?

meine idee wäre:
ich lese alles bis zum leerzeichen und speichere das gelesene in einem extra buffer.
z.b.

int variable = 5;

Pseudocode:

solage input[counter] ist nicht ' '
     extra_buffer[i] ist input[counter]
     counter=counter+1
     i=i+1
solange_ende

wenn (stringcompare(extra_buffer,"int") ist 0)
     --> token int gefunden
wenn nicht
     --> error (token unbekannt)

so?

tntnet

Du irrst. Im Beispielparser ist "45" ein Token. Und das besteht aus 2 Zeichen. Nämlich '4' und '5'. Schau Dir die Methode getNextToken genau an. Im case-Zweig, wo eine Ziffer erkannt wird, wird so lange readNextChar aufgerufen, wie weitere Ziffern folgen.

niemand. 0

tntnet schrieb:

Du irrst. Im Beispielparser ist "45" ein Token. Und das besteht aus 2 Zeichen. Nämlich '4' und '5'. Schau Dir die Methode getNextToken genau an. Im case-Zweig, wo eine Ziffer erkannt wird, wird so lange readNextChar aufgerufen, wie weitere Ziffern folgen.

ja. aber das geht nur, weil man "isdigit" verwenden kann.

ich glaube schon, dass man bei mehrzeichigen tokens das so machen muss, wie in meinem pseudocode.

es geht hier jetzt nicht um die zahl, sondern um mehrzeilige tokens.

der scanner ausm code holt sich einfach das nächste zeichen, weil ja wie gesagt die tokens nur einzeilig sind. aber wenn ich mehrzeilige tokens habe, muss ich logischerweise auch mehr zeichen auf einmal holen.
wenn ein token "int" ist, dann bringt es nichts, wenn ich mir das erste zeichen 'i' hole. ne, da muss ich schon das ganze wort (d.h. lesen bis zum trennzeichen ' ') berücksichtigen.

wie gesagt, meine lösungsstrategie wäre, solange zu lesen, wie kein leerzeichen ist, und das gelesene in einen extra-buffer zu speichern. dann am ende noch ein '\0' und dann das gelesene mit einer liste von tokens vergleichen. wenn der extra-buffer mit keinem token übereinstimmt, dann liegt ein schreibfehler vor (z.b "Int" statt "int").

wie soll man denn sonst mehrzeichige tokens erkennen?

tntnet

Dein Beispiel ist nicht so weit von der Lösung entfernt. Allerdings vermischst Du noch die Aufgabe des Scanners und Parsers.

Der Scanner erkennt nur Tokens. Im Falle eines Scanners für C- oder C++-Code ist "int" ein gültiges Token. Aber auch "Int", da das ja ein Variablen- oder Funktionsname sein kann. "int1" ist auch ein Token. Oder "+=", "+", "-" aber "=+" ist kein gültiges Token. Die Aufgabe des Scanners ist es, einfach gültige Tokens zu sammeln unabhängig vom Kontext.

Wenn man so einen Scanner schreibt, hat dieser beim lesen einen Zustand. Wenn er beispielsweise bisher "in" gelesen hat und dann ein '=' folgt, dann ist das Token zu ende. Hat er bisher "+" gelesen und dann folgt ein '=', dann ergibt das das Token "+=".

Auch hilft die Idee bis zum Leerzeichen zu lesen eben nicht, da beispielsweise die Zeichenfolge "(5+value)" zwar kein Leerzeichen enthält, aber dennoch 5 Tokens ergibt. Nämlich "(", "5", "+", "value" und ")".

Ob man jetzt isdigt verwendet oder wie auch immer, ist demjenigen überlassen, der das implementiert.

niemand. 0

ok, ich verstehe jetzt so langsam, was du meinst.

aber wie kann ich dann ein einzeiliges token von einem mehrzeiligen unterscheiden?

beispiel:
"int": 3 buchstaben (1 "wort"), aber nur 1 token
"(5+2)": 5 buchstaben (1 "wort"), aber 5 verschiedene tokens

also, sagen wir mal, ich lese zeichenweise:
"int": 3 buchstaben, 3 tokens ( 'i' , 'n' , 't' )
"(5+2)": 5 buchstaben, 5 tokens( '(' , '5' , '+' , '2' , ')' )

sorry für meine ausufernde fragerunde hier, aber das mit scanner und parser interessiert mich.

tntnet

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.

niemand. 0

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?

Eisflamme

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.

niemand. 0

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.

tntnet

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.