Haskell - Come meglio per rappresentare la grammatica di un linguaggio di programmazione?

Question

Ho cercato a Haskell e avevo abbastanza piace scrivere un compilatore (come esercizio di apprendimento) in esso, dal momento che un sacco di sue caratteristiche innate possono essere facilmente applicati ad un compilatore (in particolare un compilatore decente ricorsiva) .

Quello che non riesco a ottenere la mia testa intorno è come rappresentare la grammatica di una lingua in un modo Haskell-ian. Il mio primo pensiero è stato quello di utilizzare ricorsive definizioni dei tipi di dati, ma non riesco a vedere come li uso per abbinare contro le parole chiave nella lingua ( "se"), per esempio.

pensieri e suggerimenti molto apprezzato,

Pete

Answer 1

Un tipo di dati ricorsiva è bene per questo. Ad esempio, data la lingua:

expr ::= var
      |  "true"
      |  "false"
      |  "if" expr "then" expr "else" expr
      |  "(" expr ")"

un esempio di espressione in questa lingua potrebbe essere:

if true then x else (if false then y else true)

Il tipo di dati Haskell sarebbe simile a questa:

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr

Il parser si occuperà quindi di tradurre, per esempio, in x Var "x", e true in Lit True, ecc cioè:.

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

per la scrittura parser si può rotolare il proprio utilizzando le tecniche di cui la risposta di Norman, o utilizzando Parsec o l'uso del parser generatori come felice .

Answer 2

L'utente dichiara programmi utilizzando tipi di dati algebrici mutuamente ricorsive, e di analizzare i programmi che si utilizzano combinatori parsing . Ci sono un milione di sapori; si trovano tre articoli tutoriali utile in programma rel="noreferrer"> lunedi 23 marzo 2009. sono

• Graham Hutton e Erik Meijer, Pearl funzionale: analisi Monadica in Haskell (1998)
• Graham Hutton, funzioni di ordine superiore per l'analisi (1992)
• Jeroen Fokker, Parser funzionali (1995)

La carta Hutton e Meijer è il più breve e più semplice, ma utilizza monadi, che non sono evidenti per il dilettante. Tuttavia essi hanno una bella grammatica e parser per le espressioni. Se non si è ancora Grok monadi, tutorial Fokker è quello.

Answer 3

Forse si può guardare ad alcuni progetti reali per vedere come lo fanno?

A meno di una settimana fa, il Lingua-Python progetto è stato ha annunciato sul Haskell-Cafe mailinglist . E 'un Python parser implementato in Haskell, utilizzando il felice generatore di parser e Alex generatore lexer.

E, naturalmente, c'è Carlini , un'implementazione di Perl 6 in Haskell (la prima implementazione di Perl 6 che è conforme a un sottoinsieme significativo della specifica Perl 6).

Answer 4

Non posso dire dal tono della tua domanda se questa è la prima volta che si sta tentando di scrivere un compilatore, o se hai scritto compilatori prima e sono alla ricerca di una consulenza specifica per Haskell. Se sei già un guru compilatore, quello piccolo consiglio che ho da offrire, non sta andando per aiutare. :)

grammatiche Linguaggio di programmazione sono comunemente rappresentati in BNF modulo , che può essere utilizzato da strumenti come Yacc o Bison per analizzare il codice sorgente. Non so se questo conta come un modo Haskell-ian per farlo, ma è l'unico modo che ho sentito parlare. Con un po 'di scavo intorno a voi probabilmente può scavare uno strumento per generare il codice Haskell da una grammatica BNF; Ho trovato questo strumento che sostiene di essere in grado di fare che.

Una rapida ricerca su Google alzato questa grammatica BNF per Haskell , e ci sono probabilmente altri là fuori, nel caso in cui si vuole scrivere un compilatore per Haskell (forse si desidera scrivere un compilatore Haskell in Haskell?) grammatiche BNF per C e Java sembrano essere popolare.

Infine, se siete alla ricerca di un libro sul design del compilatore, il testo classico è " The Dragon Book ".

Answer 5

Purtroppo non c'è la grammatica Haskell per ANTLR , ma forse è possibile utilizzare il link sopra citato per creare uno. ANTLR è un grande generatore di parser basato su Java.

Steve Yegge ha una bella su scrivere compilatori, se avete bisogno di più motivazione. E 'divertente.