Ich brauche ein paar Tipps für einen kleinen Parser

[(monty) python]

tntnet schrieb:

(monty) python schrieb:

ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.

Ich gehe davon aus, dass der python-parser weder noch tut. Er wird wie bei Parsern üblich zeichenweise lesen. Und wenn da eine puffernde Schicht dazwischen ist, dann ist das sehr effizient.

also pures fgets()?

[tntnet]

(monty) python schrieb:

tntnet schrieb:

(monty) python schrieb:

ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.

Ich gehe davon aus, dass der python-parser weder noch tut. Er wird wie bei Parsern üblich zeichenweise lesen. Und wenn da eine puffernde Schicht dazwischen ist, dann ist das sehr effizient.

also pures fgets()?

Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.

[vorteil?]

tntnet schrieb:

Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.

warum ZEICHENWEISE? was hat das für einen vorteil?

keine ahnung, wie du mit einzelnen zeichen irgendwas parsen willst.

wenn ich die ganze zeile einlese, kann ich mit strcmp arbeiten.

[tntnet]

vorteil? schrieb:

tntnet schrieb:

Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.

warum ZEICHENWEISE? was hat das für einen vorteil?

keine ahnung, wie du mit einzelnen zeichen irgendwas parsen willst.

wenn ich die ganze zeile einlese, kann ich mit strcmp arbeiten.

Lese mal den Artikel über Parser. Was ist wenn Dein Format gar nicht Zeilenweise organisiert ist? Dann kannst Du mit einer Zeile gar nichts anfangen.

Ein Zeichen löst im Parser jeweils einen Zustandsübergang aus, der möglicherweise Aktivitäten auslöst. So funktioniert ein Parser halt. Ein Parser, der Zeichenweise verarbeitet, ist letzten Endes leichter zu implementieren, also so ein strcmp-strstr-strtok-usw.-parser, der leider viel zu oft implementiert wird, weil die Leute nicht wissen, wie man Parser baut. Strcmp ist naheliegend aber leider in aller Regel eine schlechte Lösung.

[zeilenweise]

ja, in der anleitung wird ja auch ein parser auf der basis von "1 + 2" erklärt.

in einer richtigen programmier- oder skriptsprache hast du aber tokens, z.b. "int".

du liest also die ganze zeile
int var1 = 5;

jetzt kann ich mit strcmp das allerste wort mit einer reihe von tokens vergleichen.

wenn du das ganze zeichenweise liest, dann hast du ein 'i'.
keine ahnung, 'i' kann so ziemlich alles bedeuten.

der parser in der anleitung ist schon ok, man sollte nur nicht alles "wörtlich" nehmen, weil eben in einer funktion nur einzeichen-tokens (wie z.b. '+' oder '-' usw.) vorkommen. da kann man gerne zeichenweise parsen, das ist da wohl das beste.

aber wenn du tokens hast, die mehr als ein zeichen haben, bringt das zeichenweise lesen nix.
ich versteh immernoch nicht ganz, wie genau du z.b. "int" erkennen willst, wenn du immer nur ein zeichen liest.

[tntnet]

Und was ist, wenn der Code so aussieht:

int
var1
= 5
;

?
Oder ein xml-parser der so etwas sieht:

<foo>
<bar
></baz

></foo
>

?

Dann viel Spaß mit strcmp. Schreib mal einen Parser. Vielleicht verstehst Du dann, wie das geht. Ich habe schon so einige Parser geschrieben und ich finde es weitaus einfacher, zeichenweise zu lesen.

Wenn der Parser ein 'i' bekommt und er ist im Zustand "lese Datentyp", dann fügt er den bisher gelesenen Datentypfeld ein 'i' hinzu. Und wenn er dann ein 'n' und ein 't' bekommt, dann machst er das gleiche, da der Zustand sich nicht verändert hat. Und wenn er in dem Zustand dann ein Leerzeichen bekommt, dann wechselt er den Zustand in "Variablenname lesen". Kommt dann wieder ein 'i', dann reagiert er eben anders. Er wird nämlich den bisher gelesenen Variablennamen um das 'i' erweitern.

Na ja - ein wenig vereinfacht, aber im prinzip ist das so. Ich implementiere immer eine Methode "parse(char)", die ein grosses switch(state) statement hat, welches auf die Zustände springt.

[ooookkkkkkk]

ok.

eine frage noch: wie speicherst du variablennamen ab? wahrscheinlich in eine verkettete liste?

wie überprüfst du, ob du den variablennamen schon kennst? dafür kann man doch strcmp nehmen, oder?

[knivil]

Warum muss das physikalische Laden der Datei mit dem Parser gekoppelt sein? Natuerlich muss zeichenweise geparst warden, aber nicht unbedingt eingelesen werden.

dafür kann man doch strcmp nehmen, oder?

Warum sollten Namen in einer Liste sein und nicht in einem Prefix-Tree? Warum bist du so fixiert auf strcmp? Warum ueberhaupt C?

[achso]

ok, an so einen präfixbaum hab ich garnicht gedacht.

[so in etwa?]

@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?

[Bernd_d_B]

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

[brauche nochmal hilfe]

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)

[so??]

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 *]

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.

[blubb blubb blubb]

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?

[muhguuuu]

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;

[mhhhhhhhhh]

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?