Was hat scannerloses Parsen mit dem "Dangling Else Problem" zu tun?

Ich verstehe diesen Satz nicht aus dem Wikipedia-Artikel über das Dangling Else-Problem :

[Das Dangling Else-Problem] ist ein Problem, das häufig bei der Compilerkonstruktion auftritt, insbesondere beim Parsen ohne Scanner.

Kann mir jemand erklären, wie scannerlose Parsing-Techniken dieses Problem verschlimmern könnten? Es scheint mir, dass das Problem bei der Grammatik liegt - da sie nicht eindeutig ist - und nicht bei der Wahl der Analysetechnik. Was vermisse ich?

Ich vermute, dass der Satz im Wikipedia-Artikel aus einem Missverständnis der Arbeit von E. Visser resultiert.

Grammatiken für scannerlose Parser (dh Grammatiken, die eine Sprache als Satz von Zeichenfolgen anstatt als Satz von Zeichenfolgen beschreiben, wobei die Token separat als Zeichenfolgen beschrieben werden) weisen häufig viele Mehrdeutigkeiten auf. E. Visser-Papier- Disambiguierungsfilter für scannerlose generalisierte LR-Parser (*) schlagen verschiedene Mechanismen zur Lösung von Mehrdeutigkeiten vor, von denen einer zur Lösung des Problems des "Dangling else" nützlich ist. Die Veröffentlichung gibt jedoch nicht an, dass die genaue Mehrdeutigkeit, die als "Dangling else problem" bezeichnet wird, mit scannerlosen Parsern zusammenhängt (und auch nicht, dass der Mechanismus für scannerlose Parser besonders nützlich ist).

Die Tatsache, dass sie einen Mechanismus zur Lösung vorschlägt, ist keine implizite Aussage, da ein weiterer Mechanismus zur Auflösung von Mehrdeutigkeiten (Priorität und Vorrang von Operatoren) auch völlig unabhängig von der Scannerlosigkeit der betrachteten Parser zu sein scheint (bedenken Sie zum Beispiel, dass diese Mehrdeutigkeiten nicht sein können) in regulären Grammatiken vorhanden sind, da sie aus der Verschachtelung resultieren, während diejenigen, die von einer Regel mit der längsten Übereinstimmung behandelt werden,).

(*) Dies ist wahrscheinlich das Papier, das als Grundlage für den Wikipedia-Artikel über scannerlose Parser dient, auch wenn sie auf ein anderes verweisen, ebenfalls von E. Visser, Scannerless Generalized-LR Parsing .

Das Dangling Else-Problem ist eine Mehrdeutigkeit in der Code-Syntaxspezifikation, bei der möglicherweise unklar ist, ob und was sonst zu welchem ​​if gehört.

Das einfachste und klassischste Beispiel:

if(conditionA)
if(conditionB)
   doFoo();
else
   doBar();

Es ist unklar, wer die Besonderheiten der Sprachspezifikation nicht auswendig kennt, der ifbekommt das else(und dieser spezielle Codeausschnitt ist in einem halben Dutzend Sprachen gültig, kann aber in jedem anders abschneiden).

Das Dangling Else-Konstrukt stellt ein potenzielles Problem für scannerlose Parserimplementierungen dar, da die Strategie darin besteht, den Dateistream zeichenweise zu verschlucken, bis der Parser erkennt, dass er genug Token hat (Zusammenfassung in die zu kompilierende Assembly- oder Zwischensprache). . Dadurch kann der Parser den minimalen Status beibehalten. Sobald er glaubt, dass er über genügend Informationen verfügt, um die Token zu schreiben, die er in die Datei geparst hat, wird er dies tun. Das ist das Endziel eines scannerlosen Parsers. Schnelle, einfache und leichte Zusammenstellung.

Unter der Annahme, dass Zeilenumbrüche und Leerzeichen vor oder nach der Interpunktion bedeutungslos sind (wie in den meisten Sprachen im C-Stil), würde diese Anweisung dem Compiler so erscheinen:

if(conditionA)if(conditionB)doFoo();else doBar;

Perfekt zum Parsen mit einem Computer, sehen wir uns das an. Ich bekomme jeweils einen Charakter, bis ich:

if(conditionA)

