Ich brauche ein paar Tipps für einen kleinen Parser

Da der Fred gekarpert wurde, werde ich mich jetzt kurz halten damit der andere ungestöhrt weitermachen kann.

@*** tutorial ***
Danke für den Link
Der hat mir sehr geholfen.
Danach hatte ich gesucht.
Leider finde ich seit einiger Zeit mit der Foren-Suche kaum mehr etwas.

Da das Skript, dass ich überprüfe nicht Zeichenbasierend sondern Wortbasieren ist, werde ich den Lexer etwas anpassen müssen.
Zum Glück ist alles durch Leerzeichen getrennt und Zeilenbasierend, was das Ganze extrem erleichtert.
(Auch wenn dass trotzdem immer noch eine aufwändige Arbeit sein wird.)

Was ich bisher hatte war ein Batzen aus einer Klasse in der der Lexer die Parseraufgaben gleich mit erledigt hat.
(War nicht sehr effektiv.)

@Bashar
Das hatte ich befürchtet.
Aber da ist dann der Schritt zur Simulation nicht mehr so groß.

mfg Bernd

also, ich hab mir jetzt nochmal den quellcode vom beispielinterpreter angesehen.

es ist tatsächlich so, dass (in diesem beispiel) zeichen für zeichen geparst wird.
dies geht aber, wie ich ja schon sagte, nur dann, wenn man tokens hat, die nur ein zeichen lang sind ('+' '-' '*' '/' usw.).

wie macht man das jetzt am besten, wenn man mehrzeichige tokens hat? wie z.b. jetzt "int"?

macht man das jetzt so?

so in etwa? schrieb:

@tntnet:

machst du das dann in etwa so:

// "int"
if( array[i] == 'i')
{
    if(array[i+1] == 'n')
    {
         if(array[i+2] == 't')
         {
              printf("'int' gefunden an Position %d\n",i);
         }
    }
}

so in etwa?

?

Bashar

Im Prinzip ja. Das ist ja nichts anderes als ein Teil eines Lexers, den du da zeigst. Auch wenn man das in der Regel datengetrieben machen würde anstatt die if-else-Zweige in der Form auszuprogrammieren.

zwutz

Du speicherst die eingelesenen Zeichen in einem Puffer.
Wenn du zu einem Zeichen kommst, dass für den aktuellen Zustand ein Trennzeichen darstellt, siehst du dir den Puffer an, speicherst das entsprechende Token und leerst ihn wieder.
Danach wechselst du in einen Zustand der vom vorigen vorgegeben wird.
Natürlich musst du auch die Möglichkeit haben, den aktuellen Zustand anhand des Pufferinhalts zu erraten (was gerade zu Beginn von Anweisungen notwendig ist)

Danach hast du idealerweise eine Liste von Tokens, mit denen du dann deinen Parser füttern kannst

(Im Beispielartikel ähnlich wie bei den Zahlen, die ja auch aus mehreren Ziffern bestehen können)

zwutz schrieb:

Du speicherst die eingelesenen Zeichen in einem Puffer.
Wenn du zu einem Zeichen kommst, dass für den aktuellen Zustand ein Trennzeichen darstellt, siehst du dir den Puffer an, speicherst das entsprechende Token und leerst ihn wieder.
Danach wechselst du in einen Zustand der vom vorigen vorgegeben wird.
Natürlich musst du auch die Möglichkeit haben, den aktuellen Zustand anhand des Pufferinhalts zu erraten (was gerade zu Beginn von Anweisungen notwendig ist)

Danach hast du idealerweise eine Liste von Tokens, mit denen du dann deinen Parser füttern kannst

(Im Beispielartikel ähnlich wie bei den Zahlen, die ja auch aus mehreren Ziffern bestehen können)

entschuldigung, aber das versteh ich nicht ganz.

sagen wir mal so als gedankenspiel, ich würde einen c-parser schreiben wollen.
eine zeile in dem zu parsenden code wäre
int variable = 5;

soweit ich das jetzt verstanden habe, willst du das so machen:

char buffer[100];
int i=0;
while(input[i] != ' ')
{
    buffer[i]=input[i];
}
buffer[i+1]='\0';

