Analisi con precedenza utente definita dall'utente

Question

OK, ecco una domanda: Dato che Haskell consente di definire nuovi operatori con precedenza arbitraria dell'operatore ... come è possibile analizzare effettivamente il codice sorgente Haskell?

Non è possibile sapere quali sono le precedenze degli operatori impostate finché non si analizza la sorgente. Ma non puoi analizzare la fonte finché non conosci le precedenze degli operatori corrette. Quindi ... um, come?

Si consideri, per esempio, l'espressione

x *** y +++ z 

Fino a quando finiamo di analisi del modulo, non sappiamo quali altri moduli sono importati, e quindi ciò che gli operatori (e altri identificatori) potrebbe essere di portata. Noi certamente non conosciamo ancora le loro precedenti. Ma il parser deve restituire qualcosa ... Ma se dovesse tornare

(x *** y) +++ z 

O dovrebbe tornare

x *** (y +++ z) 

Il povero parser non ha modo di sapere. Questo può essere determinato solo dopo aver scovato l'importazione che porta (+++) e (***) nell'ambito, caricare il file dal disco e scoprire quali sono le precedenze dell'operatore. Chiaramente il parser stesso non farà tutto ciò che I/O; un parser trasforma semplicemente un flusso di caratteri in un AST.

Chiaramente qualcuno da qualche parte ha capito come farlo. Ma non riesco a risolverlo ... Qualche suggerimento?

Answer 1

Citando il page on GHC trac per il parser:

operatori infissi sono analizzati come se fossero tutti di sinistra-associativo. Il renamer utilizza le dichiarazioni di fissità per riassociare l'albero di sintassi.

Answer 2

La risposta di András Kovács indica cosa è veramente fatto in GHC, ma c'è un po 'di storia in questo.

C'è stato in realtà un cambiamento un po 'ipotetico dal Haskell 98 allo standard Haskell 2010. Nella grammatica BNF dell'ex, la fissità dell'operatore e l'analisi sono stati intrecciati in modo tale che in teoria potreste avere alcune molto strane interazioni tra le regole per la fissità e le regole per quando le espressioni e i blocchi di indentazione finiscono. (Per le ultime due, le regole sono essenzialmente: "continua fino a quando non devi fermarti".)

In particolare, è possibile ridefinire un operatore locale e la sua fissità in modo tale che l'utilizzo di esso appartenesse alla ridefinizione interna where bloccare esattamente ... quando non è stato così. Quindi hai un paradosso del parser. Non riesco a trovare nessuno dei vecchi esempi, ma questo può essere uno:

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 hanno ufficialmente cambiato che in modo che fissità degli operatori sono determinati in una fase separata dopo la corretta analisi.

Quindi, perché questo è un cambiamento ipotetico? Perché tutti gli scrittori di compilatori lo hanno già fatto nel modo Haskell 2010, e lo hanno sempre avuto, per la loro sanità mentale.

Answer 3

Riassumendo i commenti finora, sembra le possibilità sono quindi:

• Return un albero sintattico in cui eventuali operatori infissi sono lasciati come una sorta di "lista" struttura, e quindi riorganizzare una volta precedenze diventato noto.
• Far finta di conoscere le precedenze dell'operatore e quindi riorganizzare l'albero di analisi dopo il fatto.
• Eseguire una prima analisi che legge solo le dichiarazioni di importazione e fissità, carica le importazioni e quindi esegue un'analisi completa con le precedenze conosciute.