Parsing mit benutzerdefinierten Operator Vorrang

Question

OK, also hier ist eine Frage: Angesichts, dass Haskell ermöglicht Ihnen, neue Operatoren mit beliebigen Vorrang Operator definieren ... Wie ist es möglich, tatsächlich Haskell-Quellcode zu analysieren?

Sie können nicht wissen, welche Operatoren Vorrang haben, bis Sie die Quelle analysieren. Sie können die Quelle jedoch erst analysieren, wenn Sie die korrekten Operatorvorgaben kennen. Also ... ähm, wie?

Betrachten wir zum Beispiel, der Ausdruck

x *** y +++ z 

Bis wir das Modul beenden die Analyse, wir wissen nicht, was andere Module importiert werden, und damit, was Operatoren (und andere Identifizierungsmerkmale) könnte in Umfang sein. Wir sicherlich kennen ihre Präzedenzfälle noch nicht. Aber der Parser hat etwas zurückkehren ... Aber es sollte zurückkehren

(x *** y) +++ z 

Oder sollte es zurückgeben

x *** (y +++ z) 

Der arme Parser hat keine Möglichkeit zu wissen. Dies kann nur festgestellt werden, wenn Sie den Import, der (+++) und (***) mit sich bringt, in den Gültigkeitsbereich finden, diese Datei von der Festplatte laden und feststellen, was die Operatorvorgaben sind. Offensichtlich wird der Parser selbst nicht alles I/O machen; Ein Parser verwandelt einen Buchstabenstrom in einen AST.

Offensichtlich hat jemand irgendwo herausgefunden, wie man das macht. Aber ich kann es nicht hinkriegen ... Irgendwelche Hinweise?

Answer 1

Zitiert die page on GHC trac für den Parser:

Infixoperatoren analysiert werden, als ob sie alle Linksassoziativität waren. Der Renamer verwendet die Fixity-Deklarationen, um den Syntaxbaum neu zu verknüpfen.

Answer 2

Die Antwort von András Kovács zeigt, was wirklich in GHC getan wurde, aber es gibt eine Geschichte dazu.

Es gab tatsächlich eine etwas hypothetische Änderung vom Haskell 98 zum Haskell 2010 Standard. In der BNF-Grammatik des ersteren waren Operatorenfixität und -parsing so miteinander verflochten, dass Sie theoretisch seltsame Interaktionen zwischen den Regeln für die Fixität und den Regeln für das Ende von Ausdrücken und Einrückungsblöcken haben könnten. (Für die letzten beiden sind die Regeln im Wesentlichen, "weiter so, bis Sie aufhören müssen.")

Insbesondere könnten Sie einen lokalen Operator und seine Festigkeit so definieren, dass eine Verwendung davon in der neu definierenden inneren where gehörte block genau ... wenn es nicht war. Du hast also ein Parserparadox. Ich kann nicht von den alten Beispielen finden, aber dies sein kann:

let (+) = (Prelude.+) 
    infix 9 + -- make the inner + high precedence and non-associative 
in 2 + 3 + 4 
--  ^this + cannot parse here as the inner operator, which means 
--   the let ... in ... expression should end automatically first, 
--   but then it's the standard +, and its fixity says it should parse 
--   as part of the inner expression... 

In Haskell 2010 änderten sie offiziell, dass, so dass Betreiber fixities in einer separaten Stufe nach dem Parsen richtigen bestimmt werden.

Warum war das eine hypothetische Änderung? Denn alle Compilerautoren haben es schon auf die Haskell-2010-Art und Weise getan, und hatten es immer für ihre eigene geistige Gesundheit getan.

Answer 3

die Kommentare bis jetzt zusammenfassend, so scheint es, die Möglichkeiten sind somit:

• Return ein Parse-Baum, in dem alle Infixoperatoren als eine Art „Liste“ Struktur links, und dann einmal bekannt Präzedenzfälle werden neu anordnen.
• Geben Sie vor, dass Sie die Operatorvorgaben kennen, und ordnen Sie anschließend den Syntaxbaum neu an.
• Führen Sie eine erste Analyse durch, die nur Importe und Fixity-Deklarationen liest, die Importe lädt und dann eine vollständige Analyse mit bekannten Präzedenzfällen durchführt.