Der Haskell-Bericht enthält eine etwas notorische Klausel in den Layoutregeln mit dem Namen " parse-error (t ) ". Der Zweck dieser Regel besteht darin, zu vermeiden, dass der Programmierer geschweifte Klammern in einzeiligen let -Ausdrücken und ähnlichen Situationen schreibt. Der relevante Satz ist:
Der Side-Condition-Parse-Error (t) ist wie folgt zu interpretieren: wenn die bisher durch L erzeugten Token zusammen mit dem nächsten Token t ein ungültiges Präfix der Haskell-Grammatik und die bisher von L erzeugten Token darstellen gefolgt von dem Token "}" stellt ein gültiges Präfix der Haskell-Grammatik dar, dann ist parse-error (t) wahr.
Dies erzeugt eine ungewöhnliche Abhängigkeit, bei der der Lexer notwendigerweise Tokens für den Parser erzeugt und auf Fehler reagiert, die im Parser erzeugt werden, indem zusätzliche Tokens eingefügt werden, die der Parser konsumieren kann. Dies ist im Gegensatz zu so ziemlich allem, was Sie in anderen Sprachdefinitionen finden werden, und kompliziert die Implementierung, wenn sie zu 100% wörtlich interpretiert wird.
Es überrascht nicht, dass kein Haskell-Compiler, von dem ich weiß, die gesamte Regel wie geschrieben implementiert. Zum Beispiel kann GHC den folgenden Ausdruck nicht analysieren , was laut dem Bericht legal ist:
%Vor%Es gibt eine Vielzahl anderer ähnlicher seltsamer Fälle. Dieser Beitrag enthält eine Liste einiger besonders schwieriger Beispiele. Einige dieser GHC funktionieren korrekt, aber es schlägt auch (ab 7.10.1) fehl:
%Vor% Es scheint auch, dass GHC eine undokumentierte Spracherweiterung namens AlternativeLayoutRule hat, die die URL ersetzt parse-error (t) -Klausel mit einem Stapel von Token-Kontexten im Lexer, der in den meisten Fällen ähnliche Ergebnisse liefert; Dies ist jedoch nicht das Standardverhalten.
Was tun reale Haskell-Compiler (einschließlich GHC im Besonderen), um die Parse-Error (t) -Regel während des Lesens zu approximieren? Ich bin neugierig, weil ich versuche, ein einfaches zu implementieren Haskell Compiler und diese Regel stolpert mich wirklich. (Siehe auch diese Frage .)
Ich glaube nicht, dass die parse-error(t) -Regel bedeutet, dass schwer zu implementieren ist. Ja, es erfordert, dass der Parser zurück zum Lexer kommuniziert, aber abgesehen davon, dass es wahrscheinlich relativ einfach entworfen wurde, um mit der dominanten Parsing-Technologie der Zeit zu implementieren: A LALR (1) basiert generierte Parser mit ein wenig Unterstützung für Fehlerkorrektur, wie GNU Bison, oder wie Happy, die GHC verwendet.
Es mag ironisch sein, dass, zumindest teilweise aufgrund Haskells Erfolg bei der Ermöglichung von Parser-Kombinator-Bibliotheken, diese alte Technologie zumindest in der Haskell-Gemeinschaft nicht mehr so dominant ist wie früher.
Ein mit LALR (1) (oder LR (1)) generierter Parser hat die folgenden Eigenschaften, die ziemlich gut damit übereinstimmen, wie die parse-error(t) -Regel beabsichtigt ist:
Happy hat ein spezielles error -Token, mit dem Aktionen ausgeführt werden können, wenn das aktuelle lexikalische Token nicht legal ist. In Anbetracht dessen ist die relevanteste Definition in GHC's Happy Grammatik
vccurly ("virtual close curly") ist das Token, das der Lexer sendet, wenn es selbst entscheidet, eine Layout-Ebene zu schließen. popContext ist eine Aktion, die in der Lexer-Quelle definiert ist Entfernt eine Layout-Ebene aus dem Layout-Stack. (Beachten Sie, dass in dieser Implementierung der error -Fall nicht erfordert, dass der Lexer ein vccurly -Token zurücksendet).
Damit müssen alle GHC-Parser-Regeln andernfalls close als ihr nicht-terminales Token verwenden, um einen mit vocurly geöffneten Einrückungsblock zu beenden. Unter der Annahme, dass der Rest der Grammatik korrekt ist, implementiert dies auch die Regel korrekt.
Oder zumindest ist das die Theorie. Es stellt sich heraus, dass dies manchmal aufgrund anderer Merkmale von Haskell / GHC bricht, die nicht in die LALR (1) Grammatik passen.
Von Ihren beiden obigen Beispielen wurde das erste in Haskell 2010 geändert (weil die Leute gemerkt haben, dass es zu peinlich war, es zu analysieren), also hat GHC dort recht. Aber die zweite ( e = case 1 of 1 -> 1 :: Int + 1 ) passiert wegen einer anderen Design-Entscheidung , die GHC macht:
Es ist schwierig, einen Parser genau die richtige Sprache parsen zu lassen. Der GHC-Parser folgt daher dem folgenden Prinzip:
- Wir analysieren oft "übermäßig großzügig" und filtern die schlimmen Fälle später heraus.
GHC verfügt über ausreichende Erweiterungen, die Int + 1 könnte als Typ analysieren, wobei genügend von ihnen aktiviert ist. Auch ein LARR (1) -Parser zu schreiben, um jede Kombination von aktivierten / deaktivierten Erweiterungen direkt zu behandeln, wäre wirklich peinlich (nicht sicher, ob es überhaupt möglich ist). Es analysiert also zuerst die allgemeinste Sprache und schlägt später fehl, wenn geprüft wird, ob die erforderlichen Erweiterungen für das Ergebnis aktiviert sind. Aber zu diesem Zeitpunkt ist das Parsen beendet und es ist zu spät, um die parse-error -Regel auszulösen. (Oder nehme ich an.)
Schließlich sollte ich sagen, dass ich nicht denke, dass es etwas gibt, das unmöglich ist, die parse-error(t) -Regel zu handhaben, auch wenn Sie keinen (LA) LR (1) -Parser verwenden. Ich vermute, etwas wie GHCs close Token könnte auch in einem Kombinator gut funktionieren. Aber du brauchst immer noch irgendeine Art von Kommunikation zurück zum Lexer.
Tags und Links haskell ghc parsing lexical-analysis