Hilfe beim Parsen von eigener Sprache in C++

Hallo!

Ich schreibe gerade an meinem ersten groesseren C++ Projekt und ich bin hier etwas vor ne Wand gelaufen.
Im Prinzip gehts um einen Parser fuer eine einfache, eigene Programmiersprache, der in das fertige Program eingebaut werden soll.
Die Sprache soll nichts koennen als mehrere Anweisungen (getrennt durch ";") zu geben, die entweder als true oder false gewertet werden koennen. Dabei soll auf einen internen "Vorrat" an variablen zugegriffen , und einfache Dinge getestet werden (z.B. "existiert in diesem array ein Objekt mit Wert X").

Ich habe eine Liste an Worten etc., die in der Sprache benutzt werden sollen und versuche jetzt, das ganze effizient (im Sinne vom Code-aufwand, nicht unbedingt Performance-bezogen) zu parsen.

Mein Problem hierbei ist, die verschiedenen Kombinationsmoeglichketen der Schluesselworte zu programmieren.
Ein Beispiel:

vector MUST CONTAIN 5;
vector MUST_NOT CONTAIN "test";
string MUST CONTAIN_ONLY 's';

hier sind (bei den wenigen Beispielen) schon 3 verschiedene funktionen zum parsen noetig:

bool check(int needle, const std::vector<int>& haystack, bool must, bool only)
{
  ...
}

bool check(const std::string& needle, const std::vector<std::string>& haystack, bool must, bool only)
{
...
}

bool check(char needle, const std::string& haystack, bool must, bool only)
{
...
}

Gibt es eine moeglichkeit, sozusagen zentral die noetige Funktion aufzurufen, anstatt das ganze ueber ewige if-else-Abfragen zu regeln?

bool must,only;

if(word2=="MUST")
  must=true;
else 
  must=false;

if(word3=="CONTAIN")
  only=false;
else if(word3=="CONTAIN_ONLY")
  only=true;

if(word1=="vector"&&isdigit(word4))
{
 check(word4,int_vector,must,only);
}
else if(word1=="vector"&&isstring(word4))
{
 check(word4,str_vector,must,only);
}
else if(word1=="string"&&ischar(word4))
{
 check(word4,string,must,only);
}

....

(der code ist jetzt nicht 100% richtig, war nur als Beispiel gedacht)

Das mag ja noch gehen bei 2-3 verschiedenen Typen/Kombinationen, aber ich habe inzwischen viel mehr, und ich frage mich, ob es da nicht einen einfachereren weg gibt als ueber if-else.

Jedwedige Hilfe willkomen

hustbaer

Ich meine es würde helfen erstmal eine Grammatik zu definieren. Dann siehst du ob du die mit einem "formlosen" if-else Parser gebacken bekommst, oder ob es besser/einfacher wäre sich eines Standardmodells ala Recursive-Descent-Parser zu bedienen.

http://en.wikipedia.org/wiki/Recursive_descent_parser

ps: du solltest vermutlich das "Parsen" und das "Ausführen" (Interpretieren) trennen.

Mit Compilerbau hast du dir ein relativ komplexes Thema ausgesucht, aber es gibt viel Info dazu. Google: Compilerbau

Temporary schrieb:

Hallo!

Das mag ja noch gehen bei 2-3 verschiedenen Typen/Kombinationen, aber ich habe inzwischen viel mehr, und ich frage mich, ob es da nicht einen einfachereren weg gibt als ueber if-else.

Jedwedige Hilfe willkomen

Lange if/else-Ketten in Zusammenhang mit Zuständen umgehe ich gerne mit einer State-Event-Machine. Du hast dabei relativ wenig C++-Code und eine Tabelle, in die Du das zuvor gezeichnete State-Event-Diagramm schreibst. Abhängig vom aktuellen State sind gewisse Events (Tokens) erlaubt und andere nicht. Ein Event führt zu einem Zustandsübergang. Dabei kann zusätzlich eine Funktion ausgeführt werden.

State-Machines gibts z.B. in Boost. Für komplexe Sprachen gibts vermutlich noch geeignetere Ansätze.

lg

Bzgl. Compilerbau ist ein Blick in die Theoretische Informatik sehr zu empfehlen, da dort deterministisch endliche Automaten und Sprachen sowie deren Grammatiken gelehrt werden. EBNF ist hier ein besonderes Schlagwort neben den erwähnten Automaten!

Was spricht gegen YACC?

Th69

Der Artikel Interpreterbau sollte dir auch einen Überblick über eine mögliche Parser-Implementierung geben.

Vielen Dank fuer die Antworten, ich werde mich mal durch die gelinkten Artikel durchwaelzen und das mit den boost state-machines probieren.

Famer schrieb:

Was spricht gegen YACC?

Eigentlich nichts, bis auf den Umstand, dass ich das ganze gern selbst machen wuerde (ist sowieso ein Spass-Projekt)

Achso, nadann. Ich dachte, du brauchst den Parser für dein "erstes größeres Projekt". Aber wenn der Parser ebenjenes ist, ist YACC zu benutzen natürlich witzlos ;).
Also dann, auf ins Land der DEAs und formalen Grammatiken, würd ich meinen.