Haskell - Comment mieux représenter la grammaire d'un langage de programmation?

Question

J'ai regardé Haskell et j'aime bien écrire un compilateur (comme un exercice d'apprentissage) en elle, puisque beaucoup de ses caractéristiques innées peuvent être appliquées facilement à un compilateur (en particulier un compilateur décent récursive) .

Ce que je ne peux pas tout à fait obtenir ma tête est autour de la façon de représenter la grammaire d'une langue d'une manière Haskell-ian. Ma première pensée était d'utiliser des définitions de type de données récursives, mais je ne vois pas comment je les utilise pour correspondre contre des mots-clés dans la langue ( « si »), par exemple.

Les pensées et les suggestions ont grandement apprécié,

Pete

Answer 1

Un type de données récursive est très bien pour cela. Par exemple, étant donné la langue:

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

une expression exemple dans cette langue serait:

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

Votre type de données Haskell ressemblerait à quelque chose comme ceci:

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

Votre analyseur prend alors soin de traduire, par exemple, en x Var "x" et true dans Lit True, etc. i.e..

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

Pour parseurs écriture, vous pouvez rouler votre propre en utilisant les techniques mentionnées dans la réponse de Norman, ou en utilisant parsec ou générateurs analyseur d'utilisation comme Bonne .

Answer 2

Vous représentez des programmes utilisant les types de données algébriques mutuellement récursives, et pour analyser les programmes que vous utilisez combinators parsing . Il y a un million de saveurs; vous trouverez trois documents pédagogiques utiles sur le calendrier rel="noreferrer"> lundi, 23 Mars 2009. Ils sont

• Graham Hutton et Erik Meijer, Perle fonctionnelle: analyse syntaxique Monadique à Haskell (1998)
• Graham Hutton, Fonctions d'ordre supérieur pour parser (1992)
• Jeroen Fokker, Parsers fonctionnels (1995)

Le papier Hutton et Meijer est le plus court et le plus simple, mais il utilise monades, qui ne sont pas évidentes pour l'amateur. Cependant, ils ont une grammaire très belle et analyseur pour les expressions. Si vous ne GROK encore monades, tutoriel est le Fokker.

Answer 3

Peut-être que vous pouvez regarder certains projets dans le monde réel pour voir comment ils le font?

Il y a moins d'une semaine, le Langue-Python projet a été a annoncé sur Haskell-cafe liste de diffusion. Il est un analyseur Python mis en œuvre dans Haskell, en utilisant le générateur d'analyseur de Joyeux et Alex générateur lexer.

Et bien sûr, il y a roquets , une implémentation de Perl 6 dans Haskell (la première mise en œuvre de Perl 6 qui est conforme à un sous-ensemble important de la spécification Perl 6).

Answer 4

Je ne peux pas dire du ton de votre question de savoir si cela est la première fois que vous essayez d'écrire un compilateur, ou si vous avez écrit compilateurs avant et cherchent des conseils spécifiques à Haskell. Si vous êtes déjà un gourou du compilateur, ce petit conseil que je dois offrir ne va pas aider. :)

grammaires Langage de programmation sont généralement représentés dans BNF forme , qui peut être utilisé par des outils tels que Yacc ou Bison pour analyser le code source. Je ne sais pas si cela compte comme un moyen Haskell-ian de le faire, mais il est la seule façon que je l'ai entendu parler. Avec un peu de creuser autour de vous pouvez probablement creuser un outil pour générer le code Haskell à partir d'une grammaire BNF; J'ai trouvé cet outil qui prétend être en mesure de faire que.

Une recherche rapide sur Google relevai cette grammaire BNF pour Haskell , et il y a probablement d'autres là-bas, au cas où vous voulez écrire un compilateur pour Haskell (peut-être que vous souhaitez écrire un compilateur Haskell dans Haskell?) BNF pour C grammaires et Java semblent être populaires.

Enfin, si vous êtes à la recherche d'un livre sur la conception du compilateur, le texte classique est » dragon Book ".

Answer 5

Malheureusement, il n'y a pas de grammaire Haskell pour ANTLR , mais peut-être vous pouvez utiliser le lien précité créer un. ANTLR est un grand générateur d'analyseur syntaxique basé sur Java.

Steve Yegge a une belle écrire compilateurs, si vous avez besoin de plus de motivation. Il est divertissant.