if( strcmp(buffer,"int") == 0)
{
    printf("'int' gefunden\n");
}

Bashar schrieb:

Im Prinzip ja. Das ist ja nichts anderes als ein Teil eines Lexers, den du da zeigst. Auch wenn man das in der Regel datengetrieben machen würde anstatt die if-else-Zweige in der Form auszuprogrammieren.

was genau meinst du mit "datengetrieben"?

edit:
da fehlt ein i++;

der code müsste also richtrig heißen:
char buffer[100];
int i=0;
while(input[i] != ' ')
{
buffer[i]=input[i];
i++; // !
}
buffer[i+1]='\0';

if( strcmp(buffer,"int") == 0)
{
printf("'int' gefunden\n");
}

tntnet

brauche nochmal hilfe schrieb:

also, ich hab mir jetzt nochmal den quellcode vom beispielinterpreter angesehen.

es ist tatsächlich so, dass (in diesem beispiel) zeichen für zeichen geparst wird.
dies geht aber, wie ich ja schon sagte, nur dann, wenn man tokens hat, die nur ein zeichen lang sind ('+' '-' '*' '/' usw.).

wie macht man das jetzt am besten, wenn man mehrzeichige tokens hat? wie z.b. jetzt "int"?

Schau Dir das Tutorial nochmal genau an. Dort gibt es eine Methode "readNextToken". Und die liefert ein Token , welches durchaus auch aus mehreren Zeichen bestehen kann. Ein C-Compiler sammelt möglichst lange Zeichenfolgen, die ein Token bilden können. Also beispielsweise "45", oder "Hallo" oder "<<" oder "+", aber nicht "45+". Der Tokenizer erkennt, dass nach einer 4 und 5 nur weitere Ziffern folgen dürfen. Und wenn da was anderes kommt, dann ist es ein neues Token. Die Zeichenfolge "45+" liefert dann beim ersten Aufruf das Token "45" und beim zweiten "+". Der Parser arbeitet mit den Tokens und gibt denen einen Sinn.

So nebenbei bemerkt gab es beim Problem beim Parsen von C++ bei verschachtelten Templates. So liefert ein Tokenizer bei "vector<vector<int>>" die Tokens "vector", "<", "vector", "<", "int" und ">>". Das letzte passt da eben nicht. Daher musste man vor C++11 ein Leerzeichen zwischen die ">>" schreiben, damit der Tokenizer das als 2 getrennte Tokens erkennt.

ich hab mir den c-quelltext angeschaut.

da gibts die funktion "void Scanner_readNextChar(Scanner *scanner)" aus dem code "Scanner.c".

die funktion überprüft lediglich, ob bereits das bufferende erreicht wurde.
wenn nicht, dann wird einfach das nächste zeichen aus dem buffer geparst.

könntest du nicht mal ein kleines codestückchen herzeigen?

wie gesagt, der beispielparser liest jedes zeichen einzeln.
dh "45+" wird automatisch zu "45" (per "isdigit") und zu "+".

wie müsste die funktion readNextChar aussehen, wenn das token mehr als 1 zeichen hätte?

Zunächst solltest du mal differenzieren zwischen Scanner und Parser. Das geht bei dir völlig durcheinander.

Das was du willst, ist ein Scanner/Lexer. Die Funktion, die du hier zeigst, ist nur eine Hilfsfunktion, um das nächste Zeichen einzulesen und das Ende der Eingabe zu erkennen.

Das was für dich interessant ist, ist die Funktion Scanner_getNextToken.

Diese Funktion schaut sich das erste Zeichen an und schließt daraus, was als nächstes folgen kann.

Im Fall von 0 bis 9 ist das eine Zahl, und darauf kann eine weitere Zahl folgen, welche in einem Buffer gespeichert wird.

Und genau so, solltest du das auch machen.

Im Prinzip musst du nur dein Token TT_INT definieren und dann folgendes erweitern:

case 'a': /* usw...*/ case 'z': case 'A': /* usw...*/ case 'Z':
while (ischar(scanner->curCh))
{
 if (bufPos >= SCANNER_BUF_MAX - 1)
 {
  fprintf(stderr, "Scanner-Error: Zahl ueberschreitet maximale Laenge\n");
  return NULL;
 }

  buf[bufPos] = scanner->curCh;

  Scanner_readNextChar(scanner);

  ++bufPos;
}

