4. Beispiel - Parser

  • 1) Inwieweit sollte man die Grammatik anpassen? Bei "Pars: { id ',' } [ id ] ;" zb mag bison die eckigen Klammern nicht (die afaik die Option ausdrücken, also optionalen Inhalt umschließen). Muss ich diese Teile umformulieren? Wenn wir gleich beim Thema Klammern sind, was bedeuten die geschwungenen Klammern (im Skriptum steht Iteration aber ich kann mir darunter in diesem Zusammenhang nichts vorstellen) bzw die runden Klammern als Metaoperator (also nicht als Literal der geparsten Sprache)

    yacc/bison kann keine EBNF. Du musst die entsprechenden Konstrukte entsprechend umformulieren, sodass yacc/bison damit klarkommt; geschwungene Klammern stehen für Elemente, die beliebig oft vorkommen (also auch ausgelassen werden) dürfen.

    2) Ist es sinnvoll/notwendig alle Lexeme einzeln als Token zu behandeln? Bei den Keywords habe ich jedenfalls keine andere Möglichkeit gefunden.

    Du kannst damit jedenfalls nichts falsch machen. Für Lexeme, die aus einem einzelnen Zeichen bestehen, brauchst du aber keine neuen Tokens definieren, sondern kannst die Zeichen selbst als Token verwenden; im Scanner zum Beispiel:

    Code
    1. ',' RETURN(',');
    2. ':' RETURN(':');


    oder kürzer:

    Code
    1. ','|':' RETURN(yytext[0]);


    im Parser zum Beispiel:

    Code
    1. Par ',' Par


    3) Kennt wer vielleicht noch ein gutes Tutorial?

    Funktionierende Beispiele halte ich neben diversen Tutorials immer für ein gutes Anschauungsmaterial.

  • Prinzipiell würd ich dir raten dir mal die "Allgemeinen Fragen" von der LVA-Homepage durchzulesen. Ich weiß zwar nicht, warum die LVA-Leitung so wichtige Infos so seltsam ausgelagert hat; dort finden sich aber einige Dinge, die mir sehr weitergeholfen haben.

  • Zum Ausführen, nichts aufregendes :D


  • Danke für die Tipps und Hinweise. Ich habe meinen Parser inzwischen so weit, dass nur ein paar Feinheiten bei der Grammatik verbessert werden müssen (aus den Testfällen aus der Newsgroup werden bei mir aktuell 11/13 korrekt bearbeitet).


    Eine kleine Randbemerkung bezüglich einer Kleinigkeit die mich etwas geärgert hat: Es hat ne Weile gedauert bis ich herausgefunden habe, dass man yyerror im Header der Grammatik forward deklarieren muss, ansonsten hat gcc immer gemeckert. Vielleicht hilft das ja noch dem ein oder anderen.


    Edit:
    Wie schlimm sind shift/reduce Konflikte (laut der FAQ sind diese weniger ein Problem als reduce/reduce)? Gibt es ein paar allgemeine Guidelines wie man diese reduzieren kann?

  • Ich erkenne langsam die Natur meiner Konflikte. Es liegt wohl daran wie ich die EBNF Konstrukte aufgelöst habe.


    Zb habe ich

    Code
    1. Program: { Funcdef ';' }
    2. ;


    in

    Code
    1. Program: /*empty*/
    2. | Funcdef ';'
    3. | Program Funcdef ';'
    4. ;


    umgewandelt.


    Das habe ich bei anderen Elementen die beliebig oft vorkommen sollen ähnlich gemacht, was bei mir eine Menge shift/reduce Konflikte auslöst. Muss ich das jetzt in jedem Fall durch Zusatzregeln lösen, die die Mehrdeutigkeiten eliminieren (in den meisten Fällen beziehen sich die Mehrdeutigkeiten auf den /*empty*/ Zustand, ich stelle mir halt die Frage der Sinnhaftigkeit)?


    Vermutlich liegt das ganze an meinem mangelndem Verständnis der ganzen Materie, aber ich frage lieber 3x dumm und habs dann verstanden als ich mach es 1x so "weil es halt so ist" ohne was daraus gelernt zu haben.

  • Wieso nicht gleich so:


    Code
    1. Program:
    2. | Funcdef ';' Program


    Der Sinn der Elimination von Mehrdeutigen ist der, dass die Grammatik dann nicht weiß welchen Weg du eigentlich gehen willst. Im schlimmsten Fall geht sie einen "falschen" Weg und es wird falsch abgeleitet. Wenn du Glück hast, tun beide Wege das gleiche und nichts passiert. Daher ist sinnvoll alle Konflikte zu eliminieren um sicher zu gehen, dass die Grammatik auch das macht was du vorhast.


    Du musst nicht zusätzliche Regeln einführen, oft denkt man zu kompliziert und bekommt dadurch dann die Konflikte (siehe oben).

  • Wenn ich mein make Aufrufe bekomme ich die folgenden Meldungen:


    [u0625723:~/abgabe/parser:577] make
    yacc -d parser.y
    flex -t parser.l > lexer.c
    gcc -Wall lexer.c y.tab.c -o parser -lfl
    <stdout>:1185: warning: âyyunputâ defined but not used
    y.tab.c: In function âyyparseâ:
    y.tab.c:1331: warning: implicit declaration of function âyylexâ



    Wie bekomme ich die 2 Warnings weg?

  • hab im lex-file meine definition der hexzahl geändert:


    (damals im) SCANNER: {HEX} return(strtol(yytext+1, 0, 16));
    (jetzt im) PARSER: {HEX} return(NUMBER);
    ansonsten kann der parser denk ich die hexzahlen nicht als NUMBER (tokenname) erkennen.


    Lieg ich da falsch, ist das unnötig? Für die AG werd ich das dann sowieso umbauen müssen


    Lg,


    derSeb


  • hast du

    Zitat

    #include <stdlib.h>


    bei deinem parser included?

  • Und ich finde trailing commas einen Hauch dümmer :cuss: :cuss: :wein: . Jetzt kann ich schon wieder an meinen Beispielen was ändern, was ich nicht implementiert habe, weil es mir so blöd vorkam, dass ich es als Fehler in der Angabe interpretiert habe (z.B. die Sache mit den in einer Funktion global sichtbaren Variablen ...).


    Trailing Kommas haben ihren Sinn, und erleichtern das Ändern des Codes während der Entwicklung. Beispiel (in C):


    Code
    1. enum {
    2. FIRST,
    3. BLA,
    4. BLUBB,
    5. LALALA
    6. };

    Wenn du jetzt die Zeile mit "LALALA" auskommentierst (gehen wir von C99 aus, also mit "//"), funktioniert der Code noch immer, weil die Kommas am Ende erlaubt sind. Sonst müsstest ein mehrzeilige Kommentar machen, das zwischen BLUBB und dem Komma beginnt und nach LALALA aufhört.


    Idealerweise lässt du das Trailing Komma aber auch bei LALALA dran, dann tust du dir auch mit dem Verschieben von Statements leichter (dd und p in vim), weil du nicht die fehlenden Kommas ergänzen musst, bzw. das überflüssige Komma entfernen musst (zB wenn du im obigen Beispiel die Zeile LALALA hinter FIRST schiebst). Und wenn du mit Git/SVN arbeitest, schauen deine diffs auch schöner (und lesbarer) aus, weil du beim Hinzufügen nur eine Zeile (die neue) ändern musst, statt 2 (Komma hinzufügen in letzter Zeile und danach neue Zeile einfügen).


    Hier das nicht so schöne diff:


    Diff
    1. --- old_bad.c 2009-04-22 12:15:44.000000000 +0200
    2. +++ new.c 2009-04-22 12:15:56.000000000 +0200
    3. @@ -2,6 +2,7 @@
    4. FIRST,
    5. BLA,
    6. BLUBB,
    7. - LALALA
    8. + LALALA,
    9. + NEUES_ELEMENT
    10. };

    Und hier das schöne diff, wo du ein Trailing Komma dabei hast:


    Diff
    1. --- old.c 2009-04-22 12:15:29.000000000 +0200
    2. +++ new.c 2009-04-22 12:15:56.000000000 +0200
    3. @@ -3,5 +3,6 @@
    4. BLA,
    5. BLUBB,
    6. LALALA,
    7. + NEUES_ELEMENT,
    8. };
  • Hallo,
    Bei mir hat leider ein Test fehlgeschlagen da ich denke ich zumindest folegendes übersehen habe: func() x*x+x; end; darf nicht sein und müsste func() x*(x+x); end; lauten oder irre ich mich da ?
    Wenn ich den Fehler nämlich behebe das der oben genannte fall funktioniert schlägt folgender zb. fehl: func x() x*x*x; end; da er bei mir dann Status 2 liefert aber laut
    Abgabesystem Status 0 liefern sollte. Leider hab ich gerade keine Ahnung was jetzt genau das Problem ist.


    mfg Rene

  • Hallo,
    Bei mir hat leider ein Test fehlgeschlagen da ich denke ich zumindest folegendes übersehen habe: func() x*x+x; end; darf nicht sein und müsste func() x*(x+x); end; lauten oder irre ich mich da ?

    So ist es.


    Wenn ich den Fehler nämlich behebe das der oben genannte fall funktioniert schlägt folgender zb. fehl: func x() x*x*x; end; da er bei mir dann Status 2 liefert aber laut
    Abgabesystem Status 0 liefern sollte. Leider hab ich gerade keine Ahnung was jetzt genau das Problem ist.


    In der Grammatik der Angabe steht folgendes:

    Code
    1. Expr: ( not | ’-’ ) Term
    2. | [B]Term { ’+’ Term } [/B]
    3. |[B] Term { ’*’ Term }[/B]

    Überleg dir mal, was das fett Hervorgehobene bedeutet.