Oh, ich weiß, was das bedeutet (in C #), es bedeutet " pushconditionA auf dem Eval-Stack und dann call brfalse, um nach dem nächsten Semikolon zur Anweisung zu springen, wenn es nicht wahr ist". Im Moment sehe ich kein Semikolon. Daher setze ich meinen Sprungversatz zunächst auf das nächste Leerzeichen nach dieser Anweisung und erhöhe diesen Versatz, wenn ich weitere Anweisungen einfüge, bis ich ein Semikolon sehe. Weiter zu analysieren ...

if(conditionB)

OK, dies wird zu einem ähnlichen Paar von IL-Operationen analysiert und sofort nach der Anweisung, die ich gerade analysiert habe, ausgeführt. Ich sehe kein Semikolon, daher erhöhe ich den Sprungversatz meiner vorherigen Anweisung um die Länge meiner beiden Befehle (einer für den Push und einer für den Break) und halte Ausschau.

doFoo();

Ok, das ist ganz einfach. Das ist " calldoFoo". Und ist das ein Semikolon, das ich sehe? Nun, das ist großartig, das ist das Ende der Reihe. Ich werde die Sprungversätze meiner beiden Blöcke um die Länge dieser beiden Befehle erhöhen und vergessen, dass es mich jemals interessiert hat. OK, mach weiter ...

else

... Äh-oh. Das ist nicht so einfach, wie es aussah. OK, ich habe vergessen , was ich nur tun, sondern ein elseMittel gibt es eine bedingte break - Anweisung irgendwo , dass ich schon gesehen habe, mich zurückblicken lassen ... yep, gibt es, brfalsedirekt nach schiebe ich einige „conditionB“ auf der Stapel, was auch immer das war. OK, jetzt brauche ich eine unbedingte breakals nächste Aussage. Die Aussage, die danach kommt, ist definitiv das Ziel meiner bedingten Pause. Ich werde also sicherstellen, dass ich sie richtig einsetze, und die bedingungslose Pause, die ich einsetze, inkrementieren. Weiter ...

doBar();

Das ist leicht. " calldoBar". Und es gibt ein Semikolon, und ich habe keine Klammern gesehen. Also, das Unbedingte breaksollte zur nächsten Aussage springen, was auch immer es ist, und ich kann vergessen, dass es mich jemals kümmerte.

Also, was haben wir ... (Anmerkung: Es ist 22:00 Uhr und ich habe keine Lust, Bit-Offsets in hexadezimale Werte umzuwandeln oder die vollständige IL-Shell einer Funktion mit diesen Befehlen auszufüllen. Das ist also nur Pseudo-IL Verwenden von Zeilennummern, bei denen normalerweise Byte-Offsets auftreten würden):

ldarg.1 //conditionA
brfalse <line 6> //jumps to "break"
ldarg.2 //conditionB
brfalse <line 7> //jumps to "call doBar"
call doFoo
break <line 8> //jumps beyond statement in scope
call doBar
<line 8 is here>

Nun, das funktioniert tatsächlich richtig, WENN die Regel (wie in den meisten C-Stil-Sprachen) lautet, dass das elsemit dem nächsten geht if. Eingezogen, um der Verschachtelung der Ausführung zu folgen, wird dies folgendermaßen ausgeführt: Wenn conditionA false ist, wird der gesamte Rest des Snippets übersprungen:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();

... dies geschieht jedoch durch Zufall, da der mit der äußeren ifAnweisung verbundene Umbruch zu der breakAnweisung am Ende der inneren Anweisung springt if, die den Ausführungszeiger über die gesamte Anweisung hinausführt. Es ist ein zusätzlicher unnötiger Sprung, und wenn dieses Beispiel komplexer wäre, könnte es nicht mehr funktionieren, wenn es auf diese Weise analysiert und mit einem Token versehen wird.

Was ist auch, wenn die Sprachspezifikation besagt, dass ein Dangling elsezum ersten ifgehört und wenn BedingungA falsch ist, dann wird doBar ausgeführt, während, wenn BedingungA wahr ist, aber nicht BedingungB, dann nichts passiert, so?

if(conditionA)
    if(conditionB)
       doFoo();
else
   doBar();

Der Parser hatte vergessen, dass es den ersten ifüberhaupt gab, und so würde dieser einfache Parser-Algorithmus keinen korrekten Code erzeugen, geschweige denn effizienten Code.

Jetzt könnte der Parser klug genug sein, um sich an die ifs und elses zu erinnern, die er für eine längere Zeit hat. Wenn jedoch die Sprachspezifikation sagt , dass elsenach zwei ifs Übereinstimmungen eine einzelne mit der ersten übereinstimmt if, führt dies zu einem Problem mit zwei ifs mit übereinstimmenden elses:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();
else
    doBaz();

Der Parser sieht das erste else, stimmt mit dem ersten überein if, sieht dann das zweite und gerät in Panik "Was zum Teufel habe ich nochmal gemacht". Zu diesem Zeitpunkt hat der Parser ziemlich viel Code in einem veränderlichen Zustand, den er viel lieber schon in den Ausgabedateistream gepusht hätte.

Es gibt Lösungen für all diese Probleme und Was-wäre-wenn. Aber entweder der Code, der so intelligent sein musste, erhöht die Komplexität des Parser-Algorithmus, oder die Sprachspezifikation, die es dem Parser ermöglicht, so dumm zu sein, erhöht die Ausführlichkeit des Sprachquellcodes, indem er beispielsweise terminierende Anweisungen wie end ifoder geschachtelte Klammern erfordert blockiert, wenn die ifAnweisung eine hat else(beide werden üblicherweise in anderen Sprachstilen verwendet).

Dies ist nur ein einfaches Beispiel für ein paar ifAussagen und zeigt alle Entscheidungen, die der Compiler treffen musste, und wo es ohnehin sehr leicht durcheinander gekommen sein könnte. Dies ist das Detail hinter dieser harmlosen Aussage von Wikipedia in Ihrer Frage.