buf[bufPos] = '\0';
// Wenn in buf = int ist, dann
Token_set(token, TT_INT, 0);
break;

es geht um die "switch()" schleife in dieser funktion.

ich glaub, wir reden aneinander vorbei.

wenn ich nur ein token habe das 1 char hat, zb. '+',
dann kann ich schreiben:

switch(eingelesenesZeichen)
{
    case '+':
       //...
}

wie mach ich das, wenn ich jetzt einen "int" habe?

switch(eingelesenerBuffer)
{
    case "int":
       //...
}

geht wahrscheinlich nur in c++

desweiteren verstehe ich nicht ganz, wie ich das lesen soll
beispiel:

intVariablenname;

gibt natürlich einen error.
aber wie soll ich das feststellen?

der beispeilcode liest, solage "isdigit()", aber hier habe ich nur zeichen.
verstehst du mein problem?

Eisflamme

switch auf Strings geht nicht, da musst Du ifs benutzen. Ein switch ist übrigens keine Schleife. Schleifen können sich wiederholen, ein switch hat nur Sprünge nach vorne.

intVariablenname;

Na ja, da darf int als Token nicht erkannt werden. Also muss geprüft werden, was hinter dem int kommt und da sind nur bestimmte Zeichen zulässig. Oder anders gesagt: Dort sind keine Zeichen zulässig, die den Namen erweitern können, also vermutlich [a-ZA-Z_0-9], um's Mal regextechnisch auszudrücken.

Ich habe dir genau das demonstriert. Das einzige was fehlt ist das strcmp.

case "string":

Das geht weder in C noch in C++. Dafür müsstest du schon z.B. C# verwenden.

Wenn dir aber solches Wissen fehlt, und du obigen Code nicht verstehst, dann solltest du erst mal die Grundlagen lernen, bevor du dich an so ein Projekt traust. Es wird nicht einfacher.

Selbigen Codeausschnitt findest du im Artikel auch in C++. Das ist vielleicht besser verständlich, als in C. Falles es dann aber noch immer nicht klingelt, dann ist das Projekt echt noch eine Nummer zu hoch für dich.

tntnet

blubb blubb blubb schrieb:

ich hab mir den c-quelltext angeschaut.

da gibts die funktion "void Scanner_readNextChar(Scanner *scanner)" aus dem code "Scanner.c".

die funktion überprüft lediglich, ob bereits das bufferende erreicht wurde.
wenn nicht, dann wird einfach das nächste zeichen aus dem buffer geparst.

könntest du nicht mal ein kleines codestückchen herzeigen?

wie gesagt, der beispielparser liest jedes zeichen einzeln.
dh "45+" wird automatisch zu "45" (per "isdigit") und zu "+".

wie müsste die funktion readNextChar aussehen, wenn das token mehr als 1 zeichen hätte?

Welchen c-Quelltext? Ich rede von dem Tutorial, welcher hier schon mal verlink wurde: http://www.c-plusplus.net/forum/268247. Das ist kein C sondern ausschließlich C++. Da gibt es eine Methode Token Scanner::getNextToken() . Die liefert das nächste Token, welches durchaus aus mehreren Zeichen bestehen kann. Und "45" ist kein Zeichen und is digit kann das schon gar nicht erzeugen.

Hast Du das Tutorial gelesen? Ich würde dich ja fragen, ob Du es verstanden hast, aber das hast Du offensichtlich nicht. Lies es Dir bitte Durch und versuche es zu verstehen. Ich bringe hier keine Codebeispiele, da in dem Tutorial bereits ausreichend Beispiele zu finden sind.

Wenn Du Probleme hast, das Tutorial zu verstehen, dann frag ganz konkret, was Du dort nicht verstehst.

Und noch ein Tipp: registrier dich mal hier im Forum. Es ist ein wenig lästig sich mit jemanden zu unterhalten, wenn man aufgrund der Antworten raten muss, wer das eigentlich ist.

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.