Seltsames Problem mit kontextfreier Grammatik

Ich habe also eine angemessene Zeit damit verbracht, die Grammatik (und die Bison-Ausgabe) auszuwählen und kann nicht sehen, was hier offensichtlich falsch ist. Ohne die Mittel, um es auszuführen, kann ich nicht leicht herausfinden, was durch Experimente vor sich geht. Daher sind hier einige konkrete Schritte, die ich normalerweise beim Debugging von Grammatiken durchlaufe. Hoffentlich können Sie all diese Dinge tun, die Sie noch nicht getan haben, und dann möglicherweise Follow-ups (oder bearbeiten Sie Ihre Frage) mit allen Ergebnissen, die aufschlussreich sein könnten:

1. Entwirf die kleinste (in Bezug auf die Anzahl der Tokens) mögliche Arbeitseingabe und die kleinstmöglichen nicht funktionierenden Eingaben basierend auf den Regeln, die du anwenden möchtest.
2. Erstellen Sie eine Kopie der Grammatikdatei, die nur die lästigen Regeln und so wenig weitere unterstützende Regeln enthält, wie Sie bekommen können (dh Sie möchten eine Sprache, die nur Sequenzen aus den Regeln object und more_object erlaubt , zusammen mit ARROW. Funktioniert das wie erwartet?
3. Funktioniert die Regel, in der sie verschachtelt ist, wie erwartet? Versuchen Sie, object durch eine andere sehr einfache Regel zu ersetzen (indem Sie einige Token verwenden, die anderswo nicht vorkommen), und sehen Sie, ob Sie diese Token einschließen können, ohne dass alles andere kaputt geht.
4. Run Bison mit --report=all . Überprüfen Sie die Ausgabe, um zu versuchen, die von Ihnen hinzugefügten Regeln und die von ihnen betroffenen Status zu verfolgen. Versuche diese Regeln zu entfernen und wiederhole den Prozess - was hat sich geändert? Dies ist oft sehr zeitaufwendig und ist ein großer Schmerz, aber es ist ein guter letzter Ausweg. Ich empfehle einen Bleistift und etwas Papier.

Betrachten Sie die Struktur Ihrer Fehlerausgabe - '+' wird als Bezeichner-Token erkannt und wird daher als Symbol nachgeschlagen. Es könnte sich lohnen, Ihren Lexer zu überprüfen, um zu sehen, wie er Bezeichner-Token verarbeitet. Sie könnten einfach versehentlich zu viel greifen. Als weitere Debugging-Methode könnten Sie einige dieser Token-Literale (z. B. '+', '{', usw.) in echte Token umwandeln, damit die Fehlerberichte von Bison Ihnen ein wenig helfen können.

EDIT: OK, je mehr ich mich damit beschäftigt habe, desto mehr bin ich davon überzeugt, dass der Lexer nicht unbedingt so funktioniert, wie er sein sollte. Ich würde überprüfen, ob der Tokenstrom von yylex () Ihren Erwartungen entspricht, bevor Sie fortfahren. Insbesondere sieht es aus wie eine Reihe von Symbolen, die Sie für besonders halten (z. B. '+' und '{') werden von einigen Ihrer regulären Ausdrücke erfasst oder zumindest für Kennungen übergeben.

Sie erhalten keine Shift / Reduce-Konflikte, weil Ihre Regeln mit object_name und more_objects richtig rekursiv sind - und nicht mit den linksrekursiven Regeln, die Yacc (Bison) am natürlichsten behandelt.

Bei klassischem Yacc würden Sie feststellen, dass Sie den Stack-Bereich mit einer ausreichend tiefen Verschachtelung der Notation " object->name->what->not " nicht nutzen können. Bison erweitert seinen Stack zur Laufzeit, so dass Sie nicht mehr genügend Arbeitsspeicher zur Verfügung haben müssen, was heutzutage viel schwieriger ist als bei Computern mit einigen Megabyte Arbeitsspeicher (oder weniger).

Ein Ergebnis der Rechtsrekursion ist, dass keine Reduktionen auftreten, bis Sie den letzten der Objektnamen in der Kette (genauer gesagt ein Symbol darüber hinaus) gelesen haben. Ich sehe, dass Sie die Rekursion auch mit Ihrer statement_list -Regel verwendet haben - und auch an einigen anderen Stellen.

Ich glaube, Ihr Hauptproblem besteht darin, dass Sie keinen Unterbaumkonstruktor definieren konnten in deinem Objekt Subgrammar. (EDIT: OP sagt, er hat die semantischen Aktionen für verlassen Objekt aus seinem Beispieltext. Das ändert die folgende Antwort nicht).

Wahrscheinlich müssen Sie auch die Objekte in der angegebenen Reihenfolge nachschlagen. Vielleicht beabsichtigten Sie:

Ich gehe davon aus, dass wenn Sie eine Kennung X selbst findet, Ihre Standardinterpretation ist, dass es ein variabler Name ist. Aber wenn Sie X - & gt; Y, dann auch wenn X ist ein Variablenname, wollen Sie das Objekt X mit Unterobjekt Y.

Was LookupVarOrObject tut, ist die Suche nach dem am weitesten links Bezeichner, um festzustellen, ob es sich um eine Variable handelt (und im Wesentlichen den gleichen Wert wie idlookup zurückgeben, der einen AST-Knoten des Typs AST_VAR erzeugen muss), oder sehen, ob es ein gültiger Objektname ist, und einen AST-Knoten zurückgeben, der als AST_OBJ markiert ist, oder beschweren, wenn der Bezeichner keiner von diesen ist.

Was LookupSubject tut, ist, seinen linken Operanden zu überprüfen, um sicherzustellen, dass es sich um eine AST_OBJ handelt (oder eine AST_VAR, deren Name mit dem eines Objekts identisch ist). und beschweren, wenn es nicht ist. Wenn dies der Fall ist, sucht es das yytext-child-Objekt von die benannte AST_OBJ.

BEARBEITEN: Basierend auf Diskussionskommentaren in einer anderen Antwort, Rechtsrekursion im OP-Original Die Grammatik könnte problematisch sein, wenn die semantischen Prüfungen des OP den globalen Lexer-Zustand (yytext) prüfen. Diese Lösung ist links-rekursiv und wird nicht mit dieser speziellen Falle in Konflikt geraten.

id_lookup    : IDENTIFIER

ist formal identisch mit

Objektname    : IDENTIFIER

und object_name würden alles akzeptieren, was id_lookup nicht tun würde, also assertLookup (yytext); läuft wahrscheinlich auf allem, was wie IDENTIFIER aussieht und wird nicht von enother-Regel angenommen, nur um zwischen den 2 und dann object_name kann nicht akzeptieren, weil einzelne Lookahead verbietet das.

Für die Twilight-Zone werden die zwei Zeichen, für die Sie Fehler erhalten haben, nicht als Token deklariert, die die Zone des nicht erfüllten Verhaltens öffnen und Parser veranlassen könnten, sie als potentielle Identifikatoren zu behandeln, wenn sich die Grammatik löst.

Ich habe gerade versucht, muscl in Ubuntu 10.04 mit bison 2.4.1 auszuführen und konnte beide Beispiele ohne Syntaxfehler ausführen. Meine Vermutung ist, dass Sie einen Fehler in Ihrer Version von Bison haben. Lass mich wissen, ob ich deinen Parser irgendwie falsch laufen lasse. Unten ist die Ausgabe aus dem ersten Beispiel, das Sie angegeben haben.

./muscle < ./test1.m (this was your